Tackling Longest Repeated Substring, and Building a Tool

  • Nov 29, 2012

After struggling through my worries about the best way to extract chunks of repeated code from programs last week, I decided that this week I would just implement a simple Longest Repeated Substring algorithm for ExpressionStatements, and worry about improving upon it later. This task proved a little easier said than done. I found a sub-optimal but fairly straightforward implementation of a Longest Repeated Substring algorithm online (the sub-optimality comes from using an array instead of constructing a tree, which is how the optimal algorithm works). After spending a few hours on it, this still isn't functioning as expected, but I've narrowed it close enough that I'm fairly certain that with an hour or so of work before our research meeting tomorrow, I'll have it figured out (of course now that I've said that, I've totally cursed myself).

The other substantial piece of coding I did this week (besides some small improvements and fixes to API methods) was to build a tool for Reilly to simulate the running of code tests for badge skills. Reilly, Kyle, and I had a meeting this week to discuss how best to fuze the current state of code tests, what Kyle had previously written to run code tests on the server, and what Reilly needs to be able to do for badges. We came out of that meeting with the knowledge that modifying the current server-side code to run code tests is a surmountable challenge, but not in the time between now and the end of the semester. The thought was that next semester, with Reilly's knowledge of Ruby and my knowledge of the code test structure, we'd get it running.

Which left the challenge of how for the next two weeks Reilly can get started developing tests for badge skills. The solution we came to was this: we'd create an offline simulation of running the test on all the Looking Glass worlds (which apparently Dennis has in a folder somewhere). To accomplish this, I built a tool that takes in the location of a code test that has already been designed (a .txt file containing the Jython code of the test) and then runs the test on all the Looking Glass files in a supplied directory (I haven't asked Dennis for his master-directory of worlds, so at the moment I'm only running it on the 18 worlds that I have saved on my computer). The code is most definitely a temporary solution (for example, it's running using a modified version of the code test runtime that I had to do some dirty finagling to get working), but hopefully for the next few weeks, it'll provide enough to get Reilly started until we can get things running on the server.


  • No comments yet

Log In or Sign Up to leave a comment.