[SUMMARY] Countdown (#7)

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