Name of the Countdown Numbers round problem - and algorithmic solutions?
- by Dai
For the non-Brits in the audience, there's a segment of a daytime game-show where contestants have a set of 6 numbers and a randomly generated target number. They have to reach the target number using any (but not necessarily all) of the 6 numbers using only arithmetic operators. All calculations must result in positive integers.
An example: Youtube: Countdown - The Most Extraordinary Numbers Game Ever?
A detailed description is given on Wikipedia: Countdown (Game Show)
For example:
The contentant selects 6 numbers - two large (possibilities include 25, 50, 75, 100) and four small (numbers 1 .. 10, each included twice in the pool).
The numbers picked are 75, 50, 2, 3, 8, 7 are given with a target number of 812.
One attempt is (75 + 50 - 8) * 7 - (3 * 2) = 813 (This scores 7 points for a solution within 5 of the target)
An exact answer would be (50 + 8) * 7 * 2 = 812 (This would have scored 10 points exactly matching the target).
Obviously this problem has existed before the advent of TV, but the Wikipedia article doesn't give it a name. I've also saw this game at a primary school I attended where the game was called "Crypto" as an inter-class competition - but searching for it now reveals nothing.
I took part in it a few times and my dad wrote an Excel spreadsheet that attempted to brute-force the problem, I don't remember how it worked (only that it didn't work, what with Excel's 65535 row limit), but surely there must be an algorithmic solution for the problem. Maybe there's a solution that works the way human cognition does (e.g. in-parallel to find numbers 'close enough', then taking candidates and performing 'smaller' operations).
