1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-202/#TASK2
  3 #
  4 # Given a profile as a list of altitudes, return the leftmost widest valley. A
  5 # valley is defined as a subarray of the profile consisting of two parts: the
  6 # first part is non-increasing and the second part is non-decreasing. Either
  7 # part can be empty.
  8 #
  9 ## Example 1
 10 ##
 11 ## Input: 1, 5, 5, 2, 8
 12 ## Output: 5, 5, 2, 8
 13 #
 14 ## Example 2
 15 ##
 16 ## Input: 2, 6, 8, 5
 17 ## Output: 2, 6, 8
 18 #
 19 ## Example 3
 20 ##
 21 ## Input: 9, 8, 13, 13, 2, 2, 15, 17
 22 ## Output: 13, 13, 2, 2, 15, 17
 23 #
 24 ## Example 4
 25 ##
 26 ## Input: 2, 1, 2, 1, 3
 27 ## Output: 2, 1, 2
 28 #
 29 ## Example 5
 30 ##
 31 ## Input: 1, 3, 3, 2, 1, 2, 3, 3, 2
 32 ## Output: 3, 3, 2, 1, 2, 3, 3
 33 #
 34 ############################################################
 35 ##
 36 ## discussion
 37 ##
 38 ############################################################
 39 #
 40 # Each position in the array is also the beginning of a valley. So basically we
 41 # have to find the longest valley that starts in each position in the array,
 42 # and then select the longest valley overall (and the leftmost of those if
 43 # multiple valleys are of the same length).
 44 
 45 use strict;
 46 use warnings;
 47 use feature 'say';
 48 
 49 my @examples = (
 50         [1, 5, 5, 2, 8],
 51         [2, 6, 8, 5],
 52         [9, 8, 13, 13, 2, 2, 15, 17],
 53         [2, 1, 2, 1, 3],
 54         [1, 3, 3, 2, 1, 2, 3, 3, 2]
 55 );
 56 
 57 foreach my $array (@examples) {
 58    say "Input: " . join(", ", @$array);
 59    say "Output: " . join(", ", get_longest_valley(@$array));
 60 }
 61 
 62 sub get_longest_valley {
 63    my @array = @_;
 64    my @longest = ();
 65    foreach my $index (0..$#array) {
 66       # get the longest valley starting at the current index
 67       my @valley = get_valley(@array[$index..$#array]);
 68       # if this valley is longer than the longest so far, we have a
 69       # new longest valley
 70       if($#valley > $#longest) {
 71          @longest = @valley;
 72       }
 73    }
 74    return @longest;
 75 }
 76 
 77 # get the longest valley at the beginning of the given array
 78 sub get_valley {
 79    my @array = @_;
 80    # we start off as non-increasing
 81    my $non_increasing = 1;
 82    my @result = ();
 83    # let's just grab the first element
 84    # of the array and put it into the result
 85    my $last = shift @array;
 86    push @result, $last;
 87    foreach my $elem (@array) {
 88       # if we're still in the non-increasing part, we
 89       # switch to non-decreasing if the current element
 90       # is bigger than the last one
 91       if($non_increasing) {
 92          if($elem > $last) {
 93             $non_increasing = 0;
 94          }
 95          push @result, $elem;
 96          $last = $elem;
 97       } else { # non-decreasing part
 98          # if we have a smaller value than the last, we have
 99          # found the end of valley and can return it
100          if($elem < $last) {
101             return @result;
102          }
103          push @result, $elem;
104          $last = $elem;
105       }
106    }
107    return @result;
108 }