On Jan 1, 2006, at 4:20 PM, Steven Aerts wrote:
So all comments about my ruby-coding-style are very welcome
(especially how
you think about using the throw catch statement).
Looking good so far. Here’s some general comments:
These are just style nitpicks of course though, so don’t take them
too seriously. 
James Edward G. II
In article
[email protected],
Justin B. [email protected] wrote:
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?
I think one should look at the mathematical side of the problem first.
Here are some starting ideas:
Only the first operation can possibly increase the number of zeroes in
the number (always by one).
Only the second one can change the parity of the number.
Only the last one can possibly change the number of ones in the number
(either increasing it by one, or decreasing it by possibly arbitrary
amounts)
Looking at the example (222,9999), I see the following:
222 = 0x00DE = 1101 1110 (2 zeroes, 6 ones)
9999 = 0x270F = 10 0111 0000 1111 (5 zeroes, 8 ones)
From this, we can see that we must do at least 3 left shifts (to obtain
the five zeroes), at least one right shift (to change parity), and at
least one ‘+2’ (to change the number of ones)
Looking at it in a different way: we must get a ‘1’ in position 14 from
the right. That ‘1’ can only come from position 13, using either the
‘*2’ or the ‘+2’ (with sufficient overflows) operations.
There is no ‘1’ in position 13. To get one there, we need one at
position 12, etc.
In the end to get a ‘1’ in position 14 is by moving the one in position
8 there, using a combination of at least six ‘*2’ or ‘+2’ operations.
If we do that using ‘*2’ only, the ‘1’ in position 7 would move to
position 13. We do not want a ‘1’ there, so we should use ‘+2’ at least
once.
I think logic like this will lead to a better understanding of the
problem, and possibly to more efficient solutions.
For instance: I would guess that many of the optimal solutions are
rather dull, ending in a series of (‘*2’) or (‘+2’, ‘*2’) operations to
shift in zero and one bits, followed by a single ‘/2’ if the target
value is odd (WARNING: this is just a hunch; I may be completely wrong
here)
Reinder
Gregory S. wrote:
This is my first Ruby quiz. I was hoping to have the whole thing done
by the end of the first 48 hours, but I kept getting hung up on edge
cases.
I did figure out the binary approach on my own, though.
Gregory, this is an amazing solution! However I got a failure trying
some arbitrarily selected src and dst values:
$ ruby test60.rb 4934939 39329291
./60.rb:47:in halve': Trying to halve an odd number: 49 (RuntimeError) from ./60.rb:127:insolve’
from test60.rb:7
On Jan 1, 2006, at 11:01 AM, Maurice Codik wrote:
here’s my first ever ruby quiz solution
On Jan 1, 2006, at 2:41 PM, Dave Lewis wrote:
My first quiz, as well.
On Jan 1, 2006, at 3:39 PM, Justin B. wrote:
I’m another newbie to the ruby-quiz.
On Jan 1, 2006, at 4:14 PM, Pablo Hoch wrote:
Btw, I’m new to ruby quiz, too.
On Jan 1, 2006, at 4:20 PM, Steven Aerts wrote:
hereby my first solution for the ruby quiz and my first real world
ruby program.
It’s great to see so many new faces. Welcome everyone!
James Edward G. II
This is my first Ruby quiz. I was hoping to have the whole thing done
by the end of the first 48 hours, but I kept getting hung up on edge
cases.
I did figure out the binary approach on my own, though.
On Mon, Jan 02, 2006 at 08:42:56AM +0900, Reinder V. wrote:
[…]
} I think one should look at the mathematical side of the problem first.
} Here are some starting ideas:
}
} - write both the starting and the target number in binary
} - notice that the three operators do the following:
} - add a zero to the right = left shift the number one position
} - remove a zero from the right = right shift the number one position
} - flip a bit in the one-but-rightmost position, possibly changing
} consecutive ones to zeroes to the left of this bit
[…]
} I think logic like this will lead to a better understanding of the
} problem, and possibly to more efficient solutions.
This is exactly what I started from. My solution involves no search
algorithm. It is entirely rule-based, including two optimization rules
which could be called heuristic. (My code is at the end of this
message.)
The optimization rules are that two adds are cheaper than (and equal to)
half-add-double, and four adds are cheaper than (and equal to)
half-half-add-double-double. I’m pretty sure the results are guaranteed
to
be optimal, too.
} For instance: I would guess that many of the optimal solutions are
} rather dull, ending in a series of (’*2’) or (’+2’, ‘*2’) operations
to
} shift in zero and one bits, followed by a single ‘/2’ if the target
} value is odd (WARNING: this is just a hunch; I may be completely wrong
} here)
Yeah, that’s what I’m seeing. Take a look at some results (code below
the
line of ####):
% ruby test60.rb 2 9
[2, 4, 8, 16, 18, 9]
Ops = 5: dddah
real 0m0.022s
user 0m0.017s
sys 0m0.006s
% ruby test60.rb 9 2
[9, 18, 20, 10, 12, 6, 8, 4, 2]
Ops = 8: dahahahh
real 0m0.023s
user 0m0.017s
sys 0m0.008s
% ruby test60.rb 999 222
[999, 1998, 2000, 1000, 500, 250, 252, 126, 63, 65, 67, 69, 71, 142,
144, 72, 36, 38, 19, 21, 23, 25, 27, 54, 108, 110, 220, 222]
Ops = 27: dahhhahhaaaadahhahaaaaddada
real 0m0.023s
user 0m0.018s
sys 0m0.005s
% ruby test60.rb 222 999
[222, 224, 112, 114, 116, 118, 120, 122, 124, 248, 496, 498, 996, 998,
1996, 1998, 999]
Ops = 16: ahaaaaaaddadadah
real 0m0.022s
user 0m0.015s
sys 0m0.007s
% ruby test60.rb 32 48
[32, 16, 18, 20, 22, 24, 48]
Ops = 6: haaaad
real 0m0.021s
user 0m0.013s
sys 0m0.008s
% ruby test60.rb 48 32
[48, 24, 26, 28, 30, 32]
Ops = 5: haaaa
real 0m0.022s
user 0m0.014s
sys 0m0.008s
% ruby test60.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, 22, 24, 26, 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]
Ops = 171:
dahahhhahhhahhhahahahahahahahahahhahahhhahahahhhahahhahhahhahahahhahahahhaaaaadadadadddadadadadddadaddadaddaddadaddaddadadaddadadddaddadadadaddddadddaddaddddadadadadadadad
real 0m0.039s
user 0m0.032s
sys 0m0.007s
% ruby test60.rb 8591982807778218492 150128850109293
[8591982807778218492, 4295991403889109246, 4295991403889109248,
2147995701944554624, 1073997850972277312, 536998925486138656,
268499462743069328, 134249731371534664, 67124865685767332,
33562432842883666, 33562432842883668, 16781216421441834,
16781216421441836, 8390608210720918, 8390608210720920, 4195304105360460,
2097652052680230, 2097652052680232, 1048826026340116, 524413013170058,
524413013170060, 262206506585030, 262206506585032, 131103253292516,
65551626646258, 65551626646260, 32775813323130, 32775813323132,
16387906661566, 16387906661568, 8193953330784, 4096976665392,
2048488332696, 1024244166348, 512122083174, 512122083176, 256061041588,
128030520794, 128030520796, 64015260398, 64015260400, 32007630200,
16003815100, 8001907550, 8001907552, 4000953776, 2000476888, 1000238444,
500119222, 500119224, 250059612, 125029806, 125029808, 62514904,
31257452, 15628726, 15628728, 7814364, 3907182, 3907184, 1953592,
976796, 488398, 488400, 244200, 122100, 61050, 61052, 30526, 30528,
15264, 7632, 3816, 1908, 954, 956, 478, 480, 240, 120, 60, 30, 32, 34,
36, 38, 40, 42, 44, 46, 48, 50, 25, 27, 29, 31, 33, 66, 68, 136, 272,
544, 546, 1092, 2184, 4368, 8736, 8738, 17476, 34952, 34954, 69908,
139816, 139818, 279636, 559272, 1118544, 1118546, 2237092, 2237094,
4474188, 8948376, 17896752, 35793504, 35793506, 71587012, 71587014,
143174028, 286348056, 572696112, 572696114, 1145392228, 2290784456,
4581568912, 9163137824, 18326275648, 36652551296, 73305102592,
146610205184, 293220410368, 586440820736, 586440820738, 1172881641476,
1172881641478, 2345763282956, 4691526565912, 4691526565914,
9383053131828, 9383053131830, 18766106263660, 37532212527320,
37532212527322, 75064425054644, 75064425054646, 150128850109292,
300257700218584, 300257700218586, 150128850109293]
Ops = 157:
hahhhhhhhahahahhahhahahhahahahhhhhahhahahhhahhhhahhahhhahhahhhahhhahahhhhhahahhhhaaaaaaaaaahaaaadadddaddddaddaddadddadaddddadadddaddddddddddadaddadaddadaddah
real 0m0.039s
user 0m0.030s
sys 0m0.010s
(All times on a dual G4 800.)
################################################################
require ‘60’
include NumericMazeSolver
src = ARGV[0].to_i
dst = ARGV[1].to_i
solution, ops = Solver.new(src, dst).solve
p solution
puts “\nOps = #{solution.length-1}: #{ops}”
####################################################################
module NumericMazeSolver
module BitHelpers
def bit_len(num)
return num.to_s(2).length
end
end
class NumericPath
attr_reader :result, :ops
def initialize(s)
@result = [s]
@ops = ''
end
def reset(s = nil)
@result.slice!(1, @result.length)
@result[0] = s if s
@ops = ''
end
def cur
@result.last
end
def src
@result.first
end
def add_two
@result << (cur + 2)
@ops << 'a'
#p @result
end
def double
@result << (cur << 1)
@ops << 'd'
#p @result
end
def halve
c = cur
fail "Trying to halve an odd number: #{c}" unless (c % 2) == 0
c >>= 1
@result << c
@ops << 'h'
#p @result
end
def add_one
double
add_two
halve
end
end
class Solver
include BitHelpers
def validate(src, dst)
fail "We only deal with integers." unless
(dst.kind_of? Integer) && (src.kind_of? Integer)
fail "Not dealing with negative numbers" if
(dst<0) || (src<0)
fail "Can't get to zero from a positive number." if
(dst==0) && (src>0)
end
def initialize(src, dst)
validate(src, dst)
@dst = dst
@dst_bit_len = bit_len(@dst)
@result = NumericPath.new(src)
end
def shifted_diff
tmpsrc = @result.cur
tmpdst = @dst
src_bit_len = bit_len(tmpsrc)
shift = src_bit_len - @dst_bit_len
if shift < 0
tmpsrc >>= shift #really a left shift, since shift is negative
else
tmpdst <<= shift
end
xor_not_sub = tmpdst < tmpsrc
diff = xor_not_sub ? (tmpdst ^ tmpsrc) : (tmpdst - tmpsrc)
top_matched = bit_len(tmpdst) - bit_len(diff)
return [ diff, shift, top_matched, src_bit_len ]
end
def solve
@result.reset
while @result.cur != @dst
diff, shift, top_matched, src_bit_len = shifted_diff
dist_from_top = src_bit_len - top_matched
if diff==0
while shift > 0
@result.halve
shift -= 1
end
while shift < 0
@result.double
shift += 1
end
elsif dist_from_top > 5
# getting there
try_to_halve(@result.cur)
elsif dist_from_top == 5
# one away!
# do this now in case we'd have to double-add-halve
# unnecessarily later
bit = 1 << (2 + shift + top_matched)
if (diff&bit) != 0
@result.add_two
end
@result.halve
elsif dist_from_top == 4
if shift > 0
try_to_halve(@result.cur)
else
4.times { @result.add_two }
end
elsif dist_from_top == 3
if shift > 0
try_to_halve(@result.cur)
else
2.times { @result.add_two }
end
elsif dist_from_top == 2
@result.add_two
else
@result.double
end
end
return [ @result.result, @result.ops ]
end
private
def try_to_halve(cur)
if ((cur&1) != 0)
# odd, so we can't halve yet
@result.double
@result.add_two
elsif ((cur&2) != 0)
# won't be able to halve again
@result.add_two
else
@result.halve
end
end
end
end
################################################################################
} Reinder
–Greg
Kenneth C. wrote:
Gregory S. wrote:
This is my first Ruby quiz. I was hoping to have the whole thing done
by the end of the first 48 hours, but I kept getting hung up on edge
cases.
I did figure out the binary approach on my own, though.Gregory, this is an amazing solution! However I got a failure trying
some arbitrarily selected src and dst values:$ ruby test60.rb 4934939 39329291
./60.rb:47:inhalve': Trying to halve an odd number: 49 (RuntimeError) from ./60.rb:127:insolve’
from test60.rb:7
Another case with smaller numbers:
$ ruby test60.rb 49 64
./60.rb:47:in halve': Trying to halve an odd number: 49 (RuntimeError) from ./60.rb:127:insolve’
from test60.rb:7
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 use
@@max = [(source + 2) * 2, target * 2].max
which matches your roof almost exactly (The small assymetry is due to
the
missing sub2 operator, naturally.). The speedup is huge, as you can see
in some other posting of mine. I’m not entirely certain about the
optimality
property, but look at the following example:
13, 15, 30, 32, 16, 8 # what I thought of myself, pushing through the
roof
13, 26, 28, 14, 16, 8 # what the program found, not going through the
roof
Where the point is that an odd number either +1 or +3 can always be
halved
twice, and there is no point in adding two first (though maybe in
between).
I’m even thinking
[source2+2, target2].max
could be the roof, but hey, what’s 2 more or less.
Ah well, this is not my field of expertise. Somebody can shed more light
on
this?
Bye,
Kero.
Hey everyone,
Like so many people before me, this is my first Ruby Q. that I am
letting out to the world.
The interesting thing about my solution is that I managed to come up
with most of the previously mentioned optimizations for the BFS type of
solution and I came up with one more that has not yet been mentioned.
The value I use for deciding when to stop processing nodes because they
are too far from the max value is 3max(start,end). I saw that someone
used 2max+4, so potentially my code could be improved by using that
instead.
The optimization that I have that I haven’t seen anyone else use is
always starting with the maximum value and going to the smaller value.
This allows a lot of branches to be killed early because the value gets
too high. Obviously, switching the start and end value means I need to
do num - 2 instead of num + 2 and also reverse the results.
Here is the money test on my 1.80 Ghz Pentium M:
solve_maze(222, 9999) = [222, 224, 112, 56, 28, 30, 32, 34, 36, 38, 76,
78, 156,
312, 624, 1248, 2496, 2498, 4996, 4998, 9996, 19992, 19994, 9997,
9999]
Length: 25
Tree size: 3608
0.120000 0.000000 0.120000 ( 0.120000)
Sincerely,
require ‘benchmark’
class Integer
def odd?
return self % 2 == 1
end
def even?
return !odd?
end
end
#Aliases for more quene like syntax
class Array
alias deq shift
alias enq <<
end
#Node class that knows both its children and parent
#Also, takes an intial value and a function to perform on that value
#When retrieving value from a node, the action is performed on the
value the first time
#All subsequent calls to value returns the return value of the first
time action was called with value
class Node
attr_reader :action, :children, :parent
def initialize(value, action, parent=nil)
@value = value
@action = action
@children = []
@parent = parent
@done_action = false
end
#find the path to the root node from the current node
def get_path_to_root
if(parent == nil)
return [value]
end
parent.get_path_to_root<<value
end
def tree_size
#remember that if there are no children, aka this is a leaf node,
this returns 1, the initial value of result
return children.inject(1){|result,child| result + child.tree_size }
end
def value
if(!@done_action)
@done_action = true
return @value = @action.call(@value)
end
return @value
end
#print tree in a stringified array format
def tree_as_array
print “%d” % value
print “[” if children.length != 0
children.each_with_index{|child, index| child.tree_as_array; print
", " if index != children.length - 1}
print “]” if children.length != 0
end
end
#Solves the numeric maze with a bunch of optimizations
#Optimizations:
#(1) if parent action was halve, no child should be double
#(2) if parent action was double, no child should halve
#(3) if value of current node is greater than 3 times the
max(start_num, end_num), don’t double or add 2
#(4) if value of current node has already been found, stop processing
this node
#(5) start_num should always be >= end_num. This is an optimization
because of (3).
tree. This is done
the results be reversed if start and end are switched.
def solve_maze(start_num, end_num)
reverse_solution = start_num < end_num
if reverse_solution
add_two = lambda{ |int| int-2 }
start_num,end_num = end_num,start_num
else
add_two = lambda{ |int| int+2 }
end
double = lambda{ |int| int2 }
halve = lambda{ |int| int/2 }
no_action = lambda{ |int| int } #special case for the start number
root = Node.new(start_num, no_action)
#keep track of numbers found to prevent repeat work
hash = {}
#the queue for the BFS
q = [root]
#start_num is always larger than end_num, numbers larger than this
are unlikely to be in
#an optimal solution
big_val = start_num3
while q.length != 0
node = q.deq
val = node.value
if val == end_num
solution = node.get_path_to_root
solution.reverse! if reverse_solution
return [solution, root.tree_size()]
end
if !hash.has_key?(val)
node.children << Node.new(val, add_two, node) if val.abs <
big_val
node.children << Node.new(val,double,node) if node.action !=
halve && val.abs < big_val
node.children << Node.new(val,halve,node) if val.even? &&
node.action != double
node.children.each{|kid| q.enq(kid)}
hash[val] = true
end
end
end
if ARGV.length.odd? && !ARGV.length.zero?
print “Should be an even number of arguments in the format of
start_num end_num [start_num end_num] …\n”
exit
end
puts Benchmark.measure{
ARGV.each_index do |index|
if index.odd?
next
else
start_num = ARGV[index].to_i
end_num = ARGV[index + 1].to_i
result = solve_maze(start_num, end_num)
print “solve_maze(”,start_num, ", “,end_num,”) =
",result[0].inspect,
"\nLength: ",result[0].length,
“\nTree size: “,result[1],”\n”
end
end
}
On 1/2/06, Gregory S. [email protected] wrote:
I’m pretty sure the results are guaranteed to
be optimal, too.
$ ruby test60.rb 255 257
[255, 510, 512, 514, 257]
Ops = 4: daah
Same problem I ran into 
On Mon, Jan 02, 2006 at 10:19:00AM +0900, Kenneth C. wrote:
} Kenneth C. wrote:
} > Gregory S. wrote:
} >> This is my first Ruby quiz. I was hoping to have the whole thing
done
} >> by the end of the first 48 hours, but I kept getting hung up on
edge
} >> cases.
} >> I did figure out the binary approach on my own, though.
} >>
} >
} > Gregory, this is an amazing solution! However I got a failure trying
} > some arbitrarily selected src and dst values:
} >
} > $ ruby test60.rb 4934939 39329291
} > ./60.rb:47:in halve': Trying to halve an odd number: 49 (RuntimeError) } > from ./60.rb:127:insolve’
} > from test60.rb:7
}
} Another case with smaller numbers:
}
} $ ruby test60.rb 49 64
} ./60.rb:47:in halve': Trying to halve an odd number: 49 (RuntimeError) } from ./60.rb:127:insolve’
} from test60.rb:7
Ratzafratz. I’ll look into it. Did I mention running into problems with
edge cases? Oy. Thanks for the test cases.
–Greg
On 1/2/06, Christer N. [email protected] wrote:
1000000010 >> 1
<-- <-- <-- 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 toyed with writing a optimize-function, which would take the
midstate list and find patterns that are known to be suboptimal. One
pattern to look for would be going from odd number to another, where
the distance is even and less than 32, which is the point where the
multiply, add, divide, etc starts being less ops than add 2.
The optimizer iterates from start of path, and then for each number,
find from end of path the farthest matching number, replace the ops
between with optimized version.
E.g. for [255, 510, 512, 514, 257], start from 255, then iterate
remaining numbers from end to start, 257 matches, so replace the ops
between with +2 to get [255, 257].
Other patterns? Hmm, dunno. 12 → 11 is suboptimal, 14 → 13 too, both
demonstrating a faster solution that would be divide to odd, add 2s to
match. I hypothesize that this only happens with small numbers, where
the divide-to-odd + add 2s is less ops.
[14, 16, 8, 4, 6, 12, 24, 26, 13] → [14, 7, 9, 11, 13]
(This is also weird in that Gregory’s solver gives a one step shorter
solution: [14, 16, 8, 10, 12, 24, 26, 13])
Food for thought,
Ilmari
Here’s my (first) solution (ever) for quiz #60.
I also choose a breadth-first search algorithm because I’m probably
going to need a decent searching algorithm in the near future. To
maximize reusability, I implemented 6 methods in the Integer class
that abstract the problem-specific logic out of the searching
algorithm. When I use a different ‘node’ class, I will also need to
include the Comparable mix-in and define the <=> method for the
Array.max method on line #40.
The running time for the algorithm is O(N), where N is the number of
integers the algorithm ‘visits’. To limit the number of visited
integers, I added a few of the clever optimizations already
mentioned: removing consecutive double/halves and removing adjacent
values greater than a maximum.
$ time ./quiz.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 0m2.098s
user 0m1.868s
sys 0m0.091s
Not faster than Dominik’s, but still pretty fast. Perhaps my 1.33
Ghz G4 and 768 MB of RAM is holding my back? 
Although this is one of many BFS algorithms posted, I’d really
appreciate some feedback on my implementation. Especially in regards
to potential speed ups, missed opportunities for ruby idioms, and
additional optimizations to the adjacency_list method.
~ ryan ~
#!/usr/bin/env ruby
class Integer
attr_reader :distance, :discovered
def odd?
self % 2 != 0
end
adjacent values greater than a maximum
def adjacency_list(maximum = Infinity)
list = []
list << self * 2 unless @parent == self * 2 or self * 2 > maximum
list << self / 2 unless self.odd? or @parent == self / 2
list << self + 2 unless self + 2 > maximum
list || []
end
def visit!(parent = nil)
@discovered = true
@parent = parent
@distance = parent ? parent.distance + 1 : 0
end
def path_from(start)
if self == start
[start]
else
if @parent == nil
raise “no path from #{start} to #{self} exists”
else
@parent.path_from(start) << self
end
end
end
end
def solve(start, target)
return [start] if start == target
roof = [start, target].max * 2 + 2
start.visit!
queue = [start]
queue.each do |vertex|
vertex.adjacency_list(roof).each do |child|
unless child.discovered
child.visit!(vertex)
return target.path_from(start) if target == child
queue.push(child)
end
end
end
end
if $0 == FILE
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) }
p solve(start, finish)
end
On Sun, 01 Jan 2006 19:27:56 +0100, [email protected] wrote:
For this quiz I took what I made for the word chain quiz and modified
it a bit.
I did that, too 
My solution uses unidirectional BFS (like many others). The NumericMaze
class is generic, meaning that it can also work with other ops, so
naturally it doesn’t have any optimizations for this special problem. I
only limit the search space in the “if $0 == FILE” part.
Dominik
class NumericMaze
OP_DOUBLE = lambda { |x| x * 2 }
OP_HALVE = lambda { |x| x % 2 == 0 ? x / 2 : nil }
OP_ADD_TWO = lambda { |x| x + 2 }
# ops is an array of lambdas, each lambda returns a next step for a
given
# number, or nil if no next step is possible for the given number
def initialize(ops = [OP_DOUBLE, OP_HALVE, OP_ADD_TWO])
@ops = ops
end
def solve(start, target, max_num = nil)
# build chain with simple breadth first search
current = [start]
return current if start == target
pre = { start => nil } # will contain the predecessors
catch(:done) do
until current.empty?
next_step = []
current.each do |num|
@ops.each do |op|
unless (step_num = op[num]).nil?
# have we seen this number before?
unless pre.has_key?(step_num) ||
(max_num && step_num > max_num)
pre[step_num] = num
throw(:done) if step_num == target
next_step << step_num
end
end
end
end
current = next_step
end
return nil # no chain found
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
chain.reverse
end
end
if $0 == FILE
a, b, = *ARGV.map { |str| Integer(str) }
p NumericMaze.new.solve(a, b, [a, b].max.abs * 3)
end
On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S. [email protected]
wrote:
G4 and 768 MB of RAM is holding my back?
It actually is faster than my version:
$ time ruby ryan_org.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.197s
user 0m1.138s
sys 0m0.026s
(Pentium M 1.5)
Although this is one of many BFS algorithms posted, I’d really
appreciate some feedback on my implementation. Especially in regards to
potential speed ups, missed opportunities for ruby idioms, and
additional optimizations to the adjacency_list method.
Here is a patch that speeds it up a bit:
— ryan_org.rb 2006-01-02 16:47:20.000000000 +0100
+++ ryan.rb 2006-01-02 16:47:16.000000000 +0100
@@ -1,5 +1,5 @@
class Integer
attr_reader :parent
def odd?
self % 2 != 0
@@ -15,9 +15,7 @@
end
def visit!(parent = nil)
def path_from(start)
@@ -40,7 +38,7 @@
queue = [start]
queue.each do |vertex|
vertex.adjacency_list(roof).each do |child|
unless child.discovered
unless child.parent
child.visit!(vertex)
return target.path_from(start) if target == child
queue.push(child)
It basically avoids some instance variable sets and removes distance,
which is unused.
$ time ruby ryan.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.031s
user 0m0.963s
sys 0m0.020s
I think it is an interesting idea to avoid using a hash, by storing the
parent info in an instance variable of the Fixnums and it seems to be
quite fast. But it has one big downside: solve only works once, because
Fixnums are immediate values:
$ irb -r ryan
irb(main):001:0> solve 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]
irb(main):002:0> solve 22222, 99999
=> [22222]
Dominik
On Jan 2, 2006, at 11:24 AM, Dominik B. wrote:
On Mon, 02 Jan 2006 08:25:08 +0100, J. Ryan S.
[email protected] wrote:It actually is faster than my version:
Oh nice.
self % 2 != 0@@ -40,7 +38,7 @@
distance, which is unused.
Seems like the biggest performance gain is obtained by removing the
ternary operation when setting @distance in the visit! method.
Although it wasn’t necessary to solve this problem, I included
@distance calculations because they are (or at least seem to be)
intrinsic to searching algorithms. I should have caught this before
posting my solution.
I think it is an interesting idea to avoid using a hash, by storing
the parent info in an instance variable of the Fixnums and it seems
to be quite fast.
The biggest performance gain comes from the optimization that removes
adjacent values greater than a maximum. It takes the infinite search
space of integer values and reduces it to a linear search space.
Kudos on the math wizards who originally posted that suggestion.
But it has one big downside: solve only works once, because Fixnums
are immediate values:
Good observation! Unfortunately, this problem has an infinite search
space of integer values. With a finite search space, the algorithm
can loop through and reset each vertex or node before starting. And
the best part is the running time for the BFS algorithm with this
technique remains linear. In the general case, it is O(V + E), where
V is the number of vertices and E is the number of edges in the
finite graph. (In my algorithm, N, which is the number of integers
visited, is the same as E.)
~ ryan ~
I didn’t like having the roof calculation done inside the solve
method. So here is my revised algorithm, including Dominik’s
suggestions and a new roof class method for Integer.
#!/usr/bin/env ruby
class Integer
attr_reader :parent
@@roof = 1.0/0.0
def self.roof(*args)
@@roof = args.max * 2 + 2 || @@roof
end
def odd?
self % 2 != 0
end
adjacent values greater than a maximum
def adjacency_list
list = []
list << self * 2 unless @parent == self * 2 or self * 2 > @@roof
list << self / 2 unless self.odd? or @parent == self / 2
list << self + 2 unless self + 2 > @@roof
list
end
def visit!(parent = nil)
@parent = parent
end
def path_from(start)
if self == start
[start]
else
if @parent == nil
raise “no path from #{start} to #{self} exists”
else
@parent.path_from(start) << self
end
end
end
end
def solve(start, target)
return [start] if start == target
Integer.roof(start, target)
start.visit!
queue = [start]
queue.each do |vertex|
vertex.adjacency_list.each do |child|
unless child.parent
child.visit!(vertex)
return target.path_from(start) if target == child
queue.push(child)
end
end
end
end
if $0 == FILE
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) }
p solve(start, finish)
end
~ ryan ~
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
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 = []
[AddTwo, Double, Halve].each {|op| @ops <<
op.new(@start, @goal) }
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
# there should be a better way to recover the steps
than carrying them
# around in the search tree (depth first search for
example?)
while current = @queue.shift
temp_goal, steps = *current # parallel
assignment in conditionals won’t work
return solution(steps) if done_with? temp_goal
next if @visited[temp_goal] # been there, done
that
#puts "#{@start} -> #{@goal}: testing
#{temp_goal}, steps so far: #{steps.join(" “)}”
#gets
@visited[temp_goal] = true
new_steps = steps + [temp_goal]
@ops.each do |op|
@queue << [op.apply(temp_goal),
new_steps] if op.makes_sense? temp_goal
end
end
# my guess is, that there’s always a solution. any
proof?
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
class TwoOperation
def initialize(start, goal)
@start, @goal = start, goal
end
def apply(temp_goal)
temp_goal.send(@meth, 2)
end
def makes_sense?
false
end
end
class Double < TwoOperation
def initialize(start, goal)
super
@meth = 
end
def makes_sense?(temp_goal)
temp_goal.even?
end
end
class Halve < TwoOperation
def initialize(start, goal)
super
@meth = :* # heh a kissing smiley, ruby is soo cute
end
def makes_sense?(temp_goal)
# was (@goal < @start and temp_goal.even?) or (not
temp_goal.even?)
temp_goal.odd? or @goal < @start
end
end
class AddTwo < TwoOperation
def initialize(start, goal)
super
@meth = :-
end
def makes_sense?(temp_goal)
temp_goal > 1
end
end
def solve(a, b)
Solver.solve(a,b)
end
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
def sub2
self - 2
end
Step = Struct.new(:dist, :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)
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
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[:parent] until node.nil?
result
end
tree = []
node_index = []
ARGV.each { |x|
root = {:num => x.to_i, :parent => 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, :parent
=> node } # build the next level
}
}
tree[x] = next_nodes
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