R
Ruby Quiz
Did you spot the errors in my Heap class? Dominik Bathon did, so let's fix
those up before we go any further.
To start with, the extract() method would not remove the last item from the
heap, because it would pop() it off but then reassign it to @heap[1]. Here's my
fix:
def extract( )
case size
when 0
nil
when 1
@heap.pop
else
extracted = @heap[1]
@heap[1] = @heap.pop
sift_down
extracted
end
end
That handles the edge cases with a little more care.
The other issue was that I originally developed Heap using the normal comparison
operators, but later decided to add the @comp block to allow customized ordering
for any Heap you create. I thought I updated all of the comparisons, but the
truth is that I missed one in sift_down(). Here's the corrected (by Dominik)
method:
def sift_down( )
i = 1
loop do
c = 2 * i
break if c >= @heap.size
c += 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap[c]] < 0
break if @comp[@heap, @heap[c]] <= 0
@heap[c], @heap = @heap, @heap[c]
i = c
end
end
Enough about James's buggy code, let's talk trees. How do they look? Let's
compare:
Brian Schroeder
===============
12
.----' `----.
20 15
.-' `-. .-' `-.
29 23 17 22
/ \ / \ /
35 40 26 51 19
Dave Burt
=========
12-15-22-
| | `-
| `-17-
| `-19
`-20-23-51
| `-26
`-29-40
`-35
Dominik Bathon
==============
12
|
+--+-----+
| |
20 15
| |
+--+--+ +-++
| | | |
29 23 17 22
| | |
+-++ +-++ +
| | | | |
35 40 26 51 19
Florian Frank
=============
12
+---20
| +---29
| | +---35
| | `---40
| `---23
| +---26
| `---51
`---15
+---17
| `---19
`---22
David Tran
==========
+-o 22
|
+-o 15
| |
| +-o 17
| |
| +-o 19
|
-o 12
|
| +-o 51
| |
| +-o 23
| | |
| | +-o 26
| |
+-o 20
|
| +-o 40
| |
+-o 29
|
+-o 35
There's some interesting variety in there. Which display you prefer is probably
a matter taste, but hopefully there's something in there for everyone.
It may be interesting to note that this quiz grew out of an actual problem I was
working with. I dove into the problem fully expecting to spend ten minutes on
it and was surprised when I kept running into complication after complication.
I had to restart twice as I realized that I was attacking it from the wrong
angle.
Given that, I was looking through the solutions with an eye for elegance and
simplicity. I found a couple of things I liked, but really I thought David
Tran's solution is what I was searching for. Let's take a look at that code:
def to_s( )
return "[empty heap]" if @heap.size <= 1
result = ''
root = 1
if has_right?(root)
print_node(result, ' ', true, right_index(root))
result << " |\n"
end
result << "-o #{@heap[root]}\n"
if has_left?(root)
result << " |\n"
print_node(result, ' ', false, left_index(root))
end
result
end
Clearly that relies on a few helper methods we'll meet shortly, but it's
surprisingly straight forward. The code checks for the special case of an empty
heap, then initializes a String to hold the result and a root node for the tree.
From there, the method checks to see if the root has a right child node, and
passes some information down to print_node() if it does. Note that an extra
line containing "|\n" is added if after the call.
After that, the root node is added to the result and the left child node is
forwarded to print_node(), if needed. This time though the "|\n" line is added
before the call.
Finally, the completed result is returned.
You can see the the right side is handled first, then the node itself, and
finally left. Put another way, the "right" side will be on top, the node in the
middle, then the "left" is placed on the bottom. That may seem odd, but you
need to remember that this tree is on its side. If you rotate it 90% clockwise
in your mind's eye, everything should snap into place.
Here's the work we've seen so far:
print_node(..., right_index(root))
|
-o root
|
print_node(..., left_index(root))
The four index methods should be pretty obviously. They're the node jumping
math right out of the quiz. Here they are:
private
def left_index( index ) ; index * 2 ; end
def right_index( index ) ; index * 2 + 1 ; end
def has_left?( index ) ; left_index(index) < @heap.size ; end
def has_right?( index ) ; right_index(index) < @heap.size ; end
I think pulling those out into methods is one of the things that kept this code
so clean and approachable.
The last piece of this puzzle is the mysterious print_node() method. Let's dig
inside that now:
def print_node( result, line, right, index )
if has_right?(index)
print_node(result, line + (right ? ' ' : '| '), true,
right_index(index))
result << "#{line}#{right ? ' ' : '|'} |\n"
end
result << "#{line}+-o #{@heap[index]}\n"
if has_left?(index)
result << "#{line}#{right ? '|' : ' '} |\n"
print_node(result, line + (right ? '| ' : ' '), false,
left_index(index))
end
end
We can see that this method takes four parameters. The first is the result
String we are building up, which it appends to. The second is the line up to
this branch of the tree, used in indenting new lines. The third parameter is
true or false, depending if we're on the right side of the tree (true) or left
(false). Finally, the method receives the index of the node to use as the root
of the branch.
The rest of the method is very similar to the original to_s(), even in its
recursive calls to itself to drill down into the tree. The output lines are
slightly different, mainly to account for the line variable that must be
prepended and also to deal with which way the pipe characters are flowing.
The only minus here is the near duplication of code between to_s() and
print_node(). If we want, we can remove it though. The following code is my
adaptation of David's methods to remove the duplication but produce identical
results:
def to_s( )
return "[empty heap]" if @heap.size <= 1
print_node("", "", true, true, 1).gsub!(/^[+ ]/, "")
end
private
def left_index( index ) ; index * 2 ; end
def right_index( index ) ; index * 2 + 1 ; end
def has_left?( index ) ; left_index(index) < @heap.size ; end
def has_right?( index ) ; right_index(index) < @heap.size ; end
def print_node( result, line, right, left, index )
if has_right?(index)
print_node( result, line + (right ? ' ' : '| '), true, false,
right_index(index) )
result << "#{line}#{right ? ' ' : '|'} |\n"
end
result << "#{line}+-o #{@heap[index]}\n"
if has_left?(index)
result << "#{line}#{left ? ' ' : '|'} |\n"
print_node( result, line + (left ? ' ' : '| '), false, true,
left_index(index) )
end
result
end
The resulting tree may be a little unusual with it's hanging nodes, but shifting
all data to the right freed the code of the tedious need to account for data
width at each point. Florian Frank capitalized on the same trick using a
slightly different tree format and that code is also pretty straight forward.
It's amazing what a little rethinking of the problem can do.
My usual thanks to all the solvers. You again taught me (and hopefully others)
new things about how code should be designed.
Ruby Quiz will take a one week break starting tomorrow, so I can enjoy a little
summer vacation with my family. As always, I hope to return to an inbox full of
new quiz material. Send those ideas along! The Quiz will return with a task to
show how Ruby can help you cash in on the stock market. Stay tuned...
those up before we go any further.
To start with, the extract() method would not remove the last item from the
heap, because it would pop() it off but then reassign it to @heap[1]. Here's my
fix:
def extract( )
case size
when 0
nil
when 1
@heap.pop
else
extracted = @heap[1]
@heap[1] = @heap.pop
sift_down
extracted
end
end
That handles the edge cases with a little more care.
The other issue was that I originally developed Heap using the normal comparison
operators, but later decided to add the @comp block to allow customized ordering
for any Heap you create. I thought I updated all of the comparisons, but the
truth is that I missed one in sift_down(). Here's the corrected (by Dominik)
method:
def sift_down( )
i = 1
loop do
c = 2 * i
break if c >= @heap.size
c += 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap[c]] < 0
break if @comp[@heap, @heap[c]] <= 0
@heap[c], @heap = @heap, @heap[c]
i = c
end
end
Enough about James's buggy code, let's talk trees. How do they look? Let's
compare:
Brian Schroeder
===============
12
.----' `----.
20 15
.-' `-. .-' `-.
29 23 17 22
/ \ / \ /
35 40 26 51 19
Dave Burt
=========
12-15-22-
| | `-
| `-17-
| `-19
`-20-23-51
| `-26
`-29-40
`-35
Dominik Bathon
==============
12
|
+--+-----+
| |
20 15
| |
+--+--+ +-++
| | | |
29 23 17 22
| | |
+-++ +-++ +
| | | | |
35 40 26 51 19
Florian Frank
=============
12
+---20
| +---29
| | +---35
| | `---40
| `---23
| +---26
| `---51
`---15
+---17
| `---19
`---22
David Tran
==========
+-o 22
|
+-o 15
| |
| +-o 17
| |
| +-o 19
|
-o 12
|
| +-o 51
| |
| +-o 23
| | |
| | +-o 26
| |
+-o 20
|
| +-o 40
| |
+-o 29
|
+-o 35
There's some interesting variety in there. Which display you prefer is probably
a matter taste, but hopefully there's something in there for everyone.
It may be interesting to note that this quiz grew out of an actual problem I was
working with. I dove into the problem fully expecting to spend ten minutes on
it and was surprised when I kept running into complication after complication.
I had to restart twice as I realized that I was attacking it from the wrong
angle.
Given that, I was looking through the solutions with an eye for elegance and
simplicity. I found a couple of things I liked, but really I thought David
Tran's solution is what I was searching for. Let's take a look at that code:
def to_s( )
return "[empty heap]" if @heap.size <= 1
result = ''
root = 1
if has_right?(root)
print_node(result, ' ', true, right_index(root))
result << " |\n"
end
result << "-o #{@heap[root]}\n"
if has_left?(root)
result << " |\n"
print_node(result, ' ', false, left_index(root))
end
result
end
Clearly that relies on a few helper methods we'll meet shortly, but it's
surprisingly straight forward. The code checks for the special case of an empty
heap, then initializes a String to hold the result and a root node for the tree.
From there, the method checks to see if the root has a right child node, and
passes some information down to print_node() if it does. Note that an extra
line containing "|\n" is added if after the call.
After that, the root node is added to the result and the left child node is
forwarded to print_node(), if needed. This time though the "|\n" line is added
before the call.
Finally, the completed result is returned.
You can see the the right side is handled first, then the node itself, and
finally left. Put another way, the "right" side will be on top, the node in the
middle, then the "left" is placed on the bottom. That may seem odd, but you
need to remember that this tree is on its side. If you rotate it 90% clockwise
in your mind's eye, everything should snap into place.
Here's the work we've seen so far:
print_node(..., right_index(root))
|
-o root
|
print_node(..., left_index(root))
The four index methods should be pretty obviously. They're the node jumping
math right out of the quiz. Here they are:
private
def left_index( index ) ; index * 2 ; end
def right_index( index ) ; index * 2 + 1 ; end
def has_left?( index ) ; left_index(index) < @heap.size ; end
def has_right?( index ) ; right_index(index) < @heap.size ; end
I think pulling those out into methods is one of the things that kept this code
so clean and approachable.
The last piece of this puzzle is the mysterious print_node() method. Let's dig
inside that now:
def print_node( result, line, right, index )
if has_right?(index)
print_node(result, line + (right ? ' ' : '| '), true,
right_index(index))
result << "#{line}#{right ? ' ' : '|'} |\n"
end
result << "#{line}+-o #{@heap[index]}\n"
if has_left?(index)
result << "#{line}#{right ? '|' : ' '} |\n"
print_node(result, line + (right ? '| ' : ' '), false,
left_index(index))
end
end
We can see that this method takes four parameters. The first is the result
String we are building up, which it appends to. The second is the line up to
this branch of the tree, used in indenting new lines. The third parameter is
true or false, depending if we're on the right side of the tree (true) or left
(false). Finally, the method receives the index of the node to use as the root
of the branch.
The rest of the method is very similar to the original to_s(), even in its
recursive calls to itself to drill down into the tree. The output lines are
slightly different, mainly to account for the line variable that must be
prepended and also to deal with which way the pipe characters are flowing.
The only minus here is the near duplication of code between to_s() and
print_node(). If we want, we can remove it though. The following code is my
adaptation of David's methods to remove the duplication but produce identical
results:
def to_s( )
return "[empty heap]" if @heap.size <= 1
print_node("", "", true, true, 1).gsub!(/^[+ ]/, "")
end
private
def left_index( index ) ; index * 2 ; end
def right_index( index ) ; index * 2 + 1 ; end
def has_left?( index ) ; left_index(index) < @heap.size ; end
def has_right?( index ) ; right_index(index) < @heap.size ; end
def print_node( result, line, right, left, index )
if has_right?(index)
print_node( result, line + (right ? ' ' : '| '), true, false,
right_index(index) )
result << "#{line}#{right ? ' ' : '|'} |\n"
end
result << "#{line}+-o #{@heap[index]}\n"
if has_left?(index)
result << "#{line}#{left ? ' ' : '|'} |\n"
print_node( result, line + (left ? ' ' : '| '), false, true,
left_index(index) )
end
result
end
The resulting tree may be a little unusual with it's hanging nodes, but shifting
all data to the right freed the code of the tedious need to account for data
width at each point. Florian Frank capitalized on the same trick using a
slightly different tree format and that code is also pretty straight forward.
It's amazing what a little rethinking of the problem can do.
My usual thanks to all the solvers. You again taught me (and hopefully others)
new things about how code should be designed.
Ruby Quiz will take a one week break starting tomorrow, so I can enjoy a little
summer vacation with my family. As always, I hope to return to an inbox full of
new quiz material. Send those ideas along! The Quiz will return with a task to
show how Ruby can help you cash in on the stock market. Stay tuned...