On Sun, 01 Jan 2006 19:27:56 +0100, <horndude77 / gmail.com> wrote:

> For this quiz I took what I made for the word chain quiz and modified
> it a bit.

I did that, too ;-)

My solution uses unidirectional BFS (like many others). The NumericMaze
class is generic, meaning that it can also work with other ops, so
naturally it doesn't have any optimizations for this special problem. I
only limit the search space in the "if \$0 == __FILE__" part.

Dominik

class NumericMaze

OP_DOUBLE = lambda { |x| x * 2 }
OP_HALVE = lambda { |x| x % 2 == 0 ? x / 2 : nil }
OP_ADD_TWO = lambda { |x| x + 2 }

# ops is an array of lambdas, each lambda returns a next step for a
given
# number, or nil if no next step is possible for the given number
def initialize(ops = [OP_DOUBLE, OP_HALVE, OP_ADD_TWO])
@ops = ops
end

def solve(start, target, max_num = nil)
# build chain with simple breadth first search
current = [start]
return current if start == target
pre = { start => nil } # will contain the predecessors
catch(:done) do
until current.empty?
next_step = []
current.each do |num|
@ops.each do |op|
unless (step_num = op[num]).nil?
# have we seen this number before?
unless pre.has_key?(step_num) ||
(max_num && step_num > max_num)
pre[step_num] = num
throw(:done) if step_num == target
next_step << step_num
end
end
end
end
current = next_step
end
return nil # no chain found
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
chain.reverse
end

end

if \$0 == __FILE__
a, b, = *ARGV.map { |str| Integer(str) }
p NumericMaze.new.solve(a, b, [a, b].max.abs * 3)
end