"Countdown" numbers game solver
Ruby Perl C JavaScript Gherkin Shell Other
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
bin
features
lib
public
spec
t
.dockerignore
.gitignore
Dockerfile
Gemfile
Gemfile.lock
Makefile
README.pod
build
deploy
numbers
numbers-fast.c

README.pod

NAME

numbers - "Countdown" numbers game solver

SYNOPSIS

# Show all possible combinations
./numbers NUMBER [NUMBER ...]

# As above, but only show combinations which are at least as close to the
# target as the closest found so far
./numbers -t TARGET NUMBER [NUMBER ...]

There's also a sinatra-based REST interface to the solver (returns the results as json), and a Dockerfile to run that server.

DESCRIPTION

See http://en.wikipedia.org/wiki/Countdown_(game_show)#Numbers_round

Normally the game is played with 6 numbers, and a target in the range 100-999. This solver allows 1 to 10 numbers; the numbers, and the target, may be in the range 1-999.

The solver brute-forces all possible combinations. You can either elect not to specify a target (to see all possible combinations), or to specify a target (in which case the solver only outputs combinations which are at least as close to the target as the closest found so far).

The algorithm

The heavy lifting is done in C (for speed). The results are then formatted using Perl (because it is the language I was most familiar with at the time). There's also an implementation of the formatting layer in Ruby.

The algorithm is based on a Reverse-Polish stack. At any given time we have:

  • a set of numbers we haven't used yet (i.e. initially, the 6 numbers the user entered)

  • a results stack

  • a sequence of operators and operands which got us this far

The program then tries all possible combinations: if the set of unused numbers isn't empty, we can push one of those numbers onto the stack (we try each one in turn).

If the results stack contains at least two results, we can also use operators: at any time we can push "+" or "*" (because any two numbers in Countdown can be added or multiplied); we can only push "-" if the result doesn't go zero or negative, and we can only push "/" if the result is a whole number.

Any time the results stack contains exactly one result, we have a valid sum (which may or may not be anywhere near the target).

Example: given the starting numbers 1, 5, 6, 9 we might have got to this point:

operators used: 6 9
results stack:  6 9
numbers unused: 1 5

At this point, we could push either "1" or "5" onto the stack, and keep going; or we could push "+" to get 15, or "*" to get 54, or "-" to get 3. We can't push "/", because 9/6 isn't a whole number.

If we chose to push "*", that leads us to this point:

operators used: 6 9 *
results stack:  54
numbers unused: 1 5

At this point, we have a valid answer (6 * 9 = 54); or we could push either "1" or "5" onto the stack, and keep going; we can't push any operators right now, because the results stack contains only one result.

At all times, all possible "moves" are tried.

Optimisations

The code does contain a few optimisations.

It avoids copying memory around - one only "state" is kept at any one time, and the call stack is used to mutate that state, then revert it.

If the starting numbers contain duplicates (e.g. 1 3 3 6 7) then, when it comes to trying each number in turn, duplicates are avoided.

"+" or "*" are only tried if the top result on the stack is >= the next result (e.g. we allow 9 + 6 but we avoid 6 + 9). "*" is avoided is either number is 1.

Outputting and formatting the possible answers is relatively expensive, so the fastest case is to tell the C code what target we're aiming for, and to ask only for answers which are at least as close as the closest answer so far.

AUTHOR

Rachel Evans

http://rve.org.uk/countdown