| 04 October 2026 | Challenge 391 |
Boxed Medians
Task 1: Array Median
Submitted by: Mohammad Sajid Anwar
You are given two sorted arrays.
Write a script to merge the two given sorted arrays and return the median of the merged array.
Example 1
Input: @arr1 = (2), @arr2 = (4)
Output: 3.0
Merged array: (2,4)
Median: (2+4)/2 => 3
Example 2
Input: @arr1 = (1,2,3), @arr2 = (7,8,9,10)
Output: 7.0
Merged array: (1,2,3,7,8,9,10)
Length of merged array is 7, the 4th element is 7.
Example 3
Input: @arr1 = (), @arr2 = (10,20,30,40)
Output: 25.0
Merged array: (10,20,30,40)
Median: (20+30)/2 => 25
Example 4
Input: @arr1 = (100), @arr2 = (1,2,3,4,5,6,7)
Output: 4.5
Merged array: (1,2,3,4,5,6,7,100)
Median: (4+5)/2 => 4.5
Example 5
Input: @arr1 = (1,2,2), @arr2 = (2,2,3)
Output: 2.0
Merged array: (1,2,2,2,2,3)
Median: (2+2)/2 => 2
Solution
The calculation of the median may be unified for odd- and even-sized lists \((l_1,\ldots,l_n)\) by calculating the median as the mean of the two “middle” elemets
\[m = \frac{l_{i_1} + l_{i_2}}{2}\]where
\[\begin{align*} i_1 &= \Big\lfloor \frac{n + 1}{2} \Big\rfloor \\ i_2 &= \Big\lceil \frac{n + 1}{2} \Big\rceil \end{align*}\]For odd-sized lists we have \(i_1 = i_2\).
Furthermore, the indices \(i_1\) and \(i_2\) are known before the two lists are merged and therefore the merge process may be aborted when \(l_{i_2}\) has been found.
use strict;
use warnings;
use POSIX 'Inf';
sub array_median ($arr1, $arr2) {
my @arr1 = @$arr1;
my @arr2 = @$arr2;
my $i1 = int((@arr1 + @arr2 - 1) / 2);
my $i2 = int((@arr1 + @arr2) / 2);
my @merge;
while ($#merge < $i2) {
push @merge,
($arr1[0] // Inf) <= ($arr2[0] // Inf) ?
shift @arr1 : shift @arr2;
}
($merge[$i1] + $merge[$i2]) / 2;
}
See the full solution to task 1.
Task 2: Arrange Box
Submitted by: Mohammad Sajid Anwar
You are given an array of box dimensions.
Write a script to determine the maximum number of these boxes that can fit inside each other in a single stack. For a box to fit inside another, it must be smaller in both dimensions.
Example 1
Input: @boxes = ([1, 3], [3, 5], [6, 8], [2, 4])
Output: 4
Sort by width ascending: ([1, 3], [2, 4], [3, 5], [6, 8])
Extract heights: [3, 4, 5, 8]
[1, 3] -> [2, 4] -> [3, 5] -> [6, 8]
Example 2
Input: @boxes = ([4, 5], [4, 6], [6, 7], [2, 3], [4, 3])
Output: 3
Sort by width ascending: ([2, 3], [4, 6], [4, 5], [4, 3], [6, 7])
Extract heights: (3, 6, 5, 3, 7)
[2, 3] -> [4, 5] -> [6, 7]
Example 3
Input: @boxes = ([5, 5], [5, 5], [5, 5])
Output: 1
Sort by width ascending: ([5, 5], [5, 5], [5, 5])
Extract heights: (5, 5, 5)
[5, 5]
Example 4
Input: @boxes = ([2, 100], [3, 200], [4, 300], [5, 50], [5, 400])
Output: 4
Sort by width ascending: ([2, 100], [3, 200], [4, 300], [5, 400], [5, 50])
Extract heights: (100, 200, 300, 400, 50)
[2, 100] -> [3, 200] -> [4, 300] -> [5, 400]
Example 5
Input: @boxes = ([10, 20], [15, 10], [20, 30], [12, 18], [16, 25])
Output: 3
Sort by width ascending: ([10, 20], [12, 18], [15, 10], [16, 25], [20, 30])
Extract heights: (20, 18, 10, 25, 30)
[15, 10] -> [16, 25] -> [20, 30]
Solution
The boxes may be taken as the vertices of a directed graph. Two vertices \(i, j\) are connected with an edge \((i, j)\) when box \(i\) fits into box \(j\).
The longest path in this graph corresponds to the largest stack of boxes. As the graph is cycle-free, each walk is a path.
Consider the adjacency matrix \(A = (a_{ij})\) where \(a_{ij} = 1\) if \(i\) and \(j\) are connected with a directed edge \((i, j)\) and \(a_{ij} = 0\) otherwise.
The \(n\)-th power of the adjacency matrix \(A^n = (a_{ij}^{(n)})\) can be interpreted as follows:
\(a_{ij}^{(n)}\) specifies the number of walks starting at \(i\), ending in \(j\) and having a length of exactly \(n\).
The largest power \(n\) where \(A^n\) is not the zero-matrix therefore gives the length of the longest walk / path in the graph.
Perl
This solution works for any number of dimensions.
use strict;
use warnings;
use PDL;
use PDL::MatrixOps;
sub arrange_box {
my $rect = long @_;
my $adj = ($rect->dummy(1) < $rect)->andover;
my $adjn = identity $adj;
my $i = 0;
$i++ while ($adjn x= $adj)->any;
$i + 1;
}
See the full solution to task 2.
J
arrange_box =: _(adverb define)
fits =. *./@:<"1
mult =. +/ . *
#@(mult^:a:~)@(fits/~) f. : [:
)
arrange_box (4 5), (4 6), (6 7), (2 3),: (4 3)
3
Like the Perl solution, this works for any number of dimensions. If we do not want to just stack the boxes but want one box to completely fit in another:
arrange_box (1 1 1), (2 2 2), (4 4 4),: (3 3 4)
3
See the full solution.