forked from manwar/perlweeklychallenge-club
-
Notifications
You must be signed in to change notification settings - Fork 1
/
ch-2.pl
79 lines (63 loc) · 2.3 KB
/
ch-2.pl
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/opt/perl/bin/perl
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
#
# See ../README.md
#
#
# Run as: perl ch-2.pl < input-file
#
package Tree {
use Hash::Util::FieldHash qw [fieldhash];
use List::Util qw [max];
fieldhash my %left;
fieldhash my %right;
sub new ($class) {bless do {\my $var} => $class}
sub init ($self, $input) {
#
# Initialize a tree given the input following the
# specification of how we're given a tree.
#
...; # <-- This is the yada, yada, yada operator, typically
# a placeholder for code which still needs to be written.
# Perfect! Once we have a specification of how the
# the input is structured (other than a single example
# of which anyone can instantly see it doesn't scale
# beyond trivial sizes), we can replace this piece of code.
#
# This does mean though, that rest of the code is largely
# untested. "It compiles" is the best we can do.
#
$self;
}
#
# Get the left and right child of a tree. Leaves obviously
# don't have children.
#
sub left ($self) {!$self -> isleaf && $left {$self}}
sub right ($self) {!$self -> isleaf && $right {$self}}
sub isleaf ($self) {!$left {$self} || !$right {$self}}
sub diameter ($self) {
($self -> _diameter ($self)) [1]
}
sub _diameter ($self) {
#
# Given a tree, return a tuple ($depth, $diameter), where
# first element is the depth of a tree (longest path to a leaf),
# and second the diameter (longest path in the tree).
#
# Depth of a tree is 1 + max (depth left child, depth right child)
# Diameter of a tree is max (diameter left child,
# diameter right child, depth left child + depth right child).
#
return (0, 0) if $self -> isleaf; # Leaves have no depth nor diameter.
my ($ldp, $ldm) = $self -> left -> _diameter;
my ($rdp, $rdm) = $self -> right -> _diameter;
(max ($ldp, $rdp), max ($ldm, $rdm, $ldp + $rdp))
}
}
say Tree:: -> new -> init (do {local $/; <>}) -> diameter;