Decoding the Puzzle of the Week: Simple Anagram Solver

Reading Time: 6 minutes

Every week, resident Puzzlemaster Judd Schorr presents the GeekDad Puzzle of the Week, an interesting brain teaser, usually involving one or both of his kids. The winner receives a $50 ThinkGeek gift certificate, and while it’s not impossible to win using just your brain, paper, and pencil, unless you have an encyclopedic knowledge of pop culture and can convert Base-4 to Base-7 in your head, you are most likely going to run into problems. Today, I’m going to show you how you can write a program to solve one of the recurring themes of many of Judd’s puzzles: anagrams.

There are two approaches you can take when using programming to solve a puzzle. There’s the elegant approach, where you use a complicated mathematical function that includes obscure characters like “?” and “?” and “3,” and then there’s the brute force method, which we will be using to solve last week’s puzzle. If, as a child, you filled your Red Ryder by opening the end, cupping your hand under the barrel, and dumping 450 BBs onto the garage floor, you’re already familiar with this approach to problem solving.

Photo by tvol / CC BY
Baby’s First Brute Force
Photo by Andy / CC BY

Step One: Set Up Your Environment

For this tutorial, I will be using C#. I recommend installing Microsoft’s free Visual Studio Express. However, if you don’t want the overhead on your PC, or you’re using a Mac, you can use an online interpreter such as CodingGround. In Visual Studio, create a new “Console Application” project.

New Visual Studio Project

Delete everything in Program.cs and replace it with the following. This will add the required assemblies for our project.

Author’s Note: In the examples below, new lines will be bold.


using System;
using System.Collections.Generic;
using System.Linq;
namespace GeekDad_DaycareWasMad
{
   class Program
   {
      static void Main()
      {
      }
   }
}

Step Two: Su-Su-Pseudocode

Before we write the first line of code, we have to figure out how we’re going to solve the puzzle. Modern programming languages have come a long way from:


10 PRINT "Hello"
20 GOTO 10

Even so, we’re not yet to the point of creating transparent aluminum by talking into a mouse and are therefore forced to use language that is less than intuitive. Some programming languages, such as Python, have been written precisely with this consideration in mind, but for beginning programmers even this can be daunting. Therefore, we will be writing our code in two stages. First, in plain English, describing the steps our program will take. Then, only after we fully understand what our program needs to do, will we write the code.

In C#, we use “//” at the beginning of a line to denote a comment. Comments are lines in our program that will be ignored when run. They are there just for us.


//get a list of nominees
//get a list of clues
//loop through every nominee and clue
//check each nominee against each clue until there is a match
//write the results of the match
//if there are no matches, let me know

Step Three: I’d Like to Solve the Puzzle, Pat

The first step is to get all of the data into the program. This puzzle is fairly simple because we will be testing our clues against a small set of only 24 words, so we don’t have to worry about any optimization. In contrast, one of the word lists I regularly use for these types of problems has 349,900 words.


//get a list of nominees
List< string> nominees = new List< string> { "Whiplash" , "American Sniper", "Birdman", "The Grand Budapest Hotel" , "The Imitation Game" , "Selma" , "The Theory of Everything" , "Boyhood" , "Felicity Jones" , "Marion Cotillard" , "Reese Witherspoon" , "Julianne Moore" , "Rosamund Pike" , "Michael Keaton" , "Eddie Redmayne", "Benedict Cumberbatch", "Bradley Cooper" , "Steve Carell" , "Emma Stone" , "Patricia Arquette" , "Meryl Streep" , "Laura Dern" , "Keira Knightley" , "Mark Ruffalo", "Edward Norton","J.K. Simmons" , "Robert Duvall" , "Ethan Hawke" , "The Tale of Princess Kaguya", "How to Train Your Dragon 2", "The Boxtrolls" , "Big Hero 6", "Song of the Sea" };
//get a list of clues
List< string> clues = new List< string> { "A DEPENDABLE GHOST TRUTH" , "A DROWN RODENT", "A TEENS MOM", "ARMADILLO CITRON" , "AW SHH LIP" , "BOXIER SIGH" , "DRY ROE PLACEBO" , "EMIT GOAT THIAMINE" , "EXTOLL BROTHS" , "HA THANK EWE" , "HEY RATLIKE KING", "HOGS OF SENATE", "MALES" , "OOH BODY" , "READ ULNAR" , "RICH CUB TABBED CEMENT", "SHEENIER TOWROPES", "SPOKEN RADIUM" , "SVELTER LACE" , "VALOR BLURTED" };
//loop through every nominee and clue
//check each nominee against each clue until there is a match
//write the results of the match
//if there are no matches, let me know

We now have two generic lists called nominees and clues. The next step is to loop through each item in the list, looking for a match against each item in the other list.

Author’s Note Part Deux: Before I am crucified by the entire programming community… yes, this is an incredibly inefficient method. It is also the simplest and should take less than a second to run on any decent computer. Rule #18 in the book The Programmer’s Guide I Just Made Up says, “Don’t spend more time trying to increase efficiency than the increase will save.” Also, this method is very easy for non-programmers to understand.


//loop through every nominee and clue
foreach (var clue in clues)
{
   foreach (var nominee in nominees)
   {

   }
}

This is called a “nested loop.” The program will loop through the entire set of nominees and, for each nominee, will loop through the entire set of clues looking for a match. Next, we write our comparer. Determining if one phrase is an anagram of another requires four steps.

  1. Remove all spaces
  2. Convert all letters to lower case (to the computer, “A” does not equal “a”)
  3. Put all the letters in alphabetical order
  4. Compare the two newly created sets of letters

//loop through every nominee and clue
foreach (var clue in clues)
{
   foreach (var nominee in nominees)
   {
      //check each nominee against each clue until there is a match
      var nomineeLetters = new string(nominee.Replace( " " , "" ).ToLower().ToCharArray().OrderBy(x => x).ToArray());
      var clueLetters = new string(clue.Replace( " " , "" ).ToLower().ToCharArray().OrderBy(x => x).ToArray());
      if (nomineeLetters == clueLetters)
      {
	     //write the results of the match
      }
      //if there are no matches, let me know
   }
}

Next, we display the results when the two strings are equal.


if (nomineeLetters == clueLetters)
{
  //write the results of the match
  Console.WriteLine( "{0} is an anagram of {1}" , clue, nominee);
  break;
}

We add “break” here because there is no point in continuing to check for matches with that nominee. This will break out of the second loop and jump to the next clue.

One more thing we should add is a notification that something went wrong and there were no matches to our clue. Also, we’ll add an input prompt to the end of our program so, when we run it in debug, it will stop at the end, and we can see the results.

Here is the completed code, with the comments that were updated as I went along:


using System;
using System.Collections.Generic;
using System.Linq;

namespace GeekDad_DaycareWasMad
{
   class Program
   {
      static void Main()
      {
         //get a list of nominees
         List nominees = new List { "Whiplash", "American Sniper", "Birdman", "The Grand Budapest Hotel", "The Imitation Game", "Selma", "The Theory of Everything", "Boyhood", "Felicity Jones", "Marion Cotillard", "Reese Witherspoon", "Julianne Moore", "Rosamund Pike", "Michael Keaton", "Eddie Redmayne", "Benedict Cumberbatch", "Bradley Cooper", "Steve Carell", "Emma Stone", "Patricia Arquette", "Meryl Streep", "Laura Dern", "Keira Knightley", "Mark Ruffalo", "Edward Norton", "J.K. Simmons", "Robert Duvall", "Ethan Hawke", "The Tale of Princess Kaguya", "How to Train Your Dragon 2", "The Boxtrolls", "Big Hero 6", "Song of the Sea" };

         //get a list of clues
         List clues = new List { "A DEPENDABLE GHOST TRUTH", "A DROWN RODENT", "A TEENS MOM", "ARMADILLO CITRON", "AW SHH LIP", "BOXIER SIGH", "DRY ROE PLACEBO", "EMIT GOAT THIAMINE", "EXTOLL BROTHS", "HA THANK EWE", "HEY RATLIKE KING", "HOGS OF SENATE", "MALES", "OOH BODY", "READ ULNAR", "RICH CUB TABBED CEMENT", "SHEENIER TOWROPES", "SPOKEN RADIUM", "SVELTER LACE", "VALOR BLURTED" };

         //loop through every clue
         foreach (var clue in clues)
         {
            //no matches found yet
            bool matchFound = false;

            //check each nominee against each clue until there is a match
            foreach (var nominee in nominees)
            {
               var nomineeLetters = new string(nominee.Replace(" ", "").ToLower().ToCharArray().OrderBy(x => x).ToArray());
               var clueLetters = new string(clue.Replace(" ", "").ToLower().ToCharArray().OrderBy(x => x).ToArray());
               if (nomineeLetters == clueLetters)
               {
                  //write the results of the match
                  Console.WriteLine("{0} is an anagram of {1}", clue, nominee);

                  //we have a match
                  matchFound = true;
               }
            }

            //were there no matches found?
            if (!matchFound)
            {
               Console.WriteLine();
               Console.WriteLine("***Could not find a match in the nominee list for the clue {0}***", clue);
               Console.WriteLine();
            }
         }

         //wait until the user hits Enter
         Console.Write("That's all folks.");
         Console.ReadLine();
      }
   }
}

And that’s it. Hit F5 in Visual Studio, or “Compile” then “Execute” in CodingGround.


A DEPENDABLE GHOST TRUTH is an anagram of The Grand Budapest Hotel
A DROWN RODENT is an anagram of Edward Norton
A TEENS MOM is an anagram of Emma Stone
ARMADILLO CITRON is an anagram of Marion Cotillard
AW SHH LIP is an anagram of Whiplash

***Could not find a match in the nominee list for the clue BOXIER SIGH***

DRY ROE PLACEBO is an anagram of Bradley Cooper
EMIT GOAT THIAMINE is an anagram of The Imitation Game
EXTOLL BROTHS is an anagram of The Boxtrolls
HA THANK EWE is an anagram of Ethan Hawke
HEY RATLIKE KING is an anagram of Keira Knightley
HOGS OF SENATE is an anagram of Song of the Sea
MALES is an anagram of Selma
OOH BODY is an anagram of Boyhood
READ ULNAR is an anagram of Laura Dern
RICH CUB TABBED CEMENT is an anagram of Benedict Cumberbatch
SHEENIER TOWROPES is an anagram of Reese Witherspoon
SPOKEN RADIUM is an anagram of Rosamund Pike
SVELTER LACE is an anagram of Steve Carell
VALOR BLURTED is an anagram of Robert Duvall
That's all folks.

Wait, what’s this? Judd slipped one by us by renaming the movie “Big Hero 6” to “Big Hero Six.”

Tricksy Puzzlemaster.

Have a question? Find an error in my code? Leave me a comment below.

Get the Official GeekDad Books!