• Play Online!
• Code: Learn the Secret
• Solve It

CH-CH-CH-CH-CHanges

Solution Comments

This puzzle is a decent candidate for solving with code; basically it is a matter of combining two-letter strings from a short list (the states). Unfortunately, I could not find a decent list of common three-word English phrases, so I was forced to build a list of all the "valid" phrases (4,012 in total) that could be generated under Will's rules; after generating my list I scanned it manually to spot the phrase that matched Will's description. BTW, that doesn't take as long as you might think! The upshot is, I couldn't solve it in code; I could only narrow-down the choices.

The answer, of course, is 'Made in America'. Among the more interesting alternate phrases are 'Meal or autarky', 'Dear Ms America' and 'Pain or Academe'.

To solve it, I used a 'modified brute force' approach with a binary search. I call it modified brute force because I used an improved version of binary search to check whether the beginning of a candidate word represents an actual word in the dictionary.

For example, suppose I am in the process of constructing a candidate word; and currently I am working with 'OR', the abbreviation for Oregon. Using my modified binary search, I can quickly determine that there are indeed some words that start with 'OR' (but there are none that start with Mt, for Montana.) By rejecting candidates that cannot possibly lead to legitimate words, the algorithm is speeded.

Basically, my algorithm is to loop through all the state abbreviations, constructing potential words of the correct length, rejecting any abbreviations that have already been used. When the candidate word has been constructed, I look it up in the word list using binary search; if it isn't a word, move on to the next combination. Repeat until you have generated valid words of lengths 4, 2 and 7, while excluding candidates that re-use an abbreviation.

Efficiency Analysis

For students of Algorithm Analysis, note that the run-time of a binary search is O(Ln(n)), ie. roughly proportionate to the logarithm of the array size. In my case, the array of words has length 61,406; the natural log of this number is close to 11. Interpretation: to determine whether an arbitrary word belongs to an array of this size will require approximately 11 iterations of my algorithm, which is quite fast. A hash is even faster, but cannot be modified to test for partial matches; besides 11 iterations is fast enough.

In contrast, analyzing my algorithm reveals that it is nowhere near as effecient! Since there are 7 choices being made from an array of size 50, my algorithm basically iterates 50*7! (seven factorial times fifty), or approximately 252,000 million times, minus however many candidates are rejected by my modified binary search.

Alternate Solution

Now that I've solved the problem, a alternative algorithm immediately comes to mind. It is obvious that only a few words are valid candidates for the last word in the phrase ('autarky', 'academe', 'America' and 'amerind'). A superior approach would entail iterating through the combinations of these words, plus the 13 candidates for the middle word and 104 candidates for the first word, a requiring total of just 5,408 evaluations to generate the phrase list, and then rejecting illegal combinations (which can occur when, for example, the first word uses a state necessary for either the 2nd or 3rd word.) Additionally, it requires 50*49 iterations to calculate the first word, 50 iterations to calculate the second word, and 50*49*48 iterations to calculate the final word, for a total of 120,600 iterations, approximately twice as fast as my approach. Perhaps someone can suggest how to utilize dynamic programming to improve the algorithm.

Solve the Problem in Code!

Because this puzzle takes a lot of CPU time, and because my solution is not exact, I elected not to post a javascript version on line.