Solution: Word Search

Written by Josh Alman and Nathan Pinsker

The puzzle works exactly as the instructions describe: Josh has eight words to identify, and for each word, you can guess what the word is, and Josh will either tell you that you’ve guessed correctly, or he’ll tell you the Levenshtein distance from your guess to his word.

There are many different ways to go about figuring out what the eight words are, but here are some suggestions:

  • It’s quite helpful when searching for a word to know how long it is. The Levenshtein distance between two words is always at most the length of the longer word. One case where it’s equal to the length of the longer word is when the two words share no letters. Thus, if you guess many different three-letter words, you will likely guess one which shares no letters with the secret word, and so the maximum Levenshtein distance you see will be the length of the secret word.
  • Once you know the length of the secret word, guessing short words can help narrow down what letters are used in the secret word. For instance, suppose the secret word has length 11, and your guess of PIN has edit distance 8 to the secret. Since 8+3=11, we know that the letters PIN have to appear in that order as a subsequence in the secret word (like in APPLICATION). Even if we’re not so lucky, and guess ARC which has edit distance 9, we still learn that the secret word contains two of the letters A, R, and C.
  • You can also determine how many letters are between P, I, and N by “building” off these letters. For example, guessing “PINE” will have distance 9, meaning the E needs to be deleted and so the word must end in an N. Guessing “SPIN” has an edit distance of 8, so that means there is at least one letter before the P.
  • Once you have the length of the secret word, as well as some letters you are fairly certain appear in the word, you can try guessing words of that length which contain many of those letters. Levenshtein distance was designed to match our intuitive notion of how similar two words are, so you can narrow in on the correct answer by finding words with smaller and smaller distance to the secret. Some trial and error is likely necessary.

Finally, we find that the eight words are:

Word 6 LUGE

Taking the first letters of the words in order gives us the answer, PETAFLOP.

Author’s Notes

This was one of the last puzzles to be written for the hunt. At first, we intended to write a “duck conundrum”-style puzzle, where you were given a long, complicated set of instructions and simply had to follow them correctly. We sat in a conference room and talked for almost 3 hours about ideas – then we realized that we didn’t even like duck conundrums, and were dreading the thought of testsolving our own puzzle. Josh proposed this idea, and we testsolved it on the spot.

It didn’t escape our notice that you can just write code to solve this puzzle. Although we personally aren’t fans of that solution, we also don’t mind it, since the proper strategy (without code) is both potentially faster and more enjoyable. In retrospect, though, this puzzle might be improved if solvers were forced to figure out that strategy: for example, if this was held as an “in-person” event at Mystery Hunt or something similar, where solvers could only rely on the words they knew.

This puzzle had one of the highest guess-to-solve ratios in the hunt, with around 80%.