On 1/1/06, Christer N. [email protected] wrote:
Is it possible that the complete problem is solved optimally?
Christer
It’s possible, but I don’t know.
On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote:
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 G. II
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} "
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)
#!/usr/bin/env ruby
Ruby Q. #60, Numeric Maze
Ruby Quiz - Numeric Maze (#60)
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 an optimization
suggested by Dominik B.: track what numbers have been
visited and do not build subnodes for previously visited
numbers.
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)
# 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 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)
Maurice,
I just noticed that your solution can’t find the path between two odd
numbers.
- Mark
I’ve posted my solution, along with a few words about my approach, at
http://www.io.com/~jimm/rubyquiz/quiz60/.
Jim
Jim M., [email protected], [email protected]
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: 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
On 2005-12-31, James Edward G. II [email protected] wrote:
On Dec 31, 2005, at 12:26 PM, Jim M. wrote:
Damn. I got it down from 7 minutes to 18 seconds on a 667 MHz PPC, but
it looks like I have a bit more work to do.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
Nevermind, a copy and paste error on my part!
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)
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)
paths = [[start, start+2], [start, start2]];
paths.push([start, start/2]) if (start%2 == 0);
allNum = paths.flatten.uniq;
loop {
newP = Array.new();
paths.each{ |path|
curN = path.last;
unless(allNum.include?(curN+2))
return path.push(curN+2) if (curN+2 == finish);
allNum.push(curN+2);
newP.push(path.clone.push(curN+2));
end
unless (allNum.include?(curN2))
return path.push(curN2) if (curN2 == finish);
allNum.push(curN2);
newP.push(path.clone.push(curN2));
end
if (curN%2 == 0 and not allNum.include?(curN/2))
return path.push(curN/2) if (curN/2 == finish);
allNum.push(curN/2);
newP.push(path.clone.push(curN/2));
end
}
paths = newP;
}
end
On Jan 1, 2006, at 19:54, Maurice Codik wrote:
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
OK, so this sort of counter-example is pretty trivial, but the +2 can
be composed to be equivalent to the double operation starting from
even numbers, so the double/halve optimisation doesn’t necessarily
eliminate re-visiting a number in a path (but strikes me that it
would do in the overwhelming majority of cases).
4, 6, 8, 4
+2 +2 /2
| *2 |
You could heuristicise (neologisms are a New Year’s resolution of
mine) your way out of this by limiting chains of +2 but, there also
exist other more complicated composite operations which are
equivalent to doubling, but aren’t as easy to optimise away:
6, 3, 5, 10, 12, 6 oops!
/2 +2 *2 +2 /2
| *2 |
14, 7, 9, 11, 22, 24, 26, 28, 14 oops!
/2 +2 +2 *2 +2 +2 +2 /2
| *2 |
For both these sorts of exceptions, though, you’d need more and more
instances of +2 in the double-equivalent sequence as the initial
number becomes higher and higher, so I don’t expect this will cause
any particular pain in a practical implementation.
matt.
Here’s my solution. It uses the A* algorithm and the priority queue
stuff
from quiz #44. Btw, I’m new to ruby quiz, too.
Pablo
#!/usr/bin/ruby
INF = 1.0/0.0
LOG2 = Math.log(2)
The priority queue is taken from Ruby Q. #44 (by Levin A.).
class PriorityQueue
def initialize
@storage = Hash.new { |hash, key| hash[key] = [] }
end
def push(data, priority)
@storage[priority] << data
end
def next
return nil if @storage.empty?
key, val = *@storage.min
result = val.shift
@storage.delete(key) if val.empty?
return result
end
end
def solve(a, b)
return nil if a < 0 || b < 1
q = PriorityQueue.new
cost = Hash.new{INF}
parent = {}
q.push a, 0
cost[a] = 0
logb = Math.log(b)
while n = q.next
break if n == b
sub = []
sub << n*2
sub << n/2 if n%2 == 0
sub << n+2
sub.each do |s|
# Number of operations from a to s
c = cost[n] + 1
# Discard this path if we already have a better/equal one
next if cost[s] <= c
cost[s] = c
parent[s] = n
# h = estimated min. number of operations required from s to b
x = (s > 0) ? s : 1 # log(0) = error
# This computes the number of *2 or /2 operations needed
# to go from s to b
h = ((logb-Math.log(x))/LOG2).abs.floor
q.push s, c + h
end
end
Build the path backwards
path, n = [b], b
while n = parent[n]
path << n
end
path.reverse
end
if FILE == $0
if ARGV.length == 2
steps = solve(ARGV[0].to_i, ARGV[1].to_i)
puts “#{steps.inspect} (#{steps.length})”
else
puts "Usage: #{$0} "
end
end
1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997, 9999
real 96m13.978s
user 49m27.502s
sys 46m22.817sGuess I need more than my one optimization now.
I stopped at 222 -> 4998 which took 43 seconds. Each next step will take
a rough factor 3, so I’ll end up near 3 hours. Oops…
First pruning… Slices running time to less than 0.2 seconds wheee
and to
9999 in slightly more than 0.2 seconds (which proves I got rid of that
nasty
exponential thing).
Hi all,
hereby my first solution for the ruby quiz and my first real world ruby
program.
So all comments about my ruby-coding-style are very welcome(especially
how
you think about using the throw catch statement).
The program itself runs two depth first searches in parallel one from
the
start number and one from the end number looking for the middle number
in the
end-result.
When found, the two paths to get to this middle number form the
end-result.
It is possible to use the same method to calculate both pathways by
using
negative numbers for the path from the end-point.
Hope you like it,
Steven <[email protected]>
–
class NumericMaze
def solve (from, to)
return [from] if from == to
@done = {from => :from, -to => :to}
@todo = [from, -to]
catch :found do
while true
t = @todo.shift
addEdge(2*t, t)
addEdge(t+2, t) if (t <- 2) || (0 <= t)
addEdge(t/2,t) if t.modulo(2) == 0
end
end
return @result
end
def addEdge(new, from)
return if @done[new] != nil
@done[new] = from
if @done[-new] then #path found
@result = calcPath(new.abs)
throw :found
end
@todo.push new
end
def calcPath(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
Ilmari H. wrote:
Problems appear when trying to make 255 into 257:
11111111 -> 100000001
The shortest way is by adding 2.
But the algorithm below fails at that and goes the long way:
11111111 << 1
111111110 + 2
1000000000 + 2
1000000010 >> 1
100000001
Ilmari, I tried to replicate your solution, before seeing it, and
strangely run into exactly the same behaviour. The code is not complete,
but the idea is to go downwards to 1 with both numbers. I’m using the
complement of +2, -2 for the target number.
t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
--> --> --v
<-- <-- <--
t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
Having these two sequences, I find the largest common number, in this
case 512. This gives me the non optimal solution [255,510,512,514,257],
which is exactly the same as yours. I’m not sure if identifying
shortcuts afterwards, will find the shortest path, though, in all cases.
(Finding 255 + 2 = 257, is easy, but what about finding 255 -> 259 if
257 is missing.)
I tried the six digit subproblem of your big problem, and it worked out
perfectly optimal. So I was surprised 255 -> 257 behaved so bad.
Christer
def down(x)
return [] if x==0
return [1] if x==1
return [2,1] if x==2
return [x] + down(x*2) if x.modulo(2)==1
return [x] + down(x/2) if x.modulo(4)==0
[x] + down(x-2)
end
def up(x)
return [] if x==0
return [1] if x==1
return [2,1] if x==2
return [x] + up(x*2) if x.modulo(2)==1
return [x] + up(x/2) if x.modulo(4)==0
[x] + up(x+2)
end
require ‘test/unit’
class TestIlmari < Test::Unit::TestCase
def t (actual, expect)
assert_equal expect, actual
end
def test_all
t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
#t up(72), [72,36,18,20,10,12,6,8,4,2,1]
#t down(28), [28,14,12,6,4,2,1]
#t up(150128850109293).size,82
#t down(8591982807778218492).size, 100
end
end
In article [email protected],
Matthew S. [email protected] wrote:
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?
I kept thinking that a recursive solution would be the easiest way to
go, but
I quickly found that even some of the most trival testcases overwhelmed
the
stack 
(not too surprising, I guess, given the size of the search
space).
If I have time to get it done I’ll post my non-recursive version (that
is
unfortuneately becoming quite bloated, I think).
Phil
[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
So very sorry…
Ok, my solution. It keeps track of all reached numbers and how it gets
there in a hash (path). When the target is in the hash we simply have to
go backwards and remember the values we pass on the way.
It does the 222 -> 9999 in 6.2s on my 2GHz+something system.
(should be easy to do a search from both sides, but no time [yet])
cheers
Simon
from, to = ARGV.shift || 222, ARGV.shift || 9999
t = Time.now
path = {from => :found}
while not path.include? to
path.keys.each do |n|
path[n + 2] = :add unless path.include?(n + 2)
path[n * 2] = :mul unless path.include?(n * 2)
path[n / 2] = :div unless (n % 2) != 0 || path.include?(n / 2)
end
end
result = [to]
loop do
case path[result.last]
when :add then result << result.last - 2
when :mul then result << result.last / 2
when :div then result << result.last * 2
else break
end
end
p result.reverse
puts “Time: #{Time.now - t}s”
On Jan 1, 2006, at 4:37 PM, Phil T. wrote:
I kept thinking that a recursive solution would be the easiest way
to go, but
I quickly found that even some of the most trival testcases
overwhelmed the
stack(not too surprising, I guess, given the size of the
search space).
This seems odd to me. Wouldn’t a recursive breadth-first (or even
iterative depth-first) only ever recurse as deep as there are numbers
in the solution? Everything we’ve seen so far should be well within
solvable that way, unless I’m missing something obvious here…
James Edward G. II