Tag: perl

Wherein we consider that peaks and valleys depend as much on granularity as the length of a coastline: at one scale a plain may appear flat, but the same can be said for the surface of the Earth, viewed from space. As scales change, features overlap and distinctions become hazy and blurred.

THE WEEKLY CHALLENGE – PERL & RAKU #202 Task 2

---

“Even in the valley of the shadow of death, two and two do not make six.“

— Leo Tolstoy

---

Widest Valley

Submitted by: E. Choroba

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

ANALYSIS

What an unusual puzzle. It has a few moving parts that will each need to be approached, each at their own level of resolution. We start with a definition of a valley: a subarray that begins either with its values either constant or decreasing, which then changes to values constant or ascending, and this continues until direction changes downward again. When this happens we have spanned a complete valley element. As we will need the subarray data for verbose output the elements, or the subarray head and tail indices, need to be recorded.

But that’s just the beginning. We’re not done! No, we will need to continue searching from that point where the direction turns downward and see if we can find another, wider valley. Then we can compare the new width to the old and replace our previous maximum if we succeed. We only finally stop when we run out of array.

BUT… there’s a catch. There’s always a catch, right? Real life, I have noted many times, is a messy tangle of contradictions with no escape. This mortal coil is better modeled as an abused slinky toy, bent and turned in on itself, no longer able to preform the tricks of its youth — effortlessly descending a stair, amusing the onlookers with its bouncy and charming physical attributes.

Wow that metaphor really took of, didn’t it?

The problem arises as we have defined our left valley face as non-increasing —  that is, either unchanging or decreasing in value. The same allowance for a neutral, unchanging right face is also given. This gives the two definitions an overlap, where a continuous state can be either considered ascending or descending equally, only dependent on context, and that context, too, can in some scenarios overlap.

What this means, then, is that a flat plateau at the top of the right face of one valley, and the left face of the next valley rightward can occupy the same set of values, and must be considered to be a part of both structures. So unless wee backtrack, we can’t just start counting anew when we finish one valley; we need to be already be looking ahead into the next before we finish the previous.

Perhaps a visual aid will be of service. Consider the stripped-down example using only the values 1 and 0:

        1,0,0,0,1,1,1,0,0,0,0,1
        |-----------| |-------|
              7           5
                |-------------| 
                       8

Counting the first valley we descend, remain stationary for a while, then ascend to a plateatu for three positions until the height begins to descend again and we stop. The total width is 7. Counting forward from that position we remain flat for four places, defining the left face, then ascend one for a total width of 5. The first valley is obviously larger using this reckoning. The output would be the first valley:

1, 0, 0, 0, 1, 1, 1

However this is incorrect. The second valley actually starts earlier, at the left edge of the central plateau. Including these positions, the second valley has width 8, and is the larger:

1, 1, 1, 0, 0, 0, 0, 1

We’ll have to watch for that.

METHOD

We will need some containers to hold the various valleys we collect, as we traverse the input array from left to right. Three should do, for the current valley we are in, the start of the next valley if we are ascending the far side of the first, and a copy of the largest valet we have found so far. We will also need an iterator index variable to keep our position, but we can use the topic for that.

Lastly, a flag will be necessary to keep track of which face of the valley we are currently on: the left, descending bank, including the basin at the bottom, or the right, ascending bank and any plateau at the top. The inclusive flat portions serve from the definition that the left should be “non-increasing” and the right “non-decreasing”. The closing directive that either face can be empty only comes into play at the head and tail of the array, as internally any index will be a part of some valley or another, even if there is no elevation at all. In that degenerate case the horizontal plain will be considered a valley from the beginning and will also be the widest found.

Whichever direction the first pair of indices move, up or down, will in turn determine our initial face, descending or ascending.

The process moves from index to index, but the state of the machine at any given point is dependent on the face we are on and the movement of a value relative to that at the previous index. We just need to carefully keep track of it all. A further complication is brought in because we have separate criteria for adding values to the hypothetical overlapping left face of the next valley to be examined. These only need to be checked when we are leaving our current valley, ascending the right face.

Only when the ascending right face turns downwards are we definitively out of the current valley. We then compare it to the current stored maximum, replacing that array with the current valley only if it is wider. In any case whether the current valley rates or not, it is discarded and replaced with the partial, lookahead next valley we’ve also been watching. At this point after replacing we void out the next array of our stack.

And there’s that word: stack. We could use a proper stack, an array of array references but this whole process is confusing enough and there would be little gain. But we could do that if we wanted to be data-structure purists.

Observant readers will note that there’s a little hiccup when an array is not initialized, where we need to make sure to also add the previous value along with the currently indexed, as this will have been skipped when using our look-behind paradigm to determine the slope. This happens with the very first value checked, the index [1], and again when we have zeroed out the lookahead next valley after completing a previous and swapping it out.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


my @input = @ARGV;
scalar @input == 0 and @input = (1, 3, 3, 2, 1, 2, 3, 3, 2);

my @valley = get_valley( @input );
say "@valley";


sub get_valley ( @data ) {
    my @max;
    my @curr;
    my @next;
    my $face = 0;

    for (1..$#data) {   

        if  (@curr == 0) {                      ## UNINITIALIZED, no current
            push @curr, @data[$_-1, $_];            ##   always add value and previous
        
            $data[$_] <= $data[$_-1]      
                ? $face = 0                         ##   descending or plateau  
                : $face = 1;                        ##   ascending , left is empty
            next;
        }
        
        if ($face == 0) {                       ## LEFT FACE (or basin), descending               
            push @curr, $data[$_];                  ##   always add
            
            $face = 1 if $data[$_] > $data[$_-1];   ##   upturn, switch faces
            next;
        }

        if ($face == 1) {                       ## RIGHT FACE              
            if ($data[$_] >= $data[$_-1]) {         ## ASCENDING (or plateau)
                push @curr, $data[$_];              ##   add value
                if ($data[$_] == $data[$_-1]) {     ##   plateau add to next    
                    @next                           ##   add previous if new
                        ? push @next, $data[$_]
                        : push @next, @data[$_-1, $_];
                }
            }
            
            else {                                  ## DOWNTURN, «END OF VALLEY»
                @max  = @curr if @curr > @max;      ##   check current against max
                @next                               ##   always add to next
                    ? push @next, $data[$_]
                    : push @next, @data[$_-1, $_];  ##   add previous if new

                @curr = @next;                      ##   move next to current and void
                @next = ();
                $face = 0;                          ##   switch faces
            }          
        }
    }
    
    @max  = @curr if @curr > @max;              ## final check of current

    return @max;  
}