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
, stack
(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