The (final) countdown

The Countdown game is one of the oldest TV show running in the world. It started broadcasting in 1972 on the french television as "des chiffres et des lettres", literally "numbers and letters" with a numbers round called "Le compte est bon", literally "the count is good". It started broadcasting in 1982 on British channel 4 as Countdown, and it has been running since in both countries.

The numbers round of the game is extremely simple: 6 numbers are drawn from a set of 24 which contains all numbers from 1 to 10 (small numbers) twice plus 25, 50, 75 and 100 (large numbers). Then, with these six numbers, the contestants have to find a number randomly drawn between 101 and 9991, or, if it is impossible, the closest number to the number drawn. As soon as a number has been used, it can't be used again. For example, if the six numbers drawn are 1,1,4,5,6,7 and the number to find is 899 the answer is:

```6x5=30
30+1=31
4x7=28
28+1=29
29*31=899
```

There are usually different ways to find a solution. The simplest answer is usually defined as the answer using the least number of operations, and if two solutions have the same number of operations, a possible refinement is to keep the one having the smallest highest number.

As odd as it might seem, the game, while extremely popular, never received any serious scientific attention. Many websites in France and in Great Britain discuss the game and how to program it, with lot of code, lot of statistics, and sometimes lot of errors. There are many commercial or free programs developed for this game. Some of them are bugged or use incomplete or incorrect algorithms.

The goal of this article is to do a scientific analysis of the game regarding its complexity and to provide a set of cutting edge algorithms and codes to solve it properly. It is a long preprint (17 pages), quite technical, that will be submitted, if I have the time, to a conference or a journal, probably in a reduced form (Update: A slightly shorter version has been accepted for publication at GCAI 2015. The proceedings are available here in the EPiC Series in Computer Science). It is also available on arxiv. The code needs to be cleaned up a little bit, and will then be made available on this page. However, the main program has been written to run on linux with MPI, a configuration that may not be accessible to everyone.
There is an html version of this article here. Mathematical formulas are however looking better in the pdf.

This article also discusses various improvements to turn the game into a more difficult one, such as selecting difficult problems, or changing the pool from which to pick numbers.
It also introduces a variant of the game where it is possible to use a new operation, the square operation. Each remaining number may be replaced by its square in a calculation. For example, finding 999 with 1,2,3,4,5,6 is impossible in the standard game, while it is possible in this variant:

```   Operations   Remaining numbers
{1,2,3,4,5,6}
3 x  6 =  18  {1,2,4,5,18}
18 x 18 = 324  {1,2,4,5,324}
4 +  5 =   9  {1,2,9,324}
324 +  9 = 333  {1,2,333}
1 +  2 =   3  {3,333}
333 x  3 = 999  {999}
```

With this modification, the game is no longer decidable, or at least decidability is not clear. Solutions can now be very long. For example to find 862 with 1,10,19,25,75 and 100, 14 steps are needed, using numbers as large as 400000000.

```            Operations              Remaining numbers
{1,10,10,25,75,100}
10 -        1 =         9   {9,10,25,75,100}
100 x      100 =     10000   {9,10,25,75,10000}
9 x        9 =        81   {81,10,25,75,10000}
10 x       10 =       100   {81,100,25,75,10000}
100 x      100 =     10000   {81,10000,25,75,10000}
10000 +    10000 =     20000   {81,20000,25,75}
75 x       75 =      5625   {81,20000,25,5625}
5625 x     5625 =  31640625   {81,20000,25,31640625}
20000 x    20000 = 400000000   {81,400000000,25,31640625}
400000000 - 31640625 = 368359375   {81,368359375,25}
25 x       25 =       625   {81,368359375,625}
625 x      625 =    390625   {81,368359375,390625}
368359375 /   390625 =       943   {81,943}
943 -       81 =       862   {862}
```

There are only 49 instances of the game which have currently no solution. This does not mean that there are no solution, but only that with the current numerical bounds used in the program no solutions were found. These 49 instances are:

```1 1 10 10 25 100: 858
1 1 10 10 25  75: 863
1 1 10 10 50 100: 433 453 547 683 773 853
1 1 10 10 50  75: 793 853 978
1 1 10 10 75 100: 433 453 457 478 547 618 653 682 708 718 778 793 822 853 892 907 958 978
1 1 10 25 75 100: 853 863
1 1 10 50 75 100: 793 813 853 978
1 1  5  5 25 100: 813 953
1 1  7  7 50 100: 830
1 1  8  8  9   9: 662
1 1  9 10 10 100: 478 573 587 598
1 1  9  9 10 100: 867
1 9  9 10 10 100: 867 947 957 958 967
```

The following programs solve the classical game, with a "smart" sort of the complete set of solutions (read the article):

The following program is the one used for computing all the statistics presented in the article. The Linux 64 bits version takes 13s on an i7 980X computer (the linux 32 bits version computes the result in 23s; windows version are slightly slower). To truly appreciate the speed of the algorithm, this web site presents the same result computed in 60 days (!) while kitsune (one of the best public domain program) computes these results in a few hours.

The program must be used in command line mode, and takes 4 arguments:

• How many numbers are in the set (between 4 and 10). Be careful: the program is extremely fast for 6 numbers, but, as demonstrated in the article, the complexity grows extemely fast. With 7 numbers, you'll have to wait for a few minutes, and a few hours with 8 numbers.
• The lower bound (excluded) of the numbers to find (higher than 100)
• The upper bound (excluded) of the numbers to find (higher than (lower+1))
• The maximal distance to search for approximate solutions

For example under windows:

```stats64.exe 6 100 1000 1000
```
generates the statistics for the problem with 6 numbers, looking for solutions between 101 and 999, and looking for approximate solutions as far as necessary (the "classic" game).

The program has been heavily tested in a Linux 64 bits environment. The other programs work for 6 numbers, but have not been really tested and bugs might still be there (expecially under windows because of memory allocation problems).

The program generates 3 files:

• The format of numbers.txt is:
• number to find
• number of sets finding this number
• percentage
For exemple: in numbers6.txt, 999 is found by 11571 sets out of 13243 possible. The percentage is 87.3745%.
• The format of closest.txt is:
• the distance to the solution for a pair (set of numbers,number to find)
• how many time we have this distance
• the percentage
For example: in closest6.txt, 10 858 746 problems are solved exactly (They are at a distance 0 of the solution searched) out of 13243*899=11 905 457 problems: a percentage of 91.2081%.
• The format of results.txt is:
• How many numbers are found
• How many sets find this number of numbers
For example in results6.txt, we see that there are 1226 sets that can find 899 numbers: so 1226 sets can find all the numbers.

For those who have a special nostalgy for the amiga computer, here is the C and assembly code of the first program (according to my knowledge) which solved almost properly (see in the article) the game in the allotted amount of time. The amiga executable is here.