PWC 396: Finishing Order, Trionic Array

It's a lovely Saturday morning in Wisconsin, and I feel like writing a few words about Weekly Challenge 396, which I finished earlier this week.

Task 1: Finishing Order

You are given two arrays of integers, @order and @friends. The @order array (size n) contains every integer from 1 to n exactly once. The @friends array contains ID 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.

Analysis

Using small numbers as the participants' identifiers makes this a little more confusing than it needs to be. If we modify it to use strings for participants and friends, it's a little clearer. Example 1 might then look like

• @order = (carol, alice, dave, bob, ed)
• @friends = (alice, bob, dave)
• Output: (alice, dave, bob)

Then it's a litte easier to see that this task amounts to extracting the @friends subset from @order, in the order that they appear.

The @order array is not good for looking up participants; it maps the finishing place to the participant and requires some kind of search. It would be convenient if we had a table that went the other way, from participant to place. If we had a hash table that maps friends to their finishing place, then we could use that to sort the friends array.

Synthesis

sub task($order, $friends)
{
    my $i = 0;
    my %place = map { $_ => $i++ } $order->@*;

    return [ sort { $place{$a} <=> $place{$b} } $friends->@* ];
}

Notes:

• The map statement inverts the @order array and gives us a hash to look up participants. The task has helpfully specified that there are no duplicates, so the 1-to-1 mapping can safely be inverted.
• Now we can sort @friends by their finish order.
• Wrapping the result of the sort in square brackets creates an array reference. I prefer to return references because it avoids data copies.

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

• Example 2:

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

• Example 3:

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

• 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

Analysis

In more intuitive terms, "trionic" seems to mean the array ascends to a peak, comes back down to a valley, and finishes by ascending again. The examples give us some explanatory data, like what to do with repeated values.

One thing we can note is that the array must have a minimum of four elements to form a peak and a valley.

The simplest thing that could work is to scan the array for peaks and valleys and check that there is exactly one of each. So let's do that.

Synthesis

sub task(@arr)
{
    return false if @arr < 4
                 || $arr[0]  >= $arr[1]
                 || $arr[-2] >= $arr[-1];

    my ($peak, $valley) = (0, 0);
    for my $i ( 1 .. $#arr-1 )
    {
        $peak++   if $arr[$i-1] < $arr[$i] && $arr[$i] > $arr[$i+1];
        $valley++ if $arr[$i-1] > $arr[$i] && $arr[$i] < $arr[$i+1];
    }
    return $peak == 1 && $valley == 1;
}

Notes:

• We start by eliminating some easy cases. As noted, there must be at least four elements. Also, it must start and end with an ascending pair.
• The meat of the function is to check each point to see if it's an inflection. Our for loop indexes inside the ends of the array, so that when we add or subtract 1 from $i we are guaranteed to still be within the bounds of the array.
• I don't see any cleverness that avoids making a pass through the array and checking the slope. There might be other ways to encode that information -- ascending as 1, descending as -1; or 'U' and 'D' as strings -- and therefore finding peaks and valleys could be done as array reductions or regular expression matches. But I'm not seeing that as more efficient or clearer, so let's not.
• There might be an optimization to leave the loop early as soon as $peak or $valley exceeds 1, but the test for the condition at every point might cost as more in execution than simply finishing the loop. It would depend on the data. If the arrays were typically long and irregular so that very few of them are trionic, it might be worth it.