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