There were several programming decisions or challenges that came up during the game’s creation, for which I was able to apply some of the things I learned in my recent computer science classes.
The first challenge was how to include the dictionary. The source list I used for 3-letter words (from a Scrabble dictionary) includes 1012 entries. Although I could have developed a server-side solution to check words via AJAX, I wanted the game to be as quick and responsive as possible, and 1012 3-letter words is not all that prohibitive. First, I created an array of all the words; however, that took a lot of extra bytes for all the quotes and commas. In fact, it doubled the space required. I looked at using a prefix scheme (“A” followed by all the two-letter sequences that begin with “A”) to save a few bytes, but the savings was not as great as I had initially anticipated. In the end, I just included the dictionary as a long, unbroken string: since we know that each word is 3 characters, it is easy to access any given word.
The next challenge was how to look up the user’s 3-letter sequence to see if the sequence is in our dictionary. The brute-force approach is to compare it to every word in the dictionary, which would take 1012 comparisons for a sequence that isn’t present. 1012 comparisons isn’t all that bad, but there are certainly more efficient ways, and I was thinking about the implications of expanding to a 4-letter or 5-letter game. Here are some of the look-up options I considered:
- Binary search. Because we are dealing with an alphabetized dictionary, we can start in the middle of the dictionary and immediately eliminate half as possible matches, and then perform the same binary search recursively. Now we need only 10 comparisons for a sequence that isn’t present.
- Hash table. Although we would have to create the hash table at the beginning of the game, this only took 3 comparisons for a sequence that wasn’t present (based on empirical observation).
- Bucket array. I’m not sure what else to call it, but I created a large array (17,576) that could accommodate every conceivable combination of letters. A sequence not in the dictionary remains null, and a sequence in the dictionary gets assigned a 1. This method has larger memory requirements–not extraordinary for 3-letter sequences, but would grow quickly for longer sequences. Now we only need one comparison to determine is a sequence is a dictionary word.
I picked the binary search for its simplicity.
The last major challenge was creating the “fewest moves” algorithm. The game currently tells the user the fewest number of moves it takes to convert the random sequence to a dictionary word. I struggled with this at first, until I realized that the problem is basically just a Breadth-First Search or shortest-path algorithm. I enqueue the initial sequence. For each possible one-move combination, I check it against the dictionary, and enqueue that sequence. (I enqueue an impossible dummy sequence–“###”–to indicate that we need to increment the fewest moves.)
Although many of these optimizations were not strictly necessary and the brute-force approach would have worked suitably in many cases, I think the optimizations will help the game scale to handle 4-and-5-letter words (although the dictionaries may become too heavy for 5-letter words).