Calculator Letters Puzzle – Solved!

Posted on September 18, 2014 Updated on September 20, 2014

Or, Fun with Lambdas and Set Functions!

The challenge:

This three-part challenge comes from listener Lou Gottlieb.
If you punch 0-1-4-0 into a calculator, and turn it upside-down, you get the state OHIO.
What numbers can you punch in a calculator, and turn upside-down, to get a state capital,
a country and a country’s capital?

Puzzle Location:
http://www.npr.org/2014/09/14/348220755/the-puzzle-and-the-pea

The Solution Revealed!

The first thing we need is a list of countries, state capitals, and world capitals. Fortunately, I already have files containing the required data (you can get those files if you download the solution code below):

• State Capitals
• World Capitals
• Countries

Once we have the data, it is basically a matter of determining whether one string set is entirely included within another string set. In other words, we will ask, for a number of solution candidates, whether it is a proper subset of the set of calculator letters.

To determine whether we have a subset, it is fun to use the Linq built-in set operators. In particular, we can use the method ‘Except‘. I also could have used the HashSet functionality, which actually has a method named ‘IsProperSubSet’, but HashSet is not as convenient as Linq and I just wanted to crank-out some code!

Using Linq, we can determine that one string is a proper subset of another if, when we use Except on them, the result is the empty set, i.e. a list with no members. Examples:

• “atlanta”.Except(“beignlos”) will return a list containing (‘a’, ‘t’), i.e. not a subset.
• “cheyenne”.Except(“beignlos”) will return a list containing (‘c’, ‘h’, ‘y’). Also not a subset.
• “boise”.Except(“beignlos”) returns the empty set, i.e. it is the answer!

Note: “beignlos” is a string containing all the calculator letters. The true benefit of the ‘Except’ method is apparent below:

Here’s a Super-Cool Sample of the .NET Set-Operator ‘Except’

var leftoverLetters = "boise".Except("beignlos");
if (leftoverLetters.Count() == 0)
	Console.WriteLine("Ding ding ding - we have a winner!");

Conclusion: ‘boise’ is a subset of ‘beignlos’ –> you can spell ‘Boise’ using upside down calculator letters, and the Except  function tells us that.

Use Set-Operators at Work, Too!

At work, I have recently used the ‘Except’ operator to find orders that were lost. Something along these lines: ‘var missing = outboundOrders.Except(inBoundOrders);‘

My guess is you can use the Except operator to identify a lot of other things!.

Using Lambdas as ‘First Class’ Objects

First, a little bit of terminiology: “First class objects” are objects that you can use like any other entity. Such uses include passing them as parameters. When you pass a Lambda expression as a parameter, you are taking advantage of the fact that Lambdas are first class objects.

Why did I tell you that? Because my code benefited from it in this fun little app. In particular, I have these needs:

• I need to perform the same work on 3 different files (state capitals, world capitals, countries)
• Each file has a different layout
• I would like to write a single method to do the same work for each file
• To do so, I could write 3 different lambdas; each knowing how to extract the candidate from a line in a file
• And then pass each lambda as an input parameter it to my method
• Benefit: I write one method, which uses a lambda to extract the candidate, instead of 3 methods, each with their own
  techinque to extract the candidates

Here’s the Code

private void btnSolve_Click(object sender, RoutedEventArgs e) {
  //Make a definition list of the calculator letters.
  //This maps letters to the numbers they represent in a calculator. 
  //Each letter is in lower case to make matching easier
  //Note: a 'tuple' is a type of anonymous class
  List<Tuple<char, int>> calculatorLetterMap = 
  new List<Tuple<char, int>>() { Tuple.Create('b', 8), 
    Tuple.Create('e', 3), 
    Tuple.Create('i', 1), 
    Tuple.Create('g', 6), 
    Tuple.Create('n', 4), 
    Tuple.Create('l', 7), 
    Tuple.Create('o', 0), 
    Tuple.Create('s', 5) 
  };

  //The next 3 lines process state capitals:
  Func<string, string> extractStatCap = (aLine => { 
      //Look for hyphen, take the rest of the line, trimmed, in lowercase
      return aLine.Substring(aLine.IndexOf('-') + 2)
      .TrimEnd()
      .ToLower(); 
      });
  List<string> stateCapHits = GetFileMatchesAgainstLetterSet(STATE_CAPITALS_FILE, 
                              calculatorLetterMap, extractStatCap);
  DisplayHits(stateCapHits, "State Capitals", calculatorLetterMap, txtResults);

			
  //Now world capitals:
  //The function is a bit more complicated because some names have spaces, such as 'Abu Dhabi'
  Func<string, string> extractPlaceFunc = (aLine => { 
    //Look for a tilde and take everything prior to it, removeing non-letters
    return aLine.Substring(0, aLine.IndexOf('~'))
          .Where(c => char.IsLetter(c))
          .Aggregate("", (p,c) => p + c); 
    });
    List<string> worldCapHits = GetFileMatchesAgainstLetterSet(WORLD_CAPITALS_FILE, 
              calculatorLetterMap, extractPlaceFunc);
    DisplayHits(worldCapHits, "World Capitals", calculatorLetterMap, txtResults);

			
    //Finally, country names:
    Func<string, string> extractCountryFunc = (aLine => aLine);
    List<string> countryHits = GetFileMatchesAgainstLetterSet(COUNTRIES_FILE, 
          calculatorLetterMap, extractCountryFunc);
    DisplayHits(countryHits, "Countries", calculatorLetterMap, txtResults);
  }

  /// <summary>
  /// Loops through a file and returns a list of every entry which
  /// can be composed solely with 'calculator letters'
  /// </summary>
  /// <param name="fName">The file containing things that might match</param>
  /// <param name="calculatorLetterMap">List of letters derived from upside-down 
  /// calculator numbers</param>
  /// <param name="extractPlaceFunc">Function to extract the item of interest 
  /// from each line in the file</param>
  /// <returns></returns>
  private static List<string> GetFileMatchesAgainstLetterSet(string fName, 
          List<Tuple<char, int>> calculatorLetterMap, 
          Func<string, string> extractPlaceFunc) {
  List<string> result = new List<string>();
  using (StreamReader sr = File.OpenText(fName)) {
    while (sr.Peek() != -1) {
      //Execute the Lambda provided by our caller:
      string candidate = extractPlaceFunc(sr.ReadLine());
      var leftOverLetters = candidate
        .ToLower()
        .Except(calculatorLetterMap.Select(m => m.Item1));
        //If there are no leftover letters, we have a winner!
        if (leftOverLetters.Count() == 0) {
        string propperCase = char.ToUpper(candidate[0]) + candidate.Substring(1);
        result.Add(propperCase);
      }
    }
  }

  return result;
}

  /// <summary>
  /// Displays every hit in the list with its equivalent in 'calculator letters'
  /// </summary>
  /// <param name="hitList">List if items to dispaly</param>
  /// <param name="caption">Caption, such as 'State Capitals'</param>
  /// <param name="calculatorLetterMap">List of letter/number pairs for translating</param>
  /// <param name="txtResult">Textbox to hold the result</param>
  private static void DisplayHits(List<string> hitList, string caption, 
        List<Tuple<char, int>> calculatorLetterMap, TextBox txtResult) {
    txtResult.Text += caption + "\n";
    foreach (string aHit in hitList) {
      string number = MapLettersToCalculatorNumbers(aHit, calculatorLetterMap);
      txtResult.Text += string.Format("\t{0} = {1}\n", number, aHit);
    }
  }

  /// <summary>
  /// Translates the puzzle answer ('candidate') back into 'Calculator letters'
  /// </summary>
  /// <param name="candidate">Such as 'boise' or 'benin' or 'lisbon'</param>
  /// <param name="calculatorLetterMap">List of letter/number pairs</param>
  /// <returns>A string composed of numerals</returns>
  private static string MapLettersToCalculatorNumbers(string candidate, 
    List<Tuple<char, int>> calculatorLetterMap) {
    string result = (from c in candidate
                     join m in calculatorLetterMap on c equals m.Item1
                     select m.Item2
                     ).Aggregate("", (p, c) => p + c);
    return result;
  }

Download the code here: Puzzle Code