by Brian Candler
One of the longest-running quiz shows on UK TV is called Countdown, and has a "numbers round". There are some cards laid face down in front of the host - the top row contains 'large' numbers (from the set 25, 50, 75, 100), and the rest are 'small' (1 to 10). Six cards are picked and displayed: the choice is made by one of the contestants, who typically will ask for one large number and five small ones.
Next, a machine called "Cecil" picks a target number between 100 and 999 at random. The contestants then have 30 seconds to find a way of combining the source numbers using the normal arithmetic operators (+, -, *, /) to make the target number, or to get as close as possible.
Each source card can be used no more than once. The same applies to any intermediate results, although of course you don't have to explicitly show the intermediate results.
Example: source 100 5 5 2 6 8, target 522
100 * 5 = 500
5 + 6 = 11
11 * 2 = 22
500 + 22 = 522
or more succinctly, (5*100)+((5+6)*2) = 522
Another solution is (100+6)*5-8 = 522
Normal arithmetic rules apply, and in particular you are not allowed to use integer rounding. That is, 7 divided by 3 is 2 1/3, not 2.
The quiz is to write a program which will accept one target number and a list of source numbers, and generate a solution which calculates the target or a number as close to the target as possible.
Quiz Summary
I think I need to start charging Dennis Ranke by the e-mail! Seriously, it was interesting being able to follow the late stages of development for a couple of the solutions this time around.
I found this problem very interesting and made a couple attempts to solve it myself, though these attempts didn't produce anything worth sharing. I did gain a great appreciation for what's involved, so let me walk you through the highlights.
At first glance, the search space for this problem looks very large. The six source numbers can be ordered various ways, and you don't have to use all the numbers. Beyond that, you can have one of four operators between each pair of numbers. Finally, consider that 1 * 2 + 3 is different from 1 * (2 + 3). That's a lot of combinations.
However, we can prune that large search space significantly. Let's start with some simple examples and work our way up. Addition and multiplication are commutative, so:
1 + 2 = 3 and 2 + 1 = 3
1 * 2 = 2 and 2 * 1 = 2
We don't need to handle it both ways. One will do.
Moving on to numbers, the example in the quiz used two 5s as source numbers. Obviously, these two numbers are interchangeable. The first 5 plus 2 is 7, just as the second 5 plus 2 is 7.
What about the possible source number 1? Anything times 1 is itself, so there is no need to check multiplication of 1. Similarly, anything divided by 1 is itself. No need to divide by 1.
Let's look at 0. Adding and subtracting 0 is pointless. Multiplying by 0 takes us back to 0, which is pretty far from a number between 100 and 999 (our goal). Dividing 0 by anything is the same story and dividing by 0 is illegal, of course. Conclusion: 0 is useless. Now you can't get 0 as a source number, but you can safely ignore any operation(s) that result in 0.
Those are all single number examples, of course. Time to think bigger. What about negative numbers? Our goal is somewhere between 100 to 999. Negative numbers are going the wrong way. They don't help, so you can safely ignore any operation(s) that results in a negative number.
Fractions are debatable. The quiz clearly allowed for them, but it came up in discussion that the actual game show does not. Even when you use them, they're of limited help since the goal is always a whole number. Eventually, you'll need to do something to that fractional value to bring it back to a whole number. That takes a minimum of half your operands (two to make a fraction and at least one to eliminate the fractional value). That said, they do increase your options, but leaving them out makes for faster runs and mirrors the game show.
Finally, consider:
(5 + 5) / 2 = 5
The above is just busy work. We already had a 5; we didn't need to make one. Any set of operations that result in one of their operands can be ignored.
Using simplifications like the above, you can get the search space down to something that can be brute-force searched pretty quickly, as long as we're only dealing with six numbers.
Dennis Ranke submitted the most complete example of pruning. That solution is very well commented and I encourage all who are interested to look through it.
If you would like to see a very simple, if slow, solution to the problem, have a look at Junghyun Kim's submission.
For this summary, I want to take a deeper look at Brian Schröder's solution. Here's the heart of it:
# Systematically create all terms over all subsets the set of
# numbers in source, and find the one that is closest to target.
#
# Returns the solution that is closest to the target.
#
# If a block is given, calls the block each time a better or
# equal solution is found.
#
# As a heuristic to guide the search sorts the numbers ascending.
def solve_countdown(target, source, use_module)
source = source.sort_by{|i|-i}
best = nil
best_distance = 1.0/0.0
use_module::each_term_over(source) do | term |
distance = (term.value - target).abs
if distance <= best_distance
best_distance = distance
best = term
yield best if block_given?
end
end
return best
end
This method takes the "target" and "source" numbers in addition to a Module, which I'll come back to in a minute, as parameters. The first line is the sort mentioned in the comment. Then "best" and "best_distance" are initialized to nil and Infinity, to track the best solution discovered so far.
After the setup, the method calls into the each_term_over() method, provided by the Module it was called with. The Module to use is determined by the interface code (not shown) based on the provided command-line switches. There are four possible choices. Two deal with fractions while two are integer only, and there is a recursive and "memoized" version for each number type. The program switches solving strategies based on the user's requests. (This is a nice use of the State design pattern.)
Here is each_term_over() in the Module Recursive::Integral:
# over a set of numbers.
#
# Recursive implementation, that calls a block each time a new
# term has been stitched together.
# Returns each term multiple times.
#
# This version checks, that only integral results may result.
#
# Here I explicitly coded the operators, because there is not
# much redundance.
#
# This may be a bit slow, because it zips up through the whole
# callstack each time a new term is created.
def Integral.each_term_over(source)
if source.length == 1
yield source[0]
else
source.each_partition do | p1, p2 |
each_term_over(p1) do | op1 |
yield op1
each_term_over(p2) do | op2 |
yield op2
if op2.value != 0
yield Term.new(op1, op2, :+)
yield Term.new(op1, op2, :-)
if op2.value != 1 and op1.value % op2.value == 0
yield Term.new(op1, op2, :'/')
end
end
if op1.value != 0
yield Term.new(op2, op1, :-)
if op1.value != 1
if op2.value % op1.value == 0
yield Term.new(op2, op1, :'/')
end
if op2.value != 0 and op2.value != 1
yield Term.new(op1, op2, :*)
end
end
end
end
end
end
end
end
This method recursively generates terms in every possible combination. This is a key point to a working solution and my own source of failure. I tried adding a number at a time, which generates solutions looking like:
(((num op num) op num) op num)...
The tricky example posted to Ruby Talk by daz (Target: 926, Source: 75, 2, 8, 5, 10, 10) shows off the folly of this approach. The only answer is:
(75 - 5 + 8) * (2 + 10) - 10
As you can see, the 2 + 10 term must be built separately from the 75 - 5 + 8 term and then the two can be combined.
Getting back to the code above, the each_partition() method it uses was added to Array, in a different section of the code (not shown). It works as expected, returning "each true partition (containing no empty set) exactly once". Term objects (not shown), just manage their operands and operator, providing mainly string representation and result evaluation.
The block we're yielding to in here is the block passed by solve_countdown(), which we examined earlier. It is simply keeping track of the best solution generated so far.
As an aside, I'm not convinced the yields to "op1" and "op2" are needed. I commented them out and was unable to produce a failure, but it's possible I just didn't try the right tests.
The interesting part of all this is the same method in a different module. Here's each_term_over() from Memoized::Integral:
return memo[source] if memo[source]
result = []
if source.length == 1
result << source[0]
else
source.each_partition do | p1, p2 |
each_term_over(p1, memo, &block).each do | op1 |
each_term_over(p2, memo, &block).each do | op2 |
if op2.value != 0
result << Term.new(op1, op2, :+)
result << Term.new(op1, op2, :-)
if op2.value != 1 and op1.value % op2.value == 0
result << Term.new(op1, op2, :'/')
end
end
if op1.value != 0
result << Term.new(op2, op1, :-)
if op1.value != 1
if op2.value % op1.value == 0
result << Term.new(op2, op1, :'/')
end
if op2.value != 0 and op2.value != 1
result << Term.new(op1, op2, :*)
end
end
end
end
end
end
end
result.each do | term | block.call(term) end
memo[source] = result
end
The result of this method is the same, but it uses a technique called "memoization" to work faster. When Terms are generated in here, they get added to the hash "memo". After that, all the magic is in the very first line, which simply skips all the work the next time those source numbers are examined.
This leans on memory (the hash of stored results) for speed (no repeat work). That's why the solution provides other options too. Maybe the target platform won't have the memory to spare.
This is a handy technique showcased in a nice implementation and thus worth a look, I think.
David G. Andersen submitted a similar solution with a lot of raw speed, but it was a little harder to follow. (David the Code Style Police are on their way. Just hand over the keyboard... It's for your own good.)
If you would like to play with an interactive solver without pulling down the Ruby code for these solutions, check out this great link posted by daz:
As usual, I offer my thanks to the quiz maker and takers.
We have two more contributed quizzes to come. (Great News!!!) Look for Jim Menard's quiz, tomorrow morning...
