[QUIZ] Numeric Maze (#60)

[Kero]

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.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_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)

 

[Simon Kröger]

Hello dear quizzers,

could someone please confirm (or disprove) that this i correct?

[222222222, 222222224, 111111112, 55555556, 27777778, 27777780,
13888890, 13888892, 6944446, 6944448, 3472224, 1736112, 868056, 434028,
217014, 217016, 108508, 54254, 54256, 27128, 13564, 6782, 6784, 3392,
1696, 848, 424, 212, 106, 108, 54, 27, 29, 31, 33, 35, 37, 39, 78, 156,
158, 316, 632, 634, 1268, 1270, 2540, 2542, 5084, 5086, 10172, 20344,
40688, 40690, 81380, 162760, 325520, 651040, 1302080, 1302082, 2604164,
2604166, 5208332, 10416664, 10416666, 20833332, 41666664, 41666666,
83333332, 166666664, 166666666, 333333332, 666666664, 666666666, 333333333]

75 items

Time: 62.015s

There seems to be more potential in the brute force attack than i
thought possible.

cheers

Simon

 

[Zed Lopez]

Kinda ugly, but pretty fast. Breadth first search alternating from each
end. It's the same basic algorithm I used for a Perl Quiz of the Week
Word Ladder:

http://perl.plover.com/~alias/list.cgi?mss:99:200409:dlfkjbmmdljnajmfagki

Instead of CPAN's Tree::Simple, I'm using unidirectional (nodes can find
their parents, but not their children) n-ary trees implemented in
hashes. I don't explicitly implement the don't-double-then-halve
optimization, but I get it as a side-effect of my use of node_index to
index all values already in the tree so I can avoid creating new nodes
for already existing values.

~ (300) time ./numeric_maze5.rb 8740 7630
[8740, 4370, 4372, 2186, 2188, 1094, 1096, 548, 274, 276, 138, 140, 70,
72, 36, 38, 19, 21, 23, 25, 27, 29, 58, 116, 118, 236, 238, 476, 952,
1904, 1906, 3812, 3814, 7628, 7630]

real 0m2.280s
user 0m2.105s
sys 0m0.017s
~ (301) time ./numeric_maze5.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87,
89, 91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496,
12498, 24996, 24998, 49996, 49998, 99996, 99998, 199996, 199998, 99999]

real 0m2.966s
user 0m2.796s
sys 0m0.016s


def success(x, node1, node2)
node1, node2 = node2, node1 unless x.zero?
p chain(node1).reverse + chain(node2)
exit
end

def chain(node)
(result ||= []) << node[:num] and node = node[arent] until node.nil?
result
end

tree = []
node_index = []
ARGV.each { |x|
root = {:num => x.to_i, arent => nil}
tree << [root]
node_index << { root[:num] => root }
}

x = 1
while x = 1 - x: # cycle between 0 and 1 in infinite loop
next_nodes = []
tree[x].each {|node| # for each node in current level
[node[:num]*2,
node[:num]%2 == 0 ? node[:num]/2 : 0,
x.zero? ? node[:num] + 2 : node[:num] - 2].uniq.select {|n|
n > 0 and !node_index[x].key?(n)}.each {|newnum|
# if we have a path to this result in the other tree, we're done
success(x, node, node_index[1-x][newnum]) if
node_index[1-x].key?(newnum) # only way out of the loop
next_nodes << node_index[x][newnum] = { :num => newnum, arent
=> node } # build the next level
}
}
tree[x] = next_nodes
end

 

[Simon Kröger]

Thanks for the testcases,

i just found a shorter one for (700, 1)

[700, 350, 352, 176, 88, 44, 22, 24, 12, 6, 8, 4, 2, 1]

and a different one for

test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]:
<[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78,
156, 158]> expected but was
<[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78,
156, 158]>.

cheers

Simon

Steve, there seem to be at least one difference:

<[300, 302, 304, 152, ... , 2, 1]> expected but was
<[300, 150, 152, ... , 2, 1]>.

Thanks Christer...

I'll fix that one. My search was far from exhaustive.

--Steve

 

[Kenneth Collins]

I always learn something from Ruby Quiz! Use of a ceiling (as presented
by many quizzers) greatly speeds up my solution and makes its
performance competitive with the non-binary solutions. This change took
only two lines of code.

- Ken


#!/usr/bin/env ruby
#
# Ruby Quiz #60, Numeric Maze
# http://www.rubyquiz.com/quiz60.html
#
# 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 solution builds a tree with each node having up to
# three subnodes, one for each operation. It builds the
# tree one level at a time and checks for a solution before
# proceeding down to the next level. This brute force
# approach performs much better after adding two optimizations
# suggested by Dominik Bathon and others: track what numbers
# have been visited and do not build subnodes for previously
# visited numbers; and use a ceiling to disregard numbers
# large enough that they will not be needed in the solution.
#

module NumericMaze

class Node
attr_accessor arent, :value, :children

def initialize(parent, value)
@parent = parent
@value = value
@children = {}
end

def double
@children[:double] = Node.new(self, @value * 2)
end

def halve
return :halve_failed if @value % 2 != 0
@children[:halve] = Node.new(self, @value / 2)
end

def add_two
@children[:add_two] = Node.new(self, @value + 2)
end

end

def NumericMaze.solve(start, target)
ceiling = [start, target].max*2+2
# Initialize node arrays with root node
node_arrays = []
node_arrays[0] = []
node_arrays[0] << Node.newroot, start)
# Initialize hash of visited numbers; do not
# visit a number twice (thanks to Dominik Bathon)
visited_numbers = {}
# Check for a solution at each level
level = 0
while true
# Examine nodes at this level and
# build subnodes when appropriate
node_arrays[level+1] = []
node_arrays[level].each do |node|
# Skip if method "halve" failed
next if node == :halve_failed
# Skip if number exceeds ceiling
next if node.value > ceiling
# Skip if this number has been tried already
next if visited_numbers[node.value]
visited_numbers[node.value] = true
# Has a solution been found? If yes,
# print it and exit
if node.value == target
# Build array of values used
# (from bottom up)
value_array = []
node_ptr = node
while true
break if node_ptr.parent == :root
value_array << node_ptr.value
node_ptr = node_ptr.parent
end
# Display answer and exit
p [start] + value_array.reverse
exit
end
# Collect new results at this level
node_arrays[level+1] << node.double
node_arrays[level+1] << node.halve
node_arrays[level+1] << node.add_two
end
level += 1
end
end

end

########################################

if ARGV.length != 2
puts "Usage: #{$0} <start> <target>"
exit
end

NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)

 

[Stephen Waits]

Thanks for the testcases,

You're welcome. Thanks for trying them.

--Steve

 

[Christer Nilsson]

Hello dear quizzers,

could someone please confirm (or disprove) that this i correct?

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

 

[Christer Nilsson]

okay here's my shot at the quiz, it's quite large for such a simple
problem, but i couldn't resist to use
:* in my code ;-)

42,

you seem to produce a non optimal solution:

[222, 224, 112, 56, 58, 60, 62, 124, 248, 496, 498, 996, 998, 1996,
1998, 999]
expected but was
[222, 111, 113, 115, 117, 119, 121, 123, 246, 248, 496, 498, 996, 1992,
1994, 997, 999]

(17 steps instead of 16)

Christer

 

[Wesley J. Landaker]

--nextPart1569002.vPnC8pzglV
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

and a different one for
test_minus_one_two_three_five_and_ten(TestNumericMaze) [quiz60.rb:448]:
<[159, 318, 320, 160, 80, 40, 20, 10, 5, 7, 9, 18, 36, 72, 74, 76, 78,
156, 158]> expected but was
<[159, 318, 320, 160, 80, 40, 20, 10, 12, 14, 16, 18, 36, 38, 76, 78,
156, 158]>.

(BTW, the second on there *is* shorter. =3D)

=2D-=20
Wesley J. Landaker <[email protected]> <xmpp:[email protected]>
OpenPGP FP: 4135 2A3B 4726 ACC5 9094 0097 F0A9 8A4C 4CD6 E3D2

--nextPart1569002.vPnC8pzglV
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQBDuddU8KmKTEzW49IRAuxXAJ9UoyIOD8DpP6MlFc/vimIvb8JecQCfbNL8
KQrAQvUMi2STPGeRyMMmVmA=
=u4Ze
-----END PGP SIGNATURE-----

--nextPart1569002.vPnC8pzglV--

 

[Peter Burns]

Ok, It's a day late, but I've got my solution. I've also updated the
test suite I submitted earlier with some shorter solutions. All it
assumes is that you have a method solve that takes two whole numbers
(some tests use 0 as a starting point) that returns a list of numbers
representing the path. I found it useful for testing and
benchmarking. http://rafb.net/paste/results/zoPwZL59.html

Initially I tried a blind breath first search, which worked pretty
well, but there were a lot of values in my test suite that took an
obscene amount of time to run. Today I decided to switch over to an
A* search, which improved things a lot. My heuristic
(abs(log_base(2,a) - log_base(2,b))) is based on the idea that (except
for 0 and 1) multiplying/dividing by two is the fastest way of moving
toward the goal number. I apologize if that didn't make any sense.

Anyway, assuming I implimented it correctly, and my heuristic is
optimistic (the latter claim I'm moderately sure of) this should
return the shortest path. http://rafb.net/paste/results/exPug998.html

I'd be interested in seeing other's benchmarks on this suite.

~/Documents/Projects/ruby_quiz peter$ ruby 60.rb
Loaded suite 60
Started
...........................................................................=
..........................
...........................................................................=
..........................
...........................................................................=
..........................
...........................................................................=
..........................
...........................................................................=
....
Finished in 90.666885 seconds.

483 tests, 966 assertions, 0 failures, 0 errors

[On a iBook G4, 512 meg ram]

 

[Kero]

Actually this seems to be a better view of the pattern.

Notice that the leftmost bits are coaxed into matching the leftmost bits of
the solution first, and then work to the right.

[snip 8 solutions]

I like that view.

Does that mean you can go from the source to any prefix of the target? The
shortest route from a prefix to the target is known, even though you show two
solutions near the end (for an odd number; their length is equal and both
follow a strict recipe).

If so, I'm sure it helps when the target is bigger than the source (or more
precisely, when the target is bigger than an intermediate number) and it
does not hurt when the target is smaller. However, I doubt it beats the
approach where searching starts from both source and target (as I saw at
least once, today), unless the target is significantly bigger (i.e. the
route from the prefix to the target is longer than from the source to the
prefix).

I do not see any shortcuts from the source to the prefix.
Anybody see a way to prune that?

 

[Christer Nilsson]

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

Kero, this is really the quickest solution so far, passing my little
test suite. Before you, Ryan Sobol, was the leader, clocking in at 2.376
secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972
seconds, a decrease by 17%.

I'm challenging every quizzer: There is more to fetch!

By refactoring Kero's code, I was able to squeeze the execution time to
0.37 seconds, that's another 80%.

I'm not submitting this code, as I'm sure there are more improvements to
be done.

This is my test suite:

solve(2,9), [2,4,8,16,18,9]
solve(22,99).size, 8
solve(222,999).size, 16
solve(2222,9999).size, 25
solve(22222,99999).size, 36

Christer Nilsson

 

[J. Ryan Sobol]

--Apple-Mail-7--917100501
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
format=flowed

Before you, Ryan Sobol, was the leader, clocking in at 2.376
secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972
seconds, a decrease by 17%.

Nuts.

Kudos, Kero!

~ ryan ~
--Apple-Mail-7--917100501--

 

[0x002A]

okay here's my shot at the quiz, it's quite large for such a simple
problem, but i couldn't resist to use
:* in my code ;-)

now without :* but much shorter..

class Integer
def even?
self % 2 == 0
end

def odd?
not even?
end
end

# solves rubyquiz #60
class Solver
def initialize(start, goal)
@start, @goal = start, goal
@visited = {}
@queue = [[@goal, []]]
@ops = []
@ops << lambda {|x| x - 2 if x > 1 }
@ops << lambda {|x| x * 2 if x.odd? or @goal < @start }
@ops << lambda {|x| x / 2 if x.even? }
end

# are we there yet?
def done_with?(temp_goal)
@start == temp_goal
end

# transforms the carried steps into a valid solution
def solution(steps)
steps.reverse.unshift @start
end

# does all the work
def solve
while current = @queue.shift
temp_goal, steps = *current

return solution(steps) if done_with? temp_goal
# been there, done that
next if @visited[temp_goal]

@visited[temp_goal] = true
new_steps = steps + [temp_goal]

@ops.each do |op|
if (new_goal = op.call temp_goal)
@queue << [new_goal, new_steps]
end
end
end
raise "no solution found"
end

# creates a new solver and attempts to solve(a,b)
def self.solve(a,b)
new(a,b).solve
end
end

# for the testcases
def solve(a, b)
Solver.solve(a,b)
end

 

[Christer Nilsson]

now without :* but much shorter..

Still doesn't solve (222,999) correctly. One step too much.

222 224 112 56 58 60 62 124 248 496 498 996 998 1996 1998 999
expected but was
222 111 113 115 117 119 121 123 246 248 496 498 996 1992 1994 997 999

Christer

 

[Matthew D Moss]

Here is my solution, very much a derivative of my solution to the
Knight's Travails quiz (#27). It will return a shortest solution
(chosen at random if there are more than one). It will always find a
shortest solution, though not necessarily fast. (I haven't tried timing
this.)



# Helper methods
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)
i = 0
steps = [[a]]

# steps contains all the numbers reachable in i steps
until steps.include?(b)
i += 1
steps = []
steps[i-1].each do |x|
steps.concat x.maze_adj
end
end

# path is built in reverse order, finding a legal previous
# number according to "adjacency" rules
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 was built in reverse order, so reverse to get the final path
path.reverse
end


# Examples
p solve(2, 9)
p solve(9, 2)

 

[Adam Shelly]

Here's my solution.
It's a bi-directional depth-first search. I'm not sure anyone else did that=

 

[Nathan]

Here's my solution. Short, sweet, and slow. One benefit of this
method is that it's easily adaptable to new operations.

-Nathan


$ops = [:double, :halve, :add_two]

def solve(start, finish)
solve_recur($ops, [[]], start, finish)
end

def solve_recur(ops, op_arrays, start, finish)
op_arrays.each do |op_array|
if (is_solution?(op_array, start, finish))
return print_solution(op_array, start)
end
end
new_op_arrays = multiply_ops(ops, op_arrays)
solve_recur(ops, new_op_arrays, start, finish)
end

def multiply_ops(ops, op_arrays)
result = []
ops.each do |op|
op_arrays.each do |op_array|
result << (op_array.clone << op)
end
end
result
end

def is_solution?(op_array, start, finish)
current = start
op_array.each do |op|
return false if op == :halve && current.is_odd?
current = current.send(op)
end
current == finish
end

def print_solution(op_array, start)
solution = op_array.inject([start]) do |acc, op|
acc << acc.last.send(op)
end
puts solution.inspect
end

class Integer

def double
self * 2
end

def halve
raise "unable to halve #{self}" if self.is_odd?
self / 2
end

def add_two
self + 2
end

def is_odd?
self % 2 != 0
end

end

 

[Kero]

Here it is, my solution. From mathematical and algorithmic point of

Kero, this is really the quickest solution so far, passing my little
test suite. Before you, Ryan Sobol, was the leader, clocking in at 2.376
secs with #60.20 on the Quiz list. Your #60.22, clocks in at 1.972
seconds, a decrease by 17%.

I'm challenging every quizzer: There is more to fetch!

You don't say? You do 868056 -> 651040 in 76 seconds. I broke my program off
after 15 minutes. I can not accept the title of fastest solution.

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.

By refactoring Kero's code, I was able to squeeze the execution time to
0.37 seconds, that's another 80%.

Did you do other things than eliminating method calls?

I'm not submitting this code, as I'm sure there are more improvements to
be done.

If you did other things, I'd be interested to see it, still. My mail address
is mangled,
"(e-mail address removed)-dot.nl".split(/\./).values_at(0,2).join(".")

Thanks.

 

[Steven Aerts]

Thanks for your "general comments".

I made a little adjustment to the algortihm (added ceiling) which makes it
much faster.

Steven




class NumericMaze
def solve (from, to)
return [from] if from == to

@done = {from => :from, -to => :to}
@todo = [from, -to]
@max = [from*2+2, to*2].max

catch :found do
loop do
t = @todo.shift

add_edge(2*t, t)
add_edge(t+2, t) if (t <- 2) || (0 <= t)
add_edge(t/2,t) if t.modulo(2) == 0
end
end
return @result
end

def add_edge(new, from)
return unless @done[new] == nil
return if new > @max

@done[new] = from

if @done[-new] then #path found
@result = calc_path(new.abs)
throw :found
end

@todo.push new
end

def calc_path(middle)
pathway = [middle]

t = middle
pathway.unshift(t) until (t = @done[t]) == :from

t = -middle
pathway.push(-t) until (t = @done[t]) == :to

return pathway
end
end