NPR Sunday Puzzle: January 29, 2023
This week’s challenge comes from listener Samuel Mace, of Smyrna, Del. Name a fruit in one word. Drop the last two letters. The remaining letters can be rearranged to name two other fruits. What are they?
Synopsis
This puzzle was a bit of a challenge, but I’ll bet it’s even harder if you can’t write code! Finding dual anagrams after removing letters, in your head, strikes me as very tough. But I must admit anagrams are very hard for me.
Even using code, I still chose the wrong approach a couple times. First I naively tried splitting the original fruit after dropping the last two letters. Oops! Didn’t work – try again! Then I wrote some buggy code that tried to subtract the first “sub-fruit” from the main fruit – probably buggy because I tried to make it too efficient. After fighting that for a while, I used an easier, but somewhat less efficient method that involved converting a string to a list, and chopping letters out of it.
As usual, every time I made a mistake, it felt like I couldn’t solve it, or maybe I didn’t have the right fruit list. But for each problem, I analyzed my code, identified my mistake, and eventually I solved it.
Techniques Used
General Approach
I elected to use C#/ WPF (Windows Presentation Foundation) for this because 1) you can’t load files using web solutions, 2) WPF looks great and runs fast, 3) there is no need to run this code on a mobile device, 4) Python is cool but I haven’t figured out how to make a nice UI with it. WPF is greatly underappreciated but works great! For all you .NET haters, my algorithm works in any language, and the code runs with any .NET framework, such as Xamarin or ASP.
Basic Algorithm
- Take advantage of this cool trick that tells you if two words are anagrams. Namely, if you take two words, sort their letters, and then observe that the result is the same string, then the two words are anagrams.
- Below is an example using the words ‘admirer’ and ‘married’, which we want to test for being anagrams of each other:
- With this trick in mind, load our fruit file into a dictionary
- Remember, each dictionary entry has a key and a value
- Our key will be the sorted letters
- and our value will be the original fruit name
- As illustrated in the example below, captured from a debug session in Visual Studio
- Remember, each dictionary entry has a key and a value
- Using the dictionary, I can test if an arbitrary string is the anagram of a fruit by checking whether the dictionary has such a key
- One way to do so is to use the
TryGetValuemethod that dictionaries support, such as the following:if (fruitDic.TryGetValue(sortedRemainder, out var match)) {- The code above asks my dictionary, named ‘
fruitDic‘, whether it has the key specified by variable ‘sortedRemainder‘ , and if so, placed the value into variablematch
- The code above asks my dictionary, named ‘
- Once I have built the dictionary, I can solve the puzzle by iterating it and manipulate each value
- By removing the last two letters from the value
- Then subtracting other fruit letters from said value
- Sorting the remaining letters
- And checking whether they are keys in the dictionary
- If so, we have a winner!
- As illustrated below:
Here’s the Code!
private async void btnSolve_Click(object sender, RoutedEventArgs e) {
txtResults.Clear();
await Task.Run(() => {
//1) Read the fruit file and build the dictionary from it.
//The Dictionary contains key/value pairs: the value is the fruit name;
//the key is the sorted letters of that name
//For example: fruitDic["aepr"] = "pear",
//i.e. the key is "aepr" and the value is "pear",
//because the sorted letters of pear are "aepr"
var fruitDic = LoadFruitFileIntoDictionary();
//The code can find the same answer twice, the first time it finds pear/pomegranate -> mango
//and the second time it finds mango/pomegranate -> pear
//So use this list to avoid displaying duplicates:
var prevSolutions = new List<string>();
var keyList = fruitDic.Keys.ToList();
//Now that we've built the dictionary, iterate its keys to solve the puzzle
//Each pass tests a different fruit
for (var i = 0; i < keyList.Count; i++) {
//This loop examines the remainder of dictionary, seeking a mate for
//the fruit retrieved with index 'i'
for (var j = i + 1; j < keyList.Count; j++) {
var key1 = keyList[i];
var key2 = keyList[j];
if (key1.Length < key2.Length) {
//2) Trim the last two letters off the second fruit:
var longer = fruitDic[key2][..^2];
//3) This method removes one each of the letters from longer that also exist in shorter:
var (remainder, allMmatched) = RemoveShorterStringFromLonger(key1, longer);
if (allMmatched) {
//4)Sort the letters that remain in 'longer' to see if they anagram to a fruit:
var sortedRemainder = remainder.OrderBy(c => c).Aggregate("", (p, c) => p + c);
//5)If the sorted letters match an existing key, we found a solution:
if (fruitDic.TryGetValue(sortedRemainder, out var match)) {
if (!prevSolutions.Contains(fruitDic[key2])) {
var msg = $"{fruitDic[key1]}, {match}, {fruitDic[key2]}\n";
Dispatcher.Invoke(() => txtResults.Text += msg);
prevSolutions.Add(fruitDic[key2]);
}
}
}
}
}
}
});
}
Notes Corresponding to Numbered Comments Above
//1) Read the fruit file and build the dictionary from it.
var fruitDic = LoadFruitFileIntoDictionary();
I built the dictionary in a dedicated method named 'LoadFruitFileIntoDictionary', discussed below.
//2) Trim the last two letters off the original fruit:
var longer = fruitDic[key2][..^2];
Suppose that key2 = “aaeegmnoprt”
Then the code snippet fruitDic[key2] fetches the value “pomegranate”,
We strip the last two letters off that value using the notation [..^2]
Which means “take all the letters, starting from beginning, ending two from the end”
//3) This method removes one each of the letters from longer that also exist in shorter:
var (remainder, allMmatched) = RemoveShorterStringFromLonger(key1, longer);
This executes a method ‘RemoveShorterStringFromLonger’, discussed below.
It returns two values:
- remainder
- allMatched
‘remainder‘ represents the letters left over after removing the first string
‘allMatched‘ is a boolean, set to true if every word in the first string is also found in the second string.
We only care if the first string is a proper subset of the second string
For example, if key1=”aepr” and longer = “pomegrana”, then the method
will return remainder = “omgna”
and allMatched = true
because those are the letters left over after subtracting ‘pear’, and every letter in ‘pear’ matched a letter in ‘pomegrana’.
//4) Sort the letters that remain in ‘longer’ to see if they anagram to a fruit:
var sortedRemainder = remainder.OrderBy(c => c).Aggregate(“”, (p, c) => p + c);
Here I use Linq to sort the letters and build another string.
The following snippet from above builds a sorted IEnumerable (basically a list of letters):
remainder.OrderBy(c => c)
Now, I convert that “listy thing” back to a string using the Aggregate method:
.Aggregate("", (p, c) => p + c)
“” is the seed, i.e. what we append to, in this case an empty string. We could use a hypothetical seed like “blah”, in which case the result would be “blahomgna”. But that is just a silly example to show you what the seed does.
(p,c) => p + c
This snippet, from above, is an anonymous function that operates on every char in the list and provides two input parameters:
p – the Previous value, i.e. what we have built to-date
c – the Current letter (char)
In other words, take every letter in the sorted IEnumerable; for each letter we add the current to the the string we have accumulated from processing previous letters
//5) If the sorted letters match an existing key, we found a solution:if (fruitDic.TryGetValue(sortedRemainder, out var match)) {
Suppose my variable ‘sortedRemainder’ contains “omgna”, and the dictionary ‘fruitDic’ has such a key (it does!). Then TryGetValue returns true and assigns “mango” to the variable match. Since it returned true, the lines of code below are executed. It is true because “mango” is the value associated with key “agmno”.
Method ‘LoadFruitFileIntoDictionary’
OK, above I promised to discuss this method, so here is the code. It is very short (my explanation is longer than the code!):
private Dictionary<string, string> LoadFruitFileIntoDictionary() {
var fruitDic = new Dictionary<string, string>();
using var sr = File.OpenText(fName);
//Read until the end of file:
while (sr.Peek() != -1) {
var fruit = (sr.ReadLine() ?? "").ToLower();
//Skip fruits that contain hyphens or spaces:
if (!fruit.Contains(' ') && !fruit.Contains('-')) {
var sortedLtrs = fruit.OrderBy(c => c)
.Aggregate("", (p, c) => p + c);
if (!fruitDic.ContainsKey(sortedLtrs))
fruitDic.Add(sortedLtrs, fruit);
}
}
return fruitDic;
}
Notes for Method ‘LoadFruitFileIntoDictionary’
using var sr = File.OpenText(fName);
- ‘sr’ is a StreamReader that allows me to read lines from the file using its
ReadLinemethod fNameis a class-level variable containing the path/file name of my fruit file- Because I utilized the syntax “
using“, my file stream is closed automatically when sr goes out of scope
while (sr.Peek() != -1) {
- When the
Peekmethod returns -1, it means we have hit the end of the file
var sortedLtrs = fruit.OrderBy(c => c).Aggregate("", (p, c) => p + c);
- As before, sort the letters in the fruit using the
OrderBymethod - The result is something like a list of letters (
char), actually anIEnumerable<char> - We use the
Aggregatemethod to convert that “listy thing” into a string - The
Aggregatemethod has two parameters:- The seed string
- The anonymous method that is executed on every entry in the ‘list’ provided as input
- Namely,
(p, c) => p + c) - p is the value we have accumulated after processing previous entries
- c is the current value
- + means add the current to the previous to build the value we accumulate
- Namely,
if (!fruitDic.ContainsKey(sortedLtrs)) fruitDic.Add(sortedLtrs, fruit);
If the dictionary doesn’t already contain an entry with key sortedLtrs,
- Then add a new entry
- Using
sortedLtrsfor the key - and
fruitfor the value
- Using
Method RemoveShorterStringFromLonger
private (string, bool) RemoveShorterStringFromLonger(string shorter, string longer) {
var longerLst = longer.ToList();
var matchCount = 0;
foreach(var c in shorter) {
var ndx = longerLst.IndexOf(c);
if (ndx >= 0) {
longerLst.RemoveAt(ndx);
matchCount++;
} else
break;
}
//The result has two parts:
//1) the remainder after removing shorter from longer,
//2) a boolean reflecting whether every char in shorter also belonged to longer:
return (longerLst.Aggregate("", (p, c) => p + c),
matchCount == shorter.Length);
}
Explanation:
var longerLst = longer.ToList();
- Convert the string
longerto a list, because it is slightly more efficient and easier to work with - I could revise it to use string manipulation, but it works as-is and I don’t feel like it – I fought enough bugs already!
var ndx = longerLst.IndexOf(c);
if (ndx >= 0) {
longerLst.RemoveAt(ndx);
- Search for the current character
c - If found,
ndxwill be 0 or higher - Remove the letter
cfrom the list using the index where we found it
For example, suppose this method is invoked using the parameters
shorter = “pear”
longer = “pomegrana”
Then the method would return two parameters, the first being a string with value “omgna”, and the second being a boolean with value = true.
The first return parameter is constructed with this code snippet: longerLst.Aggregate("", (p, c) => p + c)
The second return parameter is constructed with this code snippet: matchCount == shorter.Length
The second return parameter might be a bit confusing to some; what it does is apply the == operator to the two parameters. If they are the same length, then it evaluates as true, otherwise it evaluates as false.
OK, How’d You Get the Fruit File?
I ‘screen-scraped’ the list of fruits from a Wikipedia page, List of culinary fruits. For the sake of brevity, I won’t discuss that here, but if you download my code, you can see how I did it. When using HtmlAgilityPack, it is very easy, assuming you understand XPath. Download link below.
Note: if you download, build and run my code, you will need to modify the file name, because my code has a hard-coded path to a location on my PC.
Hey, You Said You Used HashSets, But I didn’t See Any!
I didn’t discuss it above, but my code uses a HashSet to avoid creating duplicates to my fruit file. You will see it if you download the code and examine the code that runs when you click the button ‘Get More Fruits’. Download link below. HashSets are a highly-efficient and convenient way to keep track of things, and to speedily check whether some value already exists in the HashSet.
Summary
- Approximately 2 hours to code the fruit file download from Wikipedia (first download runs in 4,159 milliseconds, the second requires 488 ms)
- Resulting in 906 fruit names
- Approximately 3 hours to write the code that solves the puzzle using that file
- 260 lines of code, of which about half is comments
- The UI is specified using 73 lines of XAML, edited both “visually” and “by code”
- Approximately 38 milliseconds to run the code (note that my PC is pretty fast)
- Approximately 5 hours to write this up
Get the Code!
You can download my code from this link. Note: you will need to get a DropBox account (free) to do so.
Randy's Rants, Ravings and Reflections 