# Numeric Maze (#60)

**URL:** <https://www.ruby-forum.com/t/numeric-maze-60/225896>\
**Category:** Ruby\
**Created:** [January 2, 2006, 5:10am UTC](https://www.ruby-forum.com/t/numeric-maze-60/225896 "2006-01-02T05:10:16Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [January 2, 2006, 5:10am UTC](https://www.ruby-forum.com/t/numeric-maze-60/225896/1 "2006-01-02T05:10:16Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [January 2, 2006, 5:15pm UTC](https://www.ruby-forum.com/t/numeric-maze-60/225896/2 "2006-01-02T17:15:42Z")

</div>

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