Solution to task 2

1 files changed, 133 insertions, 0 deletions

diff --git a/challenge-202/jo-37/perl/ch-2.pl b/challenge-202/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..940afb24be
--- /dev/null
+++ b/challenge-202/jo-37/perl/ch-2.pl
@@ -0,0 +1,133 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use experimental 'postderef';
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [N1 N2...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N1 N2...
+    List of altitudes
+
+EOS
+
+
+### Input and Output
+
+say join ' ', widest_valley(@ARGV);
+
+
+### Implementation
+
+# Find the leftmost widest valley in a single pass through the list.
+# This can be achieved by tracking every valley, identified by its
+# starting index, length (in data points, not steps!) and current
+# direction.  A valley at the end of its uphill slope is considered
+# "closed" and is marked with a zero direction.
+#
+sub widest_valley {
+    # Start with one valley consisting of a single point downhill slope.
+    # This enables a starting uphill half-valley.
+    my  @valleys = ({start => 0, length => 1, dir => -1});
+    my $widest = $valleys[0];
+    for my $i (0 .. $#_ - 1) {
+        my $dir = $_[$i + 1] <=> $_[$i];
+        # Mark the potential beginning of a new valley on a
+        # non-ascending step.
+        my $new = $dir <= 0;
+        for my $valley (@valleys) {
+            # Skip "closed" valleys.
+            next unless $valley->{dir};
+
+            # Close the valley if it goes uphill and the next step goes
+            # downhill.
+            #  _
+            # / \
+            #
+            # In all other cases the next step extends the valley and
+            # may lead to a new maximum.
+            #
+            # \_  \__ \_/  __  _/
+            #   \         /   /   
+            if ($valley->{dir} > 0 && $dir < 0) {
+                $valley->{dir} = 0;
+            } else {
+                $widest = $valley
+                    if ++$valley->{length} > $widest->{length};
+            }
+            # Invert the valley's direction to uphill if the next step
+            # goes uphill.
+            #
+            # \_/
+            $valley->{dir} = 1 if $valley->{dir} < 0 && $dir > 0;
+
+            # A (non-ascending) step that extends the downhill slope of
+            # a valley is not the beginning of a new valley.
+            # _   _
+            #  \_  \
+            #       \
+            $new = 0 if $valley->{dir} < 0;
+        }
+        # Open a new valley if a non-ascending step is not part of a
+        # known valley's downhill slope.
+        #   _    
+        # _/  _/\
+        #
+        # If the new valley starts with an indifferent step, it might
+        # turn out to be part of an uphill slope later, though. It would
+        # not violate the definition of a valley but cannot be maximal.
+        # Such spurious valleys do not hurt in this task.
+        #
+        #   _/
+        # _/
+        push @valleys, {start => $i, length => 2, dir => -1} if $new;
+    }
+
+    # Extract the leftmost widest valley.
+    splice @_, $widest->{start}, $widest->{length};
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is [widest_valley(1, 5, 5, 2, 8)],
+            [5, 5, 2, 8], 'example 1';
+        is [widest_valley(2, 6, 8, 5)],
+            [2, 6, 8], 'example 2';
+        is [widest_valley(9, 8, 13, 13, 2, 2, 15, 17)],
+            [13, 13, 2, 2, 15, 17], 'example 3';
+        is [widest_valley(2, 1, 2, 1, 3)],
+            [2, 1, 2], 'example 4';
+        is [widest_valley(1, 3, 3, 2, 1, 2, 3, 3, 2)],
+            [3, 3, 2, 1, 2, 3, 3], 'example 5';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        is [widest_valley(1, 2, 3, 4, 3, 4)], [1, 2, 3, 4], 'half at start';
+        is [widest_valley(4, 3, 4, 3, 2, 1)], [4, 3, 2, 1], 'haft at end';
+        is [widest_valley(2, 1, 2, 2, 1, 2, 2, 1, 2)],
+            [2, 2, 1, 2, 2], 'embedded';
+        is [widest_valley(2, 1, 2, 2, 3, 3, 4, 4, 1)],
+            [2, 1, 2, 2, 3, 3, 4, 4], 'spurious valleys';
+	}
+
+    done_testing;
+    exit;
+}