Sunday Puzzle Solved! Countries and Captials

That one was fun, and pretty simple too! It was fun because I got to use some set-manipulation features of Linq. And it was easy because I already had the data files to solve with. Furthermore, I found two answers, and the puzzler thinks there is only one. Yipee, I found an extra answer! The only unsatisfactory part was suppressing duplicates in my answer list; perhaps some intrepid reader can suggest a more elegant solution.

The challenge:

Name a certain country. Change one letter in its name to a new letter and rearrange the result to name another country’s capital. Then change one letter in that and rearrange the result to name another country. What geographical names are these?

Challenge URL: http://www.npr.org/2014/10/12/355399107/coming-to-tv-this-fall-anagrams

Screen shot showing the solution to the puzzle. Using Linq, the solution requires only a few lines of code. Key functionality: the Intersect method, which I used to determine if a capital and a country differ by just one letter.

 What You Could Learn Here

• How to use Linq to compare lists in a fairly novel manner.
• How to use the Intersect method to tell if two words differ by just one letter. Hurray, set theory!
• How to sort strings using the Aggregate method

Algorithm

1. Build a list of countries, all in lower case
2. Build a list of capitals, also in lower case
3. Using Linq, build a list of countries matching capitals…
4. According to the following comparison method:
   1. They must have the same length (i.e., country must be same length as capital)
   2. And, when we take the intersection of the country with the capital, the result must have length 1 less than the original length
   3. When this condition is met, we have satisfied Will’s requirement to “change one letter in its name and  rearrange the result to match another country’s capital”
5. Take the resulting list from above and use Linq to compare it against the country list, using the same criteria
6. The result will be a list containing our answer!
7. The only problem is that each answer is listed twice, the countries having different order
8. For example, Iraq/Riga/Iran will be listed, and so will Iran/Riga/Iraq

Here’s the Code

private void btnSolve_Click(object sender, RoutedEventArgs e) {
  List<string> countryList, capitalList;
  LoadTextFiles(out countryList, out capitalList);

  //Match countries against capitals
  var step1 = from cty in countryList
        from cap in capitalList
        where cap.Length == cty.Length 
            //Key functionality: the intersect function
            && cty.Intersect(cap).Count() == cty.Length - 1
        select new { Country = cty, Capital = cap};

  //Now match the result from above against the country list again
  var step2 = from pair1 in step1
        from cty in countryList
        where pair1.Capital.Length == cty.Length
            && pair1.Country != cty
            && pair1.Capital.Intersect(cty).Count() == pair1.Capital.Length - 1
        select new { Country1 = pair1.Country, Capital = pair1.Capital, Country2 = cty };

  //At this point, we have the answers, but they are duplicated, for example 
  //"Iran Riga Iraq" vs. "Iraq Riga Iran"
  //Use the list below to avoid displaying dups:
  List<string> distinctLetters = new List<string>();
  foreach (var answer in step2) {
    //Concatenate the countryies/captial, then sort;
    //the sorted letters will determine duplicates
    string sortedLetters = (answer.Country1 + answer.Capital + answer.Country2)
                           .OrderBy(c => c)
                           //'Aggregate' transforms the list back into a string:
                           .Aggregate("", (p, c) => p + c);
    //If we have not yet displayed this answer, do so now and 
    //record that fact in distinctLetters
    if (!distinctLetters.Contains(sortedLetters)) {
      distinctLetters.Add(sortedLetters);
      string displayMe = string.Format("{0}\t{1}\t{2}\n", 
                               answer.Country1, answer.Capital, answer.Country2);
      txtAnswer.Text += displayMe;
    }
  }
}

/// <summary>
/// Load the Capital/Country file into two lists
/// </summary>
/// <param name="countryList">The list of countries</param>
/// <param name="captialList">The list of capitals</param>
private void LoadTextFiles(out List<string> countryList, 
                   out List<string> captialList) {
  countryList = new List<string>();
  captialList = new List<string>();
  using (StreamReader sr = File.OpenText(CAPITAL_FILE)) {
    while (sr.Peek() != -1) {
      //Sample line looks like this: Athens~Greece
      string aLine = sr.ReadLine().ToLower();
      //find the tilde so we can separate the capital from the country
      int p = aLine.IndexOf("~");

      captialList.Add(aLine.Substring(0, p));
      countryList.Add(aLine.Substring(p + 1));
    }
  }
}

Download my code here: https://www.dropbox.com/s/wix8r5jb1pipjha/12Oct2014.zip?dl=0