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 Schroder's solution.

Here's the heart of it:

# Search all possible terms for the ones that fits best.

# 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:

# Call the given block for each term that can be constructed

# 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:

def Integral.each_term_over(source, memo = {}, &block)

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:

http://www.crosswordtools.com/numbers-game/

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