I’ve always wanted to participate in a Ruby quiz and now I finally had
some
time… this is (sad to say) my first submission.
I wasted a lot of time trying to get a recursive solution to work but
stack
overruns kept foiling that effort, so finally I went with this iterative
approach. It seems to work OK, but it’s quite slow on larger problems.
I
finally added a max_path cheat (see code below) to help out some -
however, I
didn’t get around to making max_path dynamic (see comment in code below)
though I have a sneaking suspicion that there is some theorem out there
somewhere for determining the upper bound on the length of the search
given
the absolute value of the difference between start and end.
Phil
##########################################################################
class Integer
def odd?
self%2 == 1
end
def even?
self%2 == 0
end
end
class Value
include Comparable
attr_reader :value
attr_reader :ops
def initialize val
@value = val
@ops = [:double, :add_two, :halve]
end
def <=> other
case other
when Value
@value <=> other.value
when Numeric
@value <=> other
end
end
def has_ops?
! @ops.empty?
end
def next_op
@ops.pop
end
def each_op
@ops.each {|op|
yield op
}
end
def do_op op
self.send op
end
#ops
def double
@value*2
end
def halve
@value/2
end
def add_two
@value+2
end
def to_s
@value.to_s
end
def to_i
@value.to_i
end
end
class NumMazeSolver
MAX_DEPTH = 20
attr_reader :solution
def initialize(start, finish)
@start,@finish = start,finish
@val_list = []
@solution = nil
# Set max value that a given solution will contain:
# -> if the finish value is the largest there is no need to go
# beyond finish*2 in any search
# -> if the start value is the largest there is no need to go
# beyond start*3 in any search:
@largest = finish > start ? finish*2+2 : start*3
#NOTE: max_depth should be dynamic:
#either:
#1) it should be increased if a solution was not found(and employ
memoization)
#2) it should be determined mathematically from the absolute
difference of
# start and finish (I suspect this would be possible, just not
sure how
# to do it - there must be a theorem somewhere (?))
@max_depth = MAX_DEPTH
end
def solve start=@start, finish=@finish
#handle the trivial case:
if start == finish
@solution = [start]
return
end
first = Value.new(start)
@val_list << first
prev_op= first.ops.last
while !(@val_list.empty?) && @val_list.last.has_ops?
next_op = @val_list.last.next_op
unless (next_op == :halve && @val_list.last.to_i.odd?) ||
(next_op == :halve && prev_op == :double) ||
(next_op == :double && prev_op ==:halve)
new_val = @val_list.last.send(next_op)
#ensure there are no cycles before adding new_val to val_list:
#NOTE: I suspect we’re spending a lot of time in find
if new_val < (@largest) && !(@val_list.find{|v| v.to_i ==
new_val})
@val_list << ( Value.new(new_val) )
end
if new_val == finish
puts “Found a solution, length is: #{@val_list.length}” if
$DEBUG
@solution ||= @val_list.clone #first time
if @solution.size > @val_list.size
@solution = @val_list.clone #take a snapshot
puts “new best solution: [ #{@solution.map{|v|
v.to_i}.join(”,")}
] length: #{@solution.length}" if @solution && $DEBUG
end
dest = @val_list.pop
end
end
if (@solution && @val_list.size >= @solution.size ) ||
@val_list.size >
@max_depth
#A solution already exists which is shorter (or max_depth
reached)
#no need to go any further on this branch, prune the search
p = @val_list.pop
end
back_track #take values with empty ops off the list
prev_op = next_op
end #while
end
back_track: clear out entries with empty ops list
def back_track
while @val_list.last && !@val_list.last.has_ops?
poppedval = @val_list.pop
end
end
def to_s
@solution.map{|v| v.to_s }.join(’,’)
end
end
if $0 == FILE
require ‘benchmark’
include Benchmark
bm(6) do |x|
#s = Solver.new(2,9)
puts “9 -> 2”
s =NumMazeSolver.new(9,2)
x.report(“9->2”) {s.solve}
puts s.solution.map{|v| v.to_i }.join(",")
puts “2 -> 9”
s =NumMazeSolver.new(2,9)
x.report(“2->9”) {s.solve}
puts s.solution.map{|v| v.to_i }.join(",")
s =NumMazeSolver.new(1,25)
x.report(“1->25”) {s.solve }
puts s.solution.map{|v| v.to_i }.join(",")
#this one takes a while on my slow machine...
s =NumMazeSolver.new(22,999)
x.report("22->999") {s.solve }
puts s.solution.map{|v| v.to_i }.join(",")
end
end