Forum: Ruby Numeric Maze (#60)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
unknown (Guest)
on 2006-01-02 06:10
(Received via mailing list)
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
Florian G. Pflug (Guest)
on 2006-01-02 18:15
(Received via mailing list)
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
This topic is locked and can not be replied to.