```On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote:

> Problem: Move from the starting point to the target, minimizing the
> number of
> operations.

Here's my simple breadth-first search with a single optimization
(described in comments).  It's not at all fast enough for the big
examples people have been throwing around, but it's pretty simple.

James Edward Gray II

#!/usr/local/bin/ruby -w

# Parse arguments.
unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ }
puts "Usage:  #{File.basename(\$0)} START_NUMBER FINISH_NUMBER"
puts "  Both number arguments must be positive integers."
exit
end
start, finish = ARGV.map { |n| Integer(n) }

# Simple helper methods for determining if divide-by-two operation is
allowed.
class Integer
def even?
self % 2 == 0
end
end

#
# A breadth-first search with a single optimization:  All numbers are
marked as
# "seen" when they are calculated, then all future calculations
resulting in an
# already seen number cause the entire path to be abandoned.  (We've
seen it
# before in equal or less steps, so there's no need to use the
alternate/longer
# path).
#
def solve( start, finish )
return [start] if start == finish

seen  = {start => true}
paths = [[start]]

until paths.first.last == finish
path = paths.shift

new_paths = [path.dup << path.last * 2, path.dup << path.last + 2]
new_paths << (path.dup << path.last / 2) if path.last.even?

new_paths.each do |new_path|
unless seen[new_path.last]
paths << new_path
seen[new_path.last] = true
end
end
end

paths.shift
end

# Run program.
puts solve(start, finish).join(", ")

```