Numeric Maze (#60)

Ruby
121

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

122

Ruby Q. schrieb:

add_two

This was really a nice riddle.
I learned much about understanding and implementing a BFS algo.
Thank you for that.

But I waited for the new riddle to appear :
I guess I have to wait another few days.
But please don’t say ‘Tomorrow's quiz is about…’ and similar.
Well I was bored today :>

I get an 403, when I try to touch /quiz61.html from rubyquiz.com
Maybe it’s is correct that I get that response, maybe not.

Don’t let us wait too long for that dice riddle :>

With kind regards from Duesseldorf, Germany
Robert “Mr. Overheadman” Retzbach

123

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

124

On Jan 6, 2006, at 12:49 PM, Robert R. wrote:

Don’t let us wait too long for that dice riddle :>

Sorry, crazy day. It’s up now.

James Edward G. II