The first thing I did was made sure that the word list would be cached on application start. This was as simple as creating an Application.cfc cfcomponent and implementing the onApplicationStart function. This function reads the dictionary in (described in the last entry) and caches the word list in a ColdFusion array. There are other options for storing this data, but this had the best mix of speed and function considering the method of search I wanted to use against it.
Although the dictionary was only 52K, this caching probably helped performance a great deal.
To generate the word list, I decided on the following algorithm:
- Choose an initial starting word (at random, or via user entry)
- Use the word to generate a regular expression. Replace a random single letter with the Regex pattern [^L] (where L is the letter you have replaced). Example: word: water regex: w[^a]ter
- Next, iterate through all of the words, testing each word against the regular expression. Store all matches.
- With each match, one-by-one, repeat Step 2 until we get a chain of N words. (Where N is the maximum length of the chain.)
- Obviously, if we have no more matches, we stop. If we have at least a 3-word chain, we can use it.
There are a few considerations not discussed above in generating the puzzle:
- If we match a word that is already in the chain, we should ignore that word to avoid duplicates.
- Not implemented: we should not replace a letter in the same position twice. For example, if we replace the “w” in water, don’t replace the “h” hater (if hater is the 2nd word).
- Depth-first versus Breadth-first searching…to be discussed