Every Sunday, PuzzleMaster Will Shortz broadcasts an intriguing puzzle, and whoever solves it
gets to play a fresh puzzle on-air. I try to solve the original puzzle with the
eleganct tools of programming,
and post my code here. For your amusement, I also create my own slightly different
version of Will's challenge for you to test your
skill.
Learn new coding skills, or prove yourself against my puzzle; either way, enjoy
the site!
How to Solve Will's Puzzle With Code
Take the name "Pensacola," remove one letter and rearrange the letters that remain to get the first
and last name of a famous person in American history. Who is it?
Code Techniques:
-
string manipulation
-
dictionary lookup
-
simple sorting
-
Understanding anagrams
Rating: easy!
Hardest part: getting the list
That was a nice easy one, especially since I fine-tuned my list of famous Americans a long time ago.
The important technique to understand is the method of determining whether two words are anagrams: if you sort both
words and then compare them letter by letter, you can quickly determine whether they are anagrams.
Since the problem was quite straightforward, I also present a pair of alternate solutions to the puzzle,
including one utilizing Linq.
Basic Algorithm Summary
-
Build a dictionary of famous Americans names, but create
the key in a special way
-
Specifically, build your key from the person's first and last names,
concatenated and sorted.
-
For example, "Abraham Lincoln" becomes "aaabchillmnnor"; use it as the the dictionary key. I like
pronouncing that one - it almost sounds like some rapper lingo!
-
Now, sort the letters in the word 'Pensacola' to get 'aacelnops'. Pensacola
is now sorted the same way as the dictionary keys, except that it has an unknown letter we must remove.
-
Working with 'aacelnops', remove one at a time and check whether the result
is a key in our dictionary - if we score a hit with any given key, use it to retrieve the
original name and solve the puzzle!
The part I enjoyed most about this puzzle was that I was able to solve it in about 45
minutes. I think I only had to fix three bugs, and that is a great feeling!
The code below illustrates the core of my algorithm:
Dictionary<string, Person> PersonDic = LoadPersonDic();
//Sort the word 'Pensacola' and store as a string:
char[] ltrs = "pensacola".ToCharArray();
Array.Sort(ltrs);
string pensacola = new string(ltrs);
//Work through all the letters and remove one at a time, removing each
//and checking if the result is a key in the dictionary:
for (int i = 0; i < pensacola.Length; i++) {
string candidate = pensacola.Remove(i, 1);
if (PersonDic.ContainsKey(candidate)) {
//Write the results to our listbox!
lstResults.Items.Add(PersonDic[candidate]);
}
}
I ommitted the code to load the dictionary, in order to jump straight to the
heart of the algorithm. Here's a
few comments on the code above:
-
Working with 'aacelnops' (the letters of pensacola sorted alphabetically) inside the loop, I try variations
'acelnops', 'aaelnops', 'aaclonps', etc., dropping a letter each try to work through all 8 possibilities.
As it turns out, the correct candidate is 'aacelnop'. Why? Because the mystery name,
when combined into a single word and sorted, is also spelled 'aacelnop'!
-
Each entry in the dictionary is a key/value pair: the value is the famous american's name,
and we use the sorted first/last name as the key.
-
I chose to use a dictionary (a type of hash table in .NET) because 1) they're realy easy
and 2) blazingly fast!
-
I used a dictionary to hold my key/value pairs because of their extreme efficiency of dictionaries
for performing lookups.
-
Thus, I built the dictionary so that Al Capone is represented by the key 'aacelnop'; the code
fragment
PersonDic[candidate] uses the key to
retrieve the value 'Al Capone' from the dictionary.
Alternate Algorithm
There is a more obvious way to solve the problem, which actually would have been more
efficient, but which turns out bo be somewhat trickier:
-
Form all the variations of Pensacola by dropping successive letters
-
For each variation, list all the combinations of the letters
-
Then look-up each of them in a dictionary of (non-sorted) first name/last names.
This method is trickier because listing all the combinations of a word is a bit of chore.
This task is actually challenging enough that some people use it as a job interview question!
-
For example, after dropping 'P', the first variant spelling of pensacola is 'ensacola',
which can then be recombined to form 5,040 variations, such as 'ensacoal', 'ensacaol',
'ensaacol', etc. 'Ensacola' has 7 letters and there are 7! different combinations.
-
Thus, under this method, we would have performed 35,280 dictionary lookups (35,280 =
7 * 5040, i.e. 7 variant spellings of pensacola times 5,040 combinations each), overall this would have
been somwhat faster than sorting the letters of each of the 13,540 names in my list of famous americans.
-
Note that, even though there are 8 letters in Pensacola, it has two a's, which
means there are actually only 7 unique variants, not 8, at least for our purposes.
-
Given moderen CPU speeds, either method performs so fast that it takes less than a second
to run, and I prefer my first method because it is easier to understand.
-
Note that the solution runs considerably quicker in C# than in Javascript, particularly if
your browser is Internet Explorer!
Alternate Algorithm: Let's try Linq!
Mainly for kicks, I decided to try solving the puzzle using Linq. For those of you unfamiliar with Linq,
it is a set of language extensions to .NET which allow you to use lambda expressions and also allow you
to perform set operations, similar to SQL. Linq is short for 'Language Integrated Query'.
After some fumbling around, I realized one way to approach the problem was to 1) create a list of
Persons, 2) create a list of sorted variants on 'Pensacola', and 3) use the join operator
on the two lists.
Step One: Build the Two Lists
Instead of storing the Person objects in a dictionary, put them into a List:
List<Person> personList = new List<Person>();
FileStream fs = new FileStream(PEOPLE_FILE, FileMode.Open, FileAccess.Read);
StreamReader sr = new StreamReader(fs);
while (sr.Peek() != -1) {
string aLine = sr.ReadLine();
personList.Add(new Person(aLine));
}
Do the same thing for the pensacola variants. Note that I couldn't find any way to use a
simple list of type
string; Linq forced me to create a class City with a single property, 'CityKey'.
List<City> pensacolaVariants = new List<City>();
string pensacola = "aacelnops";
for (int i = 0; i < pensacola.Length; i++) {
string candidate = pensacola.Remove(i, 1);
pensacolaVariants.Add(new City{cityKey = candidate});
}
Step Two: Join the Two Lists
var expr =
from p in personList
join c in pensacolaVariants
on p.SortedKey equals c.cityKey
select new { p.FirstName, p.LastName };
//Display the results.
foreach (var x in expr) {
lstResults.Items.Add(x.FirstName + " " + x.LastName);
}
Obviously, the Linq approach is less efficient than my original approach, which
merely performs 8 dictionary lookups, running in O(1) time.
My guess is that, behind the scenes, Linq expends the effort to sort both lists on CityKey/sortedKey, then traverse the two lists
simultaneously seeking matches on the two fields. The two sorts probably run in O(n Log(n)) time and the traversal
involves another n operations. However, for lists this short, the efficiency hit is negligible; once again, the
solution is presented in less than a second of run time.
Click this link to download my C#
solution code, including my list of famous americans.
You will have to modify the code to reference the correct file path to the people list on your PC.
Got a solution in your own language? Post a comment to that effect and I
may post your code on line.