I recently created a simple word game using Javascript, which presented certain challenges. The game displays 3 random letters to the player, who must then attempt to create a dictionary word in as few moves as possible by shifting the letters up or down in the alphabet.
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.)
One problem with this is that if it enqueues every one-move combination, it will enqueue many duplicates. Before I checked for duplicates, I found that the fewest moves algorithm often checked more than the 17,576 unique 3-letter sequences. For letter combinations where the nearest dictionary word was 8 or more moves away, Javascript would become unresponsive (or the browser would crash). Since the already-checked sequences were in no particular order, I used the hash table (instead of the binary search) to perform look-ups (although a brute force approach would probably have been sufficient).
Another problem with the fewest-moves algorithm is that my first approach was to use a recursive function. However, Javascript apparently does not always perform well with recursion; Firefox would throw “too much recursion” errors. I changed the function to use a while loop (continue processing while the queue is not empty), which solved that issue.
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).