Last Time, I detailed my trials, tribulations, and eventual solution for calculating permutations -- the core algorithm in my little anagram solving program. Today, I'll review the rest of the implementation.

Finding the Shorter Permutations

The game provides a six-letter jumble and accepts 3 - 6 letter words in return. As described, my solution could only calculate 6-letter permutations. My first thought was that, since I already had all 6-letter permutations I could extract the 3, 4 & 5 letter permutations from them. Another iteration of the word list then (the one created by our call to the permutation library) to might do the trick:

$words.each { |word| (0..6).each { |i| (3..6 - i).each { |j| $list << word[i,j] } } }

(For each index position in each word, get the 3, 4 5 and 6 letter words and append them onto a new list)

This works, because element referencing of a string in Ruby (i.e. foo[x,y]) takes the index as the first argument, and the length as the second. If the length is greater than the rest of the string, it simply provides the rest of the string. Ugly, but it worked.

I frequently quote (and follow) the old adage: "Make it work, make it right, make it fast." Often, I implicitly add, "Make it elegant" to the list -- although I often lump it into "make it right". The fact that this was an evening hack, and not code I intended to share with anyone, meant ugly was ok -- at least until I posted a high score.

I actually ran the program the first few times with this implementation. I knew it was inefficient (multiple scans, and duplications), but because there's only 720 elements in the permutation list I knew I could get away with it (and as we'll see, there were some real performance bottlenecks elsewhere in the code that had to be dealt with first).

One possible problem with Ruby (or the intersection of me and Ruby at least) is that its very easy to write complicated processing. This is one of my big personal reasons for practicing Test Driven Development -- it throttles my natural tendency to overcomplicate things.

The over-complexity in this case is two fold: first we don't need to extract every shorter word (e.g. the 3-letter words starting at indices 0,1 & 2) from each permutation. Since every permutation is present in the word list, each shorter permutation will appear in string order somewhere in the list. Since we are processing the whole list anyway, we can simplify the extraction to this:

$words.each { |word| (3..6).each { |i| $list << word[0,i] } }

(for each word, grab the 3, 4 5 and 6-letter word that starts it)

The second complication is iterating the word list again since this happens when the program calcuates the 6-letter permutations. Combining the simpler extraction with the final permutation code (the one I described in my previous blog entry) resulted in the final implementation:

perm = Permutation.for($jumble)
perm.each do |p| 
    word = p.project 
    (3..6).each { |i| $list << word[0,i] }
end

With all possible permutations in hand, all I needed to do was winnow the list down to something closer to valid English words. For that I needed to find a dictionary...

Filtering for English

This was one of the earliest pieces of the program I envisioned the implementation for: Open a text file full of English words and look up each permutation in it. If its in there, add it to the list of words to send at the game.

This approach leads to two implementation problems: 1) How to match the words and 2) Where to find a dictionary file. I tackled the first one as simply as possible...

$dict = IO.readlines("dictionary.txt")
$answers = Array.new
$list.uniq.each {|word|    $answers << word if $dict.include?(word) }

(use uniq to sort out any duplicate permutations (possible with repeated letters, and with my original filter algorithm) then append those words found in the array holding the dictionary)

...and then set out to find a dictionary file. It had to have several characteristics:

1. a plain text file with one word per line. Mainly because that was the implementation I wanted.
2. downloadable -- I didn't feel like experimenting with some sort of web service-like implementation where I hit dictionary.com or something (too complicated, and probably too slow)
3. contain all (i.e. less than one miss per game screen) words the anagram would expect
4. contain as few false positives (i.e. words the game wouldn't accept) as possible. Both to limit the domain of scanning and to limit the number of bad answers sent during the game (as it slows down play).
5. free (or already in my possession).

I won't bore you with the details of my search. Suffice it to say, I theorized, searched and experimented with several potential sources before finding one that worked. Some examples of things I tried and rejected:

• Textpad's spelling file. Textpad stores its spelling dictionary as a text file. I already have it, and it didn't contain many words unacceptable to the game -- however it was way too incomplete to be useful. Based on this, I eliminated all program spelling dictionaries
• Project Gutenberg's copy of Webster's Unabridged Dictionary. Freely downloadable. All the words, but also an entire dictionary's worth of definitions. In html no less
• Password cracking files. Freely downloadable. Right format. All the words -- but also lots of false positives (password files include non-word elements like common mispellings, numbers and other easily rememberable strings).
• Scrabble dictionaries. Too many false positives because these are often organized (and segmented) by what will score the most points in Scrabble.

The last one put me on the right track though. What I needed was another game or puzzle-solving site that had something similar. I finally found a shareware program called Puzzlehelp that had a plaintext dictionary of about 330,000 words -- all the words I needed with few (enough) extraneous word that I decided to give a go.

Perfect! dropping the word list into the program folder as "dictionary.txt" (presorted) gave me a minimally functional program -- if I wanted to type the words myself. But I am lazy, and I wanted to have my program send the words directly. A final hurdle then to my attempts at anagram domination was to get Ruby to do the work for me.

Typing in the Words

Unfortunately, since the game is in Flash, this hurdle was not insignificant. I don't know much about the Macromedia (sorry: Adobe Systems) technologies, and so I don't know if there is any way to interact with them directly (if anyone knows how I'd love to hear about it). I decided instead to send the keystrokes directly into the browser -- i.e. I needed to make Ruby tap on the keyboard.

I've done this in other languages of course, so I assumed it was possible in Ruby -- somehow. Figuring out just how turned out to be a bigger challenge than I counted on. Like many things, it wasn't the implementation, it was knowing how to do it, that was the challenge.

If you're using Ruby in the Unix world, its pretty straightforward (disclaimer: I haven't tried this), you simply send the keystrokes to the device as if it were any other file. Something like:

f = File.new("/dev/tty")
f.puts "myword"

should do the trick.

But this doesn't work for Windows. I didn't want to start mucking around with the Windows API's directly if I didn't have to (although this is certainly possible using the Win32API module), so I hit Google again for some ideas. After many fruitless searches, I found an example of someone (sorry lost the link but it was sample code on a mailing list) using the WIN32OLE module to access the Windows Scripting Host and its WshShell object's SendKeys function. This made short work of typing the words into the game:

require 'win32ole'
wsh = WIN32OLE.new('WScript.Shell')
while not wsh.AppActivate("Firefox")
    sleep 0.1
end
$answers.each do |word|
    sleep 0.5
    wsh.SendKeys(word + "\n") 
end

(create an instance of the WshShell object (documented in MSDN). Call the AppActivate method to set focus to the window indicated by the title (it doesn't require the entire title) then use SendKeys to send the words)

The first loop (to wait for focus) is probably not strictly necessary, but was in the example I found. The second loop simply iterates through our words and calls the SendKeys method (adding a newline to 'hit' the enter key).

With that in place and working (I tried it out on notepad first), it was time to give my program a test run on the actual anagram game. All I needed was a way to get the jumble into the program and I was ready to go (sort of).

Ready, or Not Here We Come!

I decided at first to simply pass the jumble on the command line:

speller.rb esifta

since its so easy to access:

$jumble = ARGV[0] #this is the first argument, not the program name like some languages

and give it a go.

The first run went well -- good enough to get the third highest score of the day -- finding all but a couple of words. It was also really fun to watch. :-)

There were some problems though: the words weren't in the optimal order (longer words score more points), and the program wasn't fast enough to get all the words in at the higher rounds. In short, it was time to optimize.

Performance Tweaks

The sorting was easy: Ruby arrays feature a sort method, so I added that to the call chain for the filter iteration (i.e. between uniq and each). But there were two problems with this approach:

1. (minor) I was sorting the entire list, instead of the filtered list
2. The sort order was still not optimal

By default, Array.sort will place 'ab' before 'abb' and 'aba' resulting in a pattern like this:

ab
abb
abbb
ac
acc
accc

whereas I wanted:

abbb
accc
abb
acc
ab
ac

Fortunately, Ruby made this easy too. The sort method accepts a two argument block (e.g. x,y) to change the sorting comparison. The block should return 1 if x > y, -1 if x < y and 0 if they are equal. The <=> operator in ruby does this sort of comparision. E.g. this:

{|x,y| x<=>y }

provides the same sort result as the default.

To get sort order I wanted, I needed to compare lengths; longer before shorter (to get the higher scoring words first), and only then compare actual words.

The need to provide a block makes it awkward (but not impossible) to insert the sort between uniq and each, so by sorting the result of the filtering I avoid having to sort the whole list (at the cost of one more short iteration). This is the result:

$answers.sort! {|x,y| x.length == y.length ? x <=> y : y.length <=> x.length }

(Sort the answers (in place). If lengths are equal compare as before, otherwise compare lengths).)

Since this is my code, I happily used the 'ternary if' operator without fear of someone complaining that its unreadable. Personally, I find it elegant and clear as long as its not nested, although, in general I go with the flow (but I miss it for jobs like this on projects where its been outlawed).

Sorting accomplished, there was just that little problem with speed. The performance wasn't great: it took as much as 30 seconds to start kicking out answers. This was OK in the lower rounds where the game gives as much as two minutes to answer, but much too slow for the higher rounds (and thus unsuitable for my purposes -- I wanted the high-score!).

Without profiling, a quick review of the code suggested two candidates for speed improvement: The dictionary loading, and the inclusion filter.

I had already gotten tired of restarting the program each round, so I had implemented a loop that used 'gets' to allow me to enter each new jumble. By moving the dictionary loading outside the processing loop, I made its load-time irrelevant (it turned out to be a sub-second delay anyway, but there is no need to load it after entering each word).

Speeding up the inclusion filter meant reviewing the use of Array.include?. I had my doubts about this from the get go, but as I mentioned before, I try to avoid pre-optimizing. Now it was time to try something better.

The performance of 'Include?' hinted that it was doing a sequential search and/or a string comparision. A faster search and/or a faster comparison were thus logical improvements. Indexes and hash-values leapt to mind, but I didn't really want anything too complicated, so I decided to try loading the dictionary into a hash table with the Object.hash value of each word as the key. Then I could take the hash value of each word as I scanned for inclusion and see if it was a key in the hash table. Here's the result:

$db = Hash.new
$dict.each { |word| $db[word.chomp.hash] = word.chomp }

$list.uniq.each {|word|    $answers << word if $db.has_key?(word.hash)    }

This dropped the processing time to less than a second (the hash is probably stored as a b-tree) -- more than fast enough as this promoted actual typing to "bottleneck" status (and that appears to be limited by the game).

The only remaining sticking point was the fact that if I didn't click on the game portion of the browser window, my program had a tendency to send the data into the menus of Firefox. So, I eliminated the loop (but kept the gets) inserted a 0.5 second delay before the typing began, and switched the window manually (this probably means I could lose the AppActivate call altogether, but I haven't).

Armed with this version of the program, I set the high score for the day and the month (and beat the previous month) getting one level higher than any other player. My program had conquered!

Next Steps, Final Thoughts

Why only one level higher than everyone else? Well, at the highest levels the anagram program only provides around 30 seconds to enter approximately 25 words. My program can only type 2 words per second (any faster and the program overtypes the game's processing).

Adding in my time to click windows and type in the jumble I average a sub five second delay (including program processing time and built-in delays) before the program starts typing.

With so little slack, false positives (i.e. words in my list that are not recognized by the game) are very significant at these higher levels. If my program could read the game (it lists the words at the end of each round), I could tune it simply by running it a lot and having the program remove words not accepted by the game from the dictionary.

In lieu of this, I implemented a more manual process where the program lists the words it sent at the end of the round and I can type 'y' or 'n' for whether they were accepted by the game, allowing the program to remove them from the dictionary. This howver got boring really fast. I also started manually tuning the dictionary's three and four letter words (the ones causing the biggest delays) but this got really boring too, so I called it a day.

Here then is the final program (does not include the tuning code):

require 'rubygems'
require_gem 'permutation'
require 'win32ole'

$dictionary = "dictionary.txt"

def play
    wsh = WIN32OLE.new('WScript.Shell')
    while not wsh.AppActivate("Firefox")
        sleep 0.1
    end
    sleep 0.5
    $answers.each do |word|
        sleep 0.5
        wsh.SendKeys(word + "\n") 
    end
end

puts "Loading..."
$dict = IO.readlines($dictionary)
$db = Hash.new
$dict.each { |word| $db[word.chomp.hash] = word.chomp }

print "enter code: "
$jumble = gets
$jumble.chomp!

$list = Array.new
$answers = Array.new

perm = Permutation.for($jumble)
perm.each do |p| 
    word = p.project 
    (3..6).each { |i| $list << word[0,i] }
end

$list.uniq.each {|word|    $answers << word if $db.has_key?(word.hash)    }
$answers.sort! {|x,y| x.length == y.length ? x <=> y : y.length <=> x.length }

play

All in all, this was a fun project -- combining enough learning, problem solving and need for klugey hacks into a small enough program for an evening's distraction. Hope you enjoyed my retelling of it.