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