Robbie Hatley’s Solutions, in Perl, for The Weekly Challenge #391 (“Array Median” and “Arrange Box”)

For those not familiar with "The Weekly Challenge", it is a weekly programming puzzle with two parts, with a new pair of tasks each Monday. You can find it here: The Weekly Challenge

The Weekly Challenge for the week of 2026-09-14 through 2026-09-20 is #391.

The tasks for challenge #391 are as follows:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 391-1: Array Median
Submitted by: Mohammad Sajid Anwar
You are given two sorted arrays of numbers. Write a script to
merge the two given sorted arrays and return the median of the
merged array.

"Merging" is just "my @a3 = sort {$a<=>$b} (@$a1, @$a2);". (Merge Sort won't work, because the problem doesn't state whether the arrays are increasing, decreasing, or going in opposite directions. So I force increasing.)

"Median" depends on parity. For an odd number of elements, the median is the middle element. For an even number of elements, the median is one half of the sum of the two middle elements.

Robbie Hatley's Perl Solution to The Weekly Challenge 391-1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Task 391-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.

To solve this, I first needed to find a nesting algorithm. And I found one. It revolves around sorting the boxes ascending-by-width then descending-by-depth for equal width. If one then extracts the depths, any strictly-increasing subsequences within the depths are associated with box sequences which nest. Hence the length of the longest strictly-increasing subsequence of the sequence of depths is the maximum number of boxes which can be nested.

So then I needed to find an algorithm for computing "Length Of Longest Strictly-Increasing Subsequence" (or "LOLSIS" for short) of any finite sequence of integers. And I found several.

The simplest approach is to generate all subsequences, discard the ones which are not strictly-increasing, and note the length of the longest of the remainder. This works and is conceptually simple, but has exponential complexity.

More-efficient is the method of keeping track of "length of longest strictly-increasing subsequence ending HERE" at each point in the sequence. This has quadratic complexity.

But I eventually settled on a different algorithm, the "least tails" method. This method keeps an array "@tails" such that $tails[$i] = "least ending value (tail) seen so far for strictly-increasing subsequences of length $i+1". At first I felt disinclined to also provide a binary search; but in the end I figured that since I've already gone through the hassle of implementing an exceedingly-non-intuitive algoritm, I might as well take it all the way and make a version which has O(n log n) complexity.

Robbie Hatley's Perl Solution to The Weekly Challenge 391-2

That's it for challenge 391; see you on challenge 392!