Search

The problem of generating the chain of clues is a simple search problem. In this case, depth-first search was used, because the algorithm would attempt path depth-wise and only explore another branch if the generated chain was not long enough.

Another tactic would have been to use a breadth first search. To use breadth-first search, we could have modified the regex pattern to find all words that differed from the base word by just one letter.

Using water as the base word, that regular expression looks something like: /([^w]ater|w[^a]ter|wa[^t]er|wat[^e]r|wate[^r])/. This would find all words in the dictionary that differed by one word (let’s call this word set B).

If we were using breadth-first search, we would then repeat the process with all of the words we just found (word set B).

If you were to visualize the difference between breadth-first and depth-first search, breadth-first would look like a tree with wide but shallow roots. Depth-first search would look like a tree with few but deep roots.

Query Params

The flexibility of the puzzle is enhanced by optional query parameters that may be applied. The word param allows specification of the starting or seed word. The length param specifies the maximum length of the puzzle.

Recursion

The program uses recursion to perform the search. This almost goes without saying, for it is difficult to do general search without recursion (although you could do so with macros and similar programming constructs). Search may be done using loop control structures but I can’t imagine an elegant solution using loops.

The pseudocode for the recursion is basically:

function build(baseWord, chainWords, maxLength)

regex = generateRandomRegex(baseWord)
wordSetB = getPossibleWords(regex, notIn=chainWords)
for(word in wordSetB)

    chain = build(word, chainWords+word, maxLength)
    if Length(chain) >= maxLength

        break

return chain