[QUIZ] Numeric Maze (#60)

[Christer Nilsson]

I can not accept the title of fastest solution.

I think there are a lot of winners here. Your code executed fastest for
one problem. It's quite difficult to filter out a single winner. A lot
of different problems has to be defined. So, the person owning the
problem formulation privilege, has all the power. One remedy for this
would be to let every participant suggest one problem (start and target)
each. Then every solver has to solve all suggested problems, and the
solvers will get a score according to their rank for each individual
problem. That's a lot to administer. A cut off time has to be decided,
say one second. And then we have the problem with "dirty" integers, some
solutions leave after execution. Should the clean up time be included?

"Dirty" Integer: By attaching data to the Integer objects, like "parent"
and "queue", Arrays can be avoided. But the next call to "solve" will be
affected, if the Integers are not clean. See Quiz#60.20, line 2.

As I submitted this Quiz, I wouldn't like to be part af that contest.

Did you do other things than eliminating method calls?

Inline code only account for an improvement of 7%, so the answer is yes.

If you did other things, I'd be interested to see it, still.

I've sent the code to James. Eventually it will published in his
wrap-up. If not, it will be submitted to the ML.

However, I need 21 seconds for 868056 -> 27 so I would assume that
searching for prefixes, or the approach from two sides has lots of potential.

Agreed, searching from two sides could probably gain a lot. If we have a
distance from start to target of 10, with an average branching factor of
2, the workload should be proportional to 1024. Starting from both
sides, the workload should be something like 32 + 32 = 64, with a
potential of being 16 times faster. I haven't even tried this approach,
yet.

Christer

 

[James Edward Gray II]

I've sent the code to James. Eventually it will published in his
wrap-up. If not, it will be submitted to the ML.

It's no secret. Here's the code:

Interesting optimizations
=========================
To give you a sense of what can be done to optimize, I refactored
Keros solution.

Most important, in this test suite, was to start with the larger
number. If the numbers are almost equal, this will give nothing.

The Queue operations are very important. Execution time can be more
than halved.

Using Arrays instead of Hashes also saves time, if possible.

# Optimizations introduced:
# 71.723 0% Seconds before optimization
# a 1.938 97% Start with the larger number
# b 1.642 18% Refactor enqueue/handle_num_maze
# c 1.533 7% Make code inline. Eleven defs removed
# d 1.052 31% Skip the Struct. No need to keep track of dist
# e 0.441 58% Use pop/unshift instead of shift/push
# f 0.371 16% Make route an Array instead of a Hash

class Integer
def enqueue(job)
return if !@@route[job].nil?
@@route[job] = self
@@queue.clear if job == @@target
@@queue.unshift job if job <= @@max
end
def path() [self] + (self == @@source ? [] : @@route[self].path) end
end

def solve number,target
number > target ? solver(number,target,2) : solver
(target,number,-2).reverse
end

def solver(source, target, adder)
@@source = source
@@target = target
@@route = []
@@queue = [source]
@@max = 2 + 2 * [source, target].max
@@route[source] = nil
while (job = @@queue.pop ) != target
job.enqueue(job * 2)
job.enqueue(job / 2) if job[0] == 0
job.enqueue(job + adder)
end
target.path
end

# Original code by Kero:
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.newdist, :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(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)

This test suite was used above:
t solve( 2, 9).size, 6
t solve( 22, 99).size, 8
t solve( 222, 999).size, 16
t solve( 2222, 9999).size, 25
t solve(22222,99999).size, 36
t solve(99999,22222).size, 42
t solve( 9999, 2222).size, 33
t solve( 999, 222).size, 23
t solve( 99, 22).size, 13
t solve( 9, 2).size, 9

James Edward Gray II

 

[matthew.moss.coder]

Yup, my solution is really slow. I made a minor change which reduces
the search space a little (and avoids things such as double followed by
halve, and v-v). Still rather slow, but I didn't expect it to be fast.

class Integer
def even?
self & 1 == 0
end

def maze_adj
if even?
[self + 2, self * 2, self / 2]
else
[self + 2, self * 2]
end
end
end


def solve(a, b)
known = []

i = 0
steps = [[a]]
known << a

until steps.include?(b)
i += 1
steps = []
steps[i-1].each do |x|
x.maze_adj.each { |y| steps << y unless known.include?(y) }
end
known.concat steps
end

i -= 1
path =
i.downto(0) do |k|
s = steps[k].find_all { |x| x.maze_adj.include? path.last }
path << s.sort_by { rand }.first
end

path.reverse
end


# Examples
p solve(9, 2)
p solve(2, 9)
p solve(22, 99)
p solve(222, 999)

 

[Simon Kröger]

Simon wrote:




my subproblem solution to (868056,651040) gave the same result as your,
in 76 secs.

I investigated the ideas suggested by Ilmari and Greg, but found that
there is no way of knowing if the result is optimal. The result are
impressing, but misses often trivial cases. It seems as hard to patch
the non optimal solution as it is to solve it normally.

Are you using a different approach?

Christer

Oops, sorry i kind of 'lost' this thread..

My approach isn't that different but a little bit more optimized.
I use strings instead of hashs (or arrays like you do) to store the
information (and i only store which operation leads us there, ?X is
an empty field, ?M - multiply, ?D - divide, ?A - add, ?S - sub). I
need ?S (Sub 2) because search is done from both sides.

Well, here it is, it solves the the subproblem in 0.062s.

---------------------------------------------------------------------

require 'set'

def find_path from, to
pathf = ''.ljust([from + 2, to + 2].max * 2, 'X')
pathb = pathf.dup
pathf[from] = ?F
pathb[to] = ?F

forward, backward, newbees = [from], [to], []

loop do
forward.each do |n|
pathf[newbees.push(n + 2).last] = ?S if pathf[n+2] == ?X
pathf[newbees.push(n + n).last] = ?D if pathf[n+n] == ?X
pathf[newbees.push(n / 2).last] = ?M if (n%2) == 0 && pathf[n/2]
== ?X
end
forward, newbees = newbees, []
forward.each {|n|return pathf, pathb, n if pathb[n] != ?X}

backward.each do |n|
pathb[newbees.push(n - 2).last] = ?A if n > 1 && pathb[n-2] == ?X
pathb[newbees.push(n + n).last] = ?D if pathb[n+n] == ?X
pathb[newbees.push(n / 2).last] = ?M if (n % 2) == 0 &&
pathb[n/2] == ?X
end
backward, newbees = newbees, []
backward.each {|n|return pathf, pathb, n if pathf[n] != ?X}
end
end

def solve from, to
return nil if from < 0 || to <= 0
return [from] if from == to
pathf, pathb, n = find_path(from, to)

result = [n]
[pathf, pathb].each do |path|
loop do
case path[result.last]
when ?A then result << result.last + 2
when ?S then result << result.last - 2
when ?D then result << result.last / 2
when ?M then result << result.last * 2
else break
end
end
result.reverse!
end
result.reverse
end

from, to = (ARGV.shift || 868056).to_i, (ARGV.shift || 651040).to_i

t = Time.now
p solve(from, to)
puts "Time: #{Time.now - t}"

 

[Christer Nilsson]

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

 

[Christer Nilsson]

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

 

[Robert Retzbach]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Christer Nilsson

You have a starting point and a target, say 2 and 9.

You have a set of three operations:

double
halve (Odd numbers cannot be halved.)
add_two

Problem: Move from the starting point to the target, minimizing the number of
operations.

Examples:

solve(2,9) # => [2,4,8,16,18,9]
solve(9,2) # => [9,18,20,10,12,6,8,4,2]

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

 

[James Edward Gray II]

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

Sorry, crazy day. It's up now.

James Edward Gray II