The Numbers Game – Countdown

Depending on your age, you may be familiar with the TV program Countdown, or the 8 Out 0f 10 Cats does Countdown version, or the generic original version Numbers and Letters, or maybe the even more original French version!

If you are you will know it is basically two games. Firstly an anagram game where contestants “pick” 9 random letters, and get points for how many letters they can get in their longest word. I have often suspected Susie Dent of having computer assistance with this, anagram solvers are two a penny on the net, and produce a list of words very quickly. I am sure she doesn’t though, she is much too nice to do that.

Secondly there is the numbers game. This is much more difficult to describe. Contestants randomly pick six numbers from two sets of numbers, between zero to four large numbers (25,50,75 and 100) where there is only one of each number, and the remainder of their six numbers from the small numbers, where there are two of each number from 1 to 10. A machine randomly selects a target number, between 100 and 999 inclusive. The contestants have 30 seconds to use the numbers chosen to generate the target number, just using add, subtract, multiply and divide. Each number is only to be used once, and none of the intermediate answers can be fractions (or negative I assume). I fell in love with Rachel Riley’s ability to solve these puzzles, coming up with some of the most tortuous combinations of numbers and operators to generate the answer. I also wondered if she had computer help for this, and for a long time I pondered whether there were any rules and algorithms that could be used to solve these puzzles. Over the years I have a few basic tricks to get started, but in the end intuition seems to win the day (for me).

I also wondered if there was a way for these to be solved by computers, as a programmer I was sure there was some way. However, being a programmer and not a real mathematician, all I could see was brute force solutions. Undeterred, I decided to develop my own brute force solution.

I started this a few months ago, and have had a couple pages of notes on my comfy chair side table, which I looked at occasionally, and despaired of seeing a way into the problem. I know it involved Reverse Polish Notation, and I know it involved ‘Stacks’, but writing the iteration to find all possible permutations to then calculate to see if it matched the target was doing my head in!

Until the weekend of April 1st 2022! I looked at the layout of the possible RPN formulas, and the numbers and the operators and realised that it broke down into these three problems.

In the code below, the first two section allow the user to input 6 numbers and the target. Only rudimentary checking is done.

The line

numberset =list(it.permutations(pickednumbers,6))

makes a list of all the permutations of the six numbers, a grand total of 720 of them. This could have been done by a number of iterations, but itertools allows this to be done in a single line.

The following two lines define the four operators, and creates a list of all possible permutations of five of these operators, from ‘+++++’ to ‘/////’, a grand total of 1024 (4^5). Again a series of iterations could have achieved this. This could have been a hard coded set, as it never changes.

This is a start, but not much use yet.

Reverse Polish Notation is a way of representing mathematical equations in a more machine logical form. Basically if two operands are followed by an operator, those two operands are replaced by a single operand which is the result of using the operator on the two operands.

For our problem of six numbers the simplest layout (using N for a number and O for the operator) is

N,N,O,N,O,N,O,N,O,N,O

but N,N,N,N,N,N,O,O,O,O,O is also valid, and lots of other combinations.

There are some rules as to what this format can be in this case. The first two places must be operands, and the last, 11th position must be an Operator. There must always be one more operand than the number of operators at any point in the list.

If you write this format using a 1 for a number and a 0 for the operator, it looks like this

1101010101010 or 11111100000

which are just binary numbers. If you remove the first two positions and the last position, you end up with an 8 bit binary number. The full set of 8 bit binary numbers is 256, which is a very small set, and can be generated just by counting from 0 to 255, converting to a string, and adding two digits to the front and a 0 to the end. A quick parse through each entry to make sure it follows the above rules, allows you to remove all but 42 of the set of binary numbers.

The optimised code from line 20 to line 35 generates a set of all possible patterns of the RPN layout. This could have been a hard coded set as the 42 patterns are fixed for this solution, but it takes less than a second to generate all three sets.

How does this help? Well if we take each of these patterns in turn, and apply each of the number permutations to each pattern and then apply each of the operator permutations to each of the numbers, we end up with every possible combination of numbers and operators positioned in all the possible RPN formats, each of which can be calculated to try to match the target.

However the number of calculations is nearly 31 million (42 * 720 * 1024 = 30,965,760). Fortunately not all of them go to completion, as soon as negative or fractional result is found the calculation is abandoned, or if a match is found to the target part way through, the attempt is saved and the next combination of pattern, number and operators is processed.

This line

for thispattern, thisnumber, thisoperator in it.product(patternset, numberset, operatorset):

is the clever itertools way of iterating through the three sets to generate the 31 million possible products of pattern, numbers and operators. As well as being easier to write the code, apparently it can be 20% faster in some cases.

The second programming technique I am using is the concepts of stacks. Python implements stacks very easily using normal lists. Instead of using the .push method. it just uses the normal .append method to add entries to the stack, but it does use the .pop method to remove the last entry from the stack, making it available as a variable.

Processing through Reverse Polish Notation is much easier using stacks, and I am using stacks for two purposes. Firstly to calculate the running result of the calculation, and secondly to generate the normal or ‘infix’ format for display to the user.

For the current pattern, we parse the patter for each position, and if a ‘1’ is found, the next number from the current number from the number set is pushed into the calc stack, and we keep pushing numbers in until a zero is found. At this point we pop the last two values out of the calc stack, and use the next operator from the latest operator set entry, and calculate the result of the operator on the two values. At this point we detect if the latest value is fractional, or if it is negative, and abandon this combination and go onto the next. If the latest value matches the target, the calculation has found a result, and the infix equation is saved in a list of actual results. Otherwise the result from this calculation is pushed back into the calc stack to replace the two operands.

To generate the infix equation, when a ‘1’ is found in the pattern, the next number is pushed into infix stack, and this happens until a ‘0’ is found. At this point, the last two numbers are popped, and a string consisting of the last two values with the operator between them, all between a pair of parentheses is created. If the result of the calculation is pushed in to the calcstack, then this string is pushed into the infix stack. When the value of the calc stack matches the target, the latest entry in the infix stack is popped and is added to the result stack, which is a list of the infix equations that solve the given numbers.

In this version of the code, the first 10 solutions are shown on the screen, the first solution usually with a second or two, all 10 within a few seconds. The program continues to find all remaining possible solutions, which may take a few minutes, and could be from a few hundred to a few thousand solutions.

Not all of these solutions are unique, many versions of a solution will be presented, where additions of two or three numbers occur in different orders, or results with division by 1 and multiplication by 1 can appear where just the number would have sufficed. This is why it is called a Brute Force method!

Here is an example of the full results from the program

or this one for a bit more fun. This run uses the numbers selected by James Martin on Countdown, and the game is quite famous if you are a Countdown Geek.