• Play Online!
• Code
• Solve It
• Challenge

How to Solve Will's Puzzle With Code

Overall, pretty straightforward, if you have a nice list of common trigrams and a word dictionary. Though some of the loop logic was a bit tricky, the Visual Studio debugger saved the day for me! I also had a little fun trying out more Linq/Lambda expression techniques.

Basic Algorithm Summary

• Get a list of common trigrams (optional)
• For each trigram, construct variations...
• By combining it with the letters 'r', 'f', 'e' and 'r'
• For each trigram, you can make 10 variations
• For each variation, try splitting it at various places to see if the two halves are legitmate words.
• For example, if the current trigram is 'the', one variation we could construct is 'therthefer'. We can split this at 9 different places, such as at the 3rd position, which forms two parts 'the' and 'rthefer'. Unfortunately, only the first part is a legitmate word.
• If, after splitting the variation, we get two words, then we have a potential soution!

The code below, which runs inside a loop that reads my trigrams file, illustrates the core of my algorithm:

//Read the next trigram from file (1st 3 chars on the line):
char[] trigram = sr.ReadLine().Substring(0, 3).ToLower().ToCharArray();

//for each trigram, construct a list of all 10 possible sequences
//I will discuss how this method works below
List<char[]> varList = PuzzleHelper.BuildTrigramVariations(template, trigram);

//Now split each variation and see if we get two words:
foreach (char[] variation in varList) {
    for (int i = 1; i < candidate.Length - 1; i++) {
        //take a slice out of the candidate using the 'Where' operator, 
        //then concatenate using the 'Aggregate' operator
        string word1 = variation
            .Where((c, ndx) => ndx < i)
            .Aggregate("", (s, t) => s + t);
            
        //wordDic is a dictionary (a type of hash table):
        if (wordDic.ContainsKey(word1)) { 
            //Every letter, starting from i, to the end,
            //forms our second word candidate:
            string word2 = variation
                .Where((c, ndx) => ndx >= i && ndx < variation.Length)
                .Aggregate("", (s,t) => s + t);
            if (wordDic.ContainsKey(word2)) {
                string trigramStr = new string(trigram);
                lstResults.Items.Add(trigramStr + ": " + word1 + ", " + word2);
            }
        }
    }
}

I ommitted the code that opens my trigram file, in order to jump straight to the heart of the algorithm. I also glossed-over my method 'BuildTrigramVariations', but I promise to explain it below. Here's a few comments on the code above:

• As I mentioned above, I horsed-around with some Linq operators, namely the 'Where' operator and the 'Aggregate' operator
• Those operators are a high-falutin way to split each variation at the position designated by my loop variable 'i'
• Note that each variation is an array of char.
• I used the Where operator kind of like the slice operator from languages like Javascript and Perl. However, 'where' is quite a bit more flexible. Basically, it is selecting array elments when their index (ndx) is less than the position I designate with my loop variable i.
• I used the Aggregate operator a kind of concatenation operator. The seed for the Aggregate operator is an empty string, and for each successive invocation of my lambda expression, I append the current value using the + operator.
• I'm sure most readers can think of more traditional methods to slice an array and concatenate the two halves into two strings, but this way was new and different!

Creating the Variations

As promised, here's my technique for creating the ten variations per trigram. First, let's look how we can combine the letters Will gave us with any trigram. Here is a diagram illustrating where we can place the trigram:

___r___f___e___r___

Think of my diagram as having 5 slots that we need to fill in twice, such as this sample, using the trigram 'the':

___rTHEf___eTHEr___

In this sample, I filled in the second and fourth slot. We can fill in the slots systmatically using two loops, the second loop nested within the first. The outer loop selects which slot to use for the first copy of the trigram, and the inner loop selects the other slot.

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

public static List<char[]> BuildTrigramVariations(char[] template, char[] trigram) {
    //build an empty return list which we will populate:
    List<char[]> candidateList = new List<char[]>();
    
    //Template is a char array with Will's characters (r-f-e-r)
    //placed at every 4th position
    for (int i = 0; i <= template.Length - 7; i += 4) {
        
        //insert the trigram into the template array
        //at the position dictated by i
        Array.Copy(trigram, 0, template, i, 3);
        for (int j = i + 4; j <= template.Length - 3; j += 4) {
            //insert the trigram at a second position
            Array.Copy(trigram, 0, template, j, 3);
            
            //build the candidate array by copying
            //from template, ignoring nulls:
            int dest = 0;
            char[] candidate = new char[10];
            for (int k = 0; k < template.Length; k++) {
                if (template[k] != '\0') {
                    candidate[dest++] = template[k];
                }
            }
            
            //we've built this variation; add to the return list:
            candidateList.Add(candidate);
            //blank-out the spot just used, in preparation for next pass:
            for (int k = j; k < j + 3; k++) {
                template[k] = '\0';
            }
        }
        //blank-out the spot we just inserted a trigram:
        for (int j = i; j < i + 3; j++) {
            template[j] = '\0';
        }
    }
    return candidateList;
}

Trigram List

I found a nice list of the most popular trigrams in the English language here: http://www.cs.chalmers.se/Cs/Grundutb/Kurser/krypto/en_stat.html Since it was a short list, I didn't need to do much to copy it and save to a file, and fortunately it contained the winning trigram!

Click this link to download my C# solution code, including the list of trigrams. You will have to modify the code to reference the correct file path to that list on your PC. Note that my solution also contains a separate project with some NUnit tests, which you can remove if desired.

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!

By clicking the button, you will run a small javascript program in your browser to solve the problem. It needs to fetch the word list and trigram list from the server; after that it should solve the problem in a few seconds. If you're curious, inspect the page source code! (Search for "function dataFetched".)

Take-Home Challenge!

Can you can write your own code to solve a similar problem? Think of a common phrase, associated with weddings, that contains the trigram 'ing' 4 times, and also the trigram 'eth' four times. The phrase has a number of repeated words and has a total of 8 words.