The Limber Lambda

After a gruelling end of 2011, I’ve finally had an opportunity to have some time off.  When you’re head down having to deal with the stress of trying to reach a deadline, other things tend to get neglected.  In my case, “other things” includes staying up-to-date with the technology status quo, whether it be keeping pace with my RSS feed or learning new things.

There has been so much fuss about Ruby that I’ve finally capitulated and decided to learn it.  Learning a new language is nothing to be sniffed at though, it’s a bit like eating an elephant—there’s only one way to do it—small bite by small bite.

Whenever someone decides to dream up a new language my immediate response is: “why?”.  Why spend all that effort coming up with yet another language when so many already exist?  I’ve decided that the answer seems to be: “because you can”.  Ok, trying to be a little less facetious about it … the reason why new languages pop up is because, of course, there is a need.  If there wasn’t, then any new language would surely die as quickly as it was proposed.

Yukihiro Matsumoto says that the guiding principle of Ruby is that of “least surprise”, that is, programming in a language (any language) should be a natural and intuitive process.  One shouldn’t have to fight with the language; after all, computers are there to assist us in getting things done.

Word Games

I’ve become addicted to Zynga’s word games, that is, the ones where you play against other users.  The only issue is though, that lately I’ve had a sneaky suspicion that one or two of my opponents are cheating.  When confronted with a cheater, the only option is take it to ‘em.

Here’s “Hanging with Friends” a delightfully contrived game where your character gets to hang over runny lava with a bunch of helium balloons being his/her only saving grace.  You make up words and your opponent has to guess them and vice versa.  Incorrectly guessing a word means that you lose a balloon … getting that much closer to the hot stuff.

If you’re itching to play, you can pair up with a random user.  Despite being chosen randomly (I think) all of my opponents are doing a pretty bang-up job of lava-dunking my little guy, so I figured that it was time for a Ruby script to level the playing field.

There are two opportunities for cheating, that is, a) when trying to guess your opponents word and b) when trying to come up with a word that your opponent needs to guess.  I cheat at both points.  Getting some computer-aided assistance for the former is straightforward, and I might talk about that in another post.  Now though, I want to talk about the latter, that is, coming up with a new word.

You can’t just choose any word; you’re given a random selection of letters from which to build a word.  How about if we had something that could tell us what words can be made out of the given letter selection?

Something along the lines of:

1. Find all permutations of letters for a given set, and …
2. Select those permutations that are actual words.

Straightforward, really.

English Language Words

There are a whole bunch of word lists for download, categorised in various ways.  I’m not particularly fussy and just went for “Kevin’s Word List Page”, in particular, the “Spell Checker Oriented Word Lists” (SCOWL).  The lists comprise a bunch of files, categorised by type of English (UK, US, Canada) and in some other ways.  For the purposes of cheating, I don’t really care, because you don’t get penalised if you enter an incorrectly spelled word—you just have to try again.

Using SCOWL, to get a list of all words (including some proper nouns), is a matter of …

cat /tmp/scowl-7.1/final/*

… after unzipping the SCOWL zip.

Permutations

I’m not going to pretend that I have some fancy way of figuring out words—my methods in this case are very practical … brute-force-style practical.

The method, then, is straightforward.  Given a target number of letters, and given a selection of letters from which you can choose a word, just find all permutations of those letters fitting within the target number of letters and check whether or not each is a real word.

Example:

All permutations of maximum three letters of the following set of letters: [ “a”, “b”, “c”, “d” ], gives us:

["a", "b", "c"]
["a", "b", "d"]
["a", "c", "b"]
["a", "c", "d"]
["a", "d", "b"]
["a", "d", "c"]
["b", "a", "c"]
["b", "a", "d"]
["b", "c", "a"]
["b", "c", "d"]
["b", "d", "a"]
["b", "d", "c"]
["c", "a", "b"]
["c", "a", "d"]
["c", "b", "a"]
["c", "b", "d"]
["c", "d", "a"]
["c", "d", "b"]
["d", "a", "b"]
["d", "a", "c"]
["d", "b", "a"]
["d", "b", "c"]
["d", "c", "a"]
["d", "c", "b"]

Of those, following are real words: bad, cab, cad, dab.

Loading English Words, Ruby-Style

The easiest way of doing this is to load all words from our word lists into memory, into a Hash.  This is fairly pedestrian, and looks like this:

def load_words(path_to_word_files)
    raise "Path \"#{path_to_word_files}\" is not a directory" unless File.directory? path_to_word_files
    @words = Hash.new
    Dir.new(path_to_word_files).each do |f|
        path_to_file = File.join(path_to_word_files, f)
        if File.file?(path_to_file)
            File.new(path_to_file).each_line do |l|
                word_without_newlines = l.chomp
                @words[word_without_newlines] = word_without_newlines
            end
        end
    end
end

As promised by Matz, this stuff is easy to write and easy to read.  Anyone who has written some Perl can see a influence coming in to Ruby, in particular chomp (for removing newlines) and unless (used as a statement modifier).

Permutations

Once all the words have been hashified, what remains is brute-forcing all permutations.  Fortunately, Ruby has permutation-finding built in to its Array implementation.  What we need to do becomes:

def get_words_with_letters(letters, word_length=8)
    word_length = letters.length if letters.length < word_length
    found = Hash.new
    letters.chars.to_a.permutation(word_length).each do |permutation|
        candidate = permutation.join
        next if found.has_key?(candidate)
        found[candidate] = candidate if @words.has_key?(candidate)
    end
    return found.keys
end

In a single chained call on a string containing the letters that we can work with, we:

1. Get an enumeration of characters comprising the string;
2. Convert the enumeration to an array …
3. create an array containing all the permutations for a given length of word (each permutation being an array of characters) and
4. Enumerate the array, passing each item to a block.

A few more statements with modifiers gives us a terse but expressive bit of code that eliminates duplicates (as a result of multiple of the same letter being part of the original set), and adds the item if it is a real word.

An initial, rough-and-ready but effective script is now ready to join my arsenal of cobbled-together tools needed to bring humility to any would-be “Hanging” challengers:

#!/usr/bin/env ruby

class EnglishWords
    def initialize(path_to_word_files)
        load_words(path_to_word_files)
    end

    def load_words(path_to_word_files)
        raise "Path \"#{path_to_word_files}\" is not a directory" unless File.directory? path_to_word_files
        @words = Hash.new
        Dir.new(path_to_word_files).each do |f|
            path_to_file = File.join(path_to_word_files, f)
            if File.file?(path_to_file)
                File.new(path_to_file).each_line do |l|
                    word_without_newlines = l.chomp
                    @words[word_without_newlines] = word_without_newlines
                end
            end
        end
    end

    def get_words_with_letters(letters, word_length=8)
        word_length = letters.length if letters.length < word_length
        found = Hash.new
        letters.chars.to_a.permutation(word_length).each do |permutation|
            candidate = permutation.join
            next if found.has_key?(candidate)
            found[candidate] = candidate if @words.has_key?(candidate)
        end
        return found.keys
    end
end

def print_usage_and_exit
    puts <<EOF
#{$0[/[\w\d_-]+/]} <path_to_words> <letters> <word_length>

    <path_to_words>     A folder containing English word files.  The format of word files
                        is one word per line.
    <letters>           A string of letters, a subset of which determine words to find.
    <length>            Length of words to find (must be less then the lesser of
                        the length of <letters> and 9).

    Example:

    #{$0[/[\w\d_-]+/]} /tmp/scowl/final trasse 5

    yields:

    tasser
    tasers
    terass
    reasts
    asters
    assert
    straes
    stares
    stears
    essart
EOF
    exit -1
end

print_usage_and_exit if ARGV.length < 3

words = EnglishWords.new ARGV.shift
letters = ARGV.shift
word_length = ARGV.shift.to_i

words.get_words_with_letters(letters, word_length).each { |w| puts w }

I don’t know what a tostados is, but “Hanging with Friends” seems happy with it .