Perl Weekly Challenge: Teach Them How To Say PWC…

Posted on by

With Perl Weekly Challenge 345‘s tasks being “Peak Positions” and “Last Visitor”, I was somewhat at a loss for what to what music to pick. Then I thought about how I haven’t done musical theater in a while, and it came to me: “One Last Time” from Hamilton.

So let’s teach them how to say goodbye with PWC 345…

Task 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)

Approach

This is a single loop through the array, where we compare each element with the elements on either side and skip any that aren’t strictly greater than those elements:

for i := 0 .. length(ints) do
    skip if not ints[i-1] <= ints[i]
    skip if not ints[i+1] <= ints[i]
    push i on result list
done

But then we need to handle either end of the list:

for i := 0 .. length(ints) do
    skip if not (ints[i-1] <= ints[i] or i == 0)
    skip if not (ints[i+1] <= ints[i] or i == length(ints))
    push i on result list
done

Raku

sub peakPositions(@ints) {
  my @peaks;
  for 0..@ints.end -> $i {
    next unless $i == 0         || @ints[$i - 1] <= @ints[$i];
    next unless $i == @ints.end || @ints[$i + 1] <= @ints[$i];
    @peaks.push($i);
  }
  return @peaks;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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)

Perl

sub peakPositions(@ints) {
  my @peaks;
  foreach my $i (0 .. $#ints) {
    next unless $i == 0      || $ints[$i - 1] <= $ints[$i];
    next unless $i == $#ints || $ints[$i + 1] <= $ints[$i];
    push @peaks, $i;
  }
  return @peaks;
}

View the entire Perl script for this task on GitHub.

Python

The thing I need to keep in mind with Python’s range() function is that the list it returns stops one before the end value…

def peak_positions(ints):
  peaks = []
  for i in range(len(ints)):
    if not (i == 0           or ints[i - 1] <= ints[i]):
      continue
    if not (i == len(ints)-1 or ints[i + 1] <= ints[i]):
      continue
    peaks.append(i)
  return peaks

View the entire Python script for this task on GitHub.

Elixir

Elixir doesn’t really have loops, so we need to generate the range of indices (line 16), convert that to a list (line 17), then use the Enum.map_reduce/3 function (line 18) to process each of those indices.

  def reduce_fn(i, {peaks, ints}) do
    cond do
      i != 0 && Enum.at(ints,i-1) > Enum.at(ints,i) ->
        {i, {peaks, ints}}
      i != length(ints) && Enum.at(ints,i+1) > Enum.at(ints,i) ->
        {i, {peaks, ints}}
      true ->
        {i, {peaks ++ [i], ints}}
    end
  end

  def peak_positions(ints) do
    {_, {peaks, _}} = 0..length(ints)-1
      |> Enum.to_list
      |> Enum.map_reduce({[], ints}, &reduce_fn/2)
    peaks
  end

View the entire Elixir script for this task on GitHub.

❝ Though, in reviewing the incidents of my administration, I am unconscious of intentional error, I am nevertheless too sensible of my defects not to think it probable that I may have committed many errors.❞

I’m hoping that I’m not making an error in task 2.

Task 2: Last Visitor

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.

Example 1

Input: @ints = (5, -1, -1)
Output: (5, -1)

@seen = (5)
First  -1: @ans = (5)
Second -1: @ans = (5, -1)

My walk through of algorithm:
@seen = (5)
First  -1: x = 0, push(@ans, @seen[0]), @ans = (5)
Second -1: x = 1, push(@ans, -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)

My walk through of algorithm:
@seen = (3)
@seen = (7, 3)
First  -1: x = 0, push(@ans, @seen[0]), @ans = (7)
Second -1: x = 1, push(@ans, @seen[1]), @ans = (7, 3)
Third  -1: x = 2, push(@ans, -1),       @ans = (7, 3, -1)

Example 3

Input: @ints = (2, -1, 4, -1, -1)
Output: (2, 4, 2)

My walk through of algorithm:
@seen = (2)
First  -1: x = 0, push(@ans, @seen[0]), @ans = (2)
@seen = (4, 2)
Second -1: x = 1, push(@ans, @seen[1]), @ans = (2, 2)
Third  -1: x = 2, push(@ans, -1),       @ans = (2, 2, -1)

Example 4

Input: @ints = (10, 20, -1, 30, -1, -1)
Output: (20, 30, 20)

My walk through of algorithm:
@seen = (10)
@seen = (20, 10)
First  -1: x = 0, push(@ans, @seen[0]), @ans = (20)
@seen = (30, 20, 10)
Second -1: x = 1, push(@ans, @seen[1]), @ans = (20, 20)
Third  -1: x = 2, push(@ans, @seen[2]), @ans = (20, 20, 10)

Example 5

Input: @ints = (-1, -1, 5, -1)
Output: (-1, -1, 5)

My walk through of algorithm:
@seen = ()
First  -1: x = 0, push(@ans, -1), @ans = (-1)
Second -1: x = 1, push(@ans, -1), @ans = (-1, -1)
@seen = (5)
Third  -1: x = 2, push(@ans, -1), @ans = (-1, -1, -1)

Approach

Ok, this challenge seems straightforward, but the provided output for the example doesn’t mesh with the way I’m reading the algorithm, so I’m pushing ahead with my understanding.

What we do is we walk through the values of @ints and build the arrays as directed.

Raku

sub lastVisitor(@ints) {
  my (@seen, @ans);
  my $x = 0;
  for @ints -> $i {
    if ($i > 0) {
      @seen.unshift($i); # insert at front of @seen
    }
    else {
      if ($x < @seen.elems) {   # if $x < len(@seen)
        @ans.push( @seen[$x] ); # append seen[x] to @ans
      }
      else {
        @ans.push( -1 ); # append -1 to @ans
      }
      $x++;
    }
  }
  return @ans;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @ints = (5, -1, -1)
Output: (5, -1)

Example 2:
Input: @ints = (3, 7, -1, -1, -1)
Output: (7, 3, -1)

Example 3:
Input: @ints = (2, -1, 4, -1, -1)
Output: (2, 2, -1)

Example 4:
Input: @ints = (10, 20, -1, 30, -1, -1)
Output: (20, 20, 10)

Example 5:
Input: @ints = (-1, -1, 5, -1)
Output: (-1, -1, -1)

Perl

sub lastVisitor(@ints) {
  my (@seen, @ans);
  my $x = 0;
  foreach my $i ( @ints ) {
    if ($i > 0) {
      unshift @seen, $i; # insert at front of @seen
    }
    else {
      if ($x < @seen) {   # if $x < len(@seen)
        push @ans, $seen[$x]; # append seen[x] to @ans
      }
      else {
         push @ans, -1; # append -1 to @ans
      }
      $x++;
    }
  }
  return @ans;
}

View the entire Perl script for this task on GitHub.

Python

def last_visitor(ints):
  seen = []
  ans = []
  x = 0
  for i in ints:
    if i > 0:
      seen.insert(0, i) # insert at front of @seen
    else:
      if x < len(seen):   # if $x < len(@seen)
        ans.append( seen[x] ) # append seen[x] to @ans
      else:
        ans.append( -1 ) # append -1 to @ans
      x += 1
  return ans

View the entire Python script for this task on GitHub.

Elixir

And rather than a loop, in Elixir we’re using recursion to go through the list of integers.

def last_visitor([], _, ans, _), do: ans

def last_visitor([i | ints], seen, ans, x) do
  {seen, ans, x} = if i > 0 do
    {[i] ++ seen, ans, x} # insert at front of @seen
  else
    if x < length(seen) do # if $x < len(@seen)
      # append seen[x] to @ans
      {seen, ans ++ [Enum.at(seen, x)], x+1}
    else
      {seen, ans ++ [-1], x+1} # append -1 to @ans
    end
  end
  last_visitor(ints, seen, ans, x)
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-345/packy-anderson

Leave a Reply