Perl Weekly Challenge: What do I get out of this?

Posted on by

Perl Weekly Challenge 396‘s tasks are “Finishing Order” and “Trionic Array”.

There isn’t much to go on for music here. There are a couple songs that are about finishing, but the thing that keeps popping into my head is the band New Order. I used “Blue Monday” back in PWC390, so let’s have “Sub-culture” this time.

Task 1: Finishing Order

You are given two arrays of integers, @order and @friends.

The @order (size n) contains every integer from 1 to n exactly once. The @friends contains ID in sorted in strictly increasing order.

Write a script to return the array containing IDs in finishing order.

Example 1

Input: @order = (3, 1, 4, 2, 5)
       @friends = (1, 2, 4)
Output: (1, 4, 2)

ID 1 finished 2nd.
ID 4 finished 3rd.
ID 2 finished 4th.

Example 2

Input: @order = (5, 4, 3, 2, 1)
       @friends = (1, 3, 5)
Output: (5, 3, 1)

ID 5 finished 1st.
ID 3 finished 3rd.
ID 1 finished 5th.

Example 3

Input: @order = (2, 4, 1, 3)
       @friends = (1, 2, 3, 4)
Output: (2, 4, 1, 3)

ID 2 finished 1st.
ID 4 finished 2nd.
ID 1 finished 3rd.
ID 3 finished 4th.

Example 4

Input: @order = (4, 1, 3, 2)
       @friends = (3)
Output: (3)

Example 5

Input: @order = (1, 3, 2, 6, 5, 4)
       @friends = (1, 2, 3)
Output: (1, 3, 2)

ID 1 finished 1st.
ID 3 finished 2nd.
ID 2 finished 3rd.

Approach

At first, I thought I was going to do some kind of schwartzian transform like thing where I built a list of lists which had the array order and then the friend, and then I would filter the array to include only the elements from the friend array, and then I would sort it…

Then I realized the @order array was already sorted. I didn’t need to worry about sorting it, I just needed to pull values out of @order if they were in @friends. It was a simple filtering job.

Raku

sub finishingOrder(@order, @friends) {
  @order.grep({ $_ ~~ any(@friends) });
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @order   = (3, 1, 4, 2, 5)
       @friends = (1, 2, 4)
Output: (1, 4, 2)

Example 2:
Input: @order   = (5, 4, 3, 2, 1)
       @friends = (1, 3, 5)
Output: (5, 3, 1)

Example 3:
Input: @order   = (2, 4, 1, 3)
       @friends = (1, 2, 3, 4)
Output: (2, 4, 1, 3)

Example 4:
Input: @order   = (4, 1, 3, 2)
       @friends = (3)
Output: (3)

Example 5:
Input: @order   = (1, 3, 2, 6, 5, 4)
       @friends = (1, 2, 3)
Output: (1, 3, 2)

Perl

In Perl, because any requires a block where $_ is set, I needed to store the value of $_ being used in the grep in some variable so I could compare them.

use List::AllUtils qw( any );

sub finishingOrder($order, $friends) {
  grep { my $f = $_; any { $f == $_ } @$friends } @$order;
}

View the entire Perl script for this task on GitHub.

Python

def finishing_order(order, friends):
  return [ f for f in order if f in friends ]

View the entire Python script for this task on GitHub.

Elixir

def finishing_order(order, friends) do
  Enum.filter(order, & Enum.member?(friends, &1) )
end

View the entire Elixir script for this task on GitHub.

Task 2: Trionic Array

You are given an array of integers.

Write a script to return true if the given array is Trionic otherwise return false.

An array is trionic if there exist indices 0 < p < q < n − 1 such that arr[0…p] is strictly increasing, arr[p…q] is strictly decreasing, and arr[q…n − 1] is strictly increasing.

Example 1

Input: @arr = (1, 3, 5, 4, 2, 6, 8)
Output: true

Choose p = 2 and q = 4
$arr[0..2] = (1, 3, 5) (strictly increasing)
$arr[2..4] = (5, 4, 2) (strictly decreasing)
$arr[4..6] = (2, 6, 8) (strictly increasing)

Valid indices: 0 < p (2) < q (4) < n-1 (6).

Example 2

Input: @arr = (1, 4, 4, 2, 1, 3, 5)
Output: false

The first segment (1, 4, 4) contains duplicate adjacent values, so it is not strictly increasing.
No valid p and q exist to satisfy all three strictly monotonic conditions.

Example 3

Input: @arr = (2, 10, 3, 1, 9)
Output: true

Choose p = 1 and q = 3.
$arr[0..1] = (2, 10)    (strictly increasing)
$arr[1..3] = (10, 3, 1) (strictly decreasing)
$arr[3..4] = (1, 9)     (strictly increasing)

Example 4

Input: @arr = (1, 2, 3, 4, 3, 2, 1)
Output: false

This is a standard mountain array (strictly increasing, then strictly decreasing).
There is no second valley (q) that transitions back into a strictly increasing third segment before reaching the end of the array.

Example 5

Input: @arr = (1, 3, 6, 4, 2, 7, 8, 4)
Output: false

Approach

To me, this looks like a state machine. We loop over @arr, starting in the arr[0..p] (strictly increasing) state (mode 0), and once we encounter a number that’s lower than the last number, we set the value for p and switch to the arr[p..q] (strictly decreasing) state (mode 1). Then we continue until we encounter a number that’s larger than the last number; at that point, we set q, switch to the arr[q..n-1] state (mode 2), then continue to the end of the array. If we encounter numbers along the way that don’t fit the trionic pattern, we return early with the false result.

Raku

So, first I initialized the mode to be the starting mode (0). Then I loop over the entries in the array using an index (because I want to track where we’re setting $p and $q) starting at the second character and assign variables to $curr and $last (lines 8-9) so I can compare values using names that make sense. Then I check to make sure the last value isn’t the same as the current value, because that’s not allowed in any of the modes. Then I have a given-when block (because I wanted to do something Raku-ish) to test which mode I’m in and take the appropriate steps: skipping ahead to the next value if the values are going in the correct direction, or change to the next state in the machine and set the value for $p or $q accordingly.

sub isTrionic(@arr) {
  my ($p, $q);
  my $mode = 0;
  for 1 .. @arr.end -> $i {
    my $curr = @arr[$i];
    my $last = @arr[$i-1];
    if ($last == $curr) {
      return "false", -1, -1; # no strict increase or decrease
    }
    given $mode {
      when 0 {
        next unless $last > $curr;
        $mode = 1; # proceed to strictly decreasing
        $p = $i - 1;
      }
      when 1 {
        next unless $last < $curr;
        $mode = 2; # proceed to strictly increasing
        $q = $i - 1;
      }
      when 2 {
        next unless $last >= $curr;
        return "false", -1, -1; # no strict increase
      }
    }
  }
  return "false", -1, -1 unless $mode == 2;
  return "true", $p, $q;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @arr = (1, 3, 5, 4, 2, 6, 8)
Output: true

Choose p = 2 and q = 4

Example 2:
Input: @arr = (1, 4, 4, 2, 1, 3, 5)
Output: false

Example 3:
Input: @arr = (2, 10, 3, 1, 9)
Output: true

Choose p = 1 and q = 3

Example 4:
Input: @arr = (1, 2, 3, 4, 3, 2, 1)
Output: false

Example 5:
Input: @arr = (1, 3, 6, 4, 2, 7, 8, 4)
Output: false

Perl

The Perl solution is pretty much exactly like the Raku solution, except I’m using an if-elsif block for testing the state instead of given-when.

sub isTrionic(@arr) {
  my ($p, $q);
  my $mode = 0;
  for my $i (1 .. $#arr) {
    my $curr = $arr[$i];
    my $last = $arr[$i-1];
    if ($last == $curr) {
      return "false", -1, -1; # no strict increase or decrease
    }
    if ($mode == 0) {
      next unless $last > $curr;
      $mode = 1; # proceed to strictly decreasing
      $p = $i - 1;
    }
    elsif ($mode == 1) {
      next unless $last < $curr;
      $mode = 2; # proceed to strictly increasing
      $q = $i - 1;
    }
    elsif ($mode == 2) {
      next unless $last >= $curr;
      return "false", -1, -1; # no strict increase
    }
  }
  return "false", -1, -1 unless $mode == 2;
  return "true", $p, $q;
}

View the entire Perl script for this task on GitHub.

Python

In Python, I ditched the idea of skipping ahead to the next value and just used the if-elif to test whether the numbers were going in the right direction; if they changed, I’d switch mode. This is the shortest of the solutions.

def is_trionic(arr):
  mode = 0
  for i in range(1, len(arr)):
    curr = arr[i]
    last = arr[i-1]
    if last == curr:
      return "false", -1, -1 # no strict increase or decrease
    if mode == 0 and last > curr:
      mode = 1 # proceed to strictly decreasing
      p = i - 1
    elif mode == 1 and last < curr:
      mode = 2 # proceed to strictly increasing
      q = i - 1
    elif mode == 2 and last >= curr:
      return "false", -1, -1 # no strict increase
  if not mode == 2:  return "false", -1, -1
  return "true", p, q

View the entire Python script for this task on GitHub.

Elixir

Because I wanted to be able to jump out of the loop over the array early if I hit a condition that made the array non-trionic, I’m using a Enum.reduce_while/3 call. It lets me return a :cont or :halt atom as well as the accumulator that will abort the loop early.

One irregularity I can’t explain: on line 27, when I was returning {2, p, i-1, curr} like I was in the other three languages, my results were one off:

$ elixir/ch-2.exs | diff - /tmp/ch-2.out
5c5
< Choose p = 3 and q = 4
---
> Choose p = 2 and q = 4
15c15
< Choose p = 2 and q = 3
---
> Choose p = 1 and q = 3

So I returned q as the value i instead of i-1. I’m still not sure why that is happening.

def is_trionic(arr) do
  {mode, p, q} = Enum.reduce_while(
    1 .. length(arr)-1,
    {0, nil, nil},
    fn i, {mode, p, q} ->
      curr = Enum.at(arr, i)
      last = Enum.at(arr, i-1)
      {mode, p, q} = cond do
        last == curr -> {:halt, nil, nil} # no strict inc or dec
        mode == 0 -> cond do
            # proceed to strictly decreasing
            last > curr  -> {1, i-1, q} # set p
            true         -> {mode, p, q} # stay in this state
          end
        mode == 1 -> cond do
            # proceed to strictly increasing
            last > curr  -> {2, p, i} # set q
            true         -> {mode, p, q} # stay in this state
          end
        mode == 2 -> cond do
            last >= curr -> {:halt, nil, nil} # no strict inc
            true         -> {mode, p, q} # stay in this state
          end
        # catch all for errors
        true -> {:halt, nil, nil}
      end
      if mode == :halt do
        {:halt, {:false, nil, nil}}
      else
        {:cont, {mode, p, q}}
      end
    end
  ) # end Enum.reduce_while
  if mode != 2 do
    {"false", nil, nil}
  else
    {"true", p, q}
  end
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/challenge-396-packy-anderson/challenge-396/packy-anderson

Leave a Reply