Solving Countdown (Part 4)

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

Contents

Welcome to the fourth part in a series looking at British game show Countdown from an algorithmic perspective. The first two parts developed an algorithm to solve the numbers round. The third part started on the letters round by describing the rules, choosing a data structure—the ternary search tree—and developing some code for a few basic operations. In this part we’ll finally use our understanding of ternary search trees to solve letters round puzzles. But first…

The boring stuff

When I taught computer science at university, assignments were commonly split into three parts:

Read some data from a file (that uses a format described by the assignment).
Do something with that data.
Print a result.

There were a couple of reasons for this. The first reason is straightforward enough. This pattern is the essence of what computers are: programmable machines that take an input, transform it, and produce an output. The second reason is, perhaps, slightly devious: it allows the grader to quickly diagnose a student’s work by throwing data files with every possible pitfall and corner case at it to see where it breaks.

Now students, particularly first-year students, would not be excited about step 1. It’s boring. And obvious. But step 2. Step 2! That’s exciting stuff! That’s what we’re actually discussing in class. That’s the important part. Oh they’d jump right into step 2 all right, fervent and fearless. And all would be glory and wonder, until the due date rolled around. On that day the panicked throngs would choke the hall outside the TA’s office… because they couldn’t get step 1 to work.

The moral?

If you don’t have the data, you don’t have anything.

Let’s get the data

For our project, the data is a list of all of the words we want to allow as puzzle solutions. Getting high quality word lists that are suited to a particular application is itself a hard problem. For example, suppose you are making a spelling checker.¹ It might seem that such a list should be as long as possible. You don’t want to mistakenly mark words as misspelled. But you’ll soon find problems. When checking doit, what’s more likely: that it’s the correctly spelled but archaic term for a bit of money, or that someone missed a space? Things are easier for a puzzle word list: in that case, you probably should include every word you can! Anyway, rather than get too bogged down on this point, I’ve simply provided a word list.

The next problem is how to get the data to our program. Since we’re using JavaScript, the answer is that it depends on where the program will run. If the answer is in a browser then we can download it using fetch:

async function loadWordList() {
    try {
	    const response = await fetch("word-list.txt");
        if (!response.ok) throw new Error(res.statusText);
        const text = await response.text();
        return text.split("\n");
    } catch (ex) {
        throw new Error("Unable to download word list: " + ex);
    }
}

loadWordList.then(words => {
   // do stuff with the words
   words.forEach(word => console.log(word));
});

The loadWordList function will return a Promise that resolves to the words after downloading the list and converting it into an array.

If you aren’t comfortable with Promises and asynchronous functions yet, there’s a JavaScript version of the word list that you can load like any other <script>. Just don’t tell the step 1 skippers!

Let’s get the data faster!

The word list is large: nearly one megabyte, with over 120 000 words. To reduce download times, you can compress the list to about 48% of its original size using the simple scheme that was briefly mentioned last time. Then you could decompress it by replacing return text.split("\n"); with:

return text.split("\n").map((word, i, array) => {
    // 48 is the char code of the digit character "0";
    // declare a named const for it if you like
    const prefixLength = word.charCodeAt(0) - 48;
    if (prefixLength >= 1 && prefixLength <= 9) {
        word = array[i-1].substring(0, prefixLength) + word.substring(1);
    }
    return word;
});

You may be thinking, “but the Web server will compress the list for me!” It might do, but bespoke compression that leverages inherent properties of the input can be much more efficient than a generic compression scheme. In fact, you can much better results by applying both methods:
Word list Uncompressed (bytes) Gzip (bytes) Brotli (bytes)
Original 1 016 157 310 339 294 971
Prefix compressed 491 869 174 747 162 184

Word list	Uncompressed (bytes)	Gzip (bytes)	Brotli (bytes)
Original	1 016 157	310 339	294 971
Prefix compressed	491 869	174 747	162 184

We could explore more ways to knock back the file size, but again we risk getting off topic. And anyway, this is supposed to be the boring bit!

Getting the data into the tree

You may remember that adding words to a ternary tree in sorted order is a bad idea. Instead of getting a nice, fluffy, well-balanced tree, you end up with something slow and weedy. That’s a problem since our word list is in sorted order! But you may also remember that the solution is to insert the words as if you were doing a binary search: first inserting the middle word, then the middle of each of the two halves, and so on. Let’s go ahead and add that to our class. Recursion is our friend:

addAll(words, start = 0, end) {
    if (end === undefined) end = words.length - 1;
    if (end < start) return;

    const mid = Math.floor(start + (end - start) / 2);
    this.add(words[mid]);
    this.addAll(words, start, mid - 1);
    this.addAll(words, mid + 1, end);
}

Solving the letters round

OK, enough boring stuff. I hope you’re getting comfortable with ternary search trees, because it’s finally time to solve some letter puzzles! If you want to try coding this part yourself, this is your last, last, last chance.

Where should we start?

The basic pattern for a ternary tree method, which we’ve now seen several times, is:

follow the less than branch recursively
follow the equals branch recursively—if appropriate, and possibly with special handling
follow the greater than branch recursively

We know our method will have to look something like #has, since we are matching words. And we need to be able to recover the matching strings, so it will also have to look something like #forEach. The tricky bit is always the equals branch: when do you follow it, and what do you have to update before and after?

A new wrinkle is that we are going to have a list of letters we’re allowed to use: we can only take the equals branch when the node character is one of those letters! And, like before, after we follow the equals branch, we’ll need to make that letter available again before moving on to the greater than branch. How to track available letters? Since tree nodes store their character by char code, it makes sense to do the same here as well, keeping comparisons simple. As a start we could create a sparse array to count how many times each character appears in the puzzle. (If that ends up performing poorly, we can always change it later.) That looks like this:

let charMap = [];
for(let i=0; i<letters.length; ++i) {
    const char = letters.charCodeAt(i);
    charMap[char] = charMap[char] ? charMap[char] + 1 : 1;
}

The code charMap[char] ? charMap[char] + 1 : 1 handles the fact that the initial value of charMap[char] will be undefined rather than 0. Adding 1 to undefined would yield the the not-a-number value, NaN, so we check for undefined as a special case. The shorter but more cryptic charMap[char] = (charMap[char]|0) + 1 has the same effect.

Before we follow the equals branch, we can check if charMap[node.char] > 0. If it is the letter is available: subtract a copy, follow the branch, and add it back once we return. As with forEach we also need to update the treePath so we can reconstruct words as we find them. Putting this all together, then, we finally have:

arrangements(letters) {
    // charMap[charCode] is the number of times charCode appears in letters
    let charMap = [];
    for (let i = 0; i < letters.length; ++i) {
        const char = letters.charCodeAt(i);
        charMap[char] = charMap[char] ? charMap[char] + 1 : 1;
    }
    
    const words = [];
    this.#arrangements(this.#root, charMap, [], words);
    return words;
}

#arrangements(node, charMap, treePath, words) {
    if (node == null) return;

    this.#arrangements(node.lt, charMap, treePath, words);    
    if (charMap[node.char] > 0) {
        // use one copy of the current character
        --charMap[node.char];
        // add the character to the current prefix
        treePath.push(node.char);
        // add this solution if this node is a word
        if (node.eow) {
            words.push(String.fromCharCode(...treePath));
        }
        // follow the equals branch
        this.#arrangements(node.eq, charMap, treePath, words);
        // restore the previous prefix
        treePath.pop();
        // make the current character available again
        ++charMap[node.char];
    }
    this.#arrangements(node.gt, charMap, treePath, words);
}

Note: Because the nodes store 16-bit character codes and not full Unicode code points, this method won’t handle surrogate pairs correctly, but that doesn’t matter for words made from the letters a–z. If you want to fix this issue, store full code points in the nodes instead.

As the admiral said of the alien ship, now this is beginning to make sense!

The solver

An interactive solver is included below. It’s fast enough to respond in real time, so click in the big text field and type your puzzle letters. You can type as many letters as you like, though in keeping with the rules the word list only includes words up to 9 letters.

Bonus round

There is actually a third type of round on Countdown: the conundrum. This is played once per game, at the end. It consists of two or three words that together total nine letters, which must be rearranged into a single nine letter word. You can already solve these puzzles with the letters round solver. But as a final exercise, try building a tool to generate new conundrums.

Final thought

It took a while, but finally we’ve covered both types of Countdown puzzles. On the way we got a whirlwind tour of some powerful design concepts, practiced some intermediate JavaScript language features, applied some useful algorithms and data structures, and more. I hope you had a good time, solved some puzzles, and learned something new!

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

Surely spell checking is best left to the professionals at the Ministry of Magic! ↩︎

Have a comment or correction? Let me know! I don’t use an automated comment system on this site, but I do appreciate feedback and I update pages accordingly.