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
On Jan 2, 2006, at 2:57 PM, Simon Kröger wrote:
Thanks for the testcases,
You’re welcome. Thanks for trying them.
–Steve
Simon wrote:
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
I always learn something from Ruby Q.! 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.
#!/usr/bin/env ruby
module NumericMaze
class Node
attr_accessor :parent, :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.new(:root, start)
# Initialize hash of visited numbers; do not
# visit a number twice (thanks to Dominik B.)
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} ”
exit
end
NumericMaze.solve(ARGV[0].to_i, ARGV[1].to_i)
On Monday 02 January 2006 15:57, Simon Kröger wrote:
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. =)
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]
[email protected] wrote:
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
On Jan 3, 2006, at 8:01 AM, Christer N. wrote:
Before you, Ryan S., 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 ~
Kero wrote:
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 S., 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 N.
[email protected] wrote:
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
[email protected] wrote:
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
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
def solve(a, b)
Solver.solve(a,b)
end
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.)
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]]
until steps[i].include?(b)
i += 1
steps[i] = []
steps[i-1].each do |x|
steps[i].concat x.maze_adj
end
end
i -= 1
path = [b]
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
p solve(2, 9)
p solve(9, 2)
Here’s my solution.
It’s a bi-directional depth-first search. I’m not sure anyone else did
that.
It’s reasonably fast for small numbers, but takes 25 secs to do
22222->99999
It also solves Quiz60B, if you adjust the costs. use 22->34 for an
example where the different costs affect the solution.
class NumericMazeSolver
#the allowable operations - changing the order changes the solution
#this order favors smaller numbers
OPS = {:FWD=>[:halve, :add2,:double],:REV=>[:double, :sub2,:halve]}
#create a hash mapping operations to their inverse.
ANTIOP=OPS[:FWD].zip(OPS[:REV]).inject({}){|h,s|h[s[0]]=s[1];h[s[1]]=s[0];h}
#change this line to solve Quiz60B
#COST = {:halve=>1, :add2=>1, :double=>1,:sub2=>1}
COST = {:halve=>4, :add2=>1, :double=>2,:sub2=>1}
def initialize(noisy=false)
@noisy = noisy
end
class Trail
attr_reader :path,:dir,:cost
def initialize direction, value=nil, path=[], cost = nil
@dir =direction
@path = path
@path.push value if value
@cost = if cost && value
cost + calc_cost(value)
else
path.inject(0){|sum,op| c=calc_cost(op); sum+=c if c; sum}
end
end
def grow operation
return Trail.new(@dir,operation,@path.dup,@cost)
end
def inspect
[email protected]("$#{@cost}:"){|s,v| s+"#{v}->"}
s[0..-3]
end
def invert
Trail.new(@dir, nil, @path.reverse.map{|v| ANTIOP[v] || v},@cost)
end
def calc_cost operation
@dir == :FWD ? COST[operation] : COST[ANTIOP[operation]]
end
end
#the operations
def double a
return a*2
end
def halve a
return a/2 if a%2==0
end
def add2 a
return a+2
end
def sub2 a
return a-2
end
#store the cheapest trail to each number in the solution hash
def expand(val)
trail = @sset[val]
OPS[trail.dir ].each do |op|
result= self.send(op,val)
if result
newpath = trail.grow(op)
if (foundpath = @sset[result] )
if foundpath.dir != newpath.dir
cost = foundpath.cost+newpath.cost
@match= [newpath,result, cost] if (!@match || (cost <
@match.last))
elsif foundpath.cost > newpath.cost
@sset[result] = newpath
end
else
@sset[result] = newpath
if (!@match || (newpath.cost+@depth) < @match.last)
@newvals.push(result) #only check if total cost can be
less than match cost
end
end
end
end
end
def solve(start,target)
return nil if start<0 || target < 1
return [start] if start==target
@sset = {start=>Trail.new(:FWD,start) ,
target=>Trail.new(:REV,target) }
@newvals=[start,target]
solution = nil
@match=nil
@depth=0
while true do
val = @newvals.shift
break if !val
expand(val)
@depth+=1
end
trail, matchnum = solution
trail, matchnum = @match
if trail.dir == :FWD
first,last = trail,@sset[matchnum].invert
else
first,last = @sset[matchnum],trail.invert
end
get_solution(first,last)
end
def get_solution(first,last)
puts "SOLUTION = " + first.inspect + “->” + last.inspect if @noisy
p = first.path + last.path
s=[p.shift]
p.each{ |v| s << self.send(v,s[-1]) unless v.is_a? Integer}
s
end
end
if FILE == $0
start, goal, is_noisy = ARGV[0].to_i, ARGV[1].to_i, ARGV[2]!=nil
puts “usage: @$0 start goal [noisy]” unless start && goal
p NumericMazeSolver.new(is_noisy).solve(start, goal)
end
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 S., 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,
“[email protected]”.split(/./).values_at(0,2).join(".")
Thanks.
Kero wrote:
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
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
On Jan 4, 2006, at 9:50 AM, Christer N. wrote:
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.
It’s no secret. 
Here’s the code:
On Jan 3, 2006, at 12:29 PM, NILSSON Christer wrote:
def solve number,target
@@route[source] = nil
def even?target < 0 and source >= 0
job.handle_num_mazedef handle_num_maze
if route[sub2].nil? or route[self].dist + 1 < route[sub2].dist
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 G. II
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
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[i].include?(b)
i += 1
steps[i] = []
steps[i-1].each do |x|
x.maze_adj.each { |y| steps[i] << y unless known.include?(y) }
end
known.concat steps[i]
end
i -= 1
path = [b]
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
p solve(9, 2)
p solve(2, 9)
p solve(22, 99)
p solve(222, 999)
Christer N. wrote:
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}”
cheers
Simon
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