Solutions and Discussion for Perl Quiz of the Week #5 (Expert Edition)
Mark Jason Dominus <[email protected]> Mon, 18 Nov 2002 21:47:16 -0500
| Newsgroups | gmane.comp.lang.perl.qotw.quiz-of-the-week |
|---|---|
| Organization | Plover Systems |
| Message-ID | <[email protected]> |
Sample solutions and discussion
Perl Expert Quiz of The Week #5 (20021113)
You will write a function that lays out tree diagrams.
layout_tree's arguments will be (1) an object that represents a tree,
and (2) an optional hash containing some configuration parameters.
The tree object is opaque to your function, but is guaranteed to
support at least the following methods:
$tree->children
Returns a list of tree objects that represent the subtrees
of this tree
$tree->text
Returns a reference to an array of strings that show how the
root node of this tree should be displayed.
An example $tree object might be manufactured by the following class:
package ExampleTree;
# Create a new tree object
# arguments: ->(label of root node,
# [arguments for child 1],
# [arguments for child 2],
# ...);
sub new {
my ($pack, $label, @subnodes) = @_;
my @subobjects = map $pack->new(@$_), @subnodes;
bless [$label, @subobjects] => $pack;
}
# If the label of the tree node is 'foo',
# we format it like this:
# +-----+
# | foo |
# +-----+
sub text {
my $self = shift;
my $label = $self->[0];
my $ln = length $label;
$label .= " " x (5 - $ln) if $ln < 5; # pad with spaces to width 5
$ln = length $label;
my $top = "+" . "-" x $ln . "+";
return [$top, "|$label|", $top];
}
sub children {
my $self = shift;
my @children = @$self;
shift @children; # throw away the label
@children;
}
And then one might create such an object by calling
my $t = ExampleTree->new("5",
["4 1",
["3 1 1",
["2 1 1 1",
["1 1 1 1 1"],
],
],
["2 2 1"]
],
["3 2"]);
layout_tree($t) would then manufacture an array of strings, which,
when printed, would look something like this:
+-----+
|5 |
+-----+
,-' `--------.
+-----+ +-----+
|4 1 | |3 2 |
+-----+ +-----+
,-' `----.
+-----+ +-----+
|3 1 1| |2 2 1|
+-----+ +-----+
|
+-------+
|2 1 1 1|
+-------+
|
+---------+
|1 1 1 1 1|
+---------+
Details of exactly how this is laid out and what it looks like are up
to you; you might produce output like this instead:
+-----+ +-----+ +-----+ +-------+ +---------+
|5 |-+-|4 1 |-+-|3 1 1|---|2 1 1 1|---|1 1 1 1 1|
+-----+ | +-----+ | +-----+ +-------+ +---------+
| |
| | +-----+
| +-|2 2 1|
| +-----+
| +-----+
+-|3 2 |
+-----+
However, the tree node displays returned by ->text must appear in the
output exactly as they were returned, and it must be possible to
understand the tree structure from looking at the output.
----------------------------------------------------------------
I really like programs that draw. Drawing is fun.
I got really tired of hand-drawing all the ASCII-art for the diagrams
for my book, and there were a lot of tree diagrams. So I wrote a
tree-drawing package, and hence my interest in the problem. In the
original question, the first of the two example outputs was generated
by my package. I drew the second one by hand.
I had hoped that this problem would bring up a lot of discussion about
the best way to draw trees, comparison of different methods for laying
out the nodes, and so on. It didn't. But there was some interesting
variety in the output produced by the programs that appeared on
qotw-perl-discuss. I thought at first that the programs were almost
all the same, but they turned out to be rather different on the
inside.
Here are some sample outputs:
barbie.pl
+-----+ +-----+ +-----+
|top |-+-|a |-+-|a1 |
+-----+ | +-----+ | +-----+
| | +-----+
| +-|a2 |
| +-----+
| +-----+
+-|b |
| +-----+
| +-----+
+-|c |
+-----+
--------
dax.pl
+-----+
,-|a1 |
+-----+ | +-----+
,-|a |-+
| +-----+ | +-----+
| `-|a2 |
| +-----+
|
+-----+ | +-----+
|top |-+-|b |
+-----+ | +-----+
|
| +-----+
`-|c |
+-----+
Notice how a1 and a2 are centered around the right edge of a,
and how a, b, and c are centered around 'top', instead of
hanging down below it.
--------
mjd.pl
+-----+
|top |
+-----+
,---' `-.-----.
--' `- `----
+-----+ +-----+ +-----+
|a | |b | |c |
+-----+ +-----+ +-----+
,-' `--
+-----+ +-----+
|a1 | |a2 |
+-----+ +-----+
--------
isaacson.pl
+-----+
|top |
+-----+
.---------^-.-------.
+-----+ +-----+ +-----+
|a | |b | |c |
+-----+ +-----+ +-----+
.---^---.
+-----+ +-----+
|a1 | |a2 |
+-----+ +-----+
--------
sainio.pl
+-----+ +-----+ +-----+
|top |-+-|a |-+-|a1 |
+-----+ | +-----+ | +-----+
| |
| | +-----+
| +-|a2 |
| +-----+
| +-----+
+-|b |
| +-----+
|
| +-----+
+-|c |
+-----+
--------
schmidt.pl
+-----+ +-----+ +-----+
|top |-+-|a |-+-|a1 |
+-----+ | +-----+ | +-----+
| |
| +-----+ | +-----+
+-|b | +-|a2 |
| +-----+ +-----+
|
| +-----+
+-|c |
+-----+
Notice how the 'b' node has has cuddled in behind 'a2'.
--------
Unfortunately, all of the posted examples failed on one example or
another, for various reasons. Ron Isaacson's code produced
good-looking output for eight of the nine examples I tried, but
aborted with a fatal error on one of them. I would have tried to fix
it, but unfortunately he posted it only about half an hour ago.
Still, it's nearly the shortest of the solutions, and it might not be
hard to fix.
(Lines of code)
sainio.pl 42
isaacson.pl 44
barbie.pl 47
schmidt.pl 95
dax.pl 168
mjd.pl 219
It was difficult to decide which sample code to show. The code I had
beforehand is much too big and complicated to be a good example. Also
I had designed the interface a little differently, and had to attach a
rather peculiar glue module to the original code to get it to conform
to the interface required by the question.
I finally compromised and hacked on Garth Sainio's code, which was both
short and straightforward. The result generated reasonably
good-looking outputs even for the weird test cases, and was even
shorter than the original. (35 lines! Woo hoo!)
sub layout_tree {
my($tree) = @_;
# Get the representation of the root node
my $node_lines = $tree->text;
# Get the children of the node
my @children = $tree->children;
my $child_count = scalar(@children);
# If no children, return the existing lines
return @$node_lines unless($child_count);
# Get the layout for each sub tree.
my @child_lines;
foreach my $child (@children) {
my @lines = layout_tree($child);
# push @lines, "";
push(@child_lines, \@lines);
}
# Combine the children with the current node
my $node_height = scalar(@$node_lines);
# find the index of the line nearest the middle of the array
my $middle = int(($node_height-1)/2);
# Determine the width of the current node and create a string of
# spaces to pad lines in the subtrees with.
my $node_width = length($node_lines->[0]);
my $node_pad = " " x $node_width;
# Printing children to the right of the parent.
# So prepend the lines to the child lines. Need to prepend spaces
# to the other lines.
# If there is only one child join with ---
# multiple children are joined with -+- for the first and +- for subsequent
my $yoff = $middle;
for my $i (0..$child_count-1) {
my $c_lines = $child_lines[$i];
my $c_height = scalar(@$c_lines);
# now need to combine node_lines and c_lines
for my $j (0..$c_height-1) {
my $ypos = $yoff + $j;
my $separator = " ";
if ($j == 0) {
if ($child_count == 1) {
$separator = " --";
} else {
$separator = " +-";
}
} elsif ($i < $child_count - 1) {
$separator = " | ";
}
# Attach on left side
substr($separator, 0, 1) = "-" if $ypos == $middle;
# Prepend the lines of the current node to the children lines
if($ypos < $node_height) {
$node_lines->[$ypos] = $node_lines->[$ypos] . $separator . $c_lines->[$j];
} else {
$node_lines->[$ypos] = $node_pad . $separator . $c_lines->[$j];
}
}
$yoff += $c_height;
}
return @$node_lines;
}
As with all the submissions, this program calls itself recursively to
lay out the subtrees of the current root node, and then tries to
assemble the subtree layouts and the root node text into a larger
diagram.
The program loops over the children (the 'for my $i' loop) and then
over each line in the child (the 'for my $j' loop) adding each line in
turn to $node_lines, which is its ultimate return value. As it adds
the children, it inserts 'separator' text in between the root node (on
the left) and the child node (on the right). Typically, this is just
three spaces. If the current line happens to be exactly halfway down
the root node, the separator text is adjusted so that it attaches to
the root node; if it happens to be exactly at the top of a child node,
the separator is adjusted to that it attaches to the child node.
Inside the 'for my $j' loop, $j is the index of the current line
relative to the top of the current child node, and $ypos is the index
of the current line relative to the top of the parent node.
Here's a typical output:
top-+-a-+-a1
| +-a2
+-b
+-c
If you want more space, you can uncomment the
push @lines, "";
line; the resulting diagram will have extra space below each node:
top-+-a-+-a1
| |
| +-a2
|
|
+-b
|
+-c
----------------------------------------------------------------
1. If any of the child nodes are more than one line high, the output
becomes skewed, although still accurate:
+-----+
|top |-+-+-----+
+-----+ | |a |-+-+-----+
| +-----+ | |a1 |
| | +-----+
| +-+-----+
| |a2 |
| +-----+
+-+-----+
| |b |
| +-----+
+-+-----+
|c |
+-----+
My version of this program attaches each horizontal connector to
the middle of the parent node, but to the top of the child nodes.
Mr. Sainio's original code attached it to the middle of both nodes.
Why did I change it? Because the original program only worked when
all the nodes were the same height; it assumed that a child was the
same height as its parent, and didn't otherwise keep track of child
node heights. When the assumption was correct, the output looked
fine. When it wasn't, all sorts of odd effects appeared. For
example:
Example 1 Example 2
+----+ +-+ +-----------------+ +-----+ +-+
|****| |*| |*****************| |*****| |*|
|****|-+-+-+ |*****************| |*****| +-+
|****| |*****************| |*****|
|****| |*****************| |*****|
+----+ |*****************| |*****|
| |*****************| +-----+
| +-+ |*****************|
| |*| |*****************|
+-+-+ |*****************|
| |*****************|
| +-+ |*****************|
| |*| |*****************|
+-+-+ |*****************|
| |*****************|
| +-+ |*****************|
| |*| |*****************|
+-+-+ |*****************|
| +-----------------+
| +-+ |
| |*| | +-+
+-+-+ | |*|
| +-+
In example 1, the parent node has height 6, so the horizontal
connector is attached to it is on the third row from the top;
Sainio's program has attached the connector to the child nodes at
_their_ third rows also. In example 2, the root node has height
18, so the horizontal connector is attached to it at the 9th row
from the top; the program wants to attach the connector to the 9th
row of the child nodes also, but they don't have 9th rows. Because
of a fluke in the design, the connector disappears entirely, except
for a vestigial bit at the very bottom.
*. There are at least two ways to fix this. One is to give up on
attaching the horizontal connector to the middle of the child nodes,
and attach it at the top instead. This is what I did in the
example program.
The other way to fix this is to have the layout_tree() function
return, a second value, in addition to the lines to be printed, to
indicate how far down the picture the horizontal connector should
be attached to the root node. I did this, just to see how it would
come out. I had to rework some of the insides of the function,
but the end result was not too much bigger than the original. For
the two examples above, this version of the program produces:
+-----+ +-+ +-----------------+ +-----+ +-+
|*****| +-|*| |*****************| |*****| +-|*|
|*****| | +-+ |*****************| |*****| | +-+
|*****|-+ +-+ |*****************| +-|*****|-+
|*****| +-|*| |*****************| | |*****|
|*****| | +-+ |*****************| | |*****|
+-----+ | +-+ |*****************| | +-----+
+-|*| |*****************| | +-+
| +-+ |*****************| +-|*|
| +-+ |*****************|-+ +-+
+-|*| |*****************|
| +-+ |*****************|
| +-+ |*****************|
+-|*| |*****************|
+-+ |*****************|
|*****************|
|*****************|
|*****************|
+-----------------+
Similarly, the output produced by the original program is on the
left; the output from the revised version is on the right:
*-+-+-+ +-------+ *-+ +-+ +-------+
| |*|-+-|*******| +-|*|-+ |*******|
| +-+ | |*******| | +-+ | |*******|
| | |*******| | | |*******|
| | |*******| | +-|*******|
| | |*******| | | |*******|
| | |*******| | | |*******|
| | |*******| | | |*******|
| | +-------+ | | +-------+
| | +-------+ | | +-------+
| +-|*******| | | |*******|
| |*******| | | |*******|
| |*******| | | |*******|
| |*******| | +-|*******|
| |*******| | |*******|
| |*******| | |*******|
| |*******| | |*******|
| +-------+ | +-------+
+-+-+ +-------+ | +-+ +-------+
|*|-+-|*******| +-|*|-+ |*******|
+-+ | |*******| +-+ | |*******|
| |*******| | |*******|
| |*******| +-|*******|
| |*******| | |*******|
| |*******| | |*******|
| |*******| | |*******|
| +-------+ | +-------+
| +-------+ | +-------+
+-|*******| | |*******|
|*******| | |*******|
|*******| | |*******|
|*******| +-|*******|
|*******| |*******|
|*******| |*******|
|*******| |*******|
+-------+ +-------+
Almost everyone got into trouble over this issue.
http://perl.plover.com/qotw/misc/e005/outputs/out9 is a gallery of
the results for example 2 above, a rather curious collection of
trees with teratomas, fractures, and spina bifida.
2. Code and test harnesses are at
http://perl.plover.com/qotw/misc/e005/
Garth Sainio's original program is sainio.pl. The modified version
that I presented above is sainio-mjd.pl. The version that always
attaches the connectors in the centers of the nodes is
sainio-mjd2.pl.
Sample outputs are at
http://perl.plover.com/qotw/misc/e005/outputs/
3. dax.pl assumes that the return from ->text will always be exactly
three lines high:
...
elsif(@children == 1) {
#Easy.
return horiz_line_child(
"$space ",
["$text[0] ",
"$text[1]---",
"$text[2] "],
"$space ",
$children[0]
);
}
...
If the text was a different, size, the output would be garbled:
barbie.pl DAX.PL isaacson.pl sainio.pl
top-+-a-+-a1 ,- ,-a1a top top-+-a-+-a1
| +-a2 | -+ .--^.-. | |
+-b | `-a2 a b c | +-a2
+-c | .-^. +-b
-+-top | b a1 a2 |
| +-c
|
`-c
I think the lesson to learn from this is that if you have a magic
constant like '2' in your program, you should pause and ask
yourself 'why 2?'
4. Dan Schmidt's cuddling algorithm was sometimes a little too
affectionate. For this tree:
top-+-a-+-b-+-c
| | |
| | +-d
| |
| +-e---f
|
+-g---h
It produced this output:
top-+-a-+-b-+-c
| | |
+-g-|-h +-d
|
+-e---f
See what happened? The g-h branch got moved up into the empty
spaces below the a-b branch. It fits there, but as a result the
lines overlap. One can almost imagine this as a feature, since the
broken line from "g-|-h" correctly suggests that it passes
underneath the a-b-e branch. Unfortunately, it's *not* a feature,
because for this tree:
11-+-12-+-13-+-14
| | |
| | +-24
| | |
| | +-34
| |
| +-43---44
|
+-22-+-23
|
+-33
It produces this output:
11-+-12-+-13-+-14
| | |
+-22-+-23 +-24
| |
+-33 +-34
|
+-43---44
Which isn't even a tree. (Is 23 a child of 12 or 22?)
I wanted to fix this, but I couldn't find an easy way to do it in
the time available.
In spite of this flaw, the algorithm is straightforward and
interesting and the code was very clear. I recommend that you have
a look.
5. Dan Schmidt used this construction to make an empty canvas with
$total_height lines of $total_width spaces each:
my @field = map {" " x ($total_width)} (0..($total_height-1));
Here's a shortcut:
my @field = (" " x $total_width) x $total_height;
Thanks to everyone who participated in the quiz, including both those
who mailed the -discuss list and those who did not. I will send along
sample solutions for regular quiz #5 tomorrow sometime.
The perl-qotw list now has over 1,000 subscribers! Thank you all for
your support and interest.