[QUIZ] Drawing Trees (#40)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

A common implementation of Heap data structures involves storing their tree in a
single Array. If you add one extra element at the beginning (creating a base 1
Array), you can use easy math to find child nodes. This doesn't generally bother
the user, because you don't usually access a Heap by index.

Using that system and given any index i, 2 * i is the left child node and 2 * i
+ 1 is the right child node. So the root of the tree is i = 1 and it has a child
node at i = 2 and another at i = 3. Then the i = 2 node has child nodes at i =
4 and i = 5. Reversing the traversal, i / 2 (assuming integer division) will
bring you to a parent node.

Now take a deep breath and relax because I'm not going to ask you to write a
Heap. In fact, here's a basic pure Ruby implementation (not exhaustively
tested) using the system I just described:

class Heap
def initialize( *elements, &comp )
@heap = [nil]
@comp = comp || lambda { |p, c| p <=> c }

insert(*elements)
end

def clear( )
@heap = [nil]
end

def extract( )
extracted = @heap[1]
@heap[1] = @heap.pop unless @heap.size.zero?
sift_down
extracted
end

def insert( *elements )
elements.each do |element|
@heap << element
sift_up
end
end

def size( )
@heap.size - 1
end

def inspect( )
@heap[1..-1].inspect
end

def to_s( )
# Write this!
end

private

def sift_down( )
i = 1
loop do
c = 2 * i
break if c >= @heap.size

c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]
break if @comp[@heap, @heap[c]] <= 0

@heap[c], @heap = @heap, @heap[c]
i = c
end
end

def sift_up( )
i = @heap.size - 1
until i == 1
p = i / 2
break if @comp[@heap[p], @heap] <= 0

@heap[p], @heap = @heap, @heap[p]
i = p
end
end
end

priority_queue = Heap.new
priority_queue.insert(12, 20, 15, 29, 23, 17, 22, 35, 40, 26, 51, 19)
puts priority_queue

priority_queue.insert(13)
puts priority_queue

priority_queue.extract
puts priority_queue
__END__

If you read that real closely, you saw the blank Heap.to_s() method.
Implementing a Heap as an Array is one thing and it's easy to show like that
(see Heap.inspect() above). However, we generally envision a Heap as a tree,
not an Array. Wouldn't it be nice if Heap.to_s() would show it to us that way?
I think so too.

This week's Ruby Quiz is to write Heap.to_s() so that it returns an ASCII art
representation of a Heap as a tree. For example, here's what the first tree
printed by the above code might look like:

12
|
+-------+-------+
| |
20 15
| |
+---+---+ +---+---+
| | | |
29 23 17 22
| | |
+-+-+ +-+-+ +-+
| | | | |
35 40 26 51 19

Your tree doesn't have to look like that. Maybe you would prefer to draw it
horizontally. Maybe you make better looking ASCII art than me. Whatever.
Anything that gives a feel of the structure is fine.

Heaps don't have to hold two-digit Integers of course, any Comparable should
work...

 

[Florian Frank]

On 2005-07-22 22:05:26 +0900, Ruby Quiz wrote:
[Quiz #40]

Implementation:

class HeapVisualizer
def initialize(heap)
@heap = heap.instance_variable_get@heap)[1..-1]
end

def to_s
@curved = [ ]
recurse
end

private

def recurse(node = 0, level = 0)
result = ''
return result unless @heap[node]
for l in 0 ... level
result << if @curved[l]
l == level - 1 ? '`---' : ' ' * 4
else
l == level - 1 ? '+---' : '| '
end
end
result << "#{@heap[node]}\n"
left, right = (node << 1) + 1, (node << 1) + 2
if @heap

@curved[level] = @heap

? false : true
result << recurse(left, level + 1)
if @heap

@curved[level] = true
result << recurse(right, level + 1)
end
end
result
end
end

Usage:

def to_s( )
HeapVisualizer.new(self).to_s
end

Output:

12
+---20
| +---29
| | +---35
| | `---40
| `---23
| +---26
| `---51
`---15
+---17
| `---19
`---22
12
+---20
| +---29
| | +---35
| | `---40
| `---23
| +---26
| `---51
`---13
+---15
| +---19
| `---17
`---22
13
+---20
| +---29
| | +---35
| | `---40
| `---23
| +---26
| `---51
`---15
+---17
| `---19
`---22​

 

[Brian Schröder]

Hello Everybody,

so I finally got my internet access again after having struggled with
a big german internet provider for nearly two months and first thing I
did was to complete the ruby quiz of the week.

I decided to fit the binary tree into a very strict mask, I'm not
using information about the width of the subtrees to allow for better
packing, for this kind of things I prefer outputting dot code and
piping it into doc to get a nicely layouted tree in postscript format.
But this was not asked here, so following is my solution.

def to_s( )
# We have log_2(n) levels
#
# Level i includes at most 2**i nodes when indexed starting from zero
# That means last level needs the space for at most (2**(ceil(log_2(n))=
))=20
#
# Basic implementation: Reserve the space and fill it

# Some constants for the ascii art
short_arm_left =3D '/'
short_arm_right =3D '\'

arm_left_start =3D "'"
arm_left_end =3D "."

arm_right_start =3D "`"
arm_right_end =3D "."

arm_line =3D '-'

join_string =3D ' '

# Constants for position calculation
levels =3D size.log2.ceil

max_node_width =3D @heap[1..-1].map{ | node | node.to_s.length }.max
max_line_width =3D 2**(levels-1) * max_node_width +
(2**(levels-1)-1) * join_string.length

(0...levels).inject([]) { | result, level |
level_node_width =3D max_line_width / 2**level

# Draw the arms leading to the nodes on this level
if level > 0
result <<
Array.new(2**level) { | j |
if @heap[2**level+j] # Only draw an arm, if there is a n=
ode
if level_node_width < 5 # Draw short arm for short distances
(j.even? ? short_arm_left :
short_arm_right).center(level_node_width)
else # Draw long arm for long distances
if j.even?
(arm_left_end + arm_line * (level_node_width / 2 -
1) + arm_left_start).rjust(level_node_width)
else
(arm_right_start + arm_line * (level_node_width / 2 -
1) + arm_right_end ).ljust(level_node_width)
end
end
else
' ' * level_node_width
end
}.join(join_string)#.center(max_line_width)
end

# Draw the node on this level
result << @heap[2**level...2**(level+1)].map { | node |
node.to_s.center(level_node_width)
}.join(join_string)#.center(max_line_width)
}.join("\n")
end

I'm drawing each level at a time filling the raster that is given by
the number of nodes at this level. Extra sugar is drawing of different
kinds of arms depending on how much space the arm has to span. If it
is a long distance, I draw a real arm, for short distances I only use
a slash or backslash. This gives quite good results in my opinion.

best regards,

Brian

PS: Can somebody reverse engineer the sentence that lead to the word
heap? I'd be interested in how many insertion orders lead to this same
heap.

Example output:

Start
12 =20
.----' `----. =20
20 15 =20
.-' `-. .-' `-. =20
29 23 17 22 =20
/ / / =20
35 40 26 51 19

Insert 13
12 =20
.----' `----. =20
20 13 =20
.-' `-. .-' `-. =20
29 23 15 22 =20
/ / / =20
35 40 26 51 19 17

Pop minimum
13 =20
.----' `----. =20
20 15 =20
.-' `-. .-' `-. =20
29 23 17 22 =20
/ / / =20
35 40 26 51 19

Word heap
another =20
.--------------' `--------------. =20
are data =20
.------' `------. .------' `------. =20
random heap of kind =20
.--' `--. .--' `--. .--' `--. .--' =20
this the words on to some test =20

--=20
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

 

[Brian Schröder]

[snip]

I forgot to plug the website where the full solution is, but don't
look at it before reverse-engineering the word heap

http://ruby.brian-schroeder.de/quiz/heap/

regards,

Brian
--=20
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

 

[James Edward Gray II]

I forgot to plug the website where the full solution is, but don't
look at it before reverse-engineering the word heap

http://ruby.brian-schroeder.de/quiz/heap/

Is that page supposed to reference "crossword" in the documentation =20
and download links? The download links are broken, by the way.

James Edward Gray II

 

[Brian Schröder]

On Jul 25, 2005, at 7:35 AM, Brian Schr=F6der wrote:
=20
=20
Is that page supposed to reference "crossword" in the documentation
and download links? The download links are broken, by the way.
=20
James Edward Gray II
=20
=20
=20

Thank you james its fixed now. If I continue writing ruby quiz
solutions, I have to think of a better release system than copy -
paste. (Blush)

regards,

Brian

--=20
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

 

[Dave Burt]

Hi,

I apologise for my solution. I optimised the output for compactness, and
legibility suffers a little. Also my code is hard to read and is heavy on
bit operations because I was playing with the numbers instead of solving the
problem.

The code I added is listed below the sample output, which is below. A
complete Ruby file (including this, the Heap and some tests if you run it
from the command line) is available from:
http://www.dave.burt.id.au/ruby/heap.rb

Cheers,
Dave

SAMPLE OUTPUT:
13-15-22-
| | `-
| `-17-
| `-19
`-20-23-51
| `-26
`-29-40
`-35

another-data- kind-
| | `- test
| `- of- some
| `- to
`- are- heap- on
| `-words
`-random- the
`- this

RUBY CODE:
#
# Use a right-hand-side depth-first traversal of the tree to draw the right
# arms above the left arms, with the root at the left and leaves on the
# right:
#
# 1-3
# `2
#
def to_s( )

# empty heap -> empty string
return "" if empty?

d = depth

# w is the width of a column
w = Array.new(d) do |i|
@heap[2**i, 2**i].inject(0) {|m, o| [m, o.to_s.size].max }
end

# ww is the total width of the string (and of each line in it)
ww = w.inject {|m, o| m + o + 1 } - 1

# done is a flag for the traversal algorithm - it marks indexes in
# @heap that have already been traversed.
done = Array.new(2**d)
done[0] = true

# s is the string that will be returned
s = ""

# The outer loop counts down the last @heap index for each row. last
# takes the index of each leaf node, from right to left.
(2**d - 1).downto(2**(d - 1)) do |last|
# a accumulates a list of @heap indexes for a row
a = [last]
a << (a.last >> 1) until done[a.last >> 1]
a.each {|x| done[x] = true }

# The inner loop iterates through the columns, from the root to the
# leaves.
(d - 1).downto(0) do |col|
# Append a fixed-width string: a node, a line or spaces
s << "%#{w[d - col - 1] + 1}s" %
if a.size > col # a node
@heap[a[col]].to_s + "-"
elsif last >> col - 1 & 1 == 1 # a line
"| "
elsif (last + 1) >> col - 1 & 1 == 1 # an "L" angle
"`-"
end
end

# Replace the trailing "-" after all the leaf nodes with a newline.
s[-1] = "\n"
end
s
end

def empty?( )
size == 0
end

def depth( )
if empty?
0
else
(Math.log(@heap.size - 1) / Math.log(2)).to_i + 1
end
end

 

[Dominik Bathon]

In fact, here's a basic pure Ruby implementation (not exhaustively
tested) using the system I just described:

I found two problems ;-)

class Heap ...
def extract( )
extracted =3D @heap[1]
@heap[1] =3D @heap.pop unless @heap.size.zero?
sift_down
extracted
end

This doesn't really extract the last element...

def sift_down( ) ...
c +=3D 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]

You probably wanted to say:
c +=3D 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap[c]] < 0


So, here is my solution. It draws the subtrees recursively and merges the=
=20
results.

Here are some examples:

$ ruby heap.rb
12
|
+--+-----+
| |
20 15
| |
+--+--+ +-++
| | | |
29 23 17 22
| | |
+-++ +-++ +
| | | | |
35 40 26 51 19

12
|
+---+-----+
| |
20 13
| |
+--+--+ ++--+
| | | |
29 23 15 22
| | |
+-++ +-++ +-++
| | | | | |
35 40 26 51 19 17

13
|
+--+-----+
| |
20 15
| |
+--+--+ +-++
| | | |
29 23 17 22
| | |
+-++ +-++ +
| | | | |
35 40 26 51 19

$ ruby -r heap.rb -e 'puts Heap.new(*((1..45).to_a))'
1
|
+-----------+----------------------+
| |
2 3
| |
+---------+-----------+ +-----+-----+
| | | |
4 5 6 7
| | | |
+-----+-----+ +---+-----+ +--+--+ +--+--+
| | | | | | | |
8 9 10 11 12 13 14 15
| | | | | | | |
+--+--+ +--+--+ +--+--+ ++--+ +-++ +-++ +-++ +-++
| | | | | | | | | | | | | | | |
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| | | | | | |
+-++ +-++ +-++ +-++ +-++ +-++ +-++
| | | | | | | | | | | | | |
32 33 34 35 36 37 38 39 40 41 42 43 44 45

$ ruby -r heap.rb -e 'puts Heap.new(*(%w(aaaaaaa bbbb ccccccccccccc ddddd=
d =20
ee fffff gg)))'
aaaaaaa
|
+------+----+
| |
bbbb ccccccccccccc
| |
+-+--+ +-+-+
| | | |
dddddd ee fffff gg



And here is the code:

class Heap
def initialize(*elements, &comp)
@comp =3D comp || lambda { |p, c| p <=3D> c }

clear
insert(*elements)
end

def clear
@heap =3D [nil]
end

def extract
case size <=3D> 1
when -1
nil
when 0
@heap.pop
else
extracted =3D @heap[1]
@heap[1] =3D @heap.pop
sift_down
extracted
end
end

def insert(*elements)
elements.each do |element|
@heap << element
sift_up
end
end

def size
@heap.size - 1
end

def empty?
@heap.size =3D=3D 1
end

def inspect
@heap[1..-1].inspect
end

def to_s
if empty?
"[empty heap]"
else
res, =3D to_s_rec(1)
res.shift
res.join "\n"
end
end

private

def sift_down
i =3D 1
loop do
c =3D 2 * i
break if c >=3D @heap.size

c +=3D 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap=
[c]] =20
< 0
break if @comp[@heap, @heap[c]] <=3D 0

@heap[c], @heap =3D @heap, @heap[c]
i =3D c
end
end

def sift_up
i =3D @heap.size - 1
while i > 1
p =3D i / 2
break if @comp[@heap[p], @heap] <=3D 0

@heap[p], @heap =3D @heap, @heap[p]
i =3D p
end
end

# rows1 and rows2 are arrays of strings (ascii-art), this method wil=
l =20
merge
# those into one array of strings.
# The strings from rows1 / rows2 will start at p1 / p2 in the result=

 

[Jim Freeze]

SAMPLE OUTPUT:
13-15-22-
| | `-
| `-17-
| `-19
`-20-23-51
| `-26
`-29-40
`-35

I like this layout. If the algorith could be made to
use '+' instead of '`-', it would work perfectly for
describing a directory structure in a way that you commonly
see.

 

[James Edward Gray II]

I found two problems ;-)

Good thing someone is watching over me!

class Heap
...

def extract( )
extracted = @heap[1]
@heap[1] = @heap.pop unless @heap.size.zero?
sift_down
extracted
end

This doesn't really extract the last element...

Can you please show a failing example? I tried to find one and
couldn't.

def sift_down( )
...

c += 1 if c + 1 < @heap.size and @heap[c + 1] < @heap[c]

You probably wanted to say:
c += 1 if c + 1 < @heap.size and @comp[@heap[c + 1],
@heap[c]] < 0

Right you are. Thanks!

James Edward Gray II

 

[James Edward Gray II]

def extract( )
extracted = @heap[1]
@heap[1] = @heap.pop unless @heap.size.zero?
sift_down
extracted
end



This doesn't really extract the last element...

Can you please show a failing example? I tried to find one and
couldn't.

Maybe I havn't been clear enough, I meant the heap can't get empty,
you can't remove the last remaining element:

Got it. Thanks for the lesson Dominik!

James Edward Gray II

 

[Dave Burt]

* Dave Burt <[email protected]> [2005-07-26 23:01:00 +0900]:

I like this layout. If the algorith could be made to
Thanks!

use '+' instead of '`-', it would work perfectly for

That's a one-byte change: find the line that contains "`-" and replace it
with "+-".

Unfortunately, the algorithm itself is very heap-specific, but there's no
reason you can't generate the same layout from a different data structure.

describing a directory structure in a way that you commonly
see.

I don't think I've ever seen quite this layout before - with layers lined up
horizontally; I think Florian's is more common:
1
+---3
`---2

Cheers,
Dave

 

[Dave Burt]

...
def to_s
if empty?
"[empty heap]"
else
res, = to_s_rec(1)
res.shift
res.join "\n"
end
end
...
# rows1 and rows2 are arrays of strings (ascii-art), this method will
merge
# those into one array of strings.
# The strings from rows1 / rows2 will start at p1 / p2 in the result=

The workhorse method is missing! Can you please post to_s_rec?

Cheers,
Dave

 

[Dominik Bathon]

...
def to_s
if empty?
"[empty heap]"
else
res, =3D to_s_rec(1)
res.shift
res.join "\n"
end
end
...
# rows1 and rows2 are arrays of strings (ascii-art), this method = =20
will
merge
# those into one array of strings.
# The strings from rows1 / rows2 will start at p1 / p2 in the =20
result=3D

The workhorse method is missing! Can you please post to_s_rec?

Sorry, something seems to have truncated my mail on its way to the =20
newsgroup, but it is ok on the mailing list:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/149571

Here is the code again:

class Heap
def initialize(*elements, &comp)
@comp =3D comp || lambda { |p, c| p <=3D> c }

clear
insert(*elements)
end

def clear
@heap =3D [nil]
end

def extract
case size <=3D> 1
when -1
nil
when 0
@heap.pop
else
extracted =3D @heap[1]
@heap[1] =3D @heap.pop
sift_down
extracted
end
end

def insert(*elements)
elements.each do |element|
@heap << element
sift_up
end
end

def size
@heap.size - 1
end

def empty?
@heap.size =3D=3D 1
end

def inspect
@heap[1..-1].inspect
end

def to_s
if empty?
"[empty heap]"
else
res, =3D to_s_rec(1)
res.shift
res.join "\n"
end
end

private

def sift_down
i =3D 1
loop do
c =3D 2 * i
break if c >=3D @heap.size

c +=3D 1 if c + 1 < @heap.size and @comp[@heap[c + 1], @heap=
[c]] =20
< 0
break if @comp[@heap, @heap[c]] <=3D 0

@heap[c], @heap =3D @heap, @heap[c]
i =3D c
end
end

def sift_up
i =3D @heap.size - 1
while i > 1
p =3D i / 2
break if @comp[@heap[p], @heap] <=3D 0

@heap[p], @heap =3D @heap, @heap[p]
i =3D p
end
end

# rows1 and rows2 are arrays of strings (ascii-art), this method wil=
l =20
merge
# those into one array of strings.
# The strings from rows1 / rows2 will start at p1 / p2 in the result=

 

[David Brady]

Sorry if this is too late to be a legitimate entry.

James, what is the official way to submit an entry? If posting to the
list is good enough, here you go.

My solution doesn't use recursion. It deterministically transforms
(heapindex, heapsize) coordinates into (x, y) coordinates. My only
gripe with this solution is that pre-initializing a 2D text buffer
beforehand looks kinda kludgy.

My full solution is at http://www.shinybit.com/ruby_quiz_40.rb , but
it's just the original code from James (with the bugfix addendum) with
three methods added. They are poorly named and could use some cleaning
up. Here is my output, followed by the three methods I added to the
Heap class.

I've used some kludgy mechanisms in my code. I would *love* to hear any
input on how to clean them up. If you spot an obviously missing Ruby
idiom, please let me know.

The output:

dbrady@gromit:~$ ruby ruby_quiz_40.rb
,- 35
,- 29
| `- 40
,- 20
| | ,- 26
| `- 23
| `- 51
12
| ,- 19
| ,- 17
| |
`- 15
|
`- 22
,- 35
,- 29
| `- 40
,- 20
| | ,- 26
| `- 23
| `- 51
12
| ,- 19
| ,- 15
| | `- 17
`- 13
|
`- 22
,- 35
,- 29
| `- 40
,- 20
| | ,- 26
| `- 23
| `- 51
13
| ,- 19
| ,- 17
| |
`- 15
|
`- 22

And here are the three methods I added to the Heap class:

# One bit of kludginess: The /= operator breaks indenting in emacs
# ruby-mode. This is why I use the x = x / 2 form instead.

# ----------------------------------------------------------------------
# get_depth
#
# returns the depth in the tree of a given 0-based index.
# num - 1-based index of element.
# returns - depth of the tree at this index. The root node has a
# depth of zero.
def get_depth(num)
(Math.log(num)/Math.log(2)).to_i
end

# ----------------------------------------------------------------------
# get_line
#
# for index num in a heap of depth rows, returns the line.
# num is 1-based index of element.
# returns 0-based line number, with 0 at the top (left-hand
# side). Sample tree, get_line(1) returns 7, etc.
def get_line(num)
depth = get_depth(@heap.length)
# Okay, scary algorithm. Odd-numbered indexes are down from their
# parents while even-numbered indexes are up from their parents.
# We want to move from this node, up the tree to the root,
# considering each node for even/oddness. At the leafmost level,
# the leaves move up or down 1 line. Each level you move up, the
# offset doubles, until node 1 is moved down 1/2 the size of the
# tree (because it's odd).
line = 0
while num > 0
offset = 2**(depth - get_depth(num))
if num % 2 == 1
line += offset
else
line -= offset
end
num = num / 2 # Integer divide to get parent index.
end
line-1
end

# ----------------------------------------------------------------------
# to_s
#
# converts the heap to an ascii art tree representation.
def to_s
output = []

# Initialize output as an array of strings. We're going to "draw"
into the
# output like it's a 2D text buffer, so we need to make sure the
output is
# initialized with indent strings. (By an odd coincidence, all of
ascii art
# is confined to the area to the left of each given string.
However, some
# elements are empty, so we need to make sure that all lines have
their left
# indent already buffered out.
#
# This hairy bit of math calculates the next largest power of 2 up
from @heap.length.
max_lines = 2**((Math.log(@heap.length)/Math.log(2)).to_i + 1)
max_indent = get_depth(max_lines)

(@heap.length).times { output.push(' ' * INDENT_AMOUNT * max_indent) }

@heap.each_with_index do |item, index|
next if index.zero? # @heap[0] appears to be a dummy node
output[get_line(index)] = ' ' * INDENT_AMOUNT * get_depth(index) +
item.to_s
end

# Okay, the tree nodes are now "drawn" into the output buffer.
# Now draw connecting lines. At each child node, draw ,- or `-
# into their left margin. Then bring down a column of |'s to
# the parent node.
#
# Note that since we're drilling "down" from the parent nodes, we
# only need to traverse the first half of the items in the tree.
# The careful observer might note that in the sample tree, node 7
# ("22") never gets traversed. This is okay; it gets skipped
# because we know it can't possibly have any children.
(@heap.length / 2).times do |i|
j = i+1 # The math is easier when done 1-based.

# this whole mess could be refactored; these 2 blocks
# differ only in start line, ,- vs `- text, and loop
# direction.

# connect node i to node i*2 (up from parent)
indent = get_depth(j*2) * INDENT_AMOUNT
stop_line = get_line(j)

next if j*2 >= @heap.length

start_line = get_line(j*2)
output[start_line][indent-3..indent-2] = ',-'
start_line += 1
while start_line < stop_line
output[start_line][indent-3] = '|'
start_line += 1
end

# connect node i to node i*2+1 (down from parent)
start_line = get_line(j*2+1)
indent = get_depth(j*2+1) * INDENT_AMOUNT
next if j*2+1 >= @heap.length

output[start_line][indent-3..indent-2] = '`-'
start_line -= 1
while start_line > stop_line
output[start_line][indent-3] = '|'
start_line -= 1
end
end

output.join("\n")
end

Cheers!

-dB

 

[Dave Burt]

Hi David,

Sorry if this is too late to be a legitimate entry.

It is probably legitimate enough for James to add to the official solutions
collection.

James, what is the official way to submit an entry? If posting to the
list is good enough, here you go.

Posting to the list (or newsgroup) is the only way to submit an entry.

My solution doesn't use recursion. It deterministically transforms
(heapindex, heapsize) coordinates into (x, y) coordinates.

Very nice. Thanks for sharing. It seems kind of like mine, but
cleaner-looking.

... If you spot an obviously missing Ruby idiom, please let me know.

The method name "get_depth" looks like a Java programmer wrote it. Just
"depth" works to get the width property of the Heap.

Cheers,
Dave

 

[James Edward Gray II]

Hi David,



It is probably legitimate enough for James to add to the official
solutions
collection.

Definitely! It should be up now. (Sorry for the delay. I was out
of town.)

There's really no such thing as a "legitimate entry", to my mind.

I look at what I have to look at when it is time to write a summary.
That just means you have to beat that time (usually Wednesday after a
quiz is released) if you want me to take an in-depth look at the code
and possibly decide to talk about it in the summary. Of course,
there's nothing magically significant about any of that and I do try
to link to ALL solutions I see, no matter when they come in.

My favorite aspect of Ruby Quiz is the priceless collection of
example code we have built for the community just by playing our
little games. My favorite way to learn a new library is to find a
Ruby Quiz solution that used it. You can contribute to something
like this at any time.

Posting to the list (or newsgroup) is the only way to submit an entry.

Technically, you can also mail them directly to me. There is a link
in the Ruby Quiz FAQ for this. Of course, I just forward them to
this list. It's really just a service for people not on this list
that want their code seen by all.

This is definitely the "official" Ruby Quiz channel.

James Edward Gray II