On Mon, Nov 15, 2004 at 03:25:54AM +0900, Brian Schr?der scribed:

> I recursively generate each possible term, and evaluate it. In
> my recursive generation process, each subterm is generated multiple
> times, so I used optional memoization to speed up the search. An
> exhaustive search takes around 300s without and 110s with memoization,
> but memoization uses a lot of ram.

   Sounds like my solution, which is appended below, is
pretty similar.  The only cleverness in it is doing things
pairwise to easily eliminate commutativity when possible.  The
code is a little opaque - sorry. :)  Typically finds a solution within
12 seconds if you use the memoization, and 120 seconds if you
don't.  I have another version that uses less memory by more
aggressively pruning the space, but because it does more tests,
it actually ends up being a little slower.   Oops.

  Usage:  quiz.rb [-m] [target] [val1] [val2] ... [valn]

I don't suggest running it with more than 6 sub-values, however,
unless you're really patient.  the runtime is roughly:

   6^5 * 6*5 * 5*4 * 4*3 * 3*2 * 2*1

It's not elegant, but it works.  I do apologize profusely
for my terribly lame use of "raise" to exit early from the
processing loop.  But it saved a lot of typing. :)

   -Dave

#!/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 }

$closest_diff = target
$closest_stack = nil
$nodupes = Hash.new if $lots_of_memory
$itercount = 0

def fs(stack, target, source)
  $itercount += 1
  recent = source[-1]
  raise "#{stack[-1]}"  if (recent == target)
  return false if recent == 0
  if ($lots_of_memory)
    wholeid = source.sort.join(" ")
    return false if ($nodupes.has_key?(wholeid))
    $nodupes[wholeid] = true
  end
  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|
    ival, istack = source[i], stack[i]
    (i+1...source.length).each do |j|
      jval, jstack = source[j], stack[j]
      # Linear space duplicate suppression is cheap;  use always
      myid = (ival < jval) ? "#{ival}-#{jval}" : "#{jval}-#{ival}"
      next if (observed[myid])
      observed[myid] = true
      ns = source[0...i] + source[i+1...j] + source[j+1..-1]
      nt = stack[0...i] + stack[i+1...j] + stack[j+1..-1]
      fs(nt + ["(#{istack} + #{jstack})"], target, ns + [ival + jval])
      if (ival != jval)
        fs(nt + ["(#{istack} - #{jstack})"], target, ns + [ival - jval])
        fs(nt + ["(#{jstack} - #{istack})"], target, ns + [jval - ival])
      end
      if (ival != 1 && jval != 1)
        fs(nt + ["(#{istack} * #{jstack})"], target, ns + [ival * jval])
        if (0 == (ival % jval))
	  fs(nt + ["(#{istack} / #{jstack})"], target, ns + [ival / jval])
        end
        if (0 == (jval % ival))
	  fs(nt + ["(#{jstack} / #{istack})"], target, ns + [jval / ival])
        end
      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