June 25, 2021
About 20 minutes
Algorithms Recursion Search Ternary Tree Trie Countdown Letters Round

Solving Countdown (Part 3)

Part three of a series looking at a popular game show from a computational perspective

This article is the third part in a series that looks at the British game show Countdown from an algorithmic perspective. On Countdown, contestants alternate between two kinds of rounds: the letters round, featuring word puzzles, and the numbers round, featuring mathematical puzzles. In the first two parts we looked at how to solve a numbers round problem; in this part we’ll start on the letters round.

Letters round rules

In a letters round, players are given 30 seconds to make the longest word they can from a random selection of 9 letters. As with the numbers round, contestants participate in the selection process: each letter is drawn from a stack of either consonants or vowels. At least three vowels and four consonants must be chosen. Once the 30 seconds have elapsed, players declare their words and the player with the longest valid word is awarded points equal to the word length. Nine letter words score double, and both players score in the event of a tie. An example:

A contestant requests, successively, two consonants, a vowel, two consonants, two vowels, and two consonants. This results in the following letters being drawn and placed on the board:

M H I R C O A C T

After the allotted 30 seconds passes, one player declares that they found an eight letter word, while the other player declares nine. The player with the shorter length, eight, states that their word is AROMATIC, but this is rejected because it reuses the letter A, which was only drawn once. The other player states that their word is CHROMATIC, a valid word. Since this is the longest valid word, and since it is nine letters long, the player is awarded 18 points.

Not all words are allowed: words must be listed in the Oxford Dictionary of English (not to be confused with the larger Oxford English Dictionary). Common inflections, comparatives, and superlatives are allowed even if not explicitly listed (for example, since start is listed, starting is allowed; and since frost is listed, frostiest is allowed). Not allowed are proper nouns, hyphenated words, and non-British spellings. We’re not going to worry about enforcing these rules, though: our code will take a list of valid words as input, and will accept anything on the list.

Words considered offensive are generally allowed, but may be bleeped or edited out of the broadcast.

Considering approaches

For the numbers round, we developed an algorithm from first principles. This time, we’re going to start by narrowing down some promising data structures. To do that, we need to think about which features will help us.

Our numbers round solution could solve a puzzle in several seconds by trying every combination of the numbers. We can’t tell how our letters solution will really perform until we get specific, but if we take the same approach as we did with the numbers round, we can guess that the solver might take much longer: comparing strings is slower than comparing numbers, and each time we generate a possible string we need to check it against our dictionary list of valid words. This tells us that an ideal data structure is one that helps us rule out nonsolutions quickly.

How big is the problem?

Given our new concern with efficiency, this is a good time to ask: how many possible (unvalidated) words can you make from nine random letters? The answer is about a million if no letters are repeated. We can calculate this as follows:

Consider the number of possible nine-letter words: For the first letter, we could pick any of the nine available letters. Then for the second letter, we could pick any of the eight remaining letters. For the third letter, there are seven letters to choose from, and so on, until we get to the ninth letter, for which only one choice remains:

$\mathsf{P}_9=9!=9⨯8⨯7⨯6⨯5⨯4⨯3⨯2⨯1=\mathrm{362 880}$

That’s the number of possible nine-letter words. We can repeat this process, with a small twist, for other word lengths and sum up the results to get the total for all word lengths. The twist is that each time we reduce the length by one, we also stop one step earlier. For eight-letter words, there are still nine choices for the first letter, eight for the second, and so on, until we reach two choices for the eighth letter. In other words, for length eight, stop at $⨯2$, for length seven, stop at $⨯3$, and so on. Thus, for a three letter word we have 9 choices for the first letter, 8 for the second, and 7 for the third, for a total of $9⨯8⨯7=504$. And at length one, we stop at the 9 since we can make a one letter word by choosing any one of the nine letters. Summing the number of possibilities for each length we get:

$${\displaystyle \sum _{i=1}^9\mathsf{P}_i=\sum _{i=1}^9\frac{9!}{(9-i)!}=\mathrm{986 409}\text{ possible words}}$$

I used some fancy symbols there. Don’t panic if you don’t know them. They’re not magic spells or anything. It’s just that some people spend a lot of time hanging out with those kinds of symbols when they’re growing up, and it makes those people really happy to see that the symbols are OK, that they’re out in the world doing stuff and having fun. You really can just multiply the numbers from 9 to 1, then 9 to 2, then 9 to 3, and on down to 9 to 8 and just 9, and then total up the results. You might even notice that you could save time by multiplying the numbers from 9 to 1 just once and keeping track of each intermediate result as you go. If so, ⭐ here’s a gold star!

What are our options?

Back to thinking through some data structures to look for good candidates. Let’s start with some common ones and work from there.

Hash table

Hash tables are often used to construct a set or map. We could create a set of the words from the word list, then for every possible word we could check whether or not it is in the table. This is similar to the approach we developed for the numbers round, but unfortunately it leads to just the sort of situation we said we wanted to avoid: lots and lots of string comparisons to check if words are valid (and lots of time spent generating invalid words). A hash table of strings doesn’t have the average constant time lookup usually associated with hash tables, because string hashing and comparison are both linear time operations. Moreover, a hash table is not a space efficient way to store large numbers of strings since they must hold a copy of each string plus space for the table. Let’s keep looking.

List

Here is a nice and simple approach: for each word on the word list, check if that string can be made from the puzzle letters. This may seem essentially the same as the hash table idea, but it isn’t. Critically, this approach inverts the search space. Instead of searching every possible letter combination to see if it makes a valid word, search every valid word to see if it has a letter combination! If there are far fewer valid words than possible words, this will be a significant improvement. And spoiler alert: the number of valid words is about an order of magnitude smaller!

Binary search tree

A “plain old” binary search tree would store a string reference in each node, probably consuming less memory than a hash table but with logarithmic search time. Keeping a copy of each string seems wasteful, though. Given the structure of the information, you can see that many words in a long list will have common subsequences. Indeed, a simple compression scheme for word lists is to replace a common prefix from the previous word with a digit indicating the number of common characters:

Hmm. Binary search trees are not screaming any advantages at us. But, there are other kinds of search trees that do take advantage of common prefixes!

Trie

A trie (both try and tree are accepted pronunciations) is a type of search tree that stores words by prefix: words that share a common prefix will branch out from the same node. The root represents the empty prefix, and each subsequent level adds one character to the string length. Each node has one labelled branch for each letter that can follow that node’s prefix. A sentinel letter marks the end of valid words (like C’s null-terminated strings). The trie can be checked for the presence of a word by starting at the root and attempting to “spell” the word letter by letter, at each step following the branch with the same label as the next letter. If this ends on a node with a branch for the sentinel letter, the word is found in the word list. If it does not, or if at any point there is no branch for the current letter, then the word is not present.

Tries are flexible with regard to search. Because each node represents a unique prefix and the children of that node encode every word starting with that prefix, returning all words that start with a certain prefix (as with an autocompleting input field) is trivial. With a little more effort, this can be generalized to wildcard and other near-neighbour searches.

Tries can also be converted to an even more compact deterministic acyclic finite state automaton, essentially a minimal state machine or super-efficient regular expression. But in either form, the fact that each node has a variable number of edges poses a problem. At each node, we must either waste time searching the edge list for the next letter in the target string, or waste space with tables that store null edges to non-existent child nodes.

Ternary search tree

Another prefix-based tree is the ternary search tree. Like tries, a ternary tree stores words letter-by-letter, allowing the sharing of nodes with a common prefix. But as the name suggests, nodes in a ternary tree each have 3 branches rather than a variable number. Each node is labelled with a possible next letter for the string, and the three branches represent the next node to visit if the target letter is less than, equal to, or greater than that letter. This strikes a better balance between search space and search time compared to the trie, while retaining the flexible search capabilities and compact representation. Overall, ternary trees seem like a good choice.

Navigating a ternary tree can take a little getting used to. The trick is that you only advance to the next letter of the word you are trying to match when following the equal to branch. For example, here are the steps needed to locate tea in the figure above:

1. Start at the T in tea, and at the root of the tree.
2. Since T > M, take the > branch to the T node.
3. Since T = T, take the = branch to the E node and move to the next letter, E, in tea.
4. Since E = E, take the = branch to the N node and move to the next letter, A, in tea.
5. Since A < N, take the < branch to the A node.
6. Since A = A, take the = branch. We have reached the end of the word, so now we are trying to match the end-of-word letter ◌. This sentinel is added to the end of each word inserted into the tree so that we can tell when a word is really in the tree and not just a prefix of some other word.
7. Finally, since ◌ = ◌, the word tea is in the tree.

As an exercise, try searching for cap in the figure above. You should end up in the bottom level of the tree, in the leftmost ◌ node.

Algorithms on ternary search trees

Ternary search trees are flexible enough to support a wide range of operations. We only actually need two for the letters round, but we’ll look at several to get a better feel for how they work.

To start with, we’ll need a simple structure we can use to represent a tree node:

{
    char: 0,   // char code of this node's character
    lt: null,  // the "less than" child node, or null
    eq: null,  // the "equal to" child node, or null
    gt: null   // the "greater than" child node, or null
}

JavaScript strings don’t end in a sentinel character, so to insert them we’d need to add special cases to our code. This isn’t a huge burden, but in the interest of keeping our code simple, let’s just add a boolean property eow = true (for end of word) to any node that ends a word. So, instead of searching for the special ◌ letter after matching the other characters, we can just check if the current node has the property set.

We don’t need our nodes to have any functionality themselves, so there isn’t a pressing need to make them into a class. The main advantage of doing so would be the ability to easily creating new ones without repeating code—but we’ll only create them in one place. (If we were using TypeScript, it would make sense to declare an interface for them, though, so they’d have a convenient type name.)

Instead of letting users of our code act on individual nodes, we will want to restrict them to working with the tree as a whole so we can hide some of the details of how it works. This lets us present a clean, simple API to those using the tree. It also lets us change how the tree works without requiring anyone else to change their code. This makes the an ideal candidate for a class. Let’s sketch it out, with a skeleton of some basic operations we might perform:

class TernarySearchTree {
    /** Creates a new, empty tree. */
    constructor() {
    }

    /** Adds the specified string to the tree. */
    add(word) {
    }

    /** Returns whether the tree contains the specified string. */
    has(word) {
        return false;
    }

    /** Removes a single string from the tree. */
    delete(word) {
    }

    /** Delete all strings in the tree. */
    clear() {
    }

    /** For each string in the tree, call a function with that string. */
    forEach(visitFn) {
    }    
}

As with the previous articles, we are using an object-based, though not object-oriented, approach to solving the problem. An object-based approach organizes code around objects that keep the details of their internal state hidden but present a public interface that allows you to interact with them through functions, called methods. Think of a RegExp or Date or even a lowly String in JavaScript. What does RegExp do with those patterns you give it in order to match a string? How does a Date object know what the current time is? How does String.toLocaleLowerCase know what dialect-specific rules to use? The answers to these questions are hidden from you as a user of these classes, not to keep them secret, but to keep you from having to try to keep every detail of how your program works in your head all at once and to leave JavaScript vendors free to change how they work to make them better.

One thing our tree will definitely need is a reference to the root node, the top node in the tree that eventually links to all of the other nodes. All of our methods will need to start there, then work their way down through the tree. We can add a property to our class to keep track of the root. Newer versions of JavaScript will let us mark that property as private by starting the name with #. This will truly keep our hidden implementation details hidden from users of the class, because private properties (and methods) can only be accessed from the class’s own code. Let’s add that to the top:

class TernarySearchTree {
    #root;
    
    constructor() {
    }

// ...

If the JavaScript engine you are using doesn’t support private properties and methods yet, the # will lead to a syntax error. In this case, change the hash # symbols to two underscores __. This doesn’t afford the language-level protection of #, but it does provide a visual cue for users of the class.

An empty tree

What should #node look like to start with? An empty tree has no letters in it yet, and since letters are stored in nodes, it follows that it won’t have any nodes, either. In that case there is no node for our #root to refer to, so we can set it to null instead of a node object. Since the job of the constructor is to set up a new object before it is first used, we can do that in the constructor. Although, isn’t that also the job of the clear() method? Instead of repeating ourselves, we can put the tree setup in clear() and call it from the constructor():

class TernarySearchTree {
    #root;
    
    constructor() {
        this.#clear();
    }

    clear() {
        this.#root = null;
    }

// ...

That’s easy, and now we can even create a tree if we’d like, even if so far it will always be empty:

let tree = new TernarySearchTree();

Membership

To keep our new class useless a little while longer, let’s implement has() next. It returns true if the tree contains a certain string, and otherwise false. A few sections back we saw an example of searching a tree for tea. Instead of jumping straight into JavaScript, let’s think about how this might work in general, with the help of some pseudocode.

To start, what information has to be on hand? We move through the tree, so we need to track which node we’re visiting. At the same time, we also move through the string we’re checking for letter-by-letter, so we’ll need a reference to the string and our position in it. Trees naturally lend themselves to recursive functions, so it makes sense that we’ll end up with a function that takes those values as input and recurses through the tree.

If the mention of recursion has you anxious, it might also help to review previous installments.

OK, here we go—take a deep breath, it looks long but it’s mostly comments:

def has(node, word, i):
    // check if we have reached the bottom of the tree:
    // this means either the root was null (empty tree)
    // or we followed a node.gt, node.eq, or node.lt branch
    // that does not actually have a child node
    if node = null return false

    // look up the character we are currently trying to match
    // in the target string
    let char = word[i]
    
    if char < node.char
        // search (follow) the "less than" branch
        return has(node.lt, word, i)
    end if
    
    if char > node.char
        // search the "greater than" branch
        return has(node.gt, word, i)
    end if
    
    if char = node.char
        // we have matched the current letter in the target string,
        // so move to the next letter
        i = i + 1
        
        // if that was the last letter, we have matched the whole
        // target string, but that doesn't mean it is in the tree
        // (it could be a prefix of a string that is in the tree)
        if i = word.length
            // the eow property tracks whether this node ends a word,
            // so it has the defintive answer
            return node.eow
        end if
        
        // if we didn't reach the end of the word, we keep searching
        // from the next letter by following the "equals" branch
        return has(node.eq, word, i)
    end if
end def

You would search for a string by calling the function with the tree root, the string, and 0 (to start at character 0 of the string): has(treeRootNode, "tea", 0). Take some time to understand it if you need to—all of the other methods will use variations on this pattern. If it isn’t clear, it will help to print a copy of the example tree above, or open it in a window beside the page, and trace through some examples with pencil and paper. The main takeaway is this:

At each node, compare the current character in our string to this node’s character, and follow the appropriate branch of the tree (less than, greater than, or equal to)—but only move to the next character in the target string when following the equal to branch.

Ready to translate to JavaScript? Notice that our class’s signature only takes the string to search for as an argument, while our function takes three. Since we are hiding the details of how our class works, we want to keep the original, simple signature we outlined before. We can work around this by creating a private method that takes our preferred arguments, and then delegate to it from the public method:

has(word) {
    return this.#has(this.#root, word, 0);
}

#has(node, word, i) {
    if (node == null) return false;

    let ch = word.charCodeAt(i);
    if (ch < node.char) {
    	return this.#has(node.lt, word, i);
    } else if (ch > node.char) {
        return this.#has(node.gt, word, i);
    } else {
        ++i;
        if (i === word.length) {
            return !!node.eow;
        }
        return this.#has(node.eq, word, i);
    }
}

The syntactic trickery !!node.eow ensures we return only true or false. If node.eow is true, one ! negates it to false and the second negates that back to true. But if node.eow was never defined, one ! will first coerce the undefined to false, then negate it to true, and the second negates that to false. Sometimes JavaScript is weird.

Inserting a word

Inserting a word is almost the same as searching for one, with two differences:

1. When we “run out of tree” by reaching a null node, we extend the tree instead of giving up.
2. When we reach the end of the target word, we set the eow property so that has() can find it.

Here is the private method we’ll delegate to:

#add(node, word, i) {
    let ch = word.charCodeAt(i);

    if (node == null) {
        node = {
            char: ch,
            lt: null,
            eq: null,
            gt: null
        };
    }

    if (ch < node.char) {
        node.lt = this.#add(node.lt, word, i);
    } else if (ch > node.char) {
        node.gt = this.#add(node.gt, word, i);
    } else {
        ++i;
        if (i == word.length) {
            node.eow = true;
        } else {
            node.eq = this.#add(node.eq, word, i);
        }
    }

    return node;
}

The first if statement does half the job of extending the tree with new nodes, by creating a new node when the incoming node is null. The other half of the job is updating the null reference in the parent node, which is why the function returns the (possibly new) new and each recursive call assigns that return value to the relevant branch (lt, eq, or gt) in the parent node. There is a final special case to handle, which is an empty tree. In this case, the class’s #root property starts out as null and needs to be updated. Thus, the public method looks like this:

add(word) {
    this.#root = this.#add(this.#root, word, 0);
}

Now that we have the constructor(), add(), and has() we can test how things are going so far:

// create a tree and add several words, then test whether
// each of a superset of those words is in the tree
const tree = new TernarySearchTree();
const words = ["crypt", "cat", "car", "caring", "apple"];
const missingWords = ["can", "app", "horse", "cart"];
words.forEach(word => tree.add(word));
[...words, ...missingWords].forEach(
    word => console.log(`has ${word}: ${tree.has(word)}`)
);

Which we expect to print:

has crypt: true
has cat: true
has car: true
has caring: true
has apple: true
has can: false
has app: false
has horse: false
has cart: false

The order in which words are inserted affects the depth of the tree and thus the average time taken to search for a word. The worst order to use when inserting a list of words is sorted order! To produce a nicely balanced tree, insert words in the order that you would use to binary search the list: insert the middle word first, creating two halves, then insert the middle of each of those halves, and so on.

Deleting a word

Deleting a word can be as simple as searching for it, then clearing the eow property on the node that matches the string. Try implementing this as an exercise. If you want a challenge, also clean up the tree by deleting any nodes that are no longer needed. Make sure that nodes are not deleted as long as other words still rely on them!

delete(word) {
    this.#delete(this.#root, word, 0);
}

#delete(node, word, i) {
    if (node == null) return;

    let ch = word.charCodeAt(i);

    if (ch < node.char) {
        return this.#delete(node.lt, word, i);
    } else if (ch > node.char) {
        return this.#delete(node.gt, word, i);
    } else {
        ++i;
        if (i === word.length) {
            node.eow = false;
        } else {
            this.#delete(node.eq, word, i);
        }
    }
}

Listing the words in the tree

The final method in our class (for now) is forEach, which calls a function for each word in our tree. To start the process, first think about how we would visit each node in the tree:

def forEach(node, visitFn)
    if node = null
        return
    end if
    
    visitFn(node)
    
    forEach(node.lt, visitFn)
    forEach(node.eq, visitFn)
    forEach(node.gt, visitFn)
end def

Notice that we traverse the tree by following branches in order (lt, eq, gt). This ensures that words will be visited in sorted order, which is often convenient.

So, what do we need to build this out to a function that looks at words instead of nodes? Well, the words themselves. When we reach a node with eow set, how do we recover the entire word? All we have available is the final character! Thinking about how the tree works, the word from the current node can be built by concatenating the characters from each equal to (eq) branch that was followed on the way to the node. Put another way, every string found in the subtree under a node’s equal to branch is prefixed by that node’s character, and this is true recursively all the way back up the tree.

In short, we need to be able to trace our path back up through the tree—specifically, the we need to know the character from each equal to node we passed through. An easy way to do that is to use an Array as a stack. Before following the equal to branch, we need to push the current character onto the stack, and after following it we need to pop it back off. To recover the string, we can treat the array as a queue and read them off in order. JavaScript’s spread syntax makes this last step easy:

forEach(wordFn) {
    this.#forEach(this.#root, [], wordFn);
}

#forEach(node, prefixStack, wordFn) {
    if (node == null) return;

    this.#forEach(node.lt, prefixStack, wordFn);
    prefixStack.push(node.char);
    if (node.eow) {
        wordFn(String.fromCharCode(...prefixStack));
    }
    this.#forEach(node.eq, prefixStack, wordFn);
    prefixStack.pop();
    this.#forEach(node.gt, prefixStack, wordFn);
}

There you go—a small but functionally complete ternary search tree class. We’re almost there. To solve letters round problems we’ll need one more key method, though: one that accepts a list of letters and returns a list of all strings composable from that list. We’ll do that next time, so this is your chance if you want to try tackling it yourself. Every technique you’ll need appears somewhere in this article!

Things to try

If you are looking for a slightly less daunting challenge, here are some more things you can try:

1. Add a toString() method that returns a single string that consists of a comma-separated list of all the words in the tree, in sorted order.
2. Try adding a size() method that counts and returns the number of words in the tree. This is fairly easy to do using forEach.
3. A more efficient size() method can be built by traversing the nodes yourself, without recreating the strings. Start from this pseudocode.
4. For an even more efficient version, you can add a #size property to the class and keep an accurate count as words are added or removed.
5. Add a method startsWith(prefix) that returns an array of every word that starts with a given prefix. Hint: This combines the idea of finding a string in the tree and iterating over every word in a (sub)tree.

Next time

We covered a lot of ground: we’ve considered several data structures for solving a letters round; had the key insight of reducing the search space to vastly reduce the amount of work we’ll need to do; and we’ve settled on using a ternary search tree, and implemented some core ternary tree operations. Next time we’ll wire everything together to create our letters round solver, and consider further refinements.

Continue to part four

Image credit: Article thumbnail is based on the Countdown letters round board.