A Little Hacking Run

I found myself with a lot of time on my hands yesterday -- unstructured, intermittent and otherwise generally unproductive time, but time nonetheless. And I am happy to say, I used this time to solve a meaningless programming problem. Like all entertaining hacks it was challenging, fun, and a just a bit silly. In the process of coding it up I learned how to do a few things in Ruby that previously I only assumed could be done.

Anyway, I have some more of this kind of time today, so I thought I'd share the details of my little hacking run.

Like many people, I keep a running collection of short, simple time-wasters handy for relieving boredom whenever I find myself short of something to do (i.e. during email refreshes, between phone calls, after coming back from lunch, while builds are running, pretty much any time I need to procrastinate, etc).

Most of these are games, some are websites, a few are both. All of them have in common that they are easy to begin, quick to finish, and (ahem, usually) easy to abandon when something more important happens.

One of my current obsessions diversions is an online flash/shockwave anagram game on one of those sites where they offer boatloads of such games for free, and roll ads past you as you play (for reasons that will become clear, I am doing them a favor in not telling you which one). The game presents you with a word jumble and then you have a certain amount of time to determine all of the valid words of varying lengths in that jumble. If you get enough points each round, you can go on to the next. High scores can be recorded.

I love these sorts of games(I play several on that site). After playing this one for a while, I stumbled on the fact that the game responded to the keyboard. My scores went up dramatically at this point, and I began playing a lot more in an effort to gain one of the daily top scores.

As fun as this was, the keyboard discovery inevitably led me to wonder if I could write something to automate the process, and so shift the problem from "how many words can I find" to "how can I write a program to do this for me." The more I thought about it, the more apealling it became, until I noticed I was playing the game as much to think through the program specs as to simply play for higher scores. Thus is a time-waster transformed into a time-wasting hack.

Instead of juggling letters, I began to juggle programming concepts. Soon, I was convinced that it could be done. Specifically, I thought I could see ways to solve all of the requirements of such a program. Namely:

  • it must determine all the permutations of the given jumble
  • it must filter them in some way so as to get only valid words
  • it must interact directly with the game, so I could see it run
  • it must type the words in for me
  • it must do all of this fast enough to get a high score (finding every word would be ideal)

In short, I decided to write an anagram bot to utterly beat the game to a pulp.

Now, some might see this as cheating, but like I said, my interest had shifted -- and thus so had the problem and the desired outcome (btw I am still closing in on the high scores playing manually). The way I see it, I am now playing a different game (something more like robocode). To reflect that, I decided that I would not take credit for my bot's score (i.e. I am using a different name than the one I am playing with manually). Further, I am strongly suspicious that the (previous) high score holder is itself a bot, so in a way, I am only now really playing the game for the first time.

Which is just to say, that I rationalized away any misgivings I had, and set out to write my bot anyway.

Now the astute reader (don't you just love that phrase -- whose the dull reader anyway?) may have picked up on the fact that my project was a success, and that my bot currently holds the record score, but I am getting ahead of myself.

I thought I'd share the solution before the results.

First off, I chose Ruby because I've been playing with it a lot lately, and I also figured it for the quickest and most elegant solution (I am very happy with the results). Along the way, I heavily leveraged Google, Programming Ruby (2nd edition), RubyGems, and a host of mailing lists and other sites. All in all, I spent a better part of the day (in fits and starts) and most of the evening on what in the end is a ruby program of just 35 lines or so.

The solution consists of the following sections:

  • A permuation generator to get the list of all possible words from a given jumble (after much experimentation on doing it myself, I eventually discovered and ultimately used Florian Frank's permutation library
  • a way to find shorter words in the jumble (Ruby blocks make this a snap)
  • a dictionary of valid English words (stored in a text file)
  • a filtering mechanism to limit the answers to words in the dictionary (More ruby goodness here)
  • a custom sort to get the words in maximum scoring order (Ruby Arrays feature a 'sort' method that takes a block to customize the sort criteria)
  • a keystroke entering solution so that my program could drive the game directly (hint: Ruby's OLE automation support rocks)
  • a way to get the jumble from the screen to the program so it could do its work(why get complicated, type it into the console!)

Next time, I'll go into more detail on the first of these: the permutation generator. I plan to explore each one in more detail as we go, so stay tuned...