NPR Puzzle Solved: 3 Similar Names

Posted on August 1, 2014 Updated on August 1, 2014

That puzzle was the fastest solve ever, I had the whole thing done in less than an hour! Yee-haw! The funny thing is that, just last week, Will actually said that he designs the puzzles to be just as hard to solve manually as with code. But solving this one in code was so easy that perhaps Will didn’t understand what that means…

The Challenge

This week’s challenge comes from listener Matt Jones of Portland, Ore. There are three popular men’s names, each six letters long, that differ by only their first letters. In other words, the last five letters of the names are all the same, in the same order. Of the three different first letters, two are consonants and one is a vowel. What names are these?

Challenge URL: http://www.npr.org/2014/07/27/335590211/a-flowery-puzzle-for-budding-quizmasters

What You Will Learn from Reading!

1. Improve your understanding of generic dictionaries in .NET
   • Specifically, how dictionary entries can contain complex structures, such as lists
2. String manipulation, specifically searching for substrings and extracting them from larger strings
3. A sample use of a lambda expression, using the operator ‘Aggregate’, which I use to build a comma-delimited list from a list of string

Solving the Puzzle

I have a file of the to 1,219 most common boy’s names, and was able to use it to find the three forming the solution. Sorry, I don’t remember where I got it; I thought it was from the Census Bureau, but now I can’t find it on their site. Using that file,

1. Build a dictionary to hold candidate names
2. Open the file of names for reading
3. Examine every name whose length is 6
4. Extract the last 5 letters from each name
5. Check if the dictionary already has a pre-existing entry, using the last 5 letters of each name as the key
   • If so, append the current name to the dictionary entry
6. Each entry in the dictionary is a list (because a dictionary can use any data type for the entries)
   • But, if the dictionary lacks an entry identified by the current last 5 letters, add one now
7. After loading the dictionary,
8. Traverse all its entries
9. If any entry has exactly 5 names in its list, we have a candidate!
10. Check the vowel/consonant counts, if there are 2 consonants, we’ve got a winner

Here’s the heart of the code:

private void btnSolve_Click(object sender, RoutedEventArgs e) {
  Dictionary<string, List<string<< nameDic = new Dictionary<string, List<string<<();

  //Open the file and read every line
  using (StreamReader sr = File.OpenText(NAME_FILE)) {
    while (sr.Peek() != -1) {
      string aLine = sr.ReadLine();
      //Sample lines looks like this:"DUSTIN         0.103 70.278    176"
      //                             "JUSTIN         0.311 49.040     56"
      //                             "AUSTIN         0.044 78.786    301" 

      //The name is position 1-15, the other columns are frequency counts and rank

      //Locate the end of the name
      int p = aLine.IndexOf(' ');
      if (p == NAME_LEN) {
        //grab the first 6 characters:
        string aName = aLine.Substring(0, NAME_LEN);
        //Now grab the last 5 letters of the name:
        string last5 = aName.Substring(1);

        //If we already have an entry (grouping) for the last 5 letters, add to the name list:
        if (nameDic.ContainsKey(last5)) {
          nameDic[last5].Add(aName);
        } else {
          //Start a new grouping using the last 5 letters as the key and the full name as the first strin entry
          List<string< nameList = new List<string< { aName };
          nameDic.Add(last5, nameList);
        }
      }
    }
  }

  //Now find groups of names having length 3, such as 'Justin', 'Dustin', 'Austin'
  foreach (KeyValuePair<string, List<string<< kvp in nameDic) {
    if (kvp.Value.Count == 3) {
      int vowelCount = 0;
      int consonantCount = 0;
      //Get the vowel/consonant counts of the first letters:
      foreach (string aName in kvp.Value) {
        //Binary search returns a non-negative value if it finds a match:
        //In retrospect, a binary search is not appropriate for an array of size 5, but it doesn't hurt
        if (Array.BinarySearch(vowels, aName[0]) <= 0)
          vowelCount++;
        else
          consonantCount++;
      }

      //according to the rules, there should be 1 name starting with a vowel and 2 with consonants:
      if (consonantCount == 2) {
        //We can use a lambda expression to concatenate the list entries with commas
        string combined = kvp.Value.Aggregate("", (p,c) =< p + ", " + c);
        txtAnswer.Text += combined.Substring(2) + "\n";
      }
    }
  }
}

I’ve posted the complete project here if you would like to download it. The code should run in Visual Studio 2010 or higher; you can use the free version of Visual Studio (“Express”) if you like. The data file is included in the zip folder; you can find it in the bin folder.