Merge pull request #4288 from adherzog/challenge-117-2

Add perl solution for 117-2.

2 files changed, 100 insertions, 0 deletions

diff --git a/challenge-117/adherzog/README b/challenge-117/adherzog/README
new file mode 100644
index 0000000000..b59913be6c
--- /dev/null
+++ b/challenge-117/adherzog/README
@@ -0,0 +1 @@
+Solutions by Adam Herzog.
diff --git a/challenge-117/adherzog/perl/ch-2.pl b/challenge-117/adherzog/perl/ch-2.pl
new file mode 100755
index 0000000000..1b50d53018
--- /dev/null
+++ b/challenge-117/adherzog/perl/ch-2.pl
@@ -0,0 +1,99 @@
+#!/usr/bin/env perl
+
+##############################################################################
+# Perl Weekly Challenge #117
+##############################################################################
+#
+# Task #2 - Find Possible Paths
+#
+# You are given size of a triangle.
+#
+# Write a script to find all possible paths from top to the bottom right
+# corner.
+#
+# In each step, we can either move horizontally to the right (H), or move
+# downwards to the left (L) or right (R).
+#
+# BONUS: Try if it can handle triangle of size 10 or 20.
+#
+##############################################################################
+
+use strict;
+use warnings;
+
+use Test::More;
+
+if (@ARGV) {
+    my $paths = find_possible_paths_through_triangle(@ARGV);
+    print join( "\n", @{$paths} ), "\n";
+}
+else {
+    my @tests = (
+        { input => 1, output => [qw/LH R/], },
+        { input => 2, output => [qw/LHLH LHR LLHH LRH RLH RR/], },
+    );
+
+    for my $test (@tests) {
+
+        my $paths = find_possible_paths_through_triangle( $test->{'input'} );
+
+        is( $#{$paths},
+            $#{ $test->{'output'} },
+            'Got the right number of paths'
+        );
+        is_deeply( $paths, $test->{'output'}, 'Got the right paths' );
+    }
+
+    done_testing();
+}
+
+exit;
+
+##############################################################################
+#
+# Triangle of height 2
+#
+#    *      [0,0]
+#    |\
+#    *-*    [1,0] [1,1]
+#    | /\
+#    *-*-*  [2,0] [2,1] [2,2]
+
+##############################################################################
+
+sub find_possible_paths_through_triangle {
+    my $n = shift;
+
+    die "N must be at least one" unless ( $n =~ /^\d+$/ && $n > 0 );
+
+    my $triangle = [];
+    return _paths_through_triangle( $triangle, $n, 0, 0 );
+}
+
+sub _paths_through_triangle {
+    my ( $triangle, $n, $row, $col ) = @_;
+
+    return [''] if ( $row == $n && $col == $n );
+
+    return $triangle->[$row]->[$col] if ( $triangle->[$row]->[$col] );
+
+    if ( $row != $col ) {
+
+        # move horizontal
+        my $paths = _paths_through_triangle( $triangle, $n, $row, $col + 1 );
+        push @{ $triangle->[$row]->[$col] }, map {"H$_"} @{$paths};
+    }
+
+    if ( $row < $n ) {
+
+        # move left
+        my $paths = _paths_through_triangle( $triangle, $n, $row + 1, $col );
+        push @{ $triangle->[$row]->[$col] }, map {"L$_"} @{$paths};
+
+        # move right
+        $paths = _paths_through_triangle( $triangle, $n, $row + 1, $col + 1 );
+        push @{ $triangle->[$row]->[$col] }, map {"R$_"} @{$paths};
+    }
+
+    return $triangle->[$row]->[$col];
+}