Task — Find the valleys

Given a profile as a list of altitudes, we are asked to return the leftmost widest valley. A valley is defined as a subarray of the profile consisting of two parts: the first part is non-increasing and the second part is non-decreasing. Either part can be empty.

Analysis

The supplied profile is going to have one or more highs and one or more lows, where a high is defined as a point from which you can't reach another high without first going down and a low similarly is one where you can't reach another low without first ascending. Any profile will therefore comprise an alternating sequence of highs and lows.

Note that highs and lows may be more than one point wide if two or more successive points are at the same height.

The phrase 'Either part can be empty' bears some thought. Consider the sequence 6, 5, 4. If we take the phrase literally, the 5 can be considered as a valley with its second part empty. However, we are looking for the widest valley, and unless the profile only contains a single point, there will always be a valley with a width more than 1.

So the only places where the phrase does have an impact is at the edges of the profile. Consider the sequence 1, 2, 3, 4, 3, 2. This contains two valleys: 1, 2, 3, 4 with an empty first part, and 4, 3, 2 with an empty second part.

This also illustrates the fact that the highs - 4 in this case - may be part of 2 valleys, one to its left and one to its right. This is true even if the high is more than one point wide, eg 1, 2, 3, 4, 4, 4, 3, 2 where the valleys are 1, 2, 3, 4, 4, 4 and 4, 4, 4, 3, 2.

So having though about all that I decided the best way to proceed was to look for all the lows, and for each one stretch to the left and the right to determine its extent. I kept track of the widest valley seen so far and only updated that when I found a wider one, thus ensuring that I reported on the leftmost widest one.

This is a good example of a problem that is easy to describe, easy to solve by looking at the supplied profile, but not that easy to solve algorithmically.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2023-01-30
# PWC 202 task 1

use v5.28;
use utf8;
use warnings;

# Task: Given a profile as a list of altitudes, return the leftmost widest valley. A valley is defined as a subarray 
# of the profile consisting of two parts: the first part is non-increasing and the second part is non-decreasing. 
# Either part can be empty.

# Blog: https://pjcs-pwc.blogspot.com/

my (@tests, $test, $j, $k, $is_bottom, $vl, $vr, @height, $rightmost, $widest, $width, $range);

@tests = ([1, 5, 5, 2, 8], [2, 6, 8, 5], [9, 8, 13, 13, 2, 2, 15, 17], [2, 1, 2, 1, 3], [1, 3, 3, 2, 1, 2, 3, 3, 2],
    [7, 7, 7, 7, 7], [1, 2, 3, 2, 2], [6, 5, 6, 5, 4, 3], [7, 8, 8, 7], [7], [1, 2, 3, 4], [4, 3, 2, 1]);

# loop over test values
for $test (@tests) {
    @height = @$test;
    $rightmost = scalar(@height) - 1;
    $widest = -1;
    
    # scan for low points that are at the bottom of a valley
    for $j (0 .. scalar(@height) - 1) {
        $is_bottom = 1;
        if ($j != 0) {
            $is_bottom = 0 if $height[$j - 1] < $height[$j];
        }
        if ($j != $rightmost) {
            $is_bottom = 0 if $height[$j + 1] < $height[$j];
        }
        next unless $is_bottom;
        
        # expand valley from bottom to the left
        $k = $vl = $j;
        while (-- $k >= 0) {
            last unless ($height[$k] >= $height[$vl]);
            $vl = $k;
        }
        
        # and from the bottom to the right
        $k = $vr = $j;
        while (++ $k <= $rightmost) {
            last unless ($height[$k] >= $height[$vr]);
            $vr = $k;
        }
        
        # is this the widest so far?
        $width = $vr - $vl + 1;
        if ($width > $widest) {
            $range = '';            
            $range .= qq[$height[$_], ] for $vl .. $vr;
            $widest = $width;
        }
    }
    
    # show results
    say qq[\nInput:  ] . join(', ', @$test) . qq[\nOutput: ] . substr($range, 0, -2);
}

Output

Input:  1, 5, 5, 2, 8
Output: 5, 5, 2, 8

Input:  2, 6, 8, 5
Output: 2, 6, 8

Input:  9, 8, 13, 13, 2, 2, 15, 17
Output: 13, 13, 2, 2, 15, 17

Input:  2, 1, 2, 1, 3
Output: 2, 1, 2

Input:  1, 3, 3, 2, 1, 2, 3, 3, 2
Output: 3, 3, 2, 1, 2, 3, 3

Input:  7, 7, 7, 7, 7
Output: 7, 7, 7, 7, 7

Input:  1, 2, 3, 2, 2
Output: 1, 2, 3

Input:  6, 5, 6, 5, 4, 3
Output: 6, 5, 4, 3

Input:  7, 8, 8, 7
Output: 7, 8, 8

Input:  7
Output: 7

Input:  1, 2, 3, 4
Output: 1, 2, 3, 4

Input:  4, 3, 2, 1
Output: 4, 3, 2, 1