May 25, 2020
About 17 minutes
Algorithms Recursion Divide and Conquer Countdown Numbers Round

Solving Countdown (Part 2)

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

This article is the second part in a series that discusses the British game show Countdown from an algorithmic point of view. The first part covered the rules of Countdown’s numbers round, developed an algorithm for solving it, and discussed an important optimization. In this part, we’ll implement the solver algorithm in JavaScript.

Note: You can find a working numbers round solver below if you want to skip ahead.

Representing a puzzle

To get started, we will define a class that can represent and generate number puzzles similar to those used on the show. We’ll take an object-based approach to the implementation, but the focus of this article won’t be object-oriented programming. If this is all new to you, then just go with the flow. You’ll probably follow along just fine.

To recap the rules, the numbers round asks players to calculate a three digit target number using large numbers, small numbers, and the four basic arithmetic operators. The large numbers are selected at random from 25, 50, 75, and 100, while the small numbers are chosen at random from the numbers 1–20 (with no individual number selected more than twice). Players choose how many large numbers to select, from 0–4, and additional numbers are selected from the available small numbers to make a total of 6 numbers from both sets. Numbers may not be reused and calculations that yield zero or a fraction are not allowed.

Our puzzle representation will generate puzzles that follow the standard rules by default, but also allow the construction of games with custom rules. The code is straightforward:

/**
 * The input for a numbers round: a target number and a list of values
 * that can be used to compute the target.
 */
class NumberPuzzle {
    /** The target number to reach. */
    target;
    /** @type {number[]} The numbers to combine to reach the target. */
    values;

    /**
     * Create a new numbers round. All arguments are optional; any that are
     * omitted will use the standard rules.
     * 
     * @param {number} target The target to solve for.
     * @param {number} numBigOnes The number of random "big numbers" to select.
     * @param {number} numSelections The total number of numbers to select (big and little).
     * @param {number[]} bigOnes Array of the big numbers to choose from.
     * @param {number[]} littleOnes Array of the little numbers to choose from.
     */
    constructor(target, numBigOnes, numSelections, bigOnes, littleOnes) {
        if (target == null) target = 100 + this.random(900);
        if (numBigOnes == null) numBigOnes = 2;
        if (numSelections == null) numSelections = 6;
        if (bigOnes == null) bigOnes = this.standardBigOnes();
        if (littleOnes == null) littleOnes = this.standardLittleOnes();

        bigOnes = [...bigOnes];
        littleOnes = [...littleOnes];

        this.shuffle(bigOnes);
        this.shuffle(littleOnes);

        this.values = [];
        for (let i = 0; i < numBigOnes; ++i) {
            this.values.push(bigOnes.pop());
        }
        const numLittleOnes = numSelections - numBigOnes;
        for (let i = 0; i < numLittleOnes; ++i) {
            this.values.push(littleOnes.pop());
        }

        this.target = target;
    }

    /** Return an array of the standard big numbers. */
    standardBigOnes() {
        return [100, 75, 50, 25];
    }

    /** Return an array of the standard little numbers. */
    standardLittleOnes() {
        const littles = [];
        for (let i = 1; i <= 10; ++i) {
            littles.push(i, i);
        }
        return littles;
    }

    /** Choose a random integer from 0 to n-1. */
    random(n) {
        return Math.floor(Math.random() * Math.floor(n));
    }

    /** Randomize the elements in an array. */
    shuffle(a) {
        for (let i = 0; i < a.length; ++i) {
            const j = this.random(a.length);
            const t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    toString() {
        return `Try to make ${this.target} using ${this.values.join(", ")}.`;
    }
}

If you run this in Node.js or a browser’s dev tools, you can test it out with something like:

console.log("" + new NumbersRoundPuzzle())

which will print something like the following to the console:

Try to make 284 using 50, 25, 9, 7, 4, 1.

Working values

We will also create a class to represent one of the “working values” used to compose a solution. That is, one of the numbers that can be combined to reach the target. This may seem odd: after all numbers are already a type, can’t we just use those? We could, but eventually we will want to know not just whether one of the values hits the target, but also how it gets there. That is, we’ll want to know the steps that led to the value so that we can describe a complete solution. The simplest way to capture that information is for the value itself to carry it around. Now, since we will be making millions of these values, it’s preferable if each one doesn’t have to carry its own separate complete copy those steps. That would waste a lot of space since many values will have steps in common. Fortunately, there is a nice, clean solution. Every value is either one of the input numbers we are given to solve the problem, or a combination of two other values and an operator. If the “derived” values keep a reference to the values and operator used to produce them, then we can trace those references all the way back to the original, non-derived values and recreate any value’s complete history whenever we need it. To do that, our values need to look something like this:

class Value {
  number;
  lhs = null;
  rhs = null;
  operator = null;

  constructor(n) {
      this.number = n;
  }
}

As you might guess, we’ll use the number property to store the actual numeric value. For one of the original inputs, all of the other properties will be null. For a derived value, the additional properties will refer to the left and right operands (lhs and rhs respectively) and the operator used to combine them. For example, suppose we wanted to represent the idea that the simple values 1 and 2 are combined to create 3 using addition. We could set that up using the following code:

let input1 = new Value(1);
let input2 = new Value(2);

let derived3 = new Value();
derived3.lhs = input1;
derived3.operator = "+";
derived3.rhs = input2;
derived3.number = input1.number + input2.number;

The lhs and rhs properties are references to the values used to create this value. So not only can we tell that they are used to create the 3, we can look at each of them in turn to see how they were created. In this example, that’s not very interesting—they are both simple input values. But now let’s extend the example by adding a new input value 4 which we multiply with the 3 we just derived.

let input4 = new Value(4);
let derived12 = new Value();
derived12.lhs = derived3;
derived12.operator = "×";
derived12.rhs = input4;
derived12.number = derived3.number * input4.number;

The end result is a tree of value objects that looks like this:

As we will see in a moment, you don’t actually need to store the number values, except when dealing with one of the original inputs. The numeric value can be calculated as needed by tracing through the tree and applying the indicated operations. (Interpreters for programming languages often use similar trees to execute programs.) However, these numbers are going to be used over and over while searching for a solution. Storing (caching) the precomputed numbers instead of recalculating them each time will speed up the solver a lot. This is an example of an optimization technique called memoization.

Describing a solution

Let’s suppose that this new value 12 is actually a solution to a numbers round puzzle (as in, “try to make 12 from the numbers 1, 2, and 4”). How could we describe the calculation steps represented by the solution? We can answer this by recursively traversing the tree, which will yield the steps in reverse order. To start with, we have 12. Where did the 12 come from? It was combined from 3 × 4. Where did the 4 come from? It was one of the starting values (we know this since it doesn’t lead to any other values, that is, it is just a number with no references to a lhs, rhs, or operator). Where did the 3 come from ? It was combined from 1 + 2. Where did the 2 come from? Again, it was a starting value, as was the 1. Thus we can describe the history of the calculation steps required to recreate this value by listing the calculations found in the tree from least to most recent. The starting values don’t need to be listed, as they are given, not calculated, so they don’t have a “step” to print. (The one exception to this would be if one of the starting values itself matches the target, in which case the input value itself is a solution.) For this example that gives us:

Steps to produce 12 from 1, 2, 4:
1 + 2 = 3
3 × 4 = 12

Translating this process to code, we can add the following method to the Value class:

toListOfSteps() {
    // if this is a starting value, then the only "step"
    // involved is that the number itself matches the target
    if (this.lhs == null) {
        return `${this.value} = ${this.value}`;
    }

    // recursive helper function that walks the history tree,
    // capturing the calculations performed in reverse order
    function steps(v) {
        // ignore starting values
        if (v.lhs == null) return "";
        // first gather up the steps from deeper in the tree,
        // then append this step to the end of that list
        const prevSteps = steps(v.lhs) + steps(v.rhs);
        return prevSteps + `${v.lhs.value} ${v.operator} ${v.rhs.value} = ${v.value}\n`;
    };
    return steps(this).trim();
}

Why print the steps in reverse order? What we’re doing is presenting a proof for our solution, and we want to present it in the most convincing, logical order, meaning that any result that we rely upon should already have been presented before the point at which we rely on it. The value that we start from is actually the conclusion of our argument. It points to the the steps that it directly relies upon. Those steps in turn point to the steps that they rely upon, and so on, until we reach the starting numbers, our “givens.” If we printed each step as we discovered it, our proof would come out exactly backwards. (When attending fancy parties, we could say that the tree formed by a Value is a dependency graph and that our traversal strategy results in a topological ordering of that graph.)

If you find that function hard to follow, here is something similar but simpler to implement: Suppose we want to be produce something like a JavaScript code expression that would calculate a value exactly as it is derived. We don’t require the expression to be optimal, just syntactically correct. How could we do it? Starting input values could be represented simply by converting the number to its string representation. What about derived values? We could print their left-hand value, operator, and right-hand value, so we’d get something like lhs + rhs. But each of those can also be derived from something else which must be calculated first. Therefore, we need to also recursively expand the left- and right-hand values to strings, and to ensure that they are evaluated first, wrap them in parentheses:

toExpression() {
    if (this.lhs == null) {
        return String(this.number);
    }
    return `(${this.lhs.toExpression()}) ${this.operator} (${this.rhs.toExpression()})`;
}

Since we have been using × for multiplication, this won’t yield a valid JavaScript expression as is—that’s easily fixed using String.replace, though. Take a moment and try applying this function, a step at a time, to the tree for the value 12.

[12]
([3]) × ([4])
(([1]) + ([2])) × ([4])
((1) + ([2])) × ([4])
((1) + (2)) × ([4])
((1) + (2)) × (4)

Deriving new values

In all the excitement of breaking a value down into the steps that produce it, we have neglected to add a way to actually combine two values (beyond showing how to do it manually). The method below is a straightforward automation of the of the manual steps shown before. Recalling the discussion from last time, we expect the inputs to be sorted so that the rhs passed to this method is the least of the two. We also return null if the result would break the game’s rules (by having a fractional or nonpositive value).

combine(rhs, operator) {
    let n;
    switch (operator) {
        case "+":
            n = this.number + rhs.number;
            break;
        case "×":
            n = this.number * rhs.number;
            break;
        case "-":
            n = this.number - rhs.number;
            if (n < 1) return null;
            break;
        case "/":
            n = this.number / rhs.number;
            if (!Number.isInteger(n)) return null;
            break;
        default: throw new Error(`unknown operator ${operator}`);
    }

    let v = new Value(n);
    v.lhs = this;
    v.rhs = rhs;
    v.operator = operator;
    return v;
}

Comparing values

At this point we need to decide exactly what the goal of our solver will be. Do we simply want to find any solution for a puzzle? Do we want to find all solutions? The best solution? And what if there is no solution? In the game show, if no player solves the puzzle exactly, the closest player can still earn some points if their solution is within ±10 of the target. For the purpose of this article, we’ll return an array of all of the exact solutions, along with the solution that the algorithm thinks is “best” according to some criteria. If there is no exact solution, it will return an empty array along with a “best” solution that gets as close as possible to the target. With this as your starting point, it should be easy for you to adapt the code to other goals.

So how do we decide which solution is the best? There is no one answer to this question, but we can probably agree on at least a few of the features it is likely to have. A solution that is closer to the target is better than one that is further away. A solution that requires fewer steps is generally preferable to one that requires more steps. And so on.

To help us rank values, let’s add a new property steps that keeps track of the number of calculation steps it uses. This is initially 0; when combining two values, we can sum the number of steps required by the left and right operand values and add one to determine the total number of steps for the new value. (Since values cannot be reused, no two values can have any steps in common.) Like the number property, we could calculate this as needed, but our code will be a faster if we calculate it once and store the result. Then we can compare values with:

/**
 * Compares this value to another value, returning zero if the values are equal,
 * a negative number if this value precedes the other value, or a positive number
 * otherwise.
 * 
 * @param {Value} rhs The other value to compare this value to.
 * @param {number} target The round's target number.
 */
compareTo(rhs, target) {
    // pick value closest to target
    const lDist = Math.abs(this.number - target);
    const rDist = Math.abs(rhs.number - target);
    if (lDist !== rDist) return lDist - rDist;

    // pick value that requires the fewest steps
    const lSteps = this.steps;
    const rSteps = rhs.steps;
    if (lSteps !== rSteps) return lSteps - rSteps;

    // pick value with shortest string representation
    // (which is a slightly nicer version of toExpression)
    return this.toString().length - rhs.toString().length;
}

Note: Although not shown above, the Value.toString method returns a slightly cleaner version of Value.toExpression.

Translating the algorithm

Recall from last time that the algorithm we worked up in pseudocode was still a little raw. It only returned whether a solution exists, and it checked this in several places. Having settled on exactly what we want the function to return, we can make the implementation a lot cleaner.

There is one language-related implementation detail we need to sort out before we get into the nitty-gritty details. Since we are taking an object-oriented (or at least object-based) approach to our solver, it would make sense to add a solve method to our NumberPuzzle class. However, we’re going to want some helper functions to structure our solution, and those shouldn’t be available outside of the class. The usual way to do this is with a private method, a function defined as part of a class that can only be called from other methods of that class. At the time of this writing, JavaScript does not have private methods, though they are planned. There are ways to simulate them, but they’re messy and will take our focus off of solving number puzzles. For now, we’ll just add the helper functions to the end of the file, as we might if we were writing a module.

Setting up

If we’re going to return all solutions, we’ll need something to collect them in as they’re found. Since JavaScript implementations are typically either single-threaded or prohibit access to the same memory from other threads, we could just store this in a global or static variable. It’s better practice, though, to keep the function reentrant by passing along a structure to store the collection. This allows the function to be safely called from multiple threads, in case we port the code later. Its also easier to understand because all of the context is in one place, the function.

Here’s the structure we’ll use:

{
    // array of all exact solutions, each as a Value that
    // hits the target number, sorted from best to worst
    all: [],
    // the Value that is the "best" solution, which may not be
    // an exact solution in cases where none exists
    best: null
}

It would be awkward (and error prone) to ask callers to pass this in empty, so the method we add to the NumberPuzzle class will be a façade over the more complex workings beneath: it will set things up, then invoke the real solver function. This is a common and effective strategy when you want to abstract a simpler or more coherent API from more complex parts.

Our façade method will have a few jobs to do:

1. Initialize the structure above.
2. Convert the numbers passed to the NumberPuzzle constructor into the Values used by the solver.
3. Check whether any of the raw values has already hit the target.
4. Pick the closest raw value as the initial choice for “best” solution.
5. Call the real solver function with the converted values and storage structure.
6. Sort any discovered solutions from “best” to “worst” (optional, but convenient).
7. Return the results using our structure.

And here it is:

solve() {
    let values = this.values.map(n => new Value(n));
    let solns = {
        best: values[0],
        all: []
    }    
    values.forEach(v => consider(v, this.target, solns));
    solveImpl(values, this.target, solns);
    solns.all.sort((v1, v2) => v1.compareTo(v2, this.target));
    return solns;
}

Instead of explicit loops we’ve used functional programming tools like map, forEach, and arrow functions to more clearly express our intent. This is less efficient than combining overlapping operations into a single loop, but the increased clarity is worth the wasted cycles here. If this were the inner loop of our solver, the story would be different, as it will execute millions of times.

We do steps 1 and 2 in the opposite order in the code. That’s because we want to initialize the best property with an valid Value rather than null. This lets us avoid testing if it is null every time we access it in our solver function.

Steps 3 and 4 are combined into a single task, handled by the consider function. This function does two things: First, it checks if the passed-in value is better than the current best, and if it is it replaces the current best. And second, it checks if the value is a valid solution, and if it is it adds it to the all array. The implementation is trivial:

function consider(value, target, solns) {
    if (value.compareTo(solns.best, target) < 0) {
        solns.best = value;
    }
    if (value.number === target) {
        solns.all.push(value);
    }
}

Step 5 calls the real solver, and since steps 6 and 7 are straightforward, we’re going to jump right into it next:

const operations = ["+", "-", "×", "/"];

function solveImpl(values, target, solns) {
    for (let i = 0; i < values.length - 1; ++i) {
        for (let j = i + 1; j < values.length; ++j) {
            // get pair of values to combine and ensure they are in sorted order
            let lhs = values[i], rhs = values[j];
            if (lhs.number < rhs.number) {
                [lhs, rhs] = [rhs, lhs];
            }

            // try combining the values with each operation
            for (let op of operations) {
                const result = lhs.combine(rhs, op);
                if (result == null) continue;

                consider(result, target, solns);

                // if there are more than two values left in the list,
                // we can still make more pairs from the shorter list
                if (values.length > 2) {
                    const reducedValues = reduce(values, i, j, result);
                    solveImpl(reducedValues, target, solns);
                }
            }
        }
    }
}

This function also makes use of consider to track solutions, replacing the multiple checks in the pseudocode. It relies on one last helper function, reduce, which is used to return a copy of the values that replaces the selected pair with their combined result, so we can recursively solve the shortened list. We only call it once, so we could inline this code, but using a named function improves readability. The implementation is straightforward:

function reduce(values, skipIndex1, skipIndex2, combined) {
    const copy = [combined];
    for (let i = 0; i < values.length; ++i) {
        if (i === skipIndex1 || i === skipIndex2) continue;
        copy.push(values[i]);
    }
    return copy;
}

All the pieces are now in place for a working solver based on the ideas developed in part one. To give it a quick test, we could do something like this:

let p = new NumberPuzzle();
console.log(p.toString());
console.log(p.solve().best.toListOfSteps());

which might print something like:

Try to make 913 using 25, 100, 6, 8, 1, 10.
100 + 1 = 101
101 + 10 = 111
111 × 8 = 888
888 + 25 = 913

The complete, collected solver code is available on GitHub for you to build on, and you can also play with an interactive solver below.

Things to try

Once you have the solver up and running, here are some starting points for further experimentation and learning:

1. By default, NumberPuzzle creates puzzles that use two “big” numbers, which is generally thought to produce the easiest puzzles. Test this hypothesis experimentally by comparing several puzzles using different configurations.
2. Experiment with how solutions are ranked to try to make the preferred solution more like ones that a player might pick. For example, you could try favouring addition and multiplication over subtraction and division, or favour solutions that use “easy” numbers such as 1, 2, and 10 over other numbers.
3. Modify the solve function so that, in addition to the information it already returns, it also returns a number that counts the total number of possible solutions it considered, whether or not they are valid. Examine how this changes as the number of input values (and hence possible pairs) is increased or decreased.
4. Improve overall performance by optimizing solveImpl, particularly the inner loops. The high precision performance.now() timer can be used to verify your attempts.
5. Improve average-case performance by excluding solutions that simply extend an existing solution, such as a solution that multiplies an existing solution by one.
6. As implemented in this article, the NumberPuzzle class exposes the Value class through its solve method. In other words, callers of solve need to learn how to work with Value instances in order to use solve. This may be undesirable depending on how NumberPuzzle will be used. Try refactoring the code so that solve returns a simple string value that the judges on the actual game show could use to reveal a solution when contestants fail to find one. In other words, make Value a private helper class that is not exposed to users of NumberPuzzle. (When feasible, this design strategy can make your public-facing API easier to understand and use, while also reducing the cost to maintain the code.)

The solver

An interactive version of the solver implementation is included below. There are three ways to use it:

1. Leave the input field blank to choose and solve a random puzzle.
2. Enter a single target number to choose a random puzzle using that target.
3. Enter the selected big and little numbers followed by the target number to solve a specific puzzle. Example: 75 50 7 1 1 5 528.

Choose Solve to start; results appear in the box below when ready.

Next time

That wraps it up for the numbers round! Check out the solver code on GitHub if you want to see the whole thing in context. When we pick this up again, we’ll begin our look at the other type of Countdown puzzle, the letters round. It’ll be an interesting contrast, as instead of solving the problem from first principles, we’ll start by looking for the right data structure.

Continue to part three

Image credit: Article thumbnail illustration is based on the Countdown numbers round game board.