April 24, 2020
About 13 minutes
Algorithms Recursion Divide and Conquer Countdown Numbers Round

Solving Countdown (Part 1)

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

This article is the first in a series that will look at the British game show Countdown from an algorithmic perspective. Countdown, first broadcast in 1982, is one of the longest-running game shows on television. Contestants alternate between playing two kinds of rounds for points: a word puzzle round and a number puzzle round. The contestant who scores the most points over all of these rounds is the winner, and is traditionally awarded a teapot. Both types of rounds offer interesting computational challenges, but we’ll start this series off with the numbers round.

Note: You can find a working numbers round solver at the end of part two if you want to skip ahead.

Numbers round rules

The goal of the numbers round is to calculate a three digit target number by combining six other numbers using the four basic arithmetic operations (addition, subtraction, multiplication, and division). The six other numbers are chosen from two sets: large numbers and small numbers. A contestant chooses how many large numbers to select, from 0–4. Then small numbers are selected so that together there are a total of six numbers (large and small together). The large numbers are selected at random from 25, 50, 75, and 100, while the small numbers are chosen at random from two copies of the numbers 1 through 10. Finally, a target number is randomly generated and both players get 30 seconds to try to solve the puzzle. Here is an example:

The contestant requests two large numbers (and therefore four small numbers). The following numbers are selected:

    [50, 25, 8, 2, 7, 7]

A computer then selects a random target number:

    801

A winning contestant could explain how to obtain 801 using the following steps:

    50 × 8 = 400
    400 × 2 = 800
    7 / 7 = 1
    800 + 1 = 801

A few additional rules to keep in mind:

1. A number cannot be used more than once.
2. Not all of the numbers have to be used.
3. Each step of a solution must result in a positive integer. Any calculation step that yields a negative number, a fraction, or zero is prohibited.
4. Not all puzzles are solvable. (If no contestant reaches the target exactly, points are also awarded for being closest within ±10.)

Studying the problem

How should we tackle this? A hand-wavy solution suggests itself: “Try every possible combination of number and operator; if at any point you can make the target number you are done, while if you can never make the target number there is no solution.” That does capture the basic idea, though it doesn’t immediately suggest anything practical. We don’t yet understand what “every possible combination of number and operator” means well enough to express it as an algorithm.

Breaking the problem down

If you think back to how the contestants describe a solution, you’ll notice that they break it down into steps. At each step they use two of the numbers, and then in future steps they can rely on both unused numbers and their intermediate results. (A contestant may sometimes perform a more complex step with three or more numbers, but this can always be further broken down into the simpler steps just described.)

Since numbers cannot be reused, combining two of them as part of a step effectively replaces both of the original numbers: we can now use the intermediate result, but neither of the numbers used to produce it. As a result, each operation shrinks the list of available numbers by one. If that isn’t clear, consider this simplified example:

    [1, 2, 3, 4, 5, 6]
    1 + 2 = 3 → [3, 3, 4, 5, 6]
    3 + 3 = 6 → [6, 4, 5, 6]
    6 + 4 = 10 → [10, 5, 6]
    10 + 5 = 15 → [15, 6]
    15 + 6 = 21 → [21]

Termination

We can see that if we proceed in this way, then—no matter what operations we are doing—eventually there will be only one number left, meaning that it can’t be combined with anything else. That’s good. We know for sure that we will eventually reach a stopping point. That’s a key requirement for a problem-solving procedure to qualify as an algorithm: it must be guaranteed to terminate after a finite number of steps. Consider the alternative. For example, suppose that reusing numbers was allowed. Then with each step our list of possible numbers would grow one number longer instead of shrinking. What would happen if we kept trying “every combination” of a problem that did not have a solution?

Something to ponder: If reusing numbers was allowed, would every target number have a solution?

Clarifying “every possible combination”

We’re making progress. We can perform a “step” by picking two numbers and combining them into a new number using an operator, thus generating a new, smaller set of numbers that can be the input for another step, repeatedly, until we have one number left. This in turn gives us a way to concretize the nebulous concept of “every possible combination.” Instead of trying a single step, we can try every step that can be performed from a given starting state. That is, instead of trying one pair of numbers and one operator, we can try every pair of numbers with all four operators. Instead of yielding one input state—number list—for the following step, the result will be a set of possible inputs for next steps. We can then repeat the process on each number list in this set, generating even more possible inputs for even more steps. By chasing each of these down until every list is reduced to a single number, we are guaranteed to try every possible combination. So, if there are solutions we will find them, and if there aren’t we will prove it by exhaustion.

Is it still guaranteed to terminate? The process described above may result in trying an incredibly large number of combinations, but it is still a finite number. We have shown that any particular sequence of choices for steps is finite because it reduces the set of inputs by one each time. And since the length of a number list at any step is finite, the number of number pairs that can be formed from that list is also finite. Since each of the finite number of combinations ends after a finite number of steps, the entire process must also end in a finite number of steps.

To convince ourselves that this idea will work, let’s look at solving a similar but simpler problem. (This is often a useful strategy in problem solving.) Let’s try using a list of just four numbers [2, 4, 6, 8] and two possible operators [+, ×]:

We start with our list of numbers:

    [2, 4, 6, 8]

The target number doesn’t matter for this example; let’s suppose it is 400 (which happens to be impossible). How many ways can we pick two of these numbers to combine?

    [2, 4]; [2, 6]; [2, 8]; [4, 6]; [4, 8]; [6, 8]

We could also reverse each pair, so we would have [4, 2]; [6, 2]; and so on. We can ignore that, though, since, for example, 4+2 = 2+4, a property known as commutativity. Now the numbers in each pair can in turn be combined with each of the + and × operators. So, for each pair we need to create a new list that combines the sum of the chosen pair with the remaining numbers from the original list that were not one of the chosen pair, and another list using the product.

Starting with the + operator that gives us:

    [2+4, 6, 8]; [2+6, 4, 8]; [2+8, 4, 6]; [4+6, 2, 8]; [4+8, 2, 6]; [6+8, 2, 4]

or, completing the addition:

    [6, 6, 8]; [8, 4, 8]; [10, 4, 6]; [10, 2, 8]; [12, 2, 6]; [14, 2, 4]

Similarly, the × operator will give us:

    [2×4, 6, 8]; [2×6, 4, 8]; [2×8, 4, 6]; [4×6, 2, 8]; [4×8, 2, 6]; [6×8, 2, 4]

which after completing the multiplication gives us:

    [8, 6, 8]; [12, 4, 8]; [16, 4, 6]; [24, 2, 8]; [32, 2, 6]; [48, 2, 4]

So, starting from our list of four numbers there are now 12 new lists, each of which is a possible first step for a solution. Thus after checking each of the 12 lists for the target number 400 and not finding it, we know that no solution is possible after one step. Any solution that does exist must therefore have at least two steps. To look for it, then, we continue by generating every possible second step. To do that, we need only reapply the process we used to generate the previous step. This time, however, instead of generating every possible pair and operator combination for the elements of a single list, we need to do it for all twelve of the lists generated by the first step. Since the lists are shorter now, each individual list will have fewer combinations: three possible pairs times two possible operators. Since we are doing this for each of the twelve possible starting lists, that means that there will be a total of 3×2×12 = 72 possible two-step solutions.

As stated above, there is no way to make the target with these numbers. But we can at least continue in this way to calculate the total number of possible solutions to this simplified version of the problem: after two steps we have 72 number lists. Each list has now been reduced in length to only 2 elements, so there is only one choice of pair to combine. There are still two operators, though, so there will be 1×2×72 = 144 possible three-step solutions. Each of these 144 lists contains only one element. That means that no more pairs are possible, and therefore no more steps or solutions.

Refining the approach

Now we have a plan: given a list of numbers, apply each possible operation to each possible pair of values from the list. Each of these generates another, shorter, list: apply the same procedure to each of these lists, and then each of those lists, and so on, until the target number is found or all of the lists are length one.

This general approach of breaking a problem down into one or more simpler versions of the problem, then re-applying the algorithm, is called divide and conquer. It is often implemented using recursion (functions defined in terms of themselves). Let’s try to sketch a version out. To start with, we need to select each possible pair from the list:

def solve(numbers, target):
	for each n in numbers
		for each m in numbers (except n)
			<make possible solutions using n and m>
		end for
	end for
end def

This will produce every possible pair, in every possible order. That is, if a list has elements a and b, it will produce both (a, b) and (b, a). We’ll come back to that in a moment. For now, let’s work on the body of the loops. To finish the job of combining the numbers n and m selected by the loop, we need to try applying every possible operator and check if the result hits the target value. If it doesn’t, we need to make a new, reduced copy of the list that replaces the selected numbers with the result of applying the chosen arithmetic operator, and then use that reduced list to keep looking for a solution, recursively:

def solve(numbers, target):
	for each n in numbers
		for each m in numbers (except n)
			for each operation in [+, -, ×, /]
				let result := operation(n, m)
				if result = target then return <found a solution>
				let reducedNumbers := a copy of the numbers
				remove n, m from reducedNumbers
				append result to reducedNumbers
				let solution := solve(reducedNumbers, target)
				if solution = <found a solution> return solution
			end for
		end for
	end for
	return <no solution>
end def

The pseudocode above only worries about identifying whether a solution exists. That’s all we’ll worry about for now. It isn’t a big leap to go from here to returning specific solutions, but we’ll save that until the next part of this series. There are three places in the pseudocode that can return a solution value: at the end of the function, and at two places in the innermost loop. The end of the solve function returns a value indicating that there is no solution. This works because the loops that precede this statement in the body of the function exhaust every possible combination before completing. Since within the loops we return immediately when a solution is found, the only way to reach the final “no solution” return statement is if we never find a solution after trying every possibility. Within the inner loop, we first check if combining our chosen pair and operator yields the target number. In that case, this particular step has found a solution, so we can stop. If this step doesn’t find a solution, then the rest of the code in the loop makes a new list using the new result and the remaining unused numbers, and then recursively calls solve on this smaller subproblem, stopping the loops by returning immediately if a solution is found in the subproblem.

You may have been taught that it is “bad” to have multiple return statements in a function. (It violates the rules of structured programming.) It can be. It complicates the flow of control and makes it harder to understand what assumptions are valid at a given point in the function, which is a common source of bugs. Rather than get sidetracked by a discussion of when it is OK to break this rule, just bear with me for now. The actual code will be different.

This is a start, but it certainly isn’t complete yet. The pseudocode doesn’t handle the case of a starting number already matching the target. It also doesn’t enforce all of the rules, like not allowing fractions. The first problem is easy enough to solve. The second we’ll address in the next section.

An optimization

Even with a short list and only two operators, the number of possible solutions that need to be considered is rather large. This number can grow incredibly quickly if we change the rules of the game to add more starting numbers, so much so that solving the problem this way would take impractically long. Even for the small problem size used on the game show, it may a few seconds for a computer to try every possibility. Anything we can do to reduce the amount of work needed to attempt a step, or to reduce the number of steps required, will significantly improve the algorithm’s performance.

Thinking back to those reversible pairs of numbers, one avenue for optimization suggests itself. Do we need to try both (a, b) and (b, a)? It might seem so at first: while addition and multiplication are commutative, subtraction and division are not. But recall the additional rules we listed above: no intermediate result can be negative, zero, or a fraction. By examining each possible case and comparing against these extra rules, we can readily show that only the pairs where a ≥ b are relevant:

That means we can modify the outer loops so that we only consider either (a, b) or (b, a). This one change will cut out half of the steps that the algorithm needs to perform, to about 1.6 million pair and operator combinations.

def solve(numbers, target):
	for let i := 0 to |numbers| - 2
		for let j := i + 1 to |numbers| - 1
			let n := max(numbers[i], numbers[j])
			let m := min(numbers[i], numbers[j])
			for each operation in [+, -, ×, /]
				let result := operation(n, m)
				if result = target then return <found a solution>
				if result ≥ 1 and result is a whole number then
					...make new number list and check for solutions...
				end if
			end for
		end for
	end for
	return <no solution>
end def

The modified loop above assigns exactly one of each possible (a, b) or (b, a) to n and m, and also ensures that they are sorted so that n ≥ m. It may not be obvious at first, but the two outer loops work similarly to how you would systematically produce each pair by hand. To see this, use a pencil and paper to run through a few iterations of the loops with a small example list. Or, use the developer tools console of this web page to run some experiments:

let v = ['a', 'b', 'c', 'd'];
for (let i = 0; i < v.length - 1; ++i) {
	for (let j = i + 1; j < v.length; ++j) {
		console.log(`(${v[i]}, ${v[j]})`);
	}
}

Here’s another way to think about it: Picture laying the results of the original loops out in a table, starting a new row for each value of i. A diagonal line runs through the table, falling on the entries where i = j. These entries are excluded from both versions of the code because they represent cases that would “pair” a number with itself. But this line also defines a line of symmetry through the table. Each entry on one side of the line is a reflection of a pair on the other side, that is, the same pair but with the element order reversed, like (a, b) and (b, a):

Selecting unique pairs from [a, b, c, d]

	j = 0	j = 1	j = 3	j = 3
i = 0	(a,a)	(a,b)	(a,c)	(a,d)
i = 1	(b,a)	(b,b)	(b,c)	(b,d)
i = 2	(c,a)	(c,b)	(c,c)	(c,d)
i = 3	(d,a)	(d,b)	(d,c)	(d,d)

The second version of the loops excludes the pairs that fall on one side of the line (the left/bottom side in the table above), each of which is just the reverse-order equivalent of one of the pairs from the other side of the line.

Next time

We’ve gone from a vague idea of how to solve the problem to a workable algorithm. We’re about ready to implement this in a real programming language, but I’m going to give you a chance to try it yourself first. Be sure to come back for the next installment. Before we’re done we’ll have code that can find the “nicest” solution (or all solutions), and list the exact steps required to reproduce it just like a contestant on the game show would.

Something to ponder: For any list of starting numbers, how can you determine the largest target number that could be matched exactly? Hint: It’s not as simple as multiplying the list of starting numbers together.

Continue to part two

Image credit: Article thumbnail adapted from a photograph by Jon O’Neill.