Solving Puzzlemaster Presents with JavaScript: April 15th
I love solving puzzles, I love JavaScript, and I listen to Will Shortz’ Sunday Puzzle almost every week. Oftentimes, I find myself thinking of ways I could solve Will’s puzzles with code. This post, and the ones that follow, are a way for me to combine my passions and hopefully teach a bit of JavaScript and algorithms.
This is the first installment of solving Puzzlemaster Presents puzzles with JavaScript! I’ll try to do the puzzle every week using as much of a code mentality as possible, so stay tuned for more. I’ll try to touch on the benefits and drawbacks of design decisions, but please keep in mind that the code I write here won’t necessarily be optimized for speed. That being said, if you like the solutions, have an improvement, comment, or suggestion, please add a comment!
Today’s puzzle is a word jumble between countries and animals:
The letters of Switzerland can be rearranged to spell lizard and newts — lizard being the singular name of an animal and newts as a plural. Name another country with the same property. That is name another country whose letters can be rearranged to name two animals, one singular and one plural. It’s a major country. What country is it?
Right off the bat, we see that we’ll probably need a set of all the countries and a set of all the animals.
Countries aren’t too hard, and we can find a set of all of them from github user kalinchernev ‘countries’ gist:
afghanistan
albania
algeria
...Animals are a bit trickier. We can find a list of all the singular animals from github user atduskgreg’s ‘animals’ gist:
cat
cattle
dog
...However it is important to consider that we’ll need to use the plurals of these animals. Most will have plurals that simply have an s tacked to the end, but some (like Deer or Goose) have special plurals. A google search for ‘animal plurals’ turns up the Wikipedia page on ‘Terms of Venery,’ aka what groups of animals are called like a ‘pod’ of whales. This page happens to list over 200 types of animals with their venery names, but all we care about are the plural forms of those animals:
albatross
antalopes
ants
...Note that all the word data I use in this post (and probably posts to come) has been converted to all lowercase.
More importantly, the Wikipedia Venery page has some awesome names for animal groups like a murder of crows, a shrewdness of apes, and a shadow of jaguars. If you want to beef up on your vocab for your next pre-teen birthday party, spend some quality time on the venery pages.
Now lets plan out our solution given the data we have.
First, they give us the example of switzerland becoming lizard newts. How can we be sure they’re right? To prove it, we just need to prove that the country and the singular-plural animal pair are anagrams. One quick way to tell if two strings are anagrams is to sort the strings and compare the sorted values. It also helps to remove whitespace and other less-than-helpful characters. This combination is something I’ll call smoosh-sorting, and will be referred to as smooshing, sorting, or both from now on.
// A utility method to compare strings as anagrams
// Eg, 'i like cake' => 'aceeiikkl'
function smooshSort(str) {
return str
.replace(/\s+/g, '') // Remove whitespace
.split('') // Turn the string into a list of characters
.filter(char => char) // Filter out strange falsy characters
.sort() // Sort the characters alphabetically
.join(''); // Turn the sorted characters back into a string
}Once smooshed, we see that switzerland and lizard newts both become adeilnrstwz , and thus are anagrams of one another.
One way to find all the countries that can become singular-plural animal pairs (which will just be called animal pairs from now on) would be to create a set of all the smooshed countries and a list all the smooshed animal pairs, then check to see if any of the smooshed animal pairs are in the set of smooshed countries.
I’m choosing to use an ES6 Map for the smooshed countries because it will improve lookup time compared to using an array of the smooshed countries. We could have used a Set or a regular object, and but I like to use Maps because they are more expressive.
To create our Map of countries, all we need to do is load the countries from a .txt file, sort each country, then map each sorted country name to its original name:
function smooshedCountries() {
const allCountries = loadCountries();
return new Map(allCountries.map(country => [
smooshSort(country),
country
]));
}The animals are, again, more difficult. We’ll need to create every possible combination of singular and plural animals. This is just the beginning of the list, but the full list will have a length of the total number of animals squared:
'aardvark aardvarks'
'aardvark bears'
'aardvark cats'
...
'bear aardvarks'
'bear bears'
'bear cats'
...Keep in mind that the plural animals will need to include both the singular animals with an s tacked on as well as all the special animals we got from the Venery Wikipedia page. Also, a conspiracy of lemurs?!
Anyways, while we’re making pairs, we’ll want to create the smooshed version of our pairs so we can use them in the country Map later. Heres a function that creates this list of pairs with their sorted versions. It works by iterating over all the singular animals, creating every possible plural pair for that singular animal, smooshing each of those combinations, and storing the smooshed version and the original in a list that it returns in the end:
// Creates a list of paired singular and plural animals
// Also smooshes them for later
// Output: [['acdgost', 'cat dogs'], ['acgipst', 'cat pigs'], ...]function allAnimalPairs() { // Load in the list of singular animals
const allAnimals = loadAnimals(); // Load in the list of plural animals
const allAnimalPlurals = loadAnimalPlurals(); // Initialize an empty array for the pairs
const flattenedPairs = [] // For each animal
allAnimals.forEach(singularAnimal => { // For each animal (yes, this is an n squared loop)
allAnimals.forEach(pluralAnimal => { // Add an 's' plural of the animal
const combined = `${singularAnimal} ${pluralAnimal}s`
flattenedPairs.push([smooshSort(combined), combined]);
}); // For each plural animal
allAnimals.concat(allAnimalPlurals).forEach(pluralAnimal => {
// Combine the animals without an extra 's' on the plural
const combined = `${singularAnimal} ${pluralAnimal}`
flattenedPairs.push([smooshSort(combined), combined]);
});
}); // Return the entire list of smooshed and paired tuples
return flattenedPairs;
}
Finally, we can wrap everything together. We have our Map of smooshed countries and our list of smooshed animal pairs. All we need to do is filter out the animal pairs who’s smooshed versions aren’t in the smooshed country Map:
function findCountryAnimals() {
const countries = smooshedCountries(); // Filters animal pairs who's smooshed versions
// aren't keys in the countries Map
const countryAnimals = allAnimalPairs()
.filter(animalPair => countries.has(animalPair[0])); // Removes duplicate animal pairs for a single country
return new Map(countryAnimals.map(countryAnimal => [
countries.get(countryAnimal[0]),
countryAnimal[1]
]));
}
Running our script we get the result:
'pakistan' => 'takin asp',
'switzerland' => 'newt lizards',
'mexico' => 'ox mice'Nice! It looks like there are three solutions, one of which is the Switzerland/Newt/Lizards combination that Will Shortz gave us. It looks like the “major country” answer would be Mexico/Ox/Mice, but the Pakistan/Takin/Asp answer is totally valid too. In case you were wondering, as I was, about what a Takin and an Asp are, here are some pictures:
Using a pair of Date.now() calls, I found that the script 2.79 seconds. This would be pretty terrible performance on a production server, but isn’t too bad if you have a whole week to find the answer.
I hope you enjoyed this week of Solving Puzzlemaster Presents with JavaScript! Now go charge off into the world of coding like a Crash or Rhinos.
