Perl Weekly Challenge: Week 345
Challenge 1:
Peak Positions
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 neighbours. Return the indices of all such peak positions.
Example 1
Input: @ints = (1, 3, 2)
Output: (1)
Example 2
Input: @ints = (2, 4, 6, 5, 3)
Output: (2)
Example 3
Input: @ints = (1, 2, 3, 2, 4, 1)
Output: (2, 4)
Example 4
Input: @ints = (5, 3, 1)
Output: (0)
Example 5
Input: @ints = (1, 5, 1, 5, 1, 5, 1)
Output: (1, 3, 5)
We first define an array to hold any peaks we may find.
my @peaks;
The spec says a peak must be "strictly greater than its' left and right neighbors."
As the first and last elements of @ints only have one neighbor, we search for peaks starting
from the second (i.e. index 1) element upto the second from last element. If that element is greater
than its' neighbors, we add its' index to @peaks.
for 1 ..^ @ints.end -> $i {
if @ints[$i -1] < @ints[$i] > @ints[$i + 1] {
@peaks.push($i);
}
}
That's what I thought but it turns out my interpretation of the spec was wrong. Look at example 4. 5 (index 0) is considered a peak even though it has no neighbor to its' left; it is only greater than its' neighbor to the right.
To deal with such a scenario, I added this block before the for-loop.
if @ints[0] > @ints[1] {
@peaks.push(0);
}
Also, although none of the examples require it, for the sake of completeness, I checked if the last element is a peak after the for-loop.
if @ints[*-1] > @ints[*-2] {
@peaks.push(*-1);
}
Finally we print the list of any peaks that were found in the style of the output in the examples.
say q{(}, @peaks.join(q{, }), q{)};
And this is the Perl version. It's a directt translation from Raku.
my @peaks;
if ($ints[0] > $ints[1]) {
push @peaks, 0;
}
for my $i (1 .. scalar @ints - 2) {
if ($ints[$i - 1] < $ints[$i] > $ints[$i + 1]) {
push @peaks, $i;
}
}
if ($ints[-1] > $ints[-2]) {
push @peaks, $#ints;
}
say q{(}, (join q{, }, @peaks), q{)};
Challenge 2:
Last Visitor
You are given an integer array
@intswhere 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.
Example 1
Input: @ints = (5, -1, -1)
Output: (5, -1)
@seen = (5)
First -1: @ans = (5)
Second -1: @ans = (5, -1)
Example 2
Input: @ints = (3, 7, -1, -1, -1)
Output: (7, 3, -1)
@seen = (3, 7)
First -1: @ans = (7)
Second -1: @ans = (7, 3)
Third -1: @ans = (7, 3, -1)
Example 3
Input: @ints = (2, -1, 4, -1, -1)
Output: (2, 4, 2)
Example 4
Input: @ints = (10, 20, -1, 30, -1, -1)
Output: (20, 30, 20)
Example 5
Input: @ints = (-1, -1, 5, -1)
Output: (-1, -1, 5)
Not a lot to say about this one. Basically you just have to translate the rules in the spec straight into code.
my @seen;
my @ans;
my $x = 0;
for @ints.keys -> $i {
One little hiccup I ran into was I initially incremented $x before .push()ing to @ans
here which gave me off-by-one errors.
if @ints[$i] == -1 {
@ans.push( $x < @seen.elems ?? @seen[$x] !! -1);
$x++;
} else {
@seen.unshift(@ints[$i]);
$x = 0;
}
}
say q{(}, @ans.join(q{, }), q{)};
And this is the—equally straightforward—Perl version.
my @seen;
my @ans;
my $x = 0;
for my $i (keys @ints) {
if ($ints[$i] == -1) {
push @ans, ($x < scalar @seen) ? $seen[$x] : -1;
$x++;
} else {
unshift @seen, $ints[$i];
$x = 0;
}
}
say q{(}, (join q{, }, @ans), q{)};