new file: challenge-151/mattneleigh/perl/ch-1.pl

	new file:   challenge-151/mattneleigh/perl/ch-2.pl

2 files changed, 279 insertions, 0 deletions

diff --git a/challenge-151/mattneleigh/perl/ch-1.pl b/challenge-151/mattneleigh/perl/ch-1.pl
new file mode 100755
index 0000000000..0d9fc30f58
--- /dev/null
+++ b/challenge-151/mattneleigh/perl/ch-1.pl
@@ -0,0 +1,177 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use English;
+
+################################################################################
+# Begin main execution
+################################################################################
+
+my @trees;
+my $tree;
+
+# Given cases:
+
+# Tree 0:
+#     1
+#    / \
+#   2   3
+#  / \
+# 4   5
+
+$trees[0] = make_tree_node(1);
+$trees[0]{l} = make_tree_node(2);
+$trees[0]{r} = make_tree_node(3);
+$trees[0]{l}{l} = make_tree_node(4);
+$trees[0]{l}{r} = make_tree_node(5);
+
+
+# Tree 1:
+#     1
+#    / \
+#   2   3
+#  /     \
+# 4       5
+#  \
+#   6
+
+$trees[1] = make_tree_node(1);
+$trees[1]{l} = make_tree_node(2);
+$trees[1]{r} = make_tree_node(3);
+$trees[1]{l}{l} = make_tree_node(4);
+$trees[1]{r}{r} = make_tree_node(5);
+$trees[1]{l}{l}{r} = make_tree_node(6);
+
+
+# Additional test cases:
+
+# Tree 2:
+#   1
+#  / \
+# 2   3
+#      \
+#       4
+
+$trees[2] = make_tree_node(1);
+$trees[2]{l} = make_tree_node(2);
+$trees[2]{r} = make_tree_node(3);
+$trees[2]{r}{r} = make_tree_node(4);
+
+
+print("\n");
+for $tree (0 .. $#trees){
+    printf(
+        "Minimum leaf depth for tree %d is: %d\n",
+        $tree,
+        minimum_leaf_depth($trees[$tree])
+    );
+}
+print("\n");
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Determine the minimum depth at which a leaf appears in a tree
+# Takes one argument:
+# * A ref to the tree to examine, which must consist of nodes of the type
+#   generated by make_tree_node()
+# Returns:
+# * The depth of the leaf closest to the root of the tree
+################################################################################
+sub minimum_leaf_depth{
+    my $tree = shift();
+
+    my $min_leaf_depth = 0;
+
+    _min_leaf_depth_recursor($tree, 1, \$min_leaf_depth);
+
+    return($min_leaf_depth);
+
+}
+
+
+
+################################################################################
+# Do the actual work of determining the minimum depth at which a leaf appears
+# in a tree
+# Takes three arguments:
+# * A ref to the tree to examine, which must consist of nodes of the type
+#   generated by make_tree_node()
+# * The depth of this node; this must be 1 when this function is first called
+# * A ref to a scalar which will be used to keep track of the minimum depth;
+#   this must be set to 0 when this function is first called, and it will
+#   contain the minimum depth when that call returns
+# Returns no meaningful value
+# NOTE: This function should only be called by minimum_leaf_depth(), which does
+# some initial setup
+################################################################################
+sub _min_leaf_depth_recursor{
+    my $node = shift();
+    my $curr_depth = int(shift());
+    my $min_leaf_depth = shift();
+
+    if($$min_leaf_depth && ($curr_depth >= $$min_leaf_depth)){
+        # We've seen a leaf before and we're as
+        # deep or deeper than that... no point in
+        # proceeding further
+        return();
+    }
+
+    if(!$node->{l} && !$node->{r}){
+        # This is a leaf
+        if($curr_depth < $min_leaf_depth){
+            # And it's the shallowest we've seen
+            $$min_leaf_depth = $curr_depth;
+        }
+        return();
+    }
+
+    # This wasn't a leaf- traverse down each
+    # defined branch
+    $node->{l} && _min_leaf_depth_recursor(
+        $node->{l}, $curr_depth + 1, $min_leaf_depth
+    );
+    $node->{r} && _min_leaf_depth_recursor(
+        $node->{r}, $curr_depth + 1, $min_leaf_depth
+    );
+
+    return();
+
+}
+
+
+
+################################################################################
+# Make a node for a binary tree
+# Takes one argument:
+# * A scalar that represents (or points to) the data (D) to store in this node
+# Returns:
+# * A binary tree node in the form of a hash ref with the data stored therein,
+#   and left/right ref fields set to undef, e.g.:
+#   {
+#       d => D,
+#       l => undef,
+#       r => undef
+#   }
+################################################################################
+sub make_tree_node{
+    my $n = shift();
+
+    return(
+        {
+            d => $n,
+            l => undef,
+            r => undef
+        }
+    );
+
+}
+
+
+
diff --git a/challenge-151/mattneleigh/perl/ch-2.pl b/challenge-151/mattneleigh/perl/ch-2.pl
new file mode 100755
index 0000000000..6a94d054bf
--- /dev/null
+++ b/challenge-151/mattneleigh/perl/ch-2.pl
@@ -0,0 +1,102 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use English;
+
+################################################################################
+# Begin main execution
+################################################################################
+
+# The houses on multiple streets
+my @streets = (
+    # Given cases
+    [ 2, 4, 5 ],
+    [ 4, 2, 3, 6, 5, 3 ],
+
+    # Additional test cases
+    [ 3, 9 ],
+    [ 4 ],
+    [ ],
+
+    # This one kind of shows the limitations
+    # of the starting condition...
+    [ 1, 50, 2, 3, 7, 4 ]
+);
+my $street;
+
+print("\n");
+
+foreach $street (@streets){
+    printf(
+        "The street with houses containing valuables: %s\n",
+        join(", ", @{$street})
+    );
+    printf(
+        "    will yield a total of %d loot.\n\n",
+        calculate_loot_yield_on_street(@{$street})
+    );
+}
+
+print("DISCLAIMER: Do not actually rob houses- it's not nice!\n\n");
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Determine the maximum amount of loot that can be gotten by robbing houses on
+# a street, given certain parameters and restrictions, including a requirement
+# to rob the first house on the street, and not to rob any two adjacent houses
+# Takes one argument:
+# * A list of the quantities of loot available in each house on the street
+# Returns:
+# * The maximum amount of loot that can be gotten within the restrictions
+#   specified, which will be zero (0) if the supplied list is empty
+# Shamelessly adapted from an algorithm seen at:
+# https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/
+# DISCLAIMER: Do not actually rob houses- it's not nice!
+################################################################################
+sub calculate_loot_yield_on_street{
+    use List::Util qw(max);
+
+    # Empty list, no houses to rob
+    return(0)
+        unless(@ARG);
+
+    my @loot;
+    my $loot_initial;
+    my $i;
+
+    # We always start with the first house, as
+    # specified (though this seems limiting...)
+    $loot_initial = $ARG[0];
+
+    # Strip off the first two houses- we've
+    # robbed the first and can't rob the second
+    splice(@ARG, 0, 2);
+
+    # Edge cases- zero or one houses left
+    return($loot_initial)
+        unless(@ARG);
+    if(scalar(@ARG) == 1){
+        return($loot_initial + $ARG[0]);
+    }
+
+    # Proceed as normal(?)
+    $loot[0] = $ARG[0];
+    $loot[1] = max($ARG[0], $ARG[1]);
+
+    for($i = 2; $i < scalar(@ARG); $i++){
+        $loot[$i] = max(@ARG[$i] + $loot[$i - 2], $loot[$i - 1]);
+    }
+
+    return($loot_initial + $loot[$#loot]);
+
+}
+
+
+