Sunday Puzzle: Nationality, Demonyms and Consonyms!

Posted on Updated on

This week’s challenge is a spinoff of my (e.g. Will’s) on-air puzzle. Name two countries that have consonyms that are nationalities of other countries. In each case, the consonants in the name of the country are the same consonants in the same order as those in the nationality of another country. No extra consonants can appear in either name. The letter Y isn’t used.

Link to the Challenge

Definition Demonym; noun: A name for an inhabitant or native of a specific place that is derived from the name of the place.

Two words share consonyms if they have the same consonants, in order. The consonants in Ukraine map to the same consonants in Korean.

Synopsis

Well, that was a nice, easy, fun one! Happily, I already had a list of nations and their demonyms, so it was just a matter of making two lists and matching them against each other. Each of those two lists contains the original word plus its consonym. One list uses the country as the original word, the other uses nationality as the original word. We match the lists using the consonym.

I elected to use WPF once again, mainly because it produces a nice UI and I am pretty fast in it. The choice of UI is fairly unimportant for solving this puzzle, since there is almost no interaction with the user, other than clicking the Solve button.

If you read through to the end, I’ll explain my big learning moment writing this code. Yes, I made a big mistake because I misunderstood something tricky about Linq. Hopefully you can save time by learning from my goof!

In case anyone is following me, I hope I don’t sound too over-confident in my analysis, possibly discouraging you. I always do the write-up as if I knew what I was doing from the very start, as if solving the puzzle is inevitable due to my great skill 😏. But that is not the case at all! I have a lot of struggles and plenty of dead ends. So I hope you don’t feel unworthy if I accidentally make it sound easier than it truly is. Because in reality, it only seems easy after I finally succeed.

Screenshot Showing My Results:

Screenshot showing my solution to the puzzle

I got 3 results, but from Will’s description, I think he expects two results. I re-read his description a few times and don’t see anything I misinterpreted, so let’s see what he says come Sunday. Maybe there was some confusion over Mauritania and Mauritius, two very similar names.

Techniques Used

Difficulty Level

  • Intermediate
  • Dogged beginners

Algorithm

We start with a file that looks like the following (you can download your own copy below):

As you can see above, this file has two columns, separated by a tab character. The country comes first, followed by the demonym. Given this file structure, we take the following steps to find a solution:

  1. Open the file for reading
  2. Read one line at a time
  3. Split the line on the tab character, effectively separating the two words
  4. Build two lists,
    • Using the two words from the line we just split
    • One list for nationalities
    • The other for demonyms
  5. Each list will contain a data type (a class in this case) which contains the original word and its consonym (refer to the image below)
  6. After we finish reading the file and building the list,
  7. Match the two lists using the consonym field
  8. Note that some countries will match against their own demonym, for example
    • Britain → brtn → Briton (consonants “brtn” for both)
    • Therefore, when we match the two lists, we need to avoid self-matching by requiring that the matched demonym not come from the original country

Illustration of Matching the Two Lists

Country list shown above on the left, nationality list on the right. Each entry is an instance of my class ConsonymWordPair , which consists of the consonants plus the original word. When we match entries on the left against those on the right, we find a match for “lbnn” in both lists. Now we know the two original words share a consonym, one word being a country and the other a nationality.

Here’s The Code!

//This is the main method; it runs when user clicks the 'solve' button
private void btnSolve_Click(object sender, RoutedEventArgs e) {
  txtResults.Clear();
  txtMessage.Text = "";

  //1) The subroutine (method) reads my file and builds the two lists:
  var (countryLst, nationalityLst) = BuildCountryNationalityLists();

  var solutionCount = 0;
  //2) Loop through the country list and match against the nationality list
  foreach (var c in countryLst) {
    //3) Get all the nationalities whose Consonym matches the country's
    var matches = nationalityLst.Where(n => n.Consonym == c.Consonym);
    foreach (var m in matches) {
      //4) 'Mate' is my term for the original country
      //I call it 'Mate' to make the class name more generic
      //If the country's consonym is the same as its nationalit's, skip it 
      if (m.Mate != c.Mate) {
        //5) Display the results!
        txtResults.Text += $"{c.Word} - {m.Word}  ({m.Mate})\n";
        solutionCount++;
      }
    }
  }

  txtMessage.Text = $"Analysis complete - {solutionCount} results";
}

Discussion – Main Method

🙆🏻I really like how short the main method is, it makes me feel good to write concise code that does something useful and, hopefully, something cool!

Numbered notes below correspond to the numbered comments above. If you already understand the code above, skip ahead to the next heading!

  1. The subroutine reads my file and builds the two lists
    • var (countryLst, nationalityLst) = BuildCountryNationalityLists();
    • That subroutine (‘BuildCountryNationalityLists‘) is listed below
    • Note that this method returns two variables,
      • countryLst
      • nationalityLst
    • Which is one of my favorite features of .NET!
    • Both lists contains ConsonymWordPair elements (a class defined below)
  2. Loop through the country list and match against the nationality list
    • foreach (var c in countryLst) {
    • The variable ‘c‘ is an instance of my class ‘ConsonymWordPair‘
    • And we will examine all 156 of them, one per loop pass
  3. Get all the nationalities whose Consonym matches the country’s
    • The Linq method Where does a search on the list nationalityLst
      • var matches = nationalityLst.Where(n => n.Consonym == c.Consonym);
      • n.Consonym refers to the nationality consonym
      • c.Consonym refers to the demonym consonym (say that 3 times fast!)
    • And returns all the matches.
    • Theoretically there could be more than one match, but not with this data
  4. ‘Mate’ is my term for the original country
    • if (m.Mate != c.Mate) {
    • The class is named ‘ConsonymWordPair‘, but I added an extra field ‘Mate' after naming it
    • So it isn’t really a pair any more 😑- whoops!
    • The if-statement, if (m.Mate != c.Mate) ensures that I don’t accidentally match, for example, Briton against Britain
  5. Display the results!
    • txtResults.Text += $"{c.Word} - {m.Word} ({m.Mate})\n";
    • That code appends a new solution to the textbox called ‘txtResults‘
    • The += operator causes the new string to be appended to the existing one
    • We build a string to append using the $"" nomenclature
    • This allows us to mix variables with text in a more natural way
    • Variables are recognized inside the {} brackets; everything else is plain text
    • Note that \n (look at the end of the line) is how we specify a newline

Method ‘BuildCountryNationalityLists’ 

private (List<ConsonymWordPair>, List<ConsonymWordPair>) BuildCountryNationalityLists() {
  //1) Build the two empty lists which we will populate and return: 
  var countryLst = new List<ConsonymWordPair>();
  var nationalityLst = new List<ConsonymWordPair>();
  
  //2) NATIONALITY_FILE is defined at the class-level; it is the file name
  using var sr = File.OpenText(NATIONALITY_FILE);
  //3) Read until end-of-file detected
  while (sr.Peek() != -1) {
    //4 Read the line, convert to lower case, split on tab character
    //The split operation means that 'twain' is an array
    var twain = sr.ReadLine().ToLower().Split('\t');
    if (twain != null && twain.Length == 2) {
      //5) twain[0] is the country name; build a pair with the 
      //word and its consonants
      var c1 = RemoveVowels(twain[0]);
      var cwp1 = new ConsonymWordPair(twain[0], c1, twain[0]);
      countryLst.Add(cwp1);

      //6) Now do the same for the nationality, which is in twain[1]:
      var c2 = RemoveVowels(twain[1]);
      var cwp2 = new ConsonymWordPair(twain[1], c2, twain[0]);
      nationalityLst.Add(cwp2);
    }
  }

  return (countryLst, nationalityLst);
}

Discussion – BuildCountryNationalityLists

The method reads the file and builds two lists. As above, the list numbers below correspond to numbered comments above. The string operators used are ToLower and Split. The three File IO operators are File.OpenText, StreamReader.Peek and StreamRead.ReadLine. By putting this code in a separate method, the main method is simplified and easier to read.

  1. Build the two empty lists which we will populate and return
    • Each list contains an instance of my class ‘ConsonymWordPair‘
  2. NATIONALITY_FILE is defined at the class-level; it is the file name
    • The variable sr is a StreamReader that can read a line at a time
    • The ‘using‘ keyword guarantees that the stream will be closed and disposed
  3. Read until end-of-file detected
    • The StreamReader has a Peek method that returns -1 when EOF is detected, that terminates my while-loop
  4. Read the line, convert to lower case, split on tab character. The split operation means that ‘twain’ is an array
    • I’m doing 3 things in this line:
      • var twain = sr.ReadLine().ToLower().Split('\t');
    • ReadLine should be obvious
    • ToLower converts to lower case, so that I won’t try comparing ‘Lbnn’ against ‘lbnn’, because those two strings are not equal!
    • Split does what it says → it finds the tab character (\t) and splits the line every time it finds it
    • The result is an array with two elements:
      • Element 0: the country name (everything to the left of the tab)
      • Element 1: And the nationality (everything to the right of the tab
  5. twain[0] is the country name; build a pair with the word and its consonants
    • The code below invokes my method RemoveVowels, passing twain[i] as the input
      • var c1 = RemoveVowels(twain[0]);
    • For example, if the line was ‘Albania Albanian’
      • Then twain[0] is ‘albania’ (note the lowercase ‘a’)
      • The output from invoking RemoveVowels is ‘lbn’
  6. Now do the same for the nationality, which is in twain[1]:
    • Following the example above, twain[1] will be ‘albanian’
    • The output from invoking RemoveVowels is ‘lbnn’

RemoveVowels Method

This method is really simple, so I won’t bore you with any unnecessary explanation. Here’s the code!

private string RemoveVowels(string input) {
  //StringBuilder is easy to use and a more memory-efficient way to build a string
  var result = new StringBuilder();
  //Declare and initialize the array of char
  var vowels = new[] { 'a', 'e', 'i', 'o', 'u' };
  //Examine each char in the input string
  foreach (var c in input)
    if (!vowels.Contains(c))
      result.Append(c);

  return result.ToString();
}

Class ‘ConsonymWordPair’

internal class ConsonymWordPair {
  //1) My three public properties, the most important part of the class
  public string Consonym { get; set; }
  public string Word { get; set; }
  public string Mate { get; set; }

  //2) Default constructor
  public ConsonymWordPair() {
    Consonym = Word = Mate = "";
  }

  //3) 3-parameter constructor
  public ConsonymWordPair(string newWord, string newConsonym, string newMate) : this() {
    Word = newWord;
    Consonym = newConsonym;
    Mate = newMate;
  }

  public override string ToString() {
    var result = $"{Consonym} - {Word}";
    return result;
  }
}

Discussion – ConsonymWordPair

  1. My three public properties, the most important part of the class
    • The remainder of the class is practically fluff
    • As mentioned before, “pair” is not quite accurate any more, but “tuple” is harder to understand
  2. Default constructor
    • Ensures that the public properties are initialized
  3. 3-parameter constructor
    • The constructor used by the caller. Note that it actually invokes the default constructor with the code “: this()“
    • A pattern I try to follow which ensures the code in the default constructor is only written once

One other thing, the ToString method is not invoked when I solve the puzzle – so why did I write it? The answer is that Visual Studio uses it to display the list contents during debug sessions. When I hover my mouse over the pertinent variable (a list), it displays the contents using my method. Note that I built the image above (showing how the two lists are matched against each other) using the Immediate Pane in a debug session. Again, Visual Studio utilized my ToString method to display the data in that pane for me. Kind of the opposite of “immediate pain” 😉.

Lessons Learned

🙎🏼I made one big booboo writing this code: I used .NET’s Except method instead of my current method RemoveVowels. It didn’t work and I was surprised 😒! Except doesn’t work the way I thought it does, and I’ve been using it for years. I sure hope I didn’t create any bugs in production because of this.

Here’s some sample bad code that illustrates how I attempted to use Except:

  var vowels = new[] { 'a', 'e', 'i', 'o', 'u' };
  var twain = new[] {"albania", "albanian"};
  var c1 = twain[0].Except(vowels).Aggregate("", (p,c) => p + c);
  Console.WriteLine(c1);
  var c2 = twain[1].Except(vowels).Aggregate("", (p,c) => p + c);
  Console.WriteLine(c2);

Can you guess what the output is for c2? I’ll keep you in suspense while I explain my code.

  • Note that twain[0] contains the string “albania”
  • When I invoke Except on it, passing vowels as the input parameter, I get an IEnumerable<char> as the output (something like a list) that looks like the following:
    1. ‘l’
    2. ‘b’
    3. ‘n’
  • In other words, I get everything except the vowels. Just what we all expected.
  • The code fragment .Aggregate("", (p,c) => p + c) serves to create a string from the IEnumerable; basically it iterates the char elements and uses the + operator to concatenate them into a string

OK, now that I’ve explained how c1 is created, what do you think the value of c2 is? The code is the same for both, except the input for creating c2 is “albanian”. To my surprise, c1 is “lbn”. I expected “lbnn”, i.e. two n’s. .NET dropped one of my n’s.

What happened? Except works on IEnumerables, and I gave it a string, which .NET treated like a list of char. So far, so good. Reading the documentation, it doesn’t say anything about applying the Distinct operator, so all I can guess is that, under set operations, no one cares about preserving duplicates. Yes, I studied Set Theory in college, and I don’t remember anything like that, but it does seem somewhat consistent with how we did things then. So I don’t really know why it behaves that way, but now you know what to expect!

Efficiency Analysis

OK, my data file is only 156 lines long, and the code runs in just 7 milliseconds (according to .NET when running in debug mode, see below).

Screenshot showing how I measured elapsed run time. This is an approximation influenced by how busy my computer was on other tasks.

So, I must admit that we don’t care much about whether this code runs in 7 milliseconds, or 500 milliseconds – you’ve already burned thousands of milliseconds reading this😊 But it’s always good to understand the performance of your code, for one reason, it’s interesting!

The algorithm I used runs in O(n2), meaning that it first runs through the main list (the countries) and, for each pass through that list, makes another pass through the other list (nationalities), searching for a match. In this type of analysis, we ignore the fact that the 2nd search/array pass completes in an average of just half the array size; instead we focus on limiting behavior.

For our calculations, each pass in the first list means a pass through the second, so if the first array has length n, then the algorithm runs in n × n passes, or n2.

How to Improve Performance

I could have improved my performance by storing nationalities in a dictionary instead of a list. Note that .NET dictionaries use hashing instead of what I used, namely, a linear search. Hashing is much more efficient because we can determine whether some nationality exists in our dictionary in just O(1) run time, basically one calculation instead of examining the whole list. O(1) is generally the fastest possible run time.

By using a dictionary, my algorithm could have had a run time of O(n). Maybe that would shave a whole millisecond off my run time! I leave it as an exercise for the reader to make those sweet changes. Realistically, the bottleneck for this app is the file I/O, which typically runs 1000 times slower than memory calculations, though that won’t be anywhere near as bad if you have an SSD drive.

Improve Even More?

If we want to get ridiculous and shave off another millisecond, we can parallelize the main loop. That would also require that we use some sort of locking to make sure that different threads don’t update the display simultaneously and interfere with each other; either use of the lock keyword or else Dispatcher.Invoke.

The main loop would look like the following:

Parallel.ForEach(countryLst, (c) => {
  var matches = nationalityLst.Where(n => n.Consonym == c.Consonym);
  foreach (var m in matches) {
    if (m.Mate != c.Mate) {
      Dispatcher.Invoke(() => txtResults.Text += $"{c.Word} - {m.Word}  ({m.Mate})\n");
      solutionCount++;
    }
  }
});

Since my PC has 20 cores, the code above would potentially run 20 times faster than my current main loop. Who knows what amazing things I could do with the time I saved using that technique! Seriously though, parallelization is a powerful tool for tackling certain difficult problems.

Download the Code

Here’s a copy of my code. If you choose to download it, remember to modify the file path (at the top of the code) to reference a location on your computer, not on mine. Here’s a copy of my nationalities file. You will need a free Dropbox account to download.

This entry was posted in Puzzle Solving! and tagged , , , , , .

Leave a comment