Thinking Like a Programmer: Abstraction

Reading Time: 8 minutes

Programming Abstraction

Growing up, I was a glutton for word puzzles. Scrabble, Boggle, word finds, crossword puzzles, jumbles, even those “How many words can you make from the letters in HAMBURGER” on the back of fast food placemats. If it involved finding words, I was in. In second grade, my teacher would end every week with a word find of that week’s spelling words. The first person to finish got to pick from a selection of Brach’s Royals. After winning five or six weeks in a row, she took me aside and said she’d give me a Butter Rum (my favorite) on the way home every Friday if I agreed to stop being the first one done and give the other kids a chance to win. I agreed, and, instead of finishing first, I started finding my own words, words that weren’t on the spelling list.

Earlier this year, GeekDad Judd Schorr took my little diversion and amped it up to 11. Even a veteran word finder could use a little programmatic assistance.

Update: It was only after writing this program that I realized he asked for distinct words. With that caveat, the method I use below is definitely overkill, but I’ve left it for the sake of learning.

The first step in solving the puzzle is to have a word list to search against. Unfortunately, due to copyright reasons, you’re going to have to figure this one out on your own. However, Judd is a pretty forgiving Puzzlemaster, so if you were to use, say, a regular dictionary list of words and filter out the capitalized and punctuated words, I’m sure that would be acceptable.

Now that we have a text file, we’ll need to get it into an easy to use list. As you will soon realize, if you haven’t already, I love generic lists and LINQ. They’re quick, easy, and solve 99% of most data manipulation requirements. Since we have a whole file full of strings, let’s create a generic list of strings and fill it from the text file.


      List DictionaryWords = new List();
      using ( StreamReader reader = new StreamReader ("DictionaryWords.txt" ))
        {
        while (!reader.EndOfStream)
        {
          DictionaryWords.Add(reader.ReadLine().ToLower());
        }
      }

The puzzle is not case-sensitive, so it’s a good idea to convert everything to lower case right from the beginning. This saves you the headache of later trying to figure out why strings aren’t matching.

An Abstract Concept

One of the keys to thinking like a programmer is something called abstraction. To better illustrate the concept of abstraction, think of baking a cake. At the highest level, you could explain how to bake a cake as:

  1. Prepare batter.
  2. Place batter in pan.
  3. Bake.

Obviously, this is useless to anyone who is not a professional baker. However, we can break these steps down even more to provide clarity.

Prepare Batter

  1. Combine dry ingredients.
  2. Combine wet ingredients.
  3. Mix.

As we continue breaking down each steps into its individual components, eventually, we’ll get to the step:

Crack Egg

  1. Hold egg firmly and strike on flat surface.
  2. Pull shell apart at crack.
  3. Empty contents of shell into bowl.

Now, the beauty of abstraction is that we never again need to describe how to crack an egg. Tomorrow, when I make waffles, I don’t have to read instructions on how to crack an egg, I simply access that part of my brain that stored the instructions I followed during my cake baking.

In our case, we need to break down the parts of the puzzle into items that the computer can understand. “What is the letter in the bottom corner of the word grid?” is a meaningless question until the computer knows what “word,” “grid,” and “letter” mean. We define these terms using classes, then use the built-in methods of the language to manipulate the properties of the object.

For example, each letter in our grid can be expressed as follows:


    class GridLetter
    {
      public int X { get; set; }
      public int Y { get; set; }
      public char Letter { get; set; }
    }

Now with this class, the question “What is the letter in the bottom corner of the word grid?” has meaning, and could be written as:


    var lastLetter = grid.Where(g => g.X == grid.Max(gg => gg.X) && g.Y == grid.Max(gg => gg.Y)).FirstOrDefault().Letter;

The Grid

Now that we have a place to put our grid, let’s load it from a text file.


      List grid = new List();
      int curLine = 0;
      using ( StreamReader reader = new StreamReader ("grid.txt" ))
      {
        while (!reader.EndOfStream)
        {
          char[] line = reader.ReadLine().ToLower().ToCharArray();
          for ( var count = 0; count < line.Length; count++)
          {
            grid.Add( new GridLetter { Letter = line[count], X = count, Y = curLine });
          }
          curLine++;
        }
      }

Pinch Those Digital Pennies

Everything you do in a program has a cost, whether it’s a trip out to a database to collect information (expensive), or simply shifting some bits to add a couple of numbers (cheap). Unless you enjoy the Zen of staring at a blank screen, you’ll want to be Scrooge McDuck with your program.

There are at least two ways to approach this problem. Starting in the upper left corner, we search the dictionary for “OT,” followed by “OTE,” “OTEN,” etc. There are 29 words that can be made from the letters in the top row, going left to right, starting at the letter “O”. However, we can reduce that by recognizing that the largest word possible in the “famous word tile game” is only 15 letters. There are also zero words possible going right to left. When we look at the second letter, there are still 15 words to the right, but now one to the left. This continues until the 16th letter, where the number of possible left-to-right words is only 14 and the number of right-to-left words is now 15, until you reach the last letter, where there are zero words left-to-right, but still 15 right-to-left. Continue this for every row, then rotate the grid 90 degrees and do it all again to cover every column, and you come up with 39,600 words possible in just the horizontal and vertical. Searching a 175,000 word dictionary for each word, that’s 6.93 billion searches. And we haven’t even started on the diagonals yet.

However, there’s a better way. We can reverse our thinking and instead loop through all the words in the dictionary and see if each is on a line of our word grid. Now, we are doing 175,000 searches, but only doing them 356 times, for a total of 62 million searches.

I Walk the Line

Since we will be checking an entire line of the grid at a time, we’ll need to get those lines into a string that we can search. Horizontal and vertical are simple enough. We group all of the letters that have the same X value and order them forward and backwards, then group the ones with the same Y value and do the same.


      grid.GroupBy(g => g.X).ToList().ForEach(grp =>
      {
        lines.Add(grp.OrderBy(g => g.Y).ToList());
        lines.Add(grp.OrderByDescending(g => g.Y).ToList());
      });
      grid.GroupBy(g => g.Y).ToList().ForEach(grp =>
      {
        lines.Add(grp.OrderBy(g => g.X).ToList());
        lines.Add(grp.OrderByDescending(g => g.X).ToList());
      });

Diagonals are a bit trickier, but, in what may be one of the first times since junior high, we can use the point slope form to determine if a series of points are on the same line.


      grid.Where(g => g.Y == grid.Max(gg => gg.Y) || g.Y == 0).ToList().ForEach(g => {
        lines.Add(grid.Where(gg => g.X - gg.X == 1 * (g.Y - gg.Y)).OrderBy(gg => gg.Y).ToList());
        lines.Add(grid.Where(gg => g.X - gg.X == 1 * (g.Y - gg.Y)).OrderByDescending(gg => gg.Y).ToList());
        lines.Add(grid.Where(gg => g.X - gg.X == -1 * (g.Y - gg.Y)).OrderBy(gg => gg.Y).ToList());
        lines.Add(grid.Where(gg => g.X - gg.X == -1 * (g.Y - gg.Y)).OrderByDescending(gg => gg.Y).ToList());
      });

Now we can loop through all of our lines, excluding the duplicates and those with only one letter (the corners), and check for dictionary words within that line.


      foreach ( var line in lines.Distinct().Where(l => l.Count() > 1))
      {
        foreach ( var word in CheckLineForDictionaryWords(line, DictionaryWords))
        {
          words.Add(word);
        }
      }

At this point, the simplest method would be to return a list of words that are found in the line. Judd didn’t specify that we had to fill out the grid, so there’s no need to know where the word can be found. However, it’s not much more effort to save this information for future use, perhaps as a JSON object that we can use to create an HTML page and animate the locations of all the words. To do so, we’ll need a class that contains the pertinent information for our found word.


    class GridWord
    {
      public string Word { get; set; }
      public GridLetter Start { get ; set ; }
      public GridLetter End { get ; set ; }
    }

Now we can do our dictionary search and save the results to a List object to use however we wish. We will be using IndexOf to find one bit of text within another.


     private static List CheckLineForDictionaryWords( List line, List  d)
    {
      List results = new List();
      string lineString = new string(line.Select(gl => gl.Letter).ToArray());
      foreach ( var word in d)
      {
        if (lineString.IndexOf(word) != -1)
        {
          int i = 0;
          while ((i = lineString.IndexOf(word, i)) != -1)
          {
            GridLetter start = line[i];
            GridLetter end = line[i + word.Length - 1];
            GridWord w = new GridWord { Word = word, Start = start, End = end };
            results.Add(w);
            i++;
          }
        }
      }
      return results;
    }

And that’s it. We’ll write the total and the largest word to the console, and then write the results to a text file to be used later.

Bonus for those who stuck through to the end. Here’s a codepen of the results using HTML Canvas

The complete code:


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace GeekDad_RandomWordSearch
{
    class Program
    {
        static void Main()
        {
            List DictionaryWords = new List();
            using (StreamReader reader = new StreamReader("DictionaryWords.txt"))
            {
                while (!reader.EndOfStream)
                {
                    DictionaryWords.Add(reader.ReadLine().ToLower());
                }
            }

            List grid = new List();
            int curLine = 0;
            using (StreamReader reader = new StreamReader("grid.txt"))
            {
                while (!reader.EndOfStream)
                {
                    char[] line = reader.ReadLine().ToLower().ToCharArray();
                    for (var count = 0; count < line.Length; count++)
                    {
                        grid.Add(new GridLetter { Letter = line[count], X = count, Y = curLine });
                    }
                    curLine++;
                }
            }

            List<List> lines = new List<List>();

            grid.GroupBy(g => g.X).ToList().ForEach(grp =>
            {
                lines.Add(grp.OrderBy(g => g.Y).ToList());
                lines.Add(grp.OrderByDescending(g => g.Y).ToList());
            });
            grid.GroupBy(g => g.Y).ToList().ForEach(grp =>
            {
                lines.Add(grp.OrderBy(g => g.X).ToList());
                lines.Add(grp.OrderByDescending(g => g.X).ToList());
            });

            grid.Where(g => g.Y == grid.Max(gg => gg.Y) || g.Y == 0).ToList().ForEach(g =>
            {
                lines.Add(grid.Where(gg => g.X - gg.X == 1 * (g.Y - gg.Y)).OrderBy(gg => gg.Y).ToList());
                lines.Add(grid.Where(gg => g.X - gg.X == 1 * (g.Y - gg.Y)).OrderByDescending(gg => gg.Y).ToList());
                lines.Add(grid.Where(gg => g.X - gg.X == -1 * (g.Y - gg.Y)).OrderBy(gg => gg.Y).ToList());
                lines.Add(grid.Where(gg => g.X - gg.X == -1 * (g.Y - gg.Y)).OrderByDescending(gg => gg.Y).ToList());
            });


            List words = new List();
            foreach (var line in lines.Distinct().Where(l => l.Count() > 1))
            {
                foreach (var word in CheckLineForDictionaryWords(line, DictionaryWords))
                {
                    words.Add(word);
                }
            }

            Console.WriteLine("Word Count: {0}", words.Count());
            Console.WriteLine("Largest Word: {0}", String.Join(", ", words.Where(w => w.Word.Length == words.Max(mww => mww.Word.Length)).Select(w => w.Word).ToList()));
            using (StreamWriter sw = new StreamWriter("results.txt"))
            {
                foreach (var word in words.Distinct())
                {
                    sw.WriteLine(String.Format("{0},{1},{2},{3},{4}", word.Word, word.Start.X, word.Start.Y, word.End.X, word.End.Y));
                }
            }
        }
        private static List CheckLineForDictionaryWords(List line, List d)
        {
            List results = new List();
            string lineString = new string(line.Select(gl => gl.Letter).ToArray());
            foreach (var word in d)
            {
                if (lineString.IndexOf(word) != -1)
                {
                    int i = 0;
                    while ((i = lineString.IndexOf(word, i)) != -1)
                    {
                        GridLetter start = line[i];
                        GridLetter end = line[i + word.Length - 1];
                        GridWord w = new GridWord { Word = word, Start = start, End = end };
                        results.Add(w);
                        i++;
                    }
                }
            }
            return results;
        }

        class GridWord
        {
            public string Word { get; set; }
            public GridLetter Start { get; set; }
            public GridLetter End { get; set; }
        }
        class GridLetter
        {
            public int X { get; set; }
            public int Y { get; set; }
            public char Letter { get; set; }
        }
    }
}

Get the Official GeekDad Books!