From: Christer Nilsson <janchrister.nilsson@...>
Date: 2006-01-05T22:46:02+09:00
Subject: Re: Numeric Maze (#60)

There is a small time fraction possible to squeeze out from Simon's 
solution.
These lines, by Simon, are trying to detect if contact has been made, in 
the bi-directional search:

  forward.each {|n|return pathf, pathb, n if pathb[n] != ?X}
  backward.each {|n|return pathf, pathb, n if pathf[n] != ?X}

If pathf and pathb are merged into one string, this check be done 
without iteration. To be able to do that we must distinguish between 
numbers reached by going forward and numbers reached by going backwards. 
This can be done by using lower and upper case letters:

Forward character set:
 ?f starting number
 ?a add 2
 ?d divide
 ?m multiply

Backward character set:
 ?F target number
 ?S subtract 2
 ?D divide
 ?M multiply

 ?X unreached number

Result:

t solve(22222222,99999999).size, 58   #8
t solve(99999999,22222222).size, 61   #8
Christer   5.108 secs
Simon      6.175 secs

The code is ugly, please turn down the light:

# store operations instead.
# one common string
# use letters for operations

def solve start, target
  return [start] if start == target
  @MAX = 1 + 2 + 2 * [start,target].max

  op = ''.ljust(@MAX, 'X')
  op[start] = ?f
  op[target] = ?F

  @ready = nil
  q1 = [start]
  q2 = [target]
  loop do
    q1 = solve1(q1,op)
    break if @ready
    q2 = solve2(q2,op)
    break if @ready
  end
  path(@ready[0],op).reverse + path(@ready[1],op)
end

def path(n,op)
  case op[n]
  when ?A,?a: [n] + path(n-2,op)
  when ?D,?d: [n] + path(n*2,op)
  when ?S,?s: [n] + path(n+2,op)
  when ?M,?m: [n] + path(n/2,op)
  when ?F,?f: [n]
  end
end

def solve1(queue,op)
  q = []
  queue.each do |n|

#   store1 ?m, n, n * 2 if n+n<=@MAX
    result = n + n
    if result <= @MAX then
      if op[result]==?X then
        q.push result
        op[result] = ?m
      else
        @ready = n, result if op[result] < ?a
      end
    end

#   store1 ?a, n, n + 2 if n+2<=@MAX
    result = n + 2
    if result <= @MAX then
      if op[result]==?X then
        q.push result
        op[result] = ?a
      else
        @ready = n, result if op[result] < ?a
      end
    end

#   store1 ?d, n, n / 2 if n.modulo(2) == 0
    if n.modulo(2) == 0 then
      result = n / 2
      if op[result]==?X then
			  q.push result
			  op[result] = ?d
		  else
			  @ready = n, result if op[result] < ?a
		  end
    end

    break if @ready
  end
  q
end

def solve2(queue,op)
  q = []
  queue.each do |n|

#   store2 ?M, n, n * 2 if n+n<=@MAX
    result = n + n
    if result <= @MAX then
      if op[result]==?X then
        q.push result
        op[result] = ?M
      else
        @ready = n, result if op[result] >= ?a
      end
    end

#   store2 ?S, n, n - 2 if n>2
    result = n - 2
    if result >= 1 then
      if op[result]==?X then
        q.push result
        op[result] = ?S
      else
        @ready = n, result if op[result] >= ?a
      end
    end

#   store2 ?D, n, n / 2 if n.modulo(2) == 0
    if n.modulo(2) == 0 then
      result = n / 2
      if op[result]==?X then
			  q.push result
			  op[result] = ?D
		  else
			  @ready = n, result if op[result] >= ?a
		  end
    end

    break if @ready
  end
  q
end

#def store1 op, number, result
  #if result.op.nil? then
    #@queue.push result
    #result.op = op
  #else
    #@ready = number, result if result.op < ?a
  #end
#end

#def store2 op, number, result
  #if result.op.nil? then
    #@queue.push result
    #result.op = op
  #else
    #@ready = result, number if result.op >= ?a
  #end
#end

-- 
Posted via http://www.ruby-forum.com/.