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

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

2 files changed, 163 insertions, 0 deletions

diff --git a/challenge-285/mattneleigh/perl/ch-1.pl b/challenge-285/mattneleigh/perl/ch-1.pl
new file mode 100755
index 0000000000..472c140607
--- /dev/null
+++ b/challenge-285/mattneleigh/perl/ch-1.pl
@@ -0,0 +1,88 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use English;
+
+################################################################################
+# Begin main execution
+################################################################################
+
+my @route_maps = (
+    [ ["B","C"], ["D","B"], ["C","A"] ],
+    [ ["A","Z"] ]
+);
+
+print("\n");
+foreach my $route_map (@route_maps){
+    my $rval = determine_final_destination($route_map);
+
+    printf(
+        "Input: \@routes = (%s)\nOutput: \"%s\"\n\n",
+        join(
+            ", ",
+            map(
+                "[" . join(", ", map("\"" . $_ . "\"", @{$_})) . "]",
+                @{$route_map}
+            )
+        ),
+        defined($rval) ?
+            $rval
+            :
+            "None"
+    );
+}
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Given a list of routes, defined in terms of start and end points, determine
+# whether there is a point beyond which no route departs, and if so, report
+# the name of that point
+# Takes one argument:
+# * A ref to a list of routes, each of which is itself an array consisting of a
+#   starting point and end point (e.g.
+#       [
+#           ["B","C"],
+#           ["D","B"],
+#           ["C","A"]
+#       ]
+#   )
+# Returns on success:
+# * The first destination point, in the order the waypoints are presented in
+#   the input, that does not have a route departing from it (e.g. "A" )
+# Returns on error:
+# * undef if no route was found to have an endpoint from which no other route
+#   departs
+################################################################################
+sub determine_final_destination{
+    my $routes = shift();
+
+    my %origins;
+
+    # Store a table of all origin points
+    foreach my $route (@{$routes}){
+        $origins{$route->[0]} = 1;
+    }
+
+    # Scan each destination to see if it's also an
+    # origin point; if we find one that isn't,
+    # return it
+    foreach my $route (@{$routes}){
+        return($route->[1])
+            unless($origins{$route->[1]});
+    }
+
+    # Got here- every destination had connections
+    # to further points
+    return(undef);
+
+}
+
+
+
diff --git a/challenge-285/mattneleigh/perl/ch-2.pl b/challenge-285/mattneleigh/perl/ch-2.pl
new file mode 100755
index 0000000000..e85343adf1
--- /dev/null
+++ b/challenge-285/mattneleigh/perl/ch-2.pl
@@ -0,0 +1,75 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use English;
+
+################################################################################
+# Begin main execution
+################################################################################
+
+my @amounts = (
+    9, 15, 100
+);
+my @denominations = (
+    1, 5, 10, 25, 50
+);
+
+print("\n");
+foreach my $amount (@amounts){
+    printf(
+        "Input: \$amount = %d\nOuput: %d\n\n",
+        $amount,
+        count_change_permutations($amount, \@denominations)
+    );
+}
+
+exit(0);
+################################################################################
+# End main execution; subroutines follow
+################################################################################
+
+
+
+################################################################################
+# Compute the number of ways to make change for a given amount of money, using
+# a specified set of coins or notes of denominations in the same unit as the
+# specified amount- these could be cents, dollars, pounds, etc. as long as all
+# quantities are specified in the same units
+# Takes two arguments:
+# * An amount of money for which change must be made (e.g. 100 )
+# * A ref to an array containing the denominations of coins or notes available
+#   (e.g.
+#       [ 1, 5, 10, 25, 50 ]
+#   )
+# Returns:
+# * The number of ways the specified amount of money can be made using coins or
+#   notes of the denominations provided (e.g. 292 )
+# Method adapted from pseudocode presented here:
+# https://math.stackexchange.com/questions/176363/keep-getting-generating-function-wrong-making-change-for-a-dollar/176397#176397
+################################################################################
+sub count_change_permutations{
+    my $amount = shift();
+    my $denominations = shift();
+
+    # The coefficients beyond index 0 will be autovivified
+    my @coefs = (1);
+
+    # Loop over each denomination
+    foreach my $denomination (@{$denominations}){
+        # Loop from zero to the amount less the current
+        # denomination
+        for my $i (0 .. $amount - $denomination){
+            $coefs[$i + $denomination] += $coefs[$i];
+        }
+    }
+
+    # The coefficient at the index corresponding to the
+    # target amount has the number of ways change can be
+    # made with the given denominations
+    return($coefs[$amount]);
+
+}
+
+
+