10

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).

  • 1
    I solved this graphically - use nodes to represent the results of calculations and edges to represent operations that can be done on those numbers, then use a graph search algorithm to find the desired path – ell Oct 9 '13 at 20:22
  • 1
    From a reading of the rules, it would seem that it is possible to not reach a perfect solution - for example if the numbers selected are (1, 1, 2, 2, 3, 3) and the target number is 999. So really the target for any algorithm would be finding the closest possible solution. – Rich Smith Oct 11 '13 at 15:34
  • 1
    @ell: Is your graph search solution basically a brute force search? – Martin Oct 18 '13 at 8:40
  • I just used a depth first search in my implementation, but I don't see why something like Dijkstra couldn't be used. – ell Oct 18 '13 at 16:34
  • 1
    We have some similar shows in the States: we stick approximately 6 sub-literate idiots in a house for several weeks and film them talking about each other and yelling at each other. That's about as close as our TV gets to something this intellectual in popular shows. – RBarryYoung Nov 10 '13 at 23:09
4

Disclaimer: This answer does not answer the question that completely. But it's too long for a comment.

NP-hard? I believe, this problem could be NP-hard.

Consider a special case of the Knapsack problem:

Given a set of positive integers and a positive integer b, does there exist a subset of the set such that the sum of all integers in that subset equals b?

This sounds somewhat similar to our Countdown problem, and it seems to be much simpler. However, Knapsack (and this special case of Knapsack) is NP-hard (and NP-complete, of course).

I did not manage to use this for a proof that Countdown is NP-hard. I could not get rid of the division. Consider we have a thousand 2, and b = 7. This will never be solvable with Knapsack, but always (?) with Countdown, at least in all the ways I tried to transfer the problem.

Now, if Countdown really was NP-hard, we could deduce that there with very high probability is no algorithm that is significantly more efficient than brute-force trying all possibilities. (And if we should find such an algorithm, we will become very famous.)

No, I don't think there must be an efficient algorithm.

Heuristics. The Youtube video linked in the question has a nice example: The contestant found an exact answer 952 = ((100 + 6) * 3 * 75 - 50) / 25. That is completely against my intuition, I would never have tried it that way in the first time: Produce a very large number, then divide it and yield the result.

On the other, we humans feel that we do not need to try (arbitrary example) 50 * 75 * 100 / 2 / 3 / 7 to reach a three-digit-number. But computers do not feel anything, they simple calculate.

After all, if we implemented some heuristics, and this heuristics does not find an exact solution, we still will have to try all other solutions to make sure there really is none.

What the contestant in the Youtube video does is, I think, to very quickly check a large number of possibilities and to quickly discard those that will not (or likely will not) give a solution.

Conclusion. When implementing an algorithm, one could take care to strip equal calculations such as a / b / c = a / (b * c), but I think this is quite hard to do and I do not know whether this improves the runtime significantly.

Computers of course are faster than humans in checking a large number of possibilities. And nowadays, even smartphones are so fast they can solve this problem, I think, within a second by simply trying all possibilities. (I did not test this.) There are only six numbers, it would be different if there were e.g. 60 of them.

  • The solution to the example, extremely impressive though it is, is not as complicated as it may first appear. His thought process, minus more obvious stuff he may have tried, is likely to have been "I can get to 954 using (100+6)*9, which I can do via (100+6)*3*75/25. I have a 50 left and 50/25 is two, so I can take the 50 off (100+6)*3*75 before dividing by 25". – Tim Down Nov 14 '17 at 23:31
1

An algorithm isn't actually very difficult.

Given two numbers a and b, we can produce the results a + b, abs (a - b) (I don't know if negative numbers are allowed, in which case we can produce a - b and a + b), a * b, and possibly a / b or b / a if the result is an integer. So the possible results are a set of up to five numbers. Call this set S (a, b).

Take six numbers a, b, c, d, e and f.

For each subset of two numbers, find the numbers they can produce.

Then for each subset of three numbers, find the numbers they can produce: S (a, b, c) = S (S (a,b), c) union S (S (a,c), b) union S (S (b,c), a).

Then the same for each subset of 4 or 5 numbers, then for all 6 numbers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.