Numeric Maze (#60)


#1

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


#2

Phil T. wrote:

the absolute value of the difference between start and end.
Let’s say you need the find a “path” from a to b. There are two cases:
.) a < b
if a-b is even
do add_two until you reach b.
else
double
add_two
halve (now it’s even)
do add_two until you reach b
end
.) a > b
while a > b
if a is even
halve
else
double
add_two
halve (now it’s even)
halve
end
end

For a < b, you need as most three operations until the difference is
even.
Then you’ll need at most ceil((b-a)/2) operations until you reach b.
So the path-len for a < b is bounded by 3+ceil((b-a)/2).

For b < a, you first need to make b small then a. You’ll need
ceil(log2(b/a)) steps,
each containing 4 operations in the worst case. Youl’’ end at floor(a/2)
at worst,
so you’ll need 3+ceil((a-floor(a/2)/2) operations to reach a.
This gives a bound of 4*ceil(log2(b)-log2(a)) + ceil(a/4) + 4.

greetings, Florian Pflug