TL;DR

On with TASK #2 from The Weekly Challenge #202. Enjoy!

# The challenge

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.

Example 1

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


Example 2

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


Example 3

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


Example 4

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


Example 5

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


# The questions

I thing that in some serious setting I’d ask whether the inputs are supposed to be integers, if they can go negative or not, how many of them we are supposed to receive… etc.

Also, I’d ask if an array should be returned, or just the indexes of the widest valley within the provided array.

# The solution

The following solution, in Perl, has been built by subtraction. I was initially expecting to track the latest going down, the latest going up, the best, the levels, etc. just to eventually figure that we don’t need all that tracking.

We only need to track:

• the index of the latest going down begin ($db) • the index of the latest going level begin ($lb)
• whether we’re going up or not
• the best valley found so far

and iterate over the array. The code provides enough comments to fill the missing parts.

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

my @valley =
widest_valley(grep { defined } map { split m{\D+}mxs, } @ARGV);
say join ', ', @valley;

sub widest_valley (@altitudes) {
return @altitudes if @altitudes < 2;    # trivial cases

my $db = 0; # start of a valley my$lb       = 0;                       # start of a level
my $going_up = 0; # start going down my ($vb, $vl) = (0, 1); # best valley so far my$previous = $altitudes; for my$i (1 .. $#altitudes) { my$current = $altitudes[$i];

if ($previous <$current) {          # going up
$lb =$i;                   # reset the level begin
$going_up = 1; # record the direction } # do nothing if$previous == $current elsif ($previous > $current) { # going down if ($going_up) {    # leaving the top, "close" a valley
my $length =$i - $db; ($vb, $vl) = ($db, $length) if$length > $vl;$db       = $lb; # record the start of the new valley$going_up = 0;      # record the direction
} ## end if ($going_up)$lb = $i; # reset the level begin } ## end elsif ($previous > $current)$previous = $current; # prepare for the next iteration } ## end for my$i (1 .. $#altitudes) # anyway, close the last segment my$length = @altitudes - $db; ($vb, $vl) = ($db, $length) if$length > $vl; return @altitudes[$vb .. ($vb +$vl - 1)];
} ## end sub widest_valley


The Raku version is more or less a rip-off, including comments:

#!/usr/bin/env raku
use v6;
sub MAIN (*@args) {
my @valley = widest-valley([@args.map({.comb(/\d+/)}).flat».Int]);
put @valley.join(', ');
}

sub widest-valley (@altitudes) {
return @altitudes if @altitudes < 2;    # trivial cases

my $db = 0; # start of a valley my$lb       = 0;                       # start of a level
my $going_up = 0; # start going down my ($vb, $vl) = 0, 1; # best valley so far my$previous = @altitudes;
for 1 ..^ @altitudes -> $i { my$current = @altitudes[$i]; if$previous < $current { # going up$lb       = $i; # reset the level begin$going_up = 1;                    # record the direction
}

# do nothing if $previous ==$current

elsif $previous >$current {         # going down
if ($going_up) { # leaving the top, "close" a valley my$length = $i -$db;
($vb,$vl) = $db,$length if $length >$vl;

$db =$lb;    # record the start of the new valley
$going_up = 0; # record the direction } ## end if ($going_up)
$lb =$i;              # reset the level begin
} ## end elsif ($previous >$current)

$previous =$current;     # prepare for the next iteration
} ## end for my $i (1 ..$#altitudes)

# anyway, close the last segment
my $length = @altitudes -$db;
($vb,$vl) = $db,$length if $length >$vl;

return @altitudes[$vb .. ($vb + \$vl - 1)];
} ## end sub widest_valley


It seems to work on the test inputs so I’ll call this a day, stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!