CountDown
This program solves the 'numbers game' from the TV game show Countdown. Contestants are given a random selection of six numbers and a three-digit target number; they must combine the given numbers using the operations of arithmetic to make the target number.
Instructions
- You can use the panel at the left to choose the six given numbers, or click on Random to have the computer make a random choice.
- You can type a target number into the box on the right (click in the box first), or use the right-hand Random button to choose it randomly.
- When both the given numbers and the target have been chosen, the Solve button is enabled; click on it to see the closest solution to the target. The answer appears almost instantly.
More about the program
Every year we run a programming competition for Computer Science students, usually with a puzzle as the subject. This program was designed by Stephen Williams, and won a recent competition. Stephen wrote his program in C, and I have re-implemented it in Java for this demonstration.
The Countdown problem is difficult to solve quickly because of the huge number of arithmetic expressions that can be formed from the six given numbers - about 30,000,000. We might be lucky and find an expression that gives the target value, but in problems that cannot be solved exactly, we need in principle to evaluate all these expressions in order to find the closest one.
This program uses several advanced data structures taught in our second-year courses on Algorithms and Data Structures and Formal Program Design. Syntax trees are used to represent expressions, bitmaps are used to represent the set of input numbers that each expression uses, and a hash table is used to store the expressions that evaluate to each different result. The key idea is to eliminate expressions that cannot contribute to the solution as early as possible: for example, if two expressions have the same value and use the same input numbers, there is no point in keeping both of them.
These techniques work together to allow the problem to be solved very quickly by a program that is still fairly short: the part that actually finds the solution is less than 200 lines long. Similar techniques have enabled Oxford teams, fortified by a good understanding of the theory needed to make programs fast while keeping them simple, to win the BCS Programming Competition several years in succession.
If you can solve this problem with a program, however fast or slow, then we'd love to hear from you.