[QUIZ] Numeric Maze (#60)

[Dominik Bathon]

I think I've improved upon this test code a bit. I found this one t= o
be a bit brittle, as it will fail solutions with unanticipated paths
of the same or smaller length. I lost some of the metadata in the
switch, as Steve has the different solutions ordered by type (i.e.
primes, powers of two, etc).

Looks great Peter. I posted a note about and link to your improved
version on my [original post][1].

I'm just pounding away at this test case code because my mathematici= an
buddy is busy at the moment. This is quite the nontrivial problem..=

 

[Christer Nilsson]

Christer Nilsson wrote:


I can confirm that the four digit subproblem 8740 -> 7630 is solved
optimally.

Is it possible that the complete problem is solved optimally?

Christer

 

[Christer Nilsson]

Ilmari Heikkinen wrote:

The Five digit subproblem is solved optimally.

Christer

 

[Peter Burns]

I'm still doing this in far too much of a brute force sort of method.=20
I think tomorrow I'll work more towards optimizing with some sneaky
math. One advantage of brute force is that, if you do it right, you
can be sure that you're getting a shortest path. I've found a couple
of shorter paths from Steve's, but I can't deal at all with his bigger
test cases.

Current progress:

~/Documents/Projects/ruby_quiz peter$ ruby 60.rb
Loaded suite 60
Started
.......E......E.E.E.E......
Better solution found:
[300, 150, 152, 76, 38, 40, 20, 10, 12, 6, 8, 4, 2]
[300, 150, 152, 76, 38, 40, 20, 10, 12, 14, 16, 8, 4, 2]
......E......E.................E.E...................E..................E..=
..................E...................E...................
Better solution found:
[900, 450, 452, 226, 228, 114, 116, 58, 60, 30, 32, 16, 8]
[900, 902, 904, 452, 226, 228, 114, 116, 58, 60, 30, 32, 16, 8]
....................E......................................................=
.........................................................EEEEEEEEE.EEEEEEEE=
EE.EEEEEEEEEE.EEEEEEEEEE..EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEE=
EEEEE.EEEEEEEEEE.E.........................................................=
.......................
Finished in 434.789958 seconds.

1) Error:
test_case_104(TestNumericMaze):
RuntimeError: Too Slow

[snip...]

483 tests, 738 assertions, 0 failures, 114 errors

I'm having my solve method throw an error when it is taking too long
to evaluate to more easily distinguish giving an invalid result from
just taking too long.

Slightly updated test suite: http://rafb.net/paste/results/SKaTxv60.nln.htm=
l

 

[Kenji Sihan]

Christer Nilsson wrote:



I can confirm that the four digit subproblem 8740 -> 7630 is solved
optimally.

Is it possible that the complete problem is solved optimally?

Christer

17478, 17480, 8740, 4370, 4372, 2186,

2188, 1094, 1096, 548, 274, 276, 138, 140, 70, 72, 36, 18, 20, 10, 12,
14, 28, 56, 58, 116, 118, 236, 238, 476, 952, 1904, 1906, 3812, 3814,
7628, 7630, 15260, 15262, 30524, 61048

I think this is optimal as well.

 

[Gregory Seidman]

On Sun, Jan 01, 2006 at 06:23:08PM +0900, Ilmari Heikkinen wrote:
} >
} > $ time ruby num_maze.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, 199992, 199994, 99997, 99999]
} >
} > real 0m1.768s
} > user 0m1.725s
} > sys 0m0.022s
} >
} > ;-)
}
} I wrote a heuristic solver by abusing the properties of the
} mathematical problem. It doesn't find the shortest transformation
} sequence but runs pretty fast.
}
} $ time ruby numpuz.rb 150128850109293 8591982807778218492
[...]
} real 0m0.037s
} user 0m0.029s
} sys 0m0.008s
}
} Anyone want to provide the shortest solution to that? ;-)

Whatever you're doing, I'm doing much the same thing. I get the identical
solution in almost identically the same time (note: Dual G4 800):

real 0m0.037s
user 0m0.028s
sys 0m0.009s

I wouldn't call my solver heuristic, though. There is exactly one heuristic
optimization. Other than that it is pretty much a straight analysis of the
problem, with a nasty cleanup at the end to remove path loops.

By the way, I can't get to
http://swaits.com/articles/2005/12/31/ruby-quiz-60-test-cases at the
moment. It seems to be down. Would anyone like to post some canonical test
cases to the list?

--Greg

 

[James Edward Gray II]

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

Here's my simple breadth-first search with a single optimization
(described in comments). It's not at all fast enough for the big
examples people have been throwing around, but it's pretty simple.

James Edward Gray II

#!/usr/local/bin/ruby -w

# Parse arguments.
unless ARGV.size == 2 and ARGV.all? { |n| n =~ /\A[1-9]\d*\Z/ }
puts "Usage: #{File.basename($0)} START_NUMBER FINISH_NUMBER"
puts " Both number arguments must be positive integers."
exit
end
start, finish = ARGV.map { |n| Integer(n) }

# Simple helper methods for determining if divide-by-two operation is
allowed.
class Integer
def even?
self % 2 == 0
end
end

#
# A breadth-first search with a single optimization: All numbers are
marked as
# "seen" when they are calculated, then all future calculations
resulting in an
# already seen number cause the entire path to be abandoned. (We've
seen it
# before in equal or less steps, so there's no need to use the
alternate/longer
# path).
#
def solve( start, finish )
return [start] if start == finish

seen = {start => true}
paths = [[start]]

until paths.first.last == finish
path = paths.shift

new_paths = [path.dup << path.last * 2, path.dup << path.last + 2]
new_paths << (path.dup << path.last / 2) if path.last.even?

new_paths.each do |new_path|
unless seen[new_path.last]
paths << new_path
seen[new_path.last] = true
end
end
end

paths.shift
end

# Run program.
puts solve(start, finish).join(", ")

 

[Matthew Smillie]

Here's my simple breadth-first search with a single optimization
(described in comments). It's not at all fast enough for the big
examples people have been throwing around, but it's pretty simple.

OK, so I didn't have time to code it up and see for sure, what with
some transatlantic travel and New Year's and all that stuff, but the
first thing that struck me when reading the problem was "dynamic
programming" - did anyone take this route and hence give me a bit of
satisfaction that my instincts were right?

m.s.

 

[ToRA]

Hey,

My solution's similar in style [breadth first, don't duplicate search],
though I've also roof-limited it so it can't explore the search space
above 2*[max(target,start)] + 4 which provides a fair speed up for e.g.
222, 9999. I'm not sure if that loses the optimality property though.
I can't get to the swaits.com test suite, but the other one my solver
finds smaller solutions for.

Regards,

Tris

----
require 'set'

class MazeSolver

def solve start, finish
visited = Set.new

tul, tll = if start > finish
[(start << 1) + 4, nil]
else
[(finish << 1) + 4, nil]
end

solve_it [[start]], finish, visited, tul, tll
end

def solve_it lpos, target, visited, tul, tll
n = []
lpos.each do |vs|
v = vs.last
next if tul and v > tul
next if tll and v < tll

return vs if v == target

d = v << 1 # double
h = v >> 1 unless (v & 1) == 1 # half
p2 = v + 2 # plus 2

n << (vs.clone << d) if visited.add? d
n << (vs.clone << h) if h and visited.add? h
n << (vs.clone << p2) if visited.add? p2
end

return solve_it(n, target, visited,tul, tll)
end
end

if __FILE__ == $0
puts MazeSolver.new.solve(ARGV[0].to_i, ARGV[1].to_i).join(" ")
end
--------

 

[Simon Strandgaard]

My solution is not optimal nor fast.. but different than the other
solutions so far.

--
Simon Strandgaard


def solve(a, b)
t =3D "h#{b}"
t =3D "h#{b*=3D2}" + t while b < a
s =3D "#{a}d#{a*2}"
a *=3D 2;b *=3D 2
s +=3D "a#{a+=3D2}" while a < b
s +=3D t
loop do
l =3D s.length
s.gsub!(/(\d+)d\d+a\d+a/) { "#{$1}a#{$1.to_i + 2}d" }
s.gsub!(/4a6a8/, '4d8')
s.gsub!(/(\D|^)(\d+)(?:\D\d+)+\D\2(\D|$)/) {$1 + $2 + $3}
break if s.length =3D=3D l
end
s.scan(/\d+/).map{|i|i.to_i}
end

 

[Maurice Codik]

------=_Part_3102_4389072.1136134866960
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I guess we're allowed to submit solutions now... here's my first ever ruby
quiz solution (these quizzes are a great idea, btw):

It's is an iterated-depth DFS w/ memoization written in a functional style
for fun.

It exploits the fact that the optimal path through the maze will never have
consecutive double/halves, which reduces the avg branching factor of the
search tree to ~2. Keeping track of this state makes the code a little
uglier, but faster on the longer searches.

Maurice

#! /usr/bin/ruby

# These return the next number & state
ARROWS =3D [lambda { |x,state| (state !=3D :halve) ? [x*2, :double] : nil }=
, #
double
lambda { |x,state| (x.modulo(2).zero? and state !=3D :double) ?
[x/2, :halve] : nil }, #halve
lambda { |x,state| [x+2, :initial]}] # add_two

def solver(from, to)

# constraining depth on a DFS
retval =3D nil
depth =3D 1
@memo =3D nil

# special case
return [from] if from =3D=3D to

while (retval.nil?)
retval =3D memo_solver(from, to, depth)
depth +=3D 1
end

retval
end

# cant use hash default proc memoization since i dont want to memoize on th=
e

# state parameter, only on the first 3
def memo_solver(from, to, maxdepth, state=3D:initial)
@memo ||=3D Hash.new

key =3D [from, to, maxdepth]

if not @memo.has_key? key
@memo[key] =3D iter_solver(from, to, maxdepth, state)
@memo[key]
else
@memo[key]
end
end

def iter_solver(from, to, maxdepth, state)
return nil if maxdepth.zero?

# generate next numbers in our graph
next_steps =3D ARROWS.map { |f| f.call(from, state) }.compact

if next_steps.assoc(to)
[from, to]
else
# havent found it yet, recur
kids =3D next_steps.map { |x,s| memo_solver(x, to, maxdepth-1, s)
}.compact

if kids.length.zero?
nil
else
# found something further down the tree.. return the shortest list up
best =3D kids.sort_by { |x| x.length }.first
[from, *best]
end
end
end

list =3D [ [1,1], [1,2], [2,9], [9,2], [2, 1234], [1,25], [12,11], [17,1],
[22, 999], [2, 9999], [222, 9999] ]

require 'benchmark'

list.each do |i|
puts Benchmark.measure {
p solver(*i)
}
end

I had the same thought, then decided it doesn't fit. But too, I'm
interested in watching these solutions.

I have a feeling they'll be based on exhaustive searches with a pinch
of pruning and a dash of optimization.

--Steve

------=_Part_3102_4389072.1136134866960--

 

[Ilmari Heikkinen]

T24gMS8xLzA2LCBDaHJpc3RlciBOaWxzc29uIDxqYW5jaHJpc3Rlci5uaWxzc29uQGdtYWlsLmNv
bT4gd3JvdGU6Cj4gQ2hyaXN0ZXIgTmlsc3NvbiB3cm90ZToKPgo+IElsbWFyaSBIZWlra2luZW4g
d3JvdGU6Cj4gPj4gLi4uLCA4NzQwLCA0MzcwLCA0MzcyLCAyMTg2LAo+ID4+IDIxODgsIDEwOTQs
IDEwOTYsIDU0OCwgMjc0LCAyNzYsIDEzOCwgMTQwLCA3MCwgNzIsIDM2LCAxOCwgMjAsIDEwLCAx
MiwKPiA+PiAxNCwgMjgsIDU2LCA1OCwgMTE2LCAxMTgsIDIzNiwgMjM4LCA0NzYsIDk1MiwgMTkw
NCwgMTkwNiwgMzgxMiwgMzgxNCwKPiA+PiA3NjI4LCA3NjMwLCAuLi4KPgo+IEkgY2FuIGNvbmZp
cm0gdGhhdCB0aGUgZm91ciBkaWdpdCBzdWJwcm9ibGVtIDg3NDAgLT4gNzYzMCBpcyBzb2x2ZWQK
PiBvcHRpbWFsbHkuCj4KPiBJcyBpdCBwb3NzaWJsZSB0aGF0IHRoZSBjb21wbGV0ZSBwcm9ibGVt
IGlzIHNvbHZlZCBvcHRpbWFsbHk/Cj4KPiBDaHJpc3RlcgoKSXQncyBwb3NzaWJsZSwgYnV0IEkg
ZG9uJ3Qga25vdy4K

 

[James Edward Gray II]

I guess we're allowed to submit solutions now...

Yes, 48 hours have passed sent the quiz was sent in

here's my first ever ruby quiz solution

Awesome. Thanks for joining the fun!

(these quizzes are a great idea, btw):

Thanks. I truly hope people find them helpful.

It exploits the fact that the optimal path through the maze will
never have
consecutive double/halves, which reduces the avg branching factor
of the
search tree to ~2. Keeping track of this state makes the code a little
uglier, but faster on the longer searches.

Hey, that's clever. Thanks for sharing.

James Edward Gray II

 

[horndude77]

For this quiz I took what I made for the word chain quiz and modified
it a bit. It uses a bi-directional breadth first search. I didn't allow
negative numbers at all just to make it simple for me.

-----Horndude77

def solve(from, to)
return [from] if from == to
ops = []
ops << lambda {|n| n*2}
ops << lambda {|n| n/2 if n%2 == 0}
ops << lambda {|n| n+2}

invops = []
invops << lambda {|n| n/2 if n%2 == 0}
invops << lambda {|n| n*2}
invops << lambda {|n| n-2}

fromedges = {from => :start}
toedges = {to => :start}
fromqueue = [from]
toqueue = [to]
linknode = nil

while(toqueue.length>0 && fromqueue.length>0)
fromnode = fromqueue.shift
tonode = toqueue.shift
if(toedges[fromnode] || fromnode==to) then
linknode = fromnode
break
elsif(fromedges[tonode] || tonode==from) then
linknode = tonode
break
end

ops.each do |o|
val = o.call(fromnode)
if(val && !fromedges[val] && val > 0) then
fromedges[val] = fromnode
fromqueue << val
end
end

invops.each do |o|
val = o.call(tonode)
if(val && !toedges[val] && val > 0) then
toedges[val] = tonode
toqueue << val
end
end
end

return [] if(linknode == nil)
chain = []
currnode = linknode
while(fromedges[currnode] != :start)
chain.unshift currnode if currnode != to
currnode = fromedges[currnode]
end
currnode = toedges[linknode]
while(toedges[currnode] != :start && currnode != :start)
chain << currnode
currnode = toedges[currnode]
end
return [from]+chain+[to]
end

if ARGV.length != 2 then
puts "usage: #{$0} <from> <to>"
exit
end

from, to = ARGV[0].to_i, ARGV[1].to_i
if from < 1 || to < 1 then
puts "inputs must be positive"
exit
end
p solve(from, to)

 

[Jim Menard]

I've posted my solution, along with a few words about my approach, at
<http://www.io.com/~jimm/rubyquiz/quiz60/>.

Jim
--
Jim Menard, (e-mail address removed), (e-mail address removed)
http://www.io.com/~jimm
"Generics in Java are an apology for having collections of Objects, and are
somewhat like the puritan's suspicion that someone, somewhere, might be
enjoying themselves."
-- Steven T Abell in comp.lang.smalltalk

 

[Mark]

Maurice,

I just noticed that your solution can't find the path between two odd numbe=
rs.

- Mark

 

[Mark]

Nevermind, a copy and paste error on my part!

Mark: could you explain what you mean? these were outputs from that prog:

solve(3,1233):
[3, 6, 8, 16, 18, 36, 38, 76, 152, 154, 308, 616, 1232, 2464, 2466, 1233]
solve(1,25):
[1, 3, 6, 12, 24, 48, 50, 25]

looks like it finds them just fine... or do u mean that these arent the
optimal paths?

James: Now that I think about it, your optimization and mine are almost
equivalent, I think-- I'm fairly certain that the only way to get to a
number that you've been to already is by using consecutive pairs of
double/half.. since the add_two operation isn't invertable in this quiz.

Maurice

Maurice,

I just noticed that your solution can't find the path between two odd
numbers.

- Mark

r
have

 

[Kero]

I'm using a Dual 2 Ghz G5, so the hardware is at least *some* of the
difference.

With one simple optimisation (no pruning), on a 700 MHz Duron:

kero@chmeee:~/pub/ruby/quiz$ time ruby 60-num_maze.rb 22 999
[snip answer]
real 0m0.772s
user 0m0.588s
sys 0m0.076s

But I'm not sure I want to run 8740 7630
let alone 150128850109293 8591982807778218492

 

[Dave Lewis]

My first quiz, as well.

Simple optimizations of don't-double-after-halving (and vice versa) and
pruning.

I enjoy the aesthetic feel of moving through one long queue. Not too
fast on the large cases though.

The use of detect is a bit ungainly, but it still seemed like the
appropriate function.

dave

----
#!/usr/bin/ruby

class Array
def uniquepush(num)
self.push(num) if (self.assoc(num[0]) == nil)
end
end

def interpret(val, solution)
returnval = "[" + val.to_s
solution[1].each{|step|
val = val/2 if (step == 0)
val = val+2 if (step == 1)
val = val*2 if (step == 2)
returnval += "," + val.to_s
}
returnval += "]"
end

def solve(initial, target)
queue = [[initial, Array.new]]
solution = queue.detect{|step|
if (step[0] == target)
true
else
queue.uniquepush([step[0]/2, step[1].clone().push(0)]) if (step[0]
% 2 == 0 && step[1].last != 2)
queue.uniquepush([step[0]+2, step[1].clone().push(1)])
queue.uniquepush([step[0]*2, step[1].clone().push(2)]) if
(step[1].last != 0)
false
end
}
interpret(initial, solution)
end

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

 

[Justin Bishop]

I'm another newbie to the ruby-quiz. This is a dirt-simple BFS. it
takes 8 seconds on my machine to do solve(22,999); i make sure no path
hits upon a number a previous path had ever hit upon, and i discovered
it'd run slightly faster by simply checking to see if my path is
halving right after doubling or doubling right after halving, and
*then* checking the entire list of numbers passed. (hope that made
sense)

i had toyed around with other optimizations but none seemed elegant
and time-saving enough to be worth it. what i was hoping for was a
nice way to identify when certain paths are careening insanely
off-path and clearly won't be the correct answer...i have yet to see
the solution that can do things like solve(222,9999) in
milliseconds...i am anxiously awaiting one...or did i miss it?

here is mine:
--------------------------------
def solve(start, finish)
=09paths =3D [[start, start+2], [start, start*2]];
=09paths.push([start, start/2]) if (start%2 =3D=3D 0);
=09allNum =3D paths.flatten.uniq;
=09loop {
=09 newP =3D Array.new();
=09 paths.each{ |path|
=09 curN =3D path.last;
=09 unless(allNum.include?(curN+2))
=09 return path.push(curN+2) if (curN+2 =3D=3D finish);
=09 allNum.push(curN+2);
=09 newP.push(path.clone.push(curN+2));
=09 end
=09 unless (allNum.include?(curN*2))
=09 return path.push(curN*2) if (curN*2 =3D=3D finish);
=09 allNum.push(curN*2);
=09 newP.push(path.clone.push(curN*2));
=09 end
=09 if (curN%2 =3D=3D 0 and not allNum.include?(curN/2))
=09 return path.push(curN/2) if (curN/2 =3D=3D finish);
=09 allNum.push(curN/2);
=09 newP.push(path.clone.push(curN/2));
=09 end
=09 }
=09 paths =3D newP;
=09}
end