Cheating at Countdown

This text is a written version of the video above, with future plans to incorporate graphics and figures for illustration.
As I'm working my way through the backlog of videos that were published before this website, I suggest reading the article alongside the video for a comprehensive experience.

I’ve been watching a lot of Countdown lately, especially the 8 out of 10 cats version, and while I do OK at the numbers game, you may have noticed I have this speech impediment called "being French", which makes me bad at the letters game, so I need to write some code that will make me the very best, like no one ever was.

For those who are under sixty, here’s a recap of the letters game of Countdown. It’s actually quite simple:
Nine letters are drawn in a pseudo-random manner. There’s a bunch of vowels, a bunch of consonants.
The contestants then have 30 seconds to find the longest word they can using those letters, and the contestant who comes up with the longest word wins. A 9 letter word thus guaranteeing an instant win.

Prep Work

From an algorithmic standpoint, there is no optimal way to come up with a solution other than brute-force, trying out every possible letter combination. And this takes a lot of time, even for a computer.

A better approach, albeit quite a naive one, would be to read through every word of the dictionary, and check whether this word is composed of the set of letters that are available to us.

So let’s start by doing just that, I downloaded a big list of every word in the English language. After removing words that wouldn’t work in Countdown such as hyphenated words, the final list has more than 4 hundred thousand words and weighs 4MB.

Then I needed a function that generates a pseudo-random series of 9 letters. In the real game there is a minimum number of vowels, a minimum number of consonants, and the probability of each letter to appear depends on the frequency of said letter in the English language.

Naive Approach

With this prep work out of the way, I can start working on a function that goes through the list of words, and for each word, checks whether it can be built from the provided set of random letters.
If it can, we keep track of it if it is the longest word so far, and then we move on to the next word.

private string WordSearchSelection(List<string> words, char[] originalSet)
{
    string result = null;

    foreach (var word in words)
    {
        char[] letters = originalSet.ToArray(); // Copy the set of letters
        bool valid = true;

        // Check if the word can be built from the provided letters
        foreach (var word in words)
        {
            int letterIdx = Array.IndexOf(letters, character);
            if (letterIdx >= 0)
            {
                letters[letterIdx] = '0';// "Remove" the letter from the available letters
            }
            else
            {
                // The word cannot be built using the provided letters. Abort
                valid = false;
                break;
            }
        }

        if (valid)
        {
            int letterCount = word.Length;
            if(letterCount == 9)
            {
                return word; // We have a winner no need to search further
            }
            if(result == null || letterCount > result.Length)
            {
                result = word;
            }
        }
    }
}

This works OK but as you can imagine it is quite slow. About 250ms.

We can add a few tricks to optimize this a bit:

1. First of, when we find a 9 letter word, we can stop right away as we know we won’t find a better word.
2. Second, let’s feed it a list of words that have been sorted beforehand. This way as soon as the function finds a word, we can break the loop as this has to be the longest word available.
3. Finally, we’ll filter the list to only keep words that are at least 6 letters long. No need to waste compute time on words that I could find myself without too much trouble.

All of this does yield better results, but barely a 5% improvement.

The Dentroyer

What we need is a killer solution, a perfect way to get the best word, instantly.
And what a surprise, this is actually a great opportunity to talk about what may be my favorite data structure.

The Trie.

But what does it do? Well a trie is a type of tree that excels at storing strings. Like, really.
In a Trie, each node represents a single character of a string.

For instance, let’s add the word CAT to an empty Trie.
We need to add the C node, which gives a A child, which in turn has a T child.

Now let’s add CATS. C is already there, so are A and T, so we just have to add a trailing S.

Now let’s add CATTLE. C, A, T are there, but here we need to branch out, and add another T node, before adding L and E.

When adding new words, we simply follow along the tree, adding new nodes when needed.

And then we just need some sort of flag to tell which nodes are actually words, this is obvious for nodes that have no children, but there might be words that end somewhere up in the chain, especially singular forms.

Coding the Trie

The recursive nature of the trie makes it very simple to implement.

Regarding the Node class, you need a value for the node, a flag for the end of a word, and a map of children nodes.

public class TrieNode<T>
{
    private T m_value = default;
    private bool m_isLeaf = false; // marks the end of a word
    private Dictionary<T, TrieNode<T>> m_children = new();

    public TrieNode(T value)
    {
        m_value = value;
    }

    public TrieNode<T> Get(T child)
    {
        if(m_children.TryGetValue(child, out TrieNode<T> node))
        {
            return node;
        }

        var newNode = new TrieNode<T>(child);
        m_children.Add(child, newNode);
        return newNode;
    }

    public bool HasChild(T child) => m_children.ContainsKey(child);

    public void SetLeaf() => m_isLeaf = true;
}

That’s it.

During the building phase, when you try to Get a node, if it exists it is returned, if not, it is created.

Finally we need a Trie class, that has a simple empty node that serves as root.

public class Trie<T>
{
    private TrieNode<T> m_root = new(default);

    public void Add(T[] word)
    {
        TrieNode<T> currentNode = m_root;
        for (int i = 0; i < word.Length; i++)
        {
            var element = word[i];
            currentNode = currentNode.Get(element);
        }
        currentNode.SetLeaf(); // Mark this as the end of a word
    }

    /// Get every word for a series of characters
    public List<List<T>> Lookup(T[] series)
    {
        var result = new List<List<T>>();

        LookupRecursive(new T[0], series, m_root, result);

        return result;
    }

    private void LookupRecursive(T[] current, T[] remaining, TrieNode<T> node, List<List<T>> result)
    {
        for (int i = 0; i < remaining.Length; i++)
        {
            if (node.IsLeaf)
            {
                result.Add(current.ToList());
            }

            T letter = remaining[i];
            if (node.HasChild(letter))
            {
                // Prepare arrays for the recursion
                T[] newRemaining = remaining.RemoveAt(i);
                T[] newCurrent = new T[current.Length + 1];
                current.CopyTo(newCurrent, 0);

                newCurrent[current.Length] = letter;
                // Recursive call
                LookupRecursive(newCurrent, newRemaining, node.Children[letter], result);
            }
        }
    }
}

Adding to the trie is simple, we just iterate over the string of characters, getting the next node in the trie each time, relying on the fact that it will be implicitly created if it doesn’t exist.

Then once we reach the final letter node, we mark it as a leaf.

Looking up the list of words that match a series of characters is slightly more complicated because there’s some recursion, but it’s really manageable:

We start with a current node, initially this is the root node, an array of the string of characters we have traversed so far (initially, it is empty), and an array of the characters from our countdown series.

For each of the remaining characters in our series, we check to see if it makes a valid path we can go down, and recursively call our lookup function.

If we reach a leaf node, we add the current string of characters to the list of results.

And here’s the beauty of the trie, right, you don’t make unnecessary computation, you will only go down a branch of the tree if you’re on track to find a valid word down the line.

There’s no pruning, no dead ends, it’s just… perfection.

Results

The only downside of the trie is, there is some initialization time. Building the big trie with 400'000 words takes about a second. Which is already more than the first search strategy, however once initialized, I can search for words multiple times without having to rebuild the trie.

Using a Ryzen 9 3950X.
Timings in miliseconds. Lower is better.

Looking up all the words in a series runs amazingly fast though, at an average of 2.2ms for a search.

That’s literally a hundred times faster than the first approach we tried.

And I know what you’re going to say:

"But Leonard, if the naive approach is only 250ms, and the timer runs for 30 whole seconds, you don’t need the faster approach and are therefore engaging in Premature Optimization."

To which I say, do you really think they’re going to let me bring my full size desktop computer on the set?

Cheating at Countdown

I need something stealthy that I can conceal on my person, like a raspberry pi for instance.
And these have a CPU that is quite not the same as the one in my desktop computer.

I converted the original C# code to Javascript to run it on my Raspberry Pi B+ that I have lying around, and the naive approach runs in 15s, which is already a lot closer to the 30s limit, and would certainly have failed if I had an older version of the pi, or a smaller device.

The Trie on the other hand, runs in 200ms on average, which is great.

It does take a full minute to build though, which is a long time, but I can have it run before entering the studio, and then it’s no problem.

The next question we have, is how am I going to input the letters into the program, if everything is supposed to be concealed.

I think the easiest way to do this is via morse code, as I basically only need 3 wires to make it work. What I'm imagining is having conductive metal rings, wired to the pi's GPIO pins. I can have a logic UP ring that touches either a dash ring or a dot ring, sending a logic UP signal to the program. When the rings aren’t touching, the signal is pulled down by a resistor.

Finally, the result is sent to a small LCD display.

Sending input in morse code takes a little practice, and also does take some time so I’m sure glad the word search takes under a second to complete.

Conclusion

Thanks to my device I am now the best Countdown player in the world. I am unstoppable.

As always, get the full source code for this project on the Patreon page.

There's also a bonus video for Patreon supporters if you want to see me write a program that solves the Numbers game of Countdown. Spoilers: it's bruteforce again.

I guess I’ll see you in the next video, until then, have a good one!