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

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

2 files changed, 432 insertions, 0 deletions

diff --git a/challenge-125/mattneleigh/perl/ch-1.pl b/challenge-125/mattneleigh/perl/ch-1.pl
new file mode 100755
index 0000000000..27ae4e9ec7
--- /dev/null
+++ b/challenge-125/mattneleigh/perl/ch-1.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use English;
+
+################################################################################
+# Begin main execution
+################################################################################
+
+my @integers = (5, 13, 1, 100);
+my $integer;
+my $list;
+
+foreach $integer (@integers){
+    print($integer, ":\n");
+    $list = pythagorean_triples($integer);
+    if(defined($list)){
+        foreach(@{$list}){
+            printf(
+                "    %s\n",
+                list_contents_to_string(@{$_})
+            );
+        }
+    } else{
+        print("    -1\n");
+    }
+    print("\n");
+}
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Calculate the Pythagorean triples associated with an integer N, if any exist,
+# including numbers up to 10000, e.g. (a, b, N), (N, b, c) or (a, N, c) where
+# the three numbers in the triple satisfy Pythagorean's Theorem
+# (a^2 + b^2 == c^2)
+# Takes one argument:
+# * The integer (N)
+# Returns on success:
+# * A ref to an array of Pythagorean triples, which are themselves refs to
+#   arrays, e.g.:
+#   [ [3, 4, 5], [5, 12, 13] ]
+# Returns on failure:
+# * undef if no Pythagorean triples could be found
+################################################################################
+sub pythagorean_triples{
+    my $n = int(shift());
+
+    my $i;
+    my $num;
+    my $n2 = $n ** 2;
+    my @triples;
+
+    # Find triplets where $n is the
+    # hypotenuse
+    for($i=2; $i<=int($n/2)+1; $i++){
+        $num = sqrt($n2 - $i ** 2);
+        if($num == int($num)){
+            if($i < $num){
+                push(@triples, [$i, $num, $n]);
+            } else{
+                push(@triples, [$num, $i, $n]);
+            }
+        }
+
+    }
+
+    # Find triplets where $n is one
+    # of the other two sides
+    for($i=2; $i<10000; $i++){
+        $num = sqrt($n2 + $i ** 2);
+        if($num == int($num)){
+            if($i < $n){
+                push(@triples, [$i, $n, $num]);
+            } else{
+                push(@triples, [$n, $i, $num]);
+            }
+        }
+    }
+
+    if(scalar(@triples)){
+        return(\@triples);
+    } else{
+        return(undef);
+    }
+
+}
+
+
+
+################################################################################
+# Produce a string detailing the contents of a list 
+# Takes one argument:
+# * A list of references to lists; the list must contain at least one element,
+#   e.g.:
+#   @list = (1, 3, 2, 7);
+#   list_contents_to_string(@list);
+# Returns on success:
+# * A string representation of the set of lists provided, e.g.:
+#   "(1, 3, 2, 7)"
+# Returns on error:
+# * undef if the provided list is empty
+################################################################################
+sub list_contents_to_string{
+
+    return(undef) unless(defined($ARG[0]));
+
+    return(
+        sprintf(
+            "(%s)",
+            join(", ", @ARG)
+        )
+    );
+
+}
+
+
+
diff --git a/challenge-125/mattneleigh/perl/ch-2.pl b/challenge-125/mattneleigh/perl/ch-2.pl
new file mode 100755
index 0000000000..80c574236d
--- /dev/null
+++ b/challenge-125/mattneleigh/perl/ch-2.pl
@@ -0,0 +1,308 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use Scalar::Util qw(reftype);
+
+################################################################################
+# Begin main execution
+################################################################################
+
+my @trees;
+
+# Tree 0:
+#
+#     1
+#    / \
+#   2   5
+#  / \ / \
+# 3  4 6  7
+#        / \
+#       8  10
+#      /
+#     9
+
+$trees[0] = make_tree_node(1);
+$trees[0]{l} = make_tree_node(2);
+$trees[0]{l}{l} = make_tree_node(3);
+$trees[0]{l}{r} = make_tree_node(4);
+$trees[0]{r} = make_tree_node(5);
+$trees[0]{r}{l} = make_tree_node(6);
+$trees[0]{r}{r} = make_tree_node(7);
+$trees[0]{r}{r}{l} = make_tree_node(8);
+$trees[0]{r}{r}{l}{l} = make_tree_node(9);
+$trees[0]{r}{r}{r} = make_tree_node(10);
+
+
+# Tree 1 (for testing- diameter does not
+# pass through the root node):
+#
+#     1
+#    / \
+#   2   3
+#      / \
+#     4   7
+#    /     \
+#   5       8
+#  /         \
+# 6           9
+#              \
+#              10
+
+$trees[1] = make_tree_node(1);
+$trees[1]{l} = make_tree_node(2);
+$trees[1]{r} = make_tree_node(3);
+$trees[1]{r}{l} = make_tree_node(4);
+$trees[1]{r}{l}{l} = make_tree_node(5);
+$trees[1]{r}{l}{l}{l} = make_tree_node(6);
+$trees[1]{r}{r} = make_tree_node(7);
+$trees[1]{r}{r}{r} = make_tree_node(8);
+$trees[1]{r}{r}{r}{r} = make_tree_node(9);
+$trees[1]{r}{r}{r}{r}{r} = make_tree_node(10);
+
+my $tree;
+my $diameter;
+my $path;
+my @node_IDs;
+
+# Loop over each tree and find the longest
+# path between leaves in each
+foreach $tree (@trees){
+    @node_IDs = ();
+    ($diameter, $path) = calculate_tree_diameter_path($tree);
+    printf("Diameter: $diameter\n");
+    foreach(@{$path}){
+        push(@node_IDs, $_->{d});
+    }
+    printf("Path: %s\n", join(", ", @node_IDs));
+    print("\n");
+}
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Calculate the diameter- the greatest distance between two leaves- of a binary
+# tree
+# Takes one argument:
+# * A ref to the root of a binary tree, the nodes of which must consist of hash
+#   references with references to further nodes to the left and right in fields
+#   named 'l' and 'r' respectively, e.g.:
+#
+#   {
+#       d => $data, # This will be ignored
+#       l => undef,
+#       r => undef
+#   }
+#
+# Returns:
+# * A list containing the number of nodes between (and including) the two
+#   farthest leaves in the tree, and a ref to a list of node refs that describe
+#   the path between said leaves, including the leaves and the root of the
+#   subtree through which the diameter passes, which may or may not be the root
+#   of the tree provided, e.g.:
+#
+#   ($diameter, $path) = calculate_tree_diameter_path($tree);
+#
+################################################################################
+sub calculate_tree_diameter_path{
+    my $tree = shift();
+
+    my $diameter_data = {
+        diameter => 0,
+        root => undef,
+        r_path => undef,
+        l_path => undef
+    };
+
+    # Traverse the tree; we ignore the return
+    # values since what we want is all in
+    # $diameter_data
+    calculate_max_tree_depth($tree, $diameter_data);
+
+    # Combine the left-path list, root node, 
+    # and right-path list from the subtree we
+    # found, reversing the order of the latter
+    # en passant to create a proper leaf-to-leaf
+    # path through the root node
+    push(@{$diameter_data->{l_path}}, $diameter_data->{root});
+    while(scalar(@{$diameter_data->{r_path}})){
+        push(
+            @{$diameter_data->{l_path}},
+            pop(@{$diameter_data->{r_path}})
+        );
+    }
+
+    return(
+        $diameter_data->{diameter},
+        $diameter_data->{l_path}
+    );
+
+}
+
+
+
+################################################################################
+# Calculate the maximum depth- the distance to the farthest leaf- of a binary
+# tree
+# Takes two arguments:
+# * A ref to the root of a binary tree, the nodes of which must consist of hash
+#   references with references to further nodes to the left and right in fields
+#   named 'l' and 'r' respectively, e.g.:
+#
+#   {
+#       d => $data, # This will be ignored
+#       l => undef,
+#       r => undef
+#   }
+#
+# * A ref to a hash that, if defined, will be used to store details of the
+#   tree's diameter (the longest path between two leaves) which may not
+#   necessarily pass through the root node.  The hash should be initialized as
+#   follows, with all fields required:
+#
+#   {
+#       diameter => 0,   # Diameter of the tree including both leaves and the
+#                        # root node of the subtree that includes the diameter
+#       root => undef,   # Ref to the root node of the subtree that includes
+#                        # the diameter
+#       l_path => undef, # Ref to a list of node refs along the path of the
+#                        # diameter to the left, including the leaf but NOT the
+#                        # root
+#       r_path => undef  # Ref to a list of node refs along the path of the
+#                        # diameter to the right, including the leaf but NOT
+#                        # the root
+#   }
+#
+#   All fields will be populated with the appropriate data upon this function's
+#   return; if this information is not desired, 'undef' may be passed as the
+#   second argument
+# Returns:
+# * A list containing the number of nodes between (and including) the specified
+#   root and the farthest leaf, and a ref to a list of node refs that describe
+#   the path to the farthest leaf, including the leaf but NOT the root, e.g.:
+#
+#   ($depth, $path) = calculate_max_tree_depth($tree, \%diameter);
+#
+#   or
+#
+#   ($depth, $path) = calculate_max_tree_depth($tree, undef);
+#
+################################################################################
+sub calculate_max_tree_depth{
+    my $root = shift();
+
+    unless($root){
+        # No nodes in this direction;
+        # return zero length and empty
+        # path
+        return(0, []);
+    }
+
+    my $diameter_data = shift();
+
+    my $l_depth;
+    my $l_path;
+    my $r_depth;
+    my $r_path;
+
+    # Dig deeper to the left, and to the
+    # right
+    ($l_depth, $l_path) =
+        calculate_max_tree_depth($root->{l}, $diameter_data);
+    ($r_depth, $r_path) =
+        calculate_max_tree_depth($root->{r}, $diameter_data);
+
+    # reftype() taken from Scalar::Util
+    if($diameter_data && (reftype($diameter_data) eq "HASH")){
+        # We're keeping track of the largest
+        # leaf-to-leaf distance; if the diameter at
+        # this node is the largest we've seen so
+        # far, store the data we have at this point
+        my $node_diameter = $l_depth + $r_depth + 1;
+
+        if($node_diameter > $diameter_data->{diameter}){
+            $diameter_data->{diameter} = $node_diameter;
+            $diameter_data->{root} = $root;
+            $diameter_data->{l_path} = copy_list($l_path);
+            $diameter_data->{r_path} = copy_list($r_path);
+        }
+    }
+
+    # Check which side had the deeper path,
+    # and return it
+    if($r_depth > $l_depth){
+        push(@{$r_path}, $root);
+        return($r_depth + 1, $r_path);
+    } else{
+        push(@{$l_path}, $root);
+        return($l_depth + 1, $l_path);
+    }
+
+}
+
+
+
+################################################################################
+# Make a copy of a list
+# Takes one argument:
+# * A ref to the list to copy- the source list
+# Returns on success:
+# * A ref to a copy of the source list; if the source list is empty, this will
+#   be empty as well
+# Returns on error:
+# * undef if the source list reference is undefined
+# NOTE: This function only copies the source list itself; if that list contains
+# refs to other data structures, only the refs are copied
+################################################################################
+sub copy_list{
+    my $source = shift();
+
+    my $dest = [];
+
+    unless(defined($source)){
+        return(undef);
+    }
+
+    foreach(@{$source}){
+        push(@{$dest}, $_);
+    }
+
+    return($dest);
+
+}
+
+
+
+################################################################################
+# 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
+        }
+    );
+
+}
+
+
+