Having worked at Runtime Revolution for less than three months I was somewhat daunted when asked to write an article for the company newsletter. My main problem was coming up with a suitable topic. As a result I looked to my colleagues for inspiration and was supplied with some rather creative suggestions. Given the Edinburgh office's current obsession with the board game Scrabble however, and the fact that the Technology team are performing rather poorly in the current office competition, I quickly settled on a 'Revolution Word Finder' in a bid to improve our performance (but not cheat - of course!). You can download the project here.

What It Is

The Revolution Word Finder has two options; an Anagram Finder and a Scrabble Solver. The Anagram Finder takes a list of letters and returns all the valid anagrams which can be created using them relative to a fixed list of words. Each anagram is checked for validity against the SOWPODS word list which is the word list used in current International Scrabble Tournaments.

The Scrabble Solver extends the functionality of the Anagram Finder by filtering its results to find only the anagrams which match the user entered pattern. This pattern represents an opening on the Scrabble board where, for example, the pattern 'b??' means find all three letter words starting with 'b'. Question marks must be used to represent wildcards. Only anagrams which contain the same number of characters as those in the pattern will be returned.

Implementation

The Revolution Word Finder is implemented using one recursive function, which makes up the backbone of the application, and a handful of smaller, simpler functions which perform various checks and preparation work.

We begin by generating a list of all possible permutations using the letters which were entered in the Available Letters field. This is done using a recursive function which continually splits the string of available letters down into smaller substrings, and calls itself again with a substring as the parameter. The recursion stops when the parameter string contains only one character and therefore can't be split any further. As the recursion is taking place lists of permutations are generated by placing the characters which have been taken off the start of the parameter string, in turn, between each of the remaining characters of the string. More details can be found by looking at the permuteSequence function in the card script.

Once a list of permutations has been found they are checked to see if they are valid words (relative to our dictionary). As the dictionary is quite large, we store it compressed (using the built-in compress function) in the custom property uAllWords of the stack. To check if a permutation is valid we could have used

tString is among the lines of sDictionary

but the time required for this check would be dependent on the size of the dictionary. As a result the dictionary is instead placed into an array using the code below

repeat for each line tWord in tWords
put true into sDictionary[tWord]
end repeat

This allows us to use the check

sDictionary[tString]

This will be true if tString is within the word list, and empty (i.e. false) otherwise. This check is much more efficient than checking the lines of the custom property as it can be carried out in constant time. Any permutations which are contained within the dictionary are added to a list of valid words. The final piece of processing needed is to remove any duplicates from this list of words. A duplicate can occur if there are multiple instances of a given letter in the Available Letters field since each letter is treated uniquely in terms of producing permutations.

e.g. The list of letters A1A2B, would produce the following permutations: A1, A2, B, A1A2, A2A1, BA1, BA2, A1B, A2B, A1A2B, A2A1B, A1BA2, A2BA1, BA1A2, BA2A1 (Here we indicate the individual instances of letters by a numeric subscript). The removal of duplicate entries is performed in the removeDuplicates function in the card script.

At this point the remaining words will be returned if the Anagram Finder option has been selected. If the application is running the Scrabble Solver mode a final step is required. This step further filters the list of anagrams to cut out any which do not match the pattern which the user entered. It is implemented using the filter command and takes the contents of the Pattern field to use as the regular expression.

How to Use

To use the Revolution Word Finder first select a game option; Anagram Finder or Scrabble Solver.

If you are using the Anagram Finder at least one character must be placed in the available letters field. The returned anagrams will contain only the characters which you enter. Clicking Search will start the application and cause any results to appear in the field below the button.

When using the Scrabble Solver both a pattern and list of available characters are required. The characters represent the tiles you currently hold and the pattern an opening on the board( i.e. t *blank slot* *blank slot* *blank slot*). Blank slots (i.e. wildcards) must be entered as question marks and will be interpreted as spaces which need to be filled by one of your tiles. Once you have entered both a pattern and your tiles click Search to retrieve word suggestions. An example of a valid search is shown in the screenshots below.

Due to this tool the Technology teams' Scrabble future is looking brighter. With the aid of Word Finder and Revolution, we aim to lift the office Scrabble trophy!