From: Kero <kero@...>
Date: 2006-01-03T06:12:57+09:00
Subject: Re: Numeric Maze (#60)

Here it is, my solution. From mathematical and algorithmic point of view,
you won't find anything new. However:

 - One of the few times that class variables come in handy: I put the
   halve/double operations into Integer and then decided to make the do-all
   method Integer.solve_num_maze but the steps are done in
   Integer#handle_num_maze

 - Both optimizations are done in the method #enqueue

My permanent URL has header, license anouncement and large testsuite (orig
from swaits.com, unaccessible; not updated) included:
   http://members.chello.nl/k.vangelder/ruby/quiz/

The code itself:

class Integer
  def even?
    self[0] == 0
  end

  def odd?
    self[0] == 1
  end

  def halve
    self / 2  if self.even?
  end

  def double
    self * 2
  end

  # add inverse for add_two (we're doing DynProg)
  def sub2
    self - 2
  end

  Step = Struct.new(:dist, :next)

  def self.source; @@source; end
  def self.route; @@route; end
  def self.queue; @@queue; end

  def source; @@source; end
  def route; @@route; end
  def queue; @@queue; end

  def self.solve_num_maze(source, target)
    raise ArgumentError.new("Can't solve from >=0 to <0")  if target < 0 and source >= 0
    raise ArgumentError.new("Can't solve from >0 to 0")  if target <= 0 and source > 0
    @@source = source
    @@route = {}
    @@queue = []
    @@max = [(source + 2) * 2, target * 2].max
    # @@max = [source, target].max << 2  # and other attempts
    queue << target
    route[target] = Step.new(0, nil)
    while (job = queue.shift) != source
      job.handle_num_maze
    end

    result = [source]
    step = source
    while step != target
      step = route[step].next
      result << step
    end
    result
  end

  def enqueue(job)
    # optimization 1, do not go through pending searches when effectively done
    queue.clear  if job == source

    # optimization 2, do not look for solutions where it is not necessary
    queue << job  if job <= @@max
  end

  def handle_num_maze
    if route[double].nil? or route[self].dist + 1 < route[double].dist
      route[double] = Step.new(route[self].dist+1, self)
      enqueue double
    end
    # mind the extra check on existence of #halve
    if halve and (route[halve].nil? or route[self].dist + 1 < route[halve].dist)
      route[halve] = Step.new(route[self].dist+1, self)
      enqueue halve
    end
    if route[sub2].nil? or route[self].dist + 1 < route[sub2].dist
      route[sub2] = Step.new(route[self].dist+1, self)
      enqueue sub2
    end
  end
end

p Integer.solve_num_maze(ARGV[0].to_i, ARGV[1].to_i)