On Mon, Nov 15, 2004 at 08:48:24AM +0900, Dennis Ranke scribed:
> Here is a small update to my solution. A simple optimization speeds up 
> the solver by a factor of nearly two. Now I'm down to 5 seconds for the 
> worst case on this machine :)

Thanks for the inspiration to improve my code a little more. :-)
This version uses a search trie to perform duplicate elimination,
and steals Dennis's point about not needing to worry about negative
numbers (since there's also a "minus" operator.. can't believe I forgot
that the first time).  The code is a little cleaner, and the memory
utilization is down to about 2.5 megabytes for the memoized version,
since it now knows that if you test "25 5 3" you don't need to test "25 5"
or "25".

the search trie addition is kind of cute.  It's a nice demonstration
of how easy it can be to implement some cool data structures in Ruby. :)

Runtime is about 2.7 seconds using -m for an unsolvable case,
and 2 seconds for the "hard" solvable case of 926  75 2 8 5 10 10  that
someone posted earlier.   Without -m, it takes about 12 seconds / 5
seconds, respectively, but there's no reason not to use memoization since
it consumes so little memory now.

#!/usr/local/bin/ruby

# The exit from the processing loop is a little ugly.  Would be
# better to cascade the return values, but that required more
# tests. ;-)
#
# Use with "-m" to memoize parts of the solution space and avoid
# duplicate configurations.  Requires about 14 megs of ram;  runs
# about 10x faster.

raise "usage:  quiz.rb [-m] [target] [source1] [source2] ...\n" if ARGV.length < 2

$lots_of_memory = ARGV.delete("-m")
target, *source = ARGV.map { |a| a.to_i }

class TreeMap
  # Quick and dirty search trie for duplicate detection / elimination
  def initialize()
    @root = Hash.new
  end

  def test_and_add(arr)
    cur = @root
    found = true
    arrs = arr.sort
    while (head = arrs.pop)
      found = false unless cur.has_key?(head)
      cur = cur[head] ||= Hash.new
    end
    return found
  end 
end

$tm = TreeMap.new if $lots_of_memory
$closest_diff = target
$closest_stack = nil
$itercount = 0

def fs(stack, target, source)
  $itercount += 1
  recent = source[-1]
  raise "#{stack[-1]}"  if (recent == target)
  return false if ($lots_of_memory && $tm.test_and_add(source))
  if (recent - target).abs < $closest_diff
    $closest_diff = (recent - target).abs
    $closest_stack = stack[-1]
  end
  return false if (source.length == 1)
  i = j = ns = nt = ival = istack = jval = jstack = myid = 0
  observed = Hash.new
  (0...source.length).each do |i|
    (i+1...source.length).each do |j|
      ns = source[0...i] + source[i+1...j] + source[j+1..-1]
      nt = stack[0...i] + stack[i+1...j] + stack[j+1..-1]
      i, j = j, i if (source[i] < source[j])
      ival, istack = source[i], stack[i]
      jval, jstack = source[j], stack[j]
      # Linear space duplicate suppression is cheap;  use always
      myid = "#{ival}-#{jval}"
      next if (observed.has_key?(myid))
      observed[myid] = true
      fs(nt + ["(#{istack} + #{jstack})"], target, ns + [ival + jval])
      fs(nt + ["(#{istack} - #{jstack})"], target, ns + [ival - jval]) unless ival==jval
      if (jval > 1)
        if (ival != jval && 0 == (ival % jval))
          fs(nt + ["(#{istack} / #{jstack})"], target, ns + [ival / jval]) 
        end
        fs(nt + ["(#{istack} * #{jstack})"], target, ns + [ival * jval])
      end
    end
  end
end

begin
  raise "Source contains target." if source.include? target
  fs(source.dup, target, source)
  p $closest_stack
rescue => err
  print "Done: #{err}\n"
ensure
  print "Itercount: #{$itercount}\n"
end