| 23 October 2026 | Challenge 396 |
Shaped Finishing
The construction of test data for the J solutions from the examples sometimes was more involved than the solution itself. So I took a look at the provided JSON data. It was not too difficult to extract the test cases into a suitable J format. I switched to the JSON data for the Perl solutions, too. As I do not include the tests in my blog post, these details are visible in the full solutions only.
Task 1: Finishing Order
Submitted by: Mohammad Sajid Anwar
You are given two array 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.
Solution
Suppose the number of friends would be equal to the size of the order array. Then the solution would be the the order array itself.
When there are less friends, we may just pick the elements from the order array that are contained in the friends array, too. This corresponds to the intersection of both lists as sets, preserving the order from the order array.
Perl
Create a hash that has a key for each friend. This is used to filter the order array.
use strict;
use warnings;
use experimental 'signatures';
sub finishing_order ($order, $friends) {
(\my %friends)->@{@$friends} = ();
grep exists $friends{$_}, @$order;
}
See the full solution to task 1.
J
In J this can be done with a tacit verb. It is forced to dyadic use.
NB. select items from 'x' that are contained in 'y'
finishing_order =: [: : e. # [
3 1 4 2 5 finishing_order 1 2 4
1 4 2
See the full solution.
Task 2: Trionic Array
Submitted by: Mohammad Sajid Anwar
You are given an array of integer.
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
Solution
Consider the list \((a_1,\ldots,a_n)\) and find the steps \(s_i = \operatorname{sign}(a_{i+1} - a_i)\).
Then trim adjacent equal values from \(s_i\) to a single value. A trionic array would produce the sequence \((1, -1, 1)\). Actually we may compare the trimmed step array against any target, e.g. \((1, 0, -1)\) for a mesa shaped array.
Perl
Provide the required shape as the first argument to has_shape or use is_trionic to identify a trionic array.
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub has_shape {
my $shape = long shift;
my $arr = long @_;
my $steps = (($arr(1:-1) - $arr(0:-2))->clip(-1, 1)->rle)[1];
0 + ($steps->dim(0) == $shape->dim(0)) && eqvec $steps, $shape;
}
sub is_trionic {
unshift @_, [1, -1, 1];
goto &has_shape;
}
See the full solution to task 2.
J
Building a tacit dyad has_shape from named parts for an arbitrary shape and a monad is_trionic for a trionic shape.
has_shape =: _(adverb define)
NB. sign of the difference between adjacent elements
steps =. 2 (*@(-~)/)\ ]
NB. indicator where y changes value
group_equal =. 1 , 2&(~:/\)
NB. pick first element from groups in y defined by x
first_from =. {.;.1
NB. calculate steps, group by equal values,
NB. pick the first item from each group and
NB. compare to the target array.
[: : ([ ([ -: ] first_from~ group_equal@]) steps) f.
)
is_trionic =: (1 _1 1)&has_shape f.
is_trionic 2 10 3 1 9
1
Check mesa shape:
1 0 _1 has_shape 1 2 2 1
1
See the full solution.