TL;DR

Here we are with TASK #1 from The Weekly Challenge #196. Enjoy!

The challenge

You are given a list of integers, @list.

Write a script to find out subsequence that respect Pattern 132. Return empty array if none found.

Pattern 132 in a sequence (a[i], a[j], a[k]) such that i < j < k and a[i] < a[k] < a[j].

Example 1

Input:  @list = (3, 1, 4, 2)
Output: (1, 4, 2) respect the Pattern 132.

Example 2

Input: @list = (1, 2, 3, 4)
Output: () since no susbsequence can be found.

Example 3

Input: @list = (1, 3, 2, 4, 6, 5)
Output: (1, 3, 2) if more than one subsequence found then return the first.

Example 4

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

The questions

I guess there are no questions to be asked, apart the old ones I don’t ask any more like what to do if inputs are missing (at least three numbers are needed), or not compliant with the constraints.

The solution

We’ll tackle this in the plain, old brute-forceish way, i.e. a triply nested loop. There’s a little optimization when we look for “high” middle values that should be big enough to be both greater than the “low” counterpart, as well as leave some intermediate space for the “mid” one. Nothing that makes life less complex.

#!/usr/bin/env raku
use v6;
sub MAIN (*@args is copy) {
   @args = 3, 1, 4, 2 unless @args;
   say first-pattern132(@args);
}

sub first-pattern132 (@list) {
   for 0 .. (@list - 3) -> $low {
      for $low + 1 .. (@list - 2) -> $high {
         next if @list[$high] <= @list[$low] - 1;
         for $high + 1 ..^ @list -> $mid {
            return @list[$low, $high, $mid]
               if @list[$low] < @list[$mid] < @list[$high];
         }
      }
   }
   return ();
}

The translation in Perl is straightforward, because I’m not using any Raku magic in the solution above.

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

my @result = first_pattern132(@ARGV ? @ARGV : (3, 1, 4, 2));
say "(@result)";

sub first_pattern132 (@list) {
   for my $low (0 .. (@list - 3)) {
      for my $high ($low + 1 .. (@list - 2)) {
         next if $list[$high] <= $list[$low] - 1;
         for my $mid ($high + 1 .. (@list - 1)) {
            return @list[$low, $high, $mid]
               if $list[$low] < $list[$mid] && $list[$mid] < $list[$high];
         }
      }
   }
   return;
}

This said… all is said, cheers!