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

I took a look into bi-directional search, and it's really a rewarding 
technique. I predicted a 16-fold performance increase, but it was 12. 
I'm storing the result of both searches in a common array. To keep the 
two solutions separated I use the sign. When the other side, there is a 
connection, between the two growing trees.

I really tried to find something more clever than Simon's solutions, but 
had to give up. Kudos to Simon!

Thanks to everybody, it's been really nice to follow everybody's 
efforts!

Christer

Timings:

    t solve(      2,      9).size, 6    #1
    t solve(     22,     99).size, 8    #2
    t solve(    222,    999).size, 16   #3
    t solve(   2222,   9999).size, 25   #4
    t solve(  22222,  99999).size, 36   #5
    t solve( 222222, 999999).size, 47   #6
    t solve(2222222,9999999).size, 58   #7
    t solve(9999999,2222222).size, 61   #7
    t solve( 999999, 222222).size, 51   #6
    t solve(  99999,  22222).size, 42   #5
    t solve(   9999,   2222).size, 33   #4
    t solve(    999,    222).size, 23   #3
    t solve(     99,     22).size, 13   #2
    t solve(      9,      2).size, 9    #1

Each test consists of two problems.

Test 7:
Simon     1.833 secs
Christer  3.425 secs

Test 6:
Simon     0.321 secs
Christer  0.551 secs
Ryan     37     secs

Test 5:
Simon     0.11  secs
Christer  0.15  secs
Ryan      4.597 secs
Tristan   7.18  secs
Kenneth  13.93  secs
Zed      14.241 secs
Kero     70.6   secs

Test 4:
Chris     2.614 secs

Test 2:
James     0.12  secs


def solve start, target
  return [start] if start == target
  @max = 2 + 2 * [start,target].max
  @back = []
  @back[start] = start
  @back[target] = -target
  @ready = nil
  q1 = [start]
  q2 = [target]
  loop do
    q1 = solve_level(q1, 1)
    break if @ready
    q2 = solve_level(q2, -1)
    break if @ready
  end
  path(@ready[1]).reverse + path(@ready[0])
end

def path(number)
  nr = abs(@back[number])
  [number] + (nr == number ? [] : path(nr))
end

def solve_level(queue, sign)
  @queue = []
  @sign = sign
  queue.each do |number|
    store number, number * 2
    store number, number + 2 * sign
    store number, number / 2 if number[0] == 0
    break if @ready
  end
  @queue
end

def store number, result
  return if result > @max
  return if result <= 0
  if @back[result].nil? then
    @queue.unshift result
    @back[result] = number * @sign
  else
    if sign(@back[result]) == -@sign then
      @ready = number, result
    end
  end
end

def abs(x) x > 0 ? x : -x end
def sign(x) x > 0 ? 1 : -1 end



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