Efficient and unique solutions to Countdown's Numbers game
The numbers game on the British TV show Countdown involves attempting to combine positive integers into a target number using addition, positive subtraction, multiplication and division without remainder. The problem is interesting computationally, even though it is restricted to exponential complexities, being more complicated than the subset-sum problem. A naive solution is easy to implement, but is very inefficient and takes time even for small input sizes. Improvements can be made by restricting the set of arithmetic expressions being considered, and some such improvements were suggested in literature (Alliot 2015, arXiv) but there is more that can be done. The rapidly inflating number of possible expressions is the main source of complexity, so we should aim to exclude all redundancies.
We iterate creating new combinations of expressions but:
- the first operand should be larger than the first, or have a larger address
- for repeated operations, the operands should be decreasing (10+5+2, not 5+10+2)
- no addition after subtraction or multiplication after division
- do not add or subtract an addition or subtraction
- do not multiply or divide with a multiplication or division
There are other possibilities that are technically distinct but are still
uninteresting and will inflate the set we are working with. Examples are
multiplying/dividing with 1, additions like a/d+b/d or b-a=a.
Excluding those cases is not enough, as it would still not exclude e.g. a/d+c+b/d.
Therefore we can use a dictionary that maps masks (structures that enumerate
how many copies of each input were used; this can be a simple bitmask if
there are no duplicates) to each value that was found.
Then, a solution will be excluded if there exists already a solution using a (multi)set
of numbers that is a proper subset of the set of numbers used by said solution.
This is the most expensive part of the program and we could consider
only excluding a few common possibilities like multiplying or dividing by 1.
Experimentation has shown that this nevertheless greatly inflates the space of
expressions with moderately slower speeds.
A search tree (struct Map) is used to keep track of solutions, and
expressions are represented as binary trees (struct ExprTree) so that
they can be printed in the usual infix form. When iterating through pairs
of expressions, we take care to only produce expressions using the same
total number of inputs (incl. duplicates). This lets us limit the number
of iterations, and is also conducive to parallelization.
Using a self-balancing search tree would be a good idea, but the bulk of
time consumption comes from the large size of the (squared) set of expressions,
which we iterate through in search of new combinations. This is partially mitigated
by making sure that we first generate only expressions using 2 numbers, then 3, etc.,
which inductively enables us to consider only those pairs which together fit our next target.
The indices that form the boundaries of these categories are tracked in jumps attribute
of struct ExprForest.
Regarding the 'mask' for tracking numbers that are used in an expression, we encode the information into a single integer as follows: to each of the numbers we assign a prime number. Then, the mask of an expression is the product of all such relevant primes. For example, to 25, 50 and 100 we may assign 2, 3, 5 respectively. Then if we use a 25, two 50's and three 100's, the mask would be 2x3^2x5^3. Generally this could lead to extremely large numbers, but it is robust enough that anything generated by 15 distinct values fits into a 64 bit integer. This representation is useful because expression A uses a subset of those numbers used by expression B if and only if its mask divides the mask of B. This is therefore more efficient in both time and memory compared to vectors.
Firstly, in case of distinct inputs, it is not recommended to use input size exceeding 9. If
the memory limit is exceeded (see MAX_MEMORY_), the program will exit gracefully.
Compile with
gcc countdown.c -o bin/countdown
We input an array of integers – the first is N, the input size
(e.g. 6 numbers in Countdown) followed by Q, the number of queries.
The next N numbers are the inputs which we can use and the Q after that
are the targets we wish to see solutions for. Example input and output:
bin/countdown 6 5 100 75 50 25 6 3 952 843 112 19 10998
------
Query: 952
((100+6)*75*3-50)/25
(100+3)*75*6/50+25
2 solutions found.
------
------
Query: 843
(100+50+3)*6-75
(100+25+3)*6+75
2 solutions found.
------
------
Query: 112
100+(75-3)/6
100+50*6/25
100*(25+3)/(75-50)
100*(75+3-50)/25
50*(25+3)*6/75
5 solutions found.
------
------
Query: 19
25-6
100-75-6
75-50-6
75/3-6
25-100*3/50
5 solutions found.
------
------
Query: 10998
0 solutions found.
------
32081 solutions found in total.
Time:0.010771 seconds (10.771000 miliseconds)
Memory freed successfully.
- The speed, depending on the number of solutions, can vary greatly depending on the inputs. Large, varied and diverse inputs generate more solutions, while smaller inputs with many duplicates will be much faster with larger input sizes feasible.
- An additional possiblity for optimization is excluding results larger than a certain threshold. This will exlucde some solutions, but they may not be interesting to us. With the usual Countdown rules the largest viable intermediate result is short of 100000.
- Furthermore, we could opt to exclude not only solutions using more numbers than is needed, but also new ones using exactly those that are needed, i.e. combinations that we have seen before. This will exclude some unique solutions, but will not miss any targets and will further shrink the set of expressions.
- Comments should be added to the code.