Perl Weekly Challenge: Old King Cole Was A Merry Old Soul

Posted on by

Perl Weekly Challenge 391‘s tasks are “Array Median” and “Arrange Box”.

I was trying really hard to think of some music to go with “array”, “median”, or “arrange”… when a voice in my head hit me with a brick and said “Music. Box. The Musical Box, you bozo.”

So have 10+ minutes of Peter Gabriel-era Genesis to enjoy while you read my solutions to this week’s challenge.

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.

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

Approach

The thing I noted is that we’re given two sorted arrays. So we don’t have to sort them after we merge them; we only need to make sure when we’re merging them we preserve the order. What we’ll do is shift the first item off both lists, and put the smaller on the merged list, un-shifting the larger item back where it came from. We repeat this until one of the lists is empty, and them we just append the remaining list to the merged list. Then we find the middle value in the merged list (or calculate the middle value if the number of elements in the list is even).

Raku

There isn’t much to say about the Raku solution beyond the approach; it hews to the approach pretty closely. Well, besides “append the remaining list to the merged list”; rather than trying to determine which list still has elements in it, I just append both lists to @merged because while only one of them has elements, the other is empty.

Oh, and I use sprintf("%0.1f") to return the median because Raku wants to return an integer if the numeric has no fractional component, and sprintf was the easiest way around that.

sub arrayMedian(@arr1, @arr2) {
  my @merged;
  while (@arr1 && @arr2) {
    my ($v1, $v2) = (@arr1.shift, @arr2.shift);
    if ($v1 < $v2) {
      @merged.push($v1); @arr2.unshift($v2);
    }
    else {
      @merged.push($v2); @arr1.unshift($v1);
    }
  }
  @merged.append(@arr1);
  @merged.append(@arr2);
  my $len = @merged.elems;
  if ($len % 2 == 1) {
    return sprintf("%0.1f", @merged[($len div 2)]);
  }
  my $mid = ($len div 2) - 1;
  return sprintf("%0.1f", (@merged[$mid] + @merged[$mid+1]) / 2);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @arr1 = (2), @arr2 = (4)
Output: 3.0

Example 2:
Input: @arr1 = (1, 2, 3), @arr2 = (7, 8, 9, 10)
Output: 7.0

Example 3:
Input: @arr1 = (), @arr2 = (10, 20, 30, 40)
Output: 25.0

Example 4:
Input: @arr1 = (100), @arr2 = (1, 2, 3, 4, 5, 6, 7)
Output: 4.5

Example 5:
Input: @arr1 = (1, 2, 2), @arr2 = (2, 2, 3)
Output: 2.0

Perl

The Perl solution is a straight-up translation of the Raku solution.

sub arrayMedian($arr1, $arr2) {
  my @merged;
  while (@$arr1 && @$arr2) {
    my ($v1, $v2) = (shift @$arr1, shift @$arr2);
    if ($v1 < $v2) {
      push @merged, $v1; unshift @$arr2, $v2;
    }
    else {
      push @merged, $v2; unshift @$arr1, $v1;
    }
  }
  push @merged, @$arr1;
  push @merged, @$arr2;
  my $len = scalar @merged;
  if ($len % 2 == 1) {
    return sprintf("%0.1f", $merged[int($len/2)]);
  }
  my $mid = int($len/2) - 1;
  return sprintf("%0.1f", ($merged[$mid] + $merged[$mid+1]) / 2);
}

View the entire Perl script for this task on GitHub.

Python

Same with the Python version, except it’s easier to return the median as a float: the division of integers always returns a float. So, in the case where there’s an odd number of elements in the merged list, just divide the median element by 1.

def array_median(arr1, arr2):
  merged = []
  while arr1 and arr2:
    v1, v2 = arr1.pop(0), arr2.pop(0)
    if v1 < v2:
      merged.append(v1)
      arr2.insert(0, v2)
    else:
      merged.append(v2)
      arr1.insert(0, v1)
  merged.extend(arr1)
  merged.extend(arr2)
  l = len(merged)
  if l % 2 == 1:
    return merged[l // 2] / 1 # make it a float
  else:
    mid = (l // 2) - 1
    return (merged[mid] + merged[mid+1]) / 2

View the entire Python script for this task on GitHub.

Elixir

The Elixir solution uses the same “division yielding a float” trick, but it also does a vet Elixir-ish thing by using recursion to merge the lists. Lines 4 & 5 handle appending the list that has remaining elements to the merged list.

def merge([], arr2, merged), do: merged ++ arr2
def merge(arr1, [], merged), do: merged ++ arr1
def merge([v1 | arr1], [v2 | arr2], merged) do
  if v1 < v2 do
    merge(arr1, [v2] ++ arr2, merged ++ [v1])
  else
    merge([v1] ++ arr1, arr2, merged ++ [v2])
  end
end

def array_median(arr1, arr2) do
  merged = merge(arr1, arr2, [])
  len = length(merged)
  if rem(len, 2) == 1 do
    Enum.at(merged, div(len, 2)) / 1
  else
    mid = div(len, 2) - 1
    (Enum.at(merged, mid) + Enum.at(merged, mid+1)) / 2
  end
end

View the entire Elixir script for this task on GitHub.

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.

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]

Approach

The box dimensions are provided in [width, height]; instead of following the examples and sorting the dimensions by just the width, I’m going to sort by width with height as a tiebreaker. This way, smaller boxes will always appear first.

Then we just loop through the list and see what will fit into the next larger box.

Raku

For the sorting, I’m using Raku’s generic “smart” three way comparitor, cmp. Because both values being compared are numeric, it performs a numeric comparison. Then I pull the smallest box off the front of the sorted list, put it in the “stack” of boxes (which is just a list and not a stack because we’re only appending boxes to the end of it and never removing them), then loop through the remaining boxes and see if the largest box in the “stack” (at the end) can fit into the next box on the list. If it can, we append that box to the “stack”. Then we get the next box off the sorted list.

This yields a result where if multiple smaller boxes wouldn’t fit in each other but would fit in a larger box (in example 5, [10, 20], [12, 18], or [15, 10] would each fit in [16, 25], and the example provided by Mohammad Sajid Anwar selects the largest option) it always selects the smallest option.

sub arrangeBoxes(@boxes is copy) {
  @boxes = @boxes.sort({$^a[0] cmp $^b[0] || $^a[1] cmp $^b[1]});
  my @box_stack = @boxes.shift; # put the smallest box in first
  while (my $next = @boxes.shift) {
    my $box = @box_stack[*-1];
    if ($box[0] < $next[0] && $box[1] < $next[1]) {
      @box_stack.push($next);
    }
  }
  return (@box_stack.elems, @box_stack);
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @boxes = ([1, 3], [3, 5], [6, 8], [2, 4])
Output: 4

[1, 3], [2, 4], [3, 5], [6, 8]

Example 2:
Input: @boxes = ([4, 5], [4, 6], [6, 7], [2, 3], [4, 3])
Output: 3

[2, 3], [4, 5], [6, 7]

Example 3:
Input: @boxes = ([5, 5], [5, 5], [5, 5])
Output: 1

[5, 5]

Example 4:
Input: @boxes = ([2, 100], [3, 200], [4, 300], [5, 50], [5, 400])
Output: 4

[2, 100], [3, 200], [4, 300], [5, 400]

Example 5:
Input: @boxes = ([10, 20], [15, 10], [20, 30], [12, 18], [16, 25])
Output: 3

[10, 20], [16, 25], [20, 30]

Perl

However, Perl doesn’t have a smart comparator, so I had to use the numeric spaceship operator, <=>. Had I used Perl’s string cmp operator, the operands would have been coerced to strings first, and we would have wound up with results where “50” was greater than “400”.

sub arrangeBoxes(@boxes) {
  @boxes = sort { $a->[0] <=> $b->[0] ||
                  $a->[1] <=> $b->[1] } @boxes;
  my @box_stack = shift @boxes; # put the smallest box in first
  while (my $next = shift @boxes) {
    my $box = $box_stack[-1];
    if ($box->[0] < $next->[0] && $box->[1] < $next->[1]) {
      push @box_stack, $next;
    }
  }
  return (scalar(@box_stack), @box_stack);
}

View the entire Perl script for this task on GitHub.

Python

For Python, the sorting we wanted was accomplished by providing a key function to the list.sort() method; which used a lambda function that returns first the width then the height of the box for sorting.

def arrange_boxes(boxes):
  boxes.sort(key=lambda k: (k[0], k[1]))
  box_stack = [ boxes.pop(0) ]
  while boxes:
    next = boxes.pop(0)
    box  = box_stack[-1]
    if box[0] < next[0] and box[1] < next[1]:
      box_stack.append(next)
  return len(box_stack), box_stack

View the entire Python script for this task on GitHub.

Elixir

And in Elixir I’m using the capture operator & to pass an anonymous function to Enum.sort/2. I probably could have used Enum.reduce/3 to loop over the sorted boxes, but I liked the idea of using recursion.

def box_smaller(a, b), do:
  Enum.at(a,0) < Enum.at(b,0) and Enum.at(a,1) < Enum.at(b,1)

def arrange_boxes([], box_stack), do:
  { length(box_stack), box_stack }

def arrange_boxes([next | rest], box_stack) do
  box = List.last(box_stack)
  if box_smaller(box, next) do
    arrange_boxes(rest, box_stack ++ [next])
  else
    arrange_boxes(rest, box_stack)
  end
end

def arrange_boxes(boxes) do
  boxes = Enum.sort(boxes, &(
    Enum.at(&1, 0) < Enum.at(&2, 0) or
    Enum.at(&1, 1) < Enum.at(&2, 1)
  ))
  {box, boxes} = {hd(boxes), tl(boxes)}
  arrange_boxes(boxes, [box])
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GitHub: https://github.com/packy/perlweeklychallenge-club/tree/challenge-391-packy-anderson/challenge-391/packy-anderson

Leave a Reply