On 12/31/05, Stephen W. [email protected] wrote:
version on my original post.
I’m just pounding away at this test case code because my mathematician
buddy is busy at the moment. This is quite the nontrivial problem…Exactly why I created my own test cases.
–Steve
I’d just like to chime in to say that this quiz is killing me. The
difference between ‘code to solve the problem’ and ‘code that finishes
running, you know, sometime today’ is big.
On 12/31/05, Stephen W. [email protected] wrote:
For now, I’ve posted them on http://swaits.com/
–Steve
I think I’ve improved upon this test code a bit. I found this one to
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).
http://rafb.net/paste/results/qwhnUg32.nln.html
Any feedback is, of course, appreciated.
I’m just pounding away at this test case code because my mathematician
buddy is busy at the moment. This is quite the nontrivial problem…
On Dec 31, 2005, at 10:59 PM, Wilson B. wrote:
–Steve
I’d just like to chime in to say that this quiz is killing me. The
difference between ‘code to solve the problem’ and ‘code that finishes
running, you know, sometime today’ is big.
Don’t worry, you’re not alone. 
I’m very anxious to see the code that the rest of you have come up
with. It’s been a long time since my brain worked over a problem
like this.
~ ryan ~
On Dec 31, 2005, at 4:24 PM, Peter B. wrote:
I think I’ve improved upon this test code a bit. I found this one to
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.
I’m just pounding away at this test case code because my mathematician
buddy is busy at the moment. This is quite the nontrivial problem…
Exactly why I created my own test cases. 
–Steve
On Sun, 01 Jan 2006 04:59:32 +0100, Wilson B. [email protected]
wrote:
Looks great Peter. I posted a note about and link to your improved
I’d just like to chime in to say that this quiz is killing me. The
difference between ‘code to solve the problem’ and ‘code that finishes
running, you know, sometime today’ is big.
$ 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
===== SPOILER WARNING =====
The following might be considered a spoiler, if you want to solve the
quiz
completely on your own don’t read it!
Some tips:
Try to abstract the problem: You are in a numeric maze, you have two or
three ways to go next, you want to find the shortest path to the
target.
You don’t want to visit the same number twice on your path.
It is not necessary to find some specific strategy/algorithm for this
special case, so don’t concentrate to much on the “mathematical
problem”.
There were similar quizzes in the past, check out their solutions.
Ilmari H. wrote:
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
[150128850109293, 300257700218586, 300257700218588, 150128850109294,
150128850109296, 75064425054648, 37532212527324, 18766106263662,
18766106263664, 9383053131832, 4691526565916, 2345763282958,
2345763282960, 1172881641480, 586440820740, 293220410370,
293220410372, 146610205186, 146610205188, 73305102594, 73305102596,
36652551298, 36652551300, 18326275650, 18326275652, 9163137826,
9163137828, 4581568914, 4581568916, 2290784458, 2290784460,
1145392230, 1145392232, 572696116, 286348058, 286348060, 143174030,
143174032, 71587016, 35793508, 17896754, 17896756, 8948378, 8948380,
4474190, 4474192, 2237096, 1118548, 559274, 559276, 279638, 279640,
139820, 69910, 69912, 34956, 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, 122096, 122098, 244196,
244198, 488396, 976792, 976794, 1953588, 1953590, 3907180, 7814360,
7814362, 15628724, 31257448, 31257450, 62514900, 62514902, 125029804,
250059608, 250059610, 500119220, 1000238440, 1000238442, 2000476884,
2000476886, 4000953772, 4000953774, 8001907548, 16003815096,
16003815098, 32007630196, 32007630198, 64015260396, 128030520792,
256061041584, 256061041586, 512122083172, 1024244166344,
1024244166346, 2048488332692, 2048488332694, 4096976665388,
4096976665390, 8193953330780, 8193953330782, 16387906661564,
32775813323128, 65551626646256, 131103253292512, 131103253292514,
262206506585028, 524413013170056, 1048826026340112, 1048826026340114,
2097652052680228, 4195304105360456, 4195304105360458,
8390608210720916, 16781216421441832, 33562432842883664,
67124865685767328, 67124865685767330, 134249731371534660,
134249731371534662, 268499462743069324, 268499462743069326,
536998925486138652, 536998925486138654, 1073997850972277308,
1073997850972277310, 2147995701944554620, 2147995701944554622,
4295991403889109244, 4295991403889109246, 8591982807778218492]real 0m0.037s
user 0m0.029s
sys 0m0.008sAnyone want to provide the shortest solution to that?
Beautiful!
So many bignums, so few cycles…
Would be interesting to see your heuristic solution applied to something
human, like 222->999.
I think we have to rephrase
Anyone want to provide the shortest solution to that?
to
Anyone want to provide a shorter solution to that?
Christer
On 1/1/06, Dominik B. [email protected] wrote:
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
[150128850109293, 300257700218586, 300257700218588, 150128850109294,
150128850109296, 75064425054648, 37532212527324, 18766106263662,
18766106263664, 9383053131832, 4691526565916, 2345763282958,
2345763282960, 1172881641480, 586440820740, 293220410370,
293220410372, 146610205186, 146610205188, 73305102594, 73305102596,
36652551298, 36652551300, 18326275650, 18326275652, 9163137826,
9163137828, 4581568914, 4581568916, 2290784458, 2290784460,
1145392230, 1145392232, 572696116, 286348058, 286348060, 143174030,
143174032, 71587016, 35793508, 17896754, 17896756, 8948378, 8948380,
4474190, 4474192, 2237096, 1118548, 559274, 559276, 279638, 279640,
139820, 69910, 69912, 34956, 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, 122096, 122098, 244196,
244198, 488396, 976792, 976794, 1953588, 1953590, 3907180, 7814360,
7814362, 15628724, 31257448, 31257450, 62514900, 62514902, 125029804,
250059608, 250059610, 500119220, 1000238440, 1000238442, 2000476884,
2000476886, 4000953772, 4000953774, 8001907548, 16003815096,
16003815098, 32007630196, 32007630198, 64015260396, 128030520792,
256061041584, 256061041586, 512122083172, 1024244166344,
1024244166346, 2048488332692, 2048488332694, 4096976665388,
4096976665390, 8193953330780, 8193953330782, 16387906661564,
32775813323128, 65551626646256, 131103253292512, 131103253292514,
262206506585028, 524413013170056, 1048826026340112, 1048826026340114,
2097652052680228, 4195304105360456, 4195304105360458,
8390608210720916, 16781216421441832, 33562432842883664,
67124865685767328, 67124865685767330, 134249731371534660,
134249731371534662, 268499462743069324, 268499462743069326,
536998925486138652, 536998925486138654, 1073997850972277308,
1073997850972277310, 2147995701944554620, 2147995701944554622,
4295991403889109244, 4295991403889109246, 8591982807778218492]
real 0m0.037s
user 0m0.029s
sys 0m0.008s
Anyone want to provide the shortest solution to that?
Ilmari H. wrote:
The Five digit subproblem is solved optimally.
Christer
Christer N. wrote:
Ilmari H. wrote:
…, 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, …
I can confirm that the four digit subproblem 8740 -> 7630 is solved
optimally.
Is it possible that the complete problem is solved optimally?
Christer
I’m still doing this in far too much of a brute force sort of method.
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.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE…EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.EEEEEEEEEE.E…
Finished in 434.789958 seconds.
[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.html
On Sun, Jan 01, 2006 at 06:23:08PM +0900, Ilmari H. wrote:
} On 1/1/06, Dominik B. [email protected] 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
Christer N. wrote:
Christer N. wrote:
Ilmari H. wrote:
…, 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, …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.
On 1/1/06, Christer N. [email protected] wrote:
Would be interesting to see your heuristic solution applied to something
human, like 222->999.
Ok, here’s a couple. They tend to be a step or two worse than optimal,
the worst case performance I’ve run into yet is 4x longer path (with
255 → 257.)
ruby numpuz.rb 22 999
[22, 24, 12, 14, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998, 1996,
1998, 999]
ruby numpuz.rb 222 999
[222, 224, 112, 56, 28, 30, 60, 62, 124, 248, 496, 498, 996, 998,
1996, 1998, 999]
ruby numpuz.rb 222 9999
[222, 224, 112, 56, 28, 14, 16, 18, 36, 38, 76, 78, 156, 312, 624,
1248, 2496, 2498, 4996, 4998, 9996, 9998, 19996, 19998, 9999]
ruby numpuz.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174,
176, 88, 44, 22, 24, 48, 96, 192, 194, 388, 390, 780, 1560, 1562,
3124, 6248, 12496, 12498, 24996, 24998, 49996, 49998, 99996, 99998,
199996, 199998, 99999]
On Dec 30, 2005, at 7:37 AM, Ruby Q. wrote:
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 G. II
#!/usr/local/bin/ruby -w
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) }
allowed.
class Integer
def even?
self % 2 == 0
end
end
marked as
resulting in an
seen it
alternate/longer
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
puts solve(start, finish).join(", ")
On Jan 1, 2006, at 8:04 AM, Matthew S. wrote:
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?
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
On Jan 1, 2006, at 15:47, James Edward G. II wrote:
On Dec 30, 2005, at 7:37 AM, Ruby Q. wrote:
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.
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.
My solution is not optimal nor fast… but different than the other
solutions so far.
–
Simon S.
def solve(a, b)
t = “h#{b}”
t = “h#{b*=2}” + t while b < a
s = “#{a}d#{a*2}”
a *= 2;b *= 2
s += “a#{a+=2}” while a < b
s += t
loop do
l = 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 == l
end
s.scan(/\d+/).map{|i|i.to_i}
end
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
On 12/30/05, Ruby Q. [email protected] wrote:
add_twoProblem: 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]
def nsrch(s,g)
orig_s = s
ss = s.to_s 2
gs = g.to_s 2
ops = []
bits = gs.split(//)
i = 0
while i < bits.size or ss[bits.size…-1].include? ?1
b = bits[i]
op = nil
n = 0
while ss[i,1] != b
# Add zeroes to right to make length right and
# to get the rightmost bit into an editable state.
if ss.size < i+2 or s[0] == 1
op = :*
# Delete zeroes from right to make length right.
elsif ss.size > i+2 and (s[0] == 0 and s[1] == 0)
op = 
# Add 2 if length is ok and there are no zeroes to take out.
# We are here because the second right-most bit is wrong.
# Adding 2 flips it. It may also flip every bit we’ve just
# went through, invalidating the invariant and thus we reset
# the bit counter.
else
op = :+
i = 0
end
ops << op
s = case op
when :+
s + 2
when :*
s << 1
when
s >> 1
end
ss = s.to_s 2
break if op == :+ # invariant may be bad,
# must check before continuing
end
i += 1 unless op == :+
end
r = s >> (ss.size-gs.size)
ops.push [:/](ss.size-gs.size)
a = [orig_s]
ops.each{|op|
a << case op
when :*
a.last * 2
when
a.last / 2
when :+
a.last + 2
end
}
a
end
if FILE == $0
p(nsrch(*ARGV.map{|n| n.to_i}))
end
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
ARROWS = [lambda { |x,state| (state != :halve) ? [x*2, :double] : nil },
double
lambda { |x,state| (x.modulo(2).zero? and state != :double) ?
[x/2, :halve] : nil }, #halve
lambda { |x,state| [x+2, :initial]}] # add_two
def solver(from, to)
retval = nil
depth = 1
@memo = nil
return [from] if from == to
while (retval.nil?)
retval = memo_solver(from, to, depth)
depth += 1
end
retval
end
the
def memo_solver(from, to, maxdepth, state=:initial)
@memo ||= Hash.new
key = [from, to, maxdepth]
if not @memo.has_key? key
@memo[key] = 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?
next_steps = ARROWS.map { |f| f.call(from, state) }.compact
if next_steps.assoc(to)
[from, to]
else
# havent found it yet, recur
kids = 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 = kids.sort_by { |x| x.length }.first
[from, *best]
end
end
end
list = [ [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
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs