Merge pull request #5625 from choroba/ech151

Solve 151: Binary Tree Depth & Rob the House by E. Choroba

2 files changed, 98 insertions, 0 deletions

diff --git a/challenge-151/e-choroba/perl/ch-1.pl b/challenge-151/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..a0cb9f3f03
--- /dev/null
+++ b/challenge-151/e-choroba/perl/ch-1.pl
@@ -0,0 +1,63 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+sub binary_tree_depth {
+    my ($string) = @_;
+
+    my @levels = split /\|/, $string;
+    shift @levels;
+
+    my @parents = (my $id = 0);
+    my %tree = ($id => {rank => my $rank = 0});
+
+    for my $level (@levels) {
+        ++$rank;
+        my @nodes = split ' ', $level;
+        my @next_parents;
+
+        while (@nodes) {
+            my %children;
+            @children{qw{ left right }} = splice @nodes, 0, 2;
+            for my $side (qw( left right )) {
+                if (($children{$side} // '*') ne '*') {
+                    $tree{ ++$id } = {rank   => $rank,
+                                      parent => $parents[0]};
+                    push @next_parents,
+                        $tree{ $parents[0] }{$side} = $id;
+                }
+            }
+            my $parent = shift @parents;
+
+            return $rank if ! exists $tree{$parent}{left}
+                         && ! exists $tree{$parent}{right};
+        }
+        return $rank if @parents;
+
+        @parents = @next_parents;
+    }
+    return $rank + 1
+}
+
+use Test::More tests => 15;
+
+is binary_tree_depth('1 | 2 3 | 4 5'), 2, 'Example 1';
+is binary_tree_depth('1 | 2 3 | 4 *  * 5 | * 6'), 3, 'Example 2';
+
+is binary_tree_depth('1'), 1, 'Trivial 1-node tree';
+is binary_tree_depth('1 | 2'), 2, 'Simple 2-node tree';
+
+is binary_tree_depth('1 | 2 3'), 2, 'Simple tree rank 2';
+is binary_tree_depth('1 | 2 | 3'), 3, 'Linear depth 3';
+is binary_tree_depth('1 | 2 | * 3'), 3, 'Zigzag';
+is binary_tree_depth('1 | * 2 | 3'), 3, 'Zagzig';
+is binary_tree_depth('1 | * 2 | * 3'), 3, 'Right linear depth 3';
+
+is binary_tree_depth('1 | 2 3 | * * * *'), 2, 'All stars';
+
+is binary_tree_depth('1 | 2 3 | * * 4 5'), 2, 'Missing left children';
+is binary_tree_depth('1 | 2 3 | * * 4'), 2, 'Missing left children';
+is binary_tree_depth('1 | 2 3 | * * * 4'), 2, 'Missing left children';
+is binary_tree_depth('1 | 2 3 | 4 | 5 | 6'), 2, 'Short branch';
+
+is binary_tree_depth('1 | 1 1 | 1 1 1 1 | 1 * 1 * 1 * 1'), 4, 'Repeated values';
diff --git a/challenge-151/e-choroba/perl/ch-2.pl b/challenge-151/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..eea64eb40a
--- /dev/null
+++ b/challenge-151/e-choroba/perl/ch-2.pl
@@ -0,0 +1,35 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+sub rob_the_house {
+    my (@valuables) = @_;
+    my @sums;
+    for my $i (reverse 0 .. $#valuables) {
+        $sums[$i] = $valuables[$i];
+        if ($i + 2 <= $#valuables) {
+            my $add = $sums[$i + 2];
+            $add = $sums[$i + 3] if $i + 3 <= $#valuables
+                                 && $sums[$i + 3] > $sums[$i + 2];
+            $sums[$i] += $add;
+        }
+    }
+    return $sums[0]
+}
+
+use Test::More tests => 3;
+
+is rob_the_house(2, 4, 5), 7, 'Example 1';
+is rob_the_house(4, 2, 3, 6, 5, 3), 13, 'Example 2';
+is rob_the_house((1) x 1000), 500, 'Long';
+
+=head1 Explanation
+
+ D C B X A
+
+Let's proceed in reverse. Before robbing A, we couldn't have robbed X, but we
+could have robbed B, C, or D. But going directly from D to A makes no sense,
+as we could have robbed B on the way. Therefore, we just need to compare C and
+B.
+
+=cut