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!

Comments? Octodon, , GitHub, Reddit, or drop me a line!