Solution: Word Search II

Answer: LEATHER COATS

Written by Josh Alman and Nathan Pinsker

Just as Josh and Nathan describe, Josh has six pairs of words we need to find. In order to find them, we can guess words, and for every guess we get back a pair of "distances". Before we start finding the words, we need to use the practice round in order to figure out what "distance" means here. In the practice round we can guess and word and get its "distances" to LUGE TRACK.

The "distance" measure is inspired by the two word search puzzles from last year's Galactic Puzzle Hunt. In Word Search, the setup was quite similar, and the distance between a pair of words was the Levenshtein distance. The puzzle o ea / Wrd Srch involved splitting up the consonants and vowels of words and dealing with them separately.

In this puzzle, the "distance" computes the Levenshtein distances of the vowels and consonants separately. To be precise: let L_v(x,y) denote the Levenshtein distance between the vowels of x and the vowels of y, and similarly define L_c(x,y) for consonants. Then, when Josh's secret words are w₁ and w₂, and we guess the word g, the two distances given to us are L_v(g,w₁) + L_c(g,w₂) and L_c(g,w₁) + L_v(g,w₂).

For example, when the secret words are w₁ = LUGE and w₂ = TRACK, and we guess g = FAST, the distances we're given are L(A, UE) + L(FST, TRCK) = 2 + 4 = 6, and L(FST, LG) + L(A, A) = 3 + 0 = 3 (where L(x, y) is the normal Levenshtein distance between words x and y).

Now that we've figured out what the distance measure is, we need to find the six pairs of words. There are many different ways to do this, and most of the suggestions from last year are still helpful, but here are a few additional ideas that can help:

• Words like PAT, PET, PIT, POT, and PUT, which have the same consonants in the same order but different vowels, are helpful for figuring out what vowels are in the two words. For instance, since LUGE contains E and U but not A, I or O, the first distances from PET and PUT will be one smaller than the first distances to PAT, PIT and POT. Two words that differ only in one consonant, like SLY and SHY, or MAT and CAT, can also help. Guesses that differ in both consonants and vowels, like SHOP and SNAP, are harder to reason about since we don't know if differences in the distances are coming from the vowels in one word or the consonants in the other.
• Once you've figured out one of the words, the remaining task of figuring out the other word is much easier. When you make guesses, you can subtract away the contributions of the word you already know to the distances, and then you're left with the consonant and vowel distances to the remaining unknown word.
• Similarly, once you're quite confident about the vowels in one word, you can then get much more straightforward information about the consonants of the other word. It often helps to work on both words in parallel instead of focusing on just one at a time.

Finally, we find that the six pairs of are:

As suggested by the circles when we find the correct words, we look at the first letters of these words: The first letters of the first words are EAECTS, and the first letters of the second words are LTHROA. Inspired by the distance mechanic, we take the vowels EAE from the first and consonants LTHR from the second to spell LEATHER, and we take the vowels OA from the second and consonants CTS from the first to spell COATS, giving our final answer LEATHER COATS.

Author’s Notes

We really enjoyed making and testing last year's Word Search puzzle, and this year we thought it would be more exciting if solvers had to figure out the distance measure on their own. We'd like to thank Leon Zhou for suggesting the final extraction; in our original version, the first letters simply spelled out the answer.