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

on 2006-01-02 06:10

on 2006-01-02 18:15

```
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
```