RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a median calculation and box fitting. (Note that this ends today.)

Task 1: Array Median

You are given two sorted arrays.

Write a script to merge the two given sorted arrays and return the median of the merged array.

I suppose one could take advantage of the arrays being sorted (essentially doing the last pass of a merge sort), but it's easier coding just to concatenate them and sort them again. JavaScript:

function arraymedian(a, b) {

Build the concatenated array.

    let nn = a;
    for (let n of b) {
        nn.push(n);
    }

Sort it.

    nn.sort(function(a, b) {return a-b});

Take half the length.

    const i = Math.floor(nn.length / 2);

If the length is even, take the arithmetic mean of the central two items.

    if (nn.length % 2 == 0) {
        return (nn[i - 1] + nn[i]) / 2.0;

Otherwise, take the central item. } else { return nn[i]; } }

(Of course languages with types need a floating point conversion.)

Task 2: Arrange Box

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.

The first step for me was to sort the inputs - not only by height as in the examples, but so that a later entry will never fit inside an earlier one (i.e. at least one of its dimensions is the same or larger than that dimension in the earlier entry). Many of the languages can do this automatically, but in Raku for example I need to make it explicit:

sub arrangebox(@a0) {
    my @a = @a0.sort({
        @^a[0] <=> @^b[0] ||
        @^a[1] <=> @^b[1]
    });

Then I run an exhaustive DFS. Fill the stack with every possible index as a starting point:

    my @stack;
    my $mx = 1;
    for 0 .. @a.end -> $i {
        @stack.push(($i, 1).Array);
    }

Then for each stack entry, try adding each later box, and store it if it fits outside the existing stack. Return the greatest depth seen.

    while (@stack.elems > 0) {
        my ($ix, $pm) = @stack.pop();
        if ($pm > $mx) {
            $mx = $pm;
        }
        for $ix + 1 .. @a.end -> $j {
            if (@a[$ix][0] < @a[$j][0] && @a[$ix][1] < @a[$j][1]) {
                @stack.push(($j, $pm + 1).Array);
            }
        }
    }
    $mx;
}

There's probably a more efficient way of doing this.

Full code in all tagged languages is on codeberg.