PWC 345: I Went to the Mountains

I found the two tasks this week straight-forward and oddly specific, respectively.

Music: the task titles this week are "Peak Positions" and "Last Visitor", which led me to the refrain "I went to the mountains." It's a reference to Closer to Fine by the Indigo Girls, which references Perl philosophy: "There's more than one answer to these questions pointing me in a crooked line, and the less I seek my source for some definitive, the closer I am to fine."

However, for "Peak Positions", let's go with Ain't No Mountain High Enough by Marvin Gaye; and for "Last Visitor", with it's odd back and forth, how about the venerable Hello, Goodbye by the Beatles.

Task 1: Peak Position

The task

You are given an array of integers, @ints. Find all the peaks in the array. A peak is an element that is strictly greater than its left and right neighbors. Return the indices of all such peak positions.

The thought process

My first thought was to use List::MoreUtils::indexes to test each element, but the edges make it weird. One way or another, they will have to be handled separately. Maybe put a fake element on each end? Do them first and then process the rest? Or test for edges while looping?

My mental model is that the edges of the list fall away into an abyss, so anything outside the list should be below the altitudes given at the edge positions. I suppose it's equally valid to assume that the list is surrounded by huge ice walls (winter is coming).

There are a couple of unspecified anomalies, for which I'm going to take executive decisions:

• Empty list: return an empty list
• Single element: that's one peak at index 0
• Ramp up: (e.g. 7,8,9) the rightmost element is the only peak
• Ramp down: (e.g. 6,5,4) the left-most element is the only peak
• Plateau: (e.g., 7,7,7) No peak, return an empty list. This contradicts my decision for a single element (a plateau of one). Do I contradict myself? Very well then, I contradict myself. (I am large, I contain multitudes.)

The code

sub peakPos(@int)
{
    my @peak = ();
    for my ($i, $n) ( indexed @int )
    {
        my $left  = ( $i == 0     ) ? $n-1 : $int[$i-1];
        my $right = ( $i == $#int ) ? $n-1 : $int[$i+1];
        push @peak, $i if ( $n > $left && $n > $right );
    }
    return \@peak;
}

Notes:

• Once again I chose indexed (anointed as non-experimental in Perl 5.40) for concise and efficient array traversal.
• Each element has a left neighbor and a right neighbor. For the edges, I'm going to conjure up the missing neighbor and make it less, assuming that outside the list is a bottomless void. You know the one -- the one we scream into while we're on mute during Zoom calls.

Task 2: Last Visitor

The task

You are given an integer array @ints where each element is either a positive integer or -1. We process the array from left to right while maintaining two lists:

• @seen: stores previously seen positive integers (newest at the front)
• @ans: stores the answers for each -1

Rules:

• If $ints[i] is a positive number -> insert it at the front of @seen
  • If $ints[i] is -1:
  • Let $x be how many -1s in a row we’ve seen before this one.
  • If $x < len(@seen) -> append seen[x] to @ans
  • Else -> append -1 to @ans

At the end, return @ans.

The thought process

This task description is highly proscriptive. I'm not sure there's anything better to do here than to translate the text into Perl statements.

sub lastVisitor(@int)
{
    my @seen = ();
    my @ans  = ();

    my $x = 0;  # Count of consecutive -1s
    for ( @int )
    {
        if ( $_ > 0 )
        {
            $x = 0;
            unshift @seen, $_;
        }
        else
        {
            if ( $x < @seen )
            {
                push @ans, $seen[$x];
            }
            else
            {
                push @ans, -1;
            }
            $x++;
        }
    }
    return \@ans;
}

Notes: I don't think there's much to add. There's a couple of basic language features being exploited.

• for (@int) -- use the implicit $_ variable for array elements to avoid having to think of a name
• unshift -- put things on the front of a list
• @seen -- in scalar context gives the size of the array (no need for a length())

The only thing tricky here is incrementing and resetting $x so that it correctly counts the consecutive occurrences of -1. Because there was a possibility of error, I of course made that error, but unit tests straightened me out.