Count Down
Count Down 
Count down is a TV quiz show in England. Contestants are asked to do a few things within a set time limit. One of the tasks is to make a target number from numbers. Here is the rule.
Six numbers are given: usually one number has 3 digits, two numbers have 2 digits each, and the other three are single digit numbers. A target number is then announced. In 30 seconds, you must use some or all the six numbers, elementary arithmetic operators (+, -, *, /) and brackets to build an expression that evaluates to the target number, or as close to it as you can.
Here are some cunning examples:
Download the program:
Now you can download the program that gave the above answers. Either
How to use the program:
The Rules menu chooses how the random numbers are generated. Make 10 generates integers between 1 and 9 inclusive, The 24 game generates integers between 1 and 10 inclusive, and Count down generates integers in the manner described at the top of this page.
The Algorithms menu lets you specify how the program searches for the solutions. The slowest combination is Basic binary tree and No tree removal. The fastest combination is Multiple branches (remove negatives) and Tree removal - integer values. Try different options and observe how each algorithm behaves.
Inside the Main window, you specify how many numbers are used in the game, and whether the solution must use all numbers. Make 10 and The 24 game should use 4 and all 4 numbers, Count down should use up to 6 numbers, but there is nothing stop you changing the rules. You might have already noticed that you can type in the numbers yourself.
Click Calculate and observe how the computer searches for the solutions. On my K6-3 450MHz computer, it can take more than 10 minutes to solve the standard count down game using the basic algorithm. Using the fastest algorithm, it takes approximately 20 seconds to find all the solutions.
Explanation of the algorithms:
Each expression can be organised as a tree. The bottom nodes (end of the branches) are numbers, other higher level nodes are operators. For example, 3 + 4 is a tree with a "+" node at the top, and it branches out into the nodes: "3" and "4". Note that the tree is a binary tree, as arithmetic operators are binary operators (combine two numbers).
6 numbers need 5 operators. There are 6 different tree shapes in Count down:
Basic Binary Tree: The basic algorithm simply place 6 numbers in all permutations, and try all operators on each operator node. The total number of basic binary trees is
T = 42 * 6! * 4^5 = 30965760
In the program, we build the trees bottom-up. All sub-trees using the same set of numbers can be generated once only and then reused.
Communicative Rule Optimization: By introducing two new operators: [reversed minus] and [reversed divided], we can reduce all structual mirror images. Number of possible trees are largely reduced, but we now have 6 operators.
Multiple Branches Search: 1+(2+3) = (1+2)+3. This is association rule. When connected opearators are all [+] and [-], we can collapse them into a multiple branch nodes. This reduces permutations in number nodes. Similarly, we collapse connected [*] and [/] operators in a tree into a multiple branches node.
Multiple Branches (Remove Negatives): This is optimization on distribution rule (1-2)*(3-4) = (2-1)*(4-3). Only factors of (-1) are re-distributed.
Tree Removal (Integer Values): if two expressions built by the same set of numbers give the same integer output, then only one expression needs to be remembered.
Have fun.