• Play
• Code
• Solve It
• Challenge

How to Solve Will's Puzzle With Code

Overall, pretty straightforward, if you have a list of word pronunciations, or else a phoneme list. A phoneme is "the smallest linguistically distinctive unit of sound", and there are about 39 phonemes in standard english. If you know the phonemes for a given word, you can determine whether it contains a short A.

Basic Algorithm Summary

• Get a list of words and the phonemes that make them up
• Look at all the words having length four
• And also containing the phonme 'AE', which is the representation for a short A
• Add each 4-letter word to a dictionary
• Once we have constructed the complete list, examine each entry
• For each entry, swap the 3rd and 4th letters to make a candidate word
• If the candidate word is also in the dictionary, we might have a winner!

I used the CMU prouncing dictionary, which is a list of english words and their phonemes. Note that entries in my file look like this:

By way of explanation, the word 'bag' is composed of four phonemes, 'B, 'AE1',  and 'G'. The numeral 1 indicates the level of stress to place on the phoneme, and as I already mentioned, 'AE' indicates a short A. To process a line of data like this, we need extract the word at the beginning of the line, but only if there is a phoneme 'AE', and only if the word has length four.

The code below, which runs inside a loop that reads my phoneme file, illustrates how to extract the words we want from the file:

//Read a line using 'sr', a StreamReader object:
string aLine = sr.ReadLine();
//There is a space following the word
int p = aLine.IndexOf(" ");
string aWord = aLine.Substring(0, p);
if (aWord.Length == 4) {
    p = aLine.IndexOf(" AE", p + 2);
    if (p > 0) {
        wordDic.Add(aWord, 'a');
    }
}

Swapping the Letters and Checking the Dictionary

Swapping letters is simple string manipulation. We use the 'Substring' method to extract portions of the word, and the plus sign to concatenate those portions into a candidate word. Then we check the dictionary to see whether we built a proper word.

At this point, you may find it easier to read the code than to follow my explanation!

//Iterate the dictionary:
foreach (KeyValuePair<string, char> wordPair in wordDic) {
    //the second letter should be an 'a', according to Will:
    if (wordPair.Key[1] == 'A') {
        //construct the variant by swapping the letters at positions 2 and 3:
        string variant = wordPair.Key.Substring(0, 2) + 
                         wordPair.Key.Substring(3, 1) + 
                         wordPair.Key.Substring(2, 1);

        //if the variant is a word, put it into the results list:
        if (variant != wordPair.Key && wordDic.ContainsKey(variant)) {
            lstResults.Items.Add(wordPair.Key + " - " + variant);
        }
    }
}

Interpreting the Results

My algorithm spits out a list of 28 candidates that meet the criteria of 1) length == 4, 2) contain a short A, 3) matches another word by swapping letters 3 and 4. These entries are not necessarily common phrases, and most of them are not even grammatical. I could use my parts of speech dictionary to determine which ones are grammatical, thus shortening the list. But, a list of 28 is short enough, especially given the amount of work that would be necessary to shorten the list by applying grammar rules.

Examine the 28 candidates and you will observe one pair that did indeed exist, in New York, between 1982 and 2000, though it helps if you know something about theatre!

Click this link to download my C# solution code. You can get the CMU Pronouncing dictionary by following this link. You will have to modify my code to reference the correct file path to that list on your PC.

Got a solution in your own programming language? Post a comment to that effect and I may post your code on line.

Solve the Problem Now!

Sorry - this week's solution is not suitable for solving with JavaScript. The main problem is that the phoneme file is too big. Attempting to process a file of this size is bogging down the processor to the point that each line of code seems to require 30 seconds to run, regardless of whether I try IE or Firefox.

Take-Home Challenge!

Can you can write your own code to solve a similar problem? See if you can think of two related words that have the following properties:

• Both words have a short A sound in them
• When you swap two letters, the word meaning switches from two-dimensional to three dimensional
• Each word has three syllables