How to improve wordfeud solver algorithm?

Question

I created a simple wordfeud solver that checks what words can be created with the supplied letters.

public void GetResults(string characters)
{
    // place all the characters we have in a dictionary with key=letter, value=amount
    var charCount = SplitCharacters(characters);

    // get all the unique letters (the keys)
    char[] individualChars = charCount.Keys.ToArray();

    // create a regex for these letters, because only those letters are allowed in a word
    string regex = @"^[" + new string(individualChars) + "]+$";

    // get all the words that contain only the letters we have on our board
    IEnumerable<string> possibleWords = _words.Where(x => Regex.IsMatch(x, regex));

    // walk through the words that have only the letters on our board, and check if
    // there are sufficient letters on our board to create that word
    IEnumerable<string> results = possibleWords
        .Where(x => SplitCharacters(x).All(y => charCount[y.Key] >= y.Value) && x.Length > 1)
        .OrderByDescending(x => x.Length)
        .Take(25);

    // convert the words to ViewModel objects to display in the view
    foreach (string result in results)
    {
        Results.Add(new ResultViewModel { Word = result });
    }
}

private Dictionary<char, int> SplitCharacters(string characters)
{
    char[] chars = characters.ToLower().ToCharArray();

    var charCount = new Dictionary<char, int>();

    foreach (char c in chars)
    {
        if (!charCount.ContainsKey(c))
        {
            charCount[c] = 1;
        }
        else
        {
            charCount[c]++;
        }
    }

    return charCount;
}

It works, but I think this can be done more efficient. I worked this out on my own, but I feel like I'm creating too many new arrays/enumerables for all the steps in the algorithm. It runs quite fast on my PC (core i7 2600) but it's a little bit slow on my Surface tablet.

Can this be done more efficiently?

Answer 1

This is a rather interesting problem, first let's analyze a couple of algorithms and their respective algorithmic complexities.

We say that A is the set of characters given to us from the Wordfeud game: the set of characters from which we can form words. B is the lexigraphically sorted set of all valid words we can form, in practise, the words of a dictionary. The set of words in B that we can form from the characters in A is C.

Naive algorithms

The naive algorithm for this problem is to simply loop through all elements of B and check whether these words can be formed from the characters in B, with a regex like proposed here, or with a frequency map. If so, we put the word in C. For an average word length k and n words in B this runs in worst-case O(n k) time.

This is the fastest we can go without doing some kind of precomputation. In my tests, this algorithm runs in about 2s on the dictionary in /usr/share/dict/words in Ruby on 2 Ghz. This is the mean running time from different sets of A of 25 characters of which about 15 letters are distinct.

A simple iteration on this naive algorithm, is the observation that if a character is not in A, then we do not have to loop through all the words that start with this letter in B. E.g. if there's no letter c in A, we can skip to the words beginning with d when we encounter the first word which begins with c in B and so on. We can precompute a table that stores this information, i.e. the intervals at which the words start with a letter k. E.g. words with index 1..3482 in B all start with a. Thus if A does not contain a, we can just jump to the word with index the 3482 + 1.

The speed of this iteration depends on how many words in B start with each character in A. Say that v is the highest number of words that starts with any character in B, and i is the number of distinct characters from which we can form words, then this runs in worst-case O(v i) time. In my tests, this was about twice as fast as the previous algorithm.

Another iteration is threading it. For each segment we check (e.g. the words from a..b) we create a thread that checks this. With native threads, this halves the run time once again. This got me down to about 0.5s with the above setup running on JRuby.

Using a Trie

A trie is a tree data structure to store prefixes of strings. You start with a root node, and from there you have 25 edges, one for each character in the alphabet. If you follow one of these edges, e.g. the edge for the letter 'a' there will be X new edges. For each of those edges the prefix a + that letter exists in B. For instance one of the edges in X could be p and from there we could follow another edge e.

The vertex we landed at after following e is marked, because if we follow the edges back to the root node and save the characters on the way to the root in reverse order, we get a word in B: ape. The edge p existed because ap is a prefix of ape, and thus a prefix in B, as stated in the previous definition.

With this data structure in mind, we can design a new algorithm. Build a freqency map with default value 0 from A, i.e. a map where the key is the letter in A and the value of that key is the amount of times this letter occurs in A.

Traverse the tree with a depth-first search where you recursively traverse all options that you can do while all keys in the frequency map are > 0. Every time you hit a vertex which is marked, you traverse up to the root node to determine the word and add this word to C.

In reality you might want to pay the memory cost of storing the word at the vertex so you avoid traversing back to the root node every time you hit a marked vertex.

I won't get into algorithmic complexity analysis of this one, since it is rather complicated to analyze. However, in my tests, creating the trie from the dictionary takes less than 1s (e.g. for a web-service this penalty can just be paid when starting the app) and querying with a frequency table of A takes about 0.05s.

I do not know C#, however, I implemented this algorithm in Ruby.

Answer 2

Nice task for brains :). First of all you should prepare your available list of words for faster search: extract all letters, sort them and order by descending length (so that you don't need to sort results later. Make sure to cache it somewhere as that would be the most time-consuming operation.

I've written almost all, leaving you the method to compare 2 sorted character arrays :).

public class Solver : Controller
{
    //index of available words: char[] is the ordered list of letters in the word, string[] is the list of all words that consist from these letters.
    private readonly Tuple<char[], string[]>[] _wordIndex;

    public Solver(IEnumerable<string> words)
    {
        _wordIndex = words
            .GroupBy(GetLetters)
            .OrderByDescending(g => g.Key.Length)
            .Select(g => Tuple.Create(g.Key, g.ToArray()))
            .ToArray();
    }

    private static char[] GetLetters(string word)
    {
        return word.ToLowerInvariant().ToCharArray().OrderBy(c => c).ToArray();
    }

    /// <summary>Checks whether <paramref name="availableLetters"/> is a superset of <paramref name="toBeChecked"/>.</summary>
    /// <param name="availableLetters">Ordered list of letters available.</param>
    /// <param name="toBeChecked">Ordered list of letters present in a word</param>
    /// <returns><c>true</c> if all letters in <paramref name="toBeChecked"/> are present in <paramref name="availableLetters"/></returns>
    private bool IsSuperSet(char[] availableLetters, char[] toBeChecked)
    {
        throw new NotImplementedException();
    }

    public void GetResults(string characters)
    {
        var letters = GetLetters(characters);

        var results = _wordIndex
            .Where(indexEntry => IsSuperSet(letters, indexEntry.Item1))
            .SelectMany(indexEntry => indexEntry.Item2)
            .Take(25);

        // convert the words to ViewModel objects to display in the view
        foreach (string result in results)
        {
            Results.Add(new ResultViewModel { Word = result });
        }
    }
}

Answer 3

Here's a different approach. You'll need to test it to see if it's more efficient or not.

public static string Alphabetize(this string input, bool forRegex = false)
{
    var arr = input.ToCharArray();
    Array.Sort(arr);
    if (forRegex) return String.Join<char>("?",arr) + "?";
    else return new string(arr);
}

This would produce a regex like b?e?e?e?k?k?o?o?p?r? for bookkeeper. And then in your code:

string regex = @"^" + characters.Alphabetize(true) + "$";
IEnumerable<string> results = _words.Where(x => Regex.IsMatch(x.Alphabetize(), regex));
foreach (string result in results)
...

You could use .OrderBy() instead of the .Alphabetize() in the second case, but I seem to remember reading that it's faster to do as an array than with LINQ.

---

As an alternative, since you already have the letters and their counts, sort the string then make the regex b{0,1}e{0,3}k{0,2}o{0,2}p{0,1}r{0,1}.