• Play
• Code
• Solve It
• Challenge

How to Solve Will's Puzzle With Code

A great ego boost for me! Getting the magazine list was exceptionally easy, and working with anagrams is old hat. I finished this one before the end of the show and was feeling pretty good! The only glitch was I initially forgot to remove spaces and punctuation from the magazine names before using for anagram purposes.

Basic Algorithm Summary

• Get a list of magazines. Wikipedia has a great list!
• Use it to build a list in memory
• Each entry in our list will be a class with two parts: the magazine name, and the sorted magazine name
• For example, "life|eifl" or "time|eimt"
• To make searching fast, sort the list, not on the magazine name, but on the second value, the sorted name
• Sort Will's phrase "more corruptness" to get "ceemnooprrrsstu"
• Search our list and see whether any entry in our list matches ceemnooprrrsstu; if so, we have a winner!

If you're a regular reader, you might be asking 'Why didn't you use a dictionary, instead of a list?'. My answer: I was little bored and decided to do it a different way. Also, it might be helpful for regular readers to learn a different way of performing efficient lookups.

First, I will create a simple class consisting of just two properties: a word and the sorted equivalent. Shortly, I will use this class to build a list of magazine names.

    public class SortedWord {
        private string _Word;
        private string _Sorted;

        //Will hold the magazine name
        public string Word {
            get { return _Word; }
            set { _Word = value; }
        }

        //Will hold the sorted version of the magazine name
        public string Sorted {
            get { return _Sorted; }
            set { _Sorted = value; }
        }

        //Default constructor
        public SortedWord() {
        }

        //The constructor takes the magazine name, sorts it,
        //and stores it in our field '_Sorted'
        public SortedWord(string newWord) {
            _Word = newWord;
            char[] ltrs = newWord.ToCharArray();
            Array.Sort(ltrs);
            _Sorted = new string(ltrs);
        }
    }

Using the List

In case you've never worked with anagrams, you're probably wondering why I sorted each magazine name. The answer is that, when you sort two words that are anagrams of each other, their sorted names become the same.

Take a look at the word pairs to the left. Note that, when you sort 'time', you get 'eimt', and when you sort 'item', you also get 'eimt'. If any two words are anagrams, then, when you sort their letters, you will always get the same result. This is the principle that now allows me to search for any magazine that is an anagram of will's phrase, 'more corruptness'.

Next, I read my magazine file and use it to build the list, which I also sort:

List<SortedWord> magazineList = new List<SortedWord>();
FileStream fs = new FileStream("Periodicals.txt",
                      FileMode.Open, FileAccess.Read);
StreamReader sr = new StreamReader(fs);
while (sr.Peek() != -1) {
    //Read each line, lower case, remove spaces and punctuation:
    string mag = CleanNonLetters(sr.ReadLine().ToLower());

    SortedWord sw = new SortedWord(mag);
    magazineList.Add(sw);
}
//sort on the sorted name, not the original word:
magazineList.Sort((x, y) => 
                 { return string.Compare(x.Sorted, y.Sorted); });
...
...
...

public static string CleanNonLetters(string inStr) {
    StringBuilder sb = new StringBuilder();
    foreach(char c in inStr) {
        if (char.IsLetter(c)) {
            sb.Append(c);
        }
    }
    return sb.ToString();
}

I hope the code is all straightforward, except for the line where I sort the list. That line of code uses a lambda expression to assist with the sort operation. Why do I need the lambda expresion? In order to sort anything besides simple types like int and string, you need to tell .NET how to compare each entry in the list. In this case, I am telling .NET to sort by comparing the property named 'Sorted' for each pair of entries in the list.

Searching the List for the Solution!

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

//Sort Will's phrase and see if it is in the list:
string willPhrase = "morecorruptness";
ltrs = willPhrase.ToCharArray();
Array.Sort(ltrs);
SortedWord key = new SortedWord 
                 { Word = string.Empty, Sorted = new string(ltrs) };

int pos = magazineList.BinarySearch(key, new SortedWordComparer());
if (pos > 0)
    //Score!
    lstResults.Items.Add(magazineList[pos].Word);
...
...
...
//This class controls the comparison operation used for the 
//binary search above
public class SortedWordComparer : IComparer<SortedWord> {
    public int Compare(SortedWord x, SortedWord y) {
        return string.Compare(x.Sorted, y.Sorted);
    }
}

A Few Loose Ends

Note that the binary search method needs to know two things: what to look for, and how to compare two objects in the list. My little class 'SortedWordComparer' serves the purpose of designating how to compare two objects, and the thing we are looking for is the SorteWord named 'key'.

Note that when you perform a binary search, it returns the position (index) in the list where it found your item. If it doesn't find it, it will return a negative number, equivalent to the boolean inverse of the index, which represents the position of the closest match (before inversion). In our case, all we care about is whether we get a non-negative number.

Algorithm Analysis: Dictionary vs. a List with Binary Search

As it turns out, not only are dictionaries more effiecient, but they would actually have been easier to use for this puzzle. A dictionary can perform a look-up in O(1) time (constant time), whereas a binary search needs O(ln(n)) time. Since my list only has about 600 entries, this means I used approximately 6.3 operations, instead of one. This is actually pretty small difference, particularly since I only perform one lookup, making the design decision a moot point for this puzzle.

Also, had I used a dictionary, I would not have needed my two simple classes 'SortedWord' and 'SortedWordComparer', simplifying the code. But, as I said above, I mainly decided to use a list, instead of a dictionary, for a change in pace./p>

Click this link to download my C# solution code. Look in the 'bin' folder for my list of periodicals, which I got from Wikipedia at http://en.wikipedia.org/wiki/List_of_United_States_magazines

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!

Take-Home Challenge!

Can you can write your own code to solve a similar problem? See if you can think of the magazines that are anagrams of the phrases below:

• dead register
• bead town
• moan story
• ad returnee
• animism tuts
• clad worm
• malefic pus
• fined woo