Whirly Words

There is this game on iPhone called “Whirly Word”: 6 scrambled letters, and you need to find English words using them. Pretty easy to play, very addictive. See example below:

  In order to kill the addiction, we can write a program to solve the game. First things first: we need is a list of English words. Don’t worry, there are two good news here: first, there are plenty of (incomplete) list of English words available out there, just Bing it. Second, even if you combine all those lists together, it won’t be a huge list – with few searches I found three quite large files, combined them together and came up with my dictionary of ~500,000 words (most of them questionable words, but in any case, a dictionary). Your laptop memory won’t be bothered by 1/2 million words, trust me, and a hash-table for quick lookup suits perfectly as the data structure to use.

  Alright, now the question becomes, if we permute or do the combinatorial of all the possible words with up to six letters, won’t that be too huge? Nah… Look, worst case this will turn out being 6x6x6x6x6x6, or 6^6, which is less that 2^18, and two to the power of eighteen, honestly, is nothing: http://www.bing.com/search?q=2%5E18&qs=n&form=QBLH&pq=2%5E18&sc=8-4&sp=-1&sk=&cvid=18efa02b59d94612a59ec27cd315dc3f. If you do a for loop from 1 to 2^18, you’ll get the results before you can finish reading this sentence.

  Cool, now that we’re convinced this code won’t run for hours/days/years, let’s think about the approach: read the words, push them to a hash-table. Now recursively, try all the different combinations of >=3 letter words. As you land into one combination, (1) check whether it is a valid word and if so (2) check that you have not seen it before. Just be careful to not try the same letter twice, and remember that letters in the input might come repeated, so don’t “mark as visited” based on the actual letter, but rather do it based on the position of the letter. Putting it all together, and you have a simple, compact C# code:

using System;

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

namespace Words

{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length != 2)
            {
                Console.WriteLine("Usage: words.exe <list of letters> <dictionary file>");
                return;
            }
 
            string listOfChars = args[0].ToLower();
            string fileName = args[1];
            Hashtable htWords = new Hashtable();
            Hashtable htUsedPositions = new Hashtable();
            Hashtable htWordsFound = new Hashtable();

            ReadWords(fileName,

                      htWords);

            Process(listOfChars,

                    0,
                    "",
                    htUsedPositions,
                    3,
                    htWords,
                    htWordsFound);
 
            if (htWordsFound.Count > 0)
            {
                Console.WriteLine("{0} words found:", htWordsFound.Count);
                foreach (string wordFound in htWordsFound.Keys)
                {
                    Console.WriteLine("  {0}", wordFound);
                }
            }
            else
            {
                Console.WriteLine("No solutions found!");
            }
        }

        static void Process(string listOfChars,

                            int currentPosition,
                            string currentWord,
                            Hashtable htUsedPositions,
                            int minLenToCheck,
                            Hashtable htWords,
                            Hashtable htWordsFound)
        {
            if (currentPosition > listOfChars.Length)
            {
                return;
            }
 
            if (currentWord.Length >= minLenToCheck)
            {
                if (htWords.ContainsKey(currentWord))
                {
                    if (!htWordsFound.ContainsKey(currentWord))
                    {
                        htWordsFound.Add(currentWord, true);
                    }
                }
            }
 
            for (int i = 0; i < listOfChars.Length; i++)
            {
                if (!htUsedPositions.ContainsKey(i))
                {
                    htUsedPositions.Add(i, true);

                    Process(listOfChars,

                            currentPosition + 1,
                            currentWord + listOfChars[i].ToString(),
                            htUsedPositions,
                            minLenToCheck,
                            htWords,
                            htWordsFound);
 
                    htUsedPositions.Remove(i);
                }
            }
        }
 
        static void ReadWords(string fileName,
                              Hashtable htWords)
        {
            if (!File.Exists(fileName))
            {
                Console.WriteLine("File {0} does not exist", fileName);
                return;
            }

            FileInfo fi = new FileInfo(fileName);

            StreamReader sr = fi.OpenText();

            while (!sr.EndOfStream)

            {
                string word = sr.ReadLine().ToLower();
                if (!htWords.ContainsKey(word))
                {
                    htWords.Add(word, true);
                }
            }

            if (sr != null)

            {
                sr.Close();
            }
        }
    }
}

For the example shown above, the program ran in a blink of an eye and extracted 49 words from the initial letters, out of which only a few (highlighted) are part of the official solution (remember the 1/2 million words dictionary? Yeah, some words are indeed questionable). Down below you can see the final screenshot of the actual game. Good programming problem, end of addiction.