The Weekly Challenge: Arranging things

Weekly Challenge 391

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

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.

My solution

For input from the command line, I take two strings and find all integer values to create each list.

import re

def main():
    arr1 = [int(i) for i in re.findall(r"\d+", sys.argv[1])]
    arr2 = [int(i) for i in re.findall(r"\d+", sys.argv[2])]
    result = array_median(arr1, arr2)
    print(float(result))

Python has a median function from the statistics module. Therefore the solution is to join the two lists, and return the median.

from statistics import median

def array_median(arr1: list[int], arr2: list[int]) -> float:
    return median(arr1 + arr2)

For the Perl solution, I went old school and wrote a function that sorts the joined array. If there are an odd number of items, it returns the middle number. If there is an even number, it takes the average of the two middle values.

sub main ( $str1, $str2 ) {
    my @arr1 = ( $str1 =~ /(\d+)/g );
    my @arr2 = ( $str2 =~ /(\d+)/g );

    my @sorted_array = sort { $a <=> $b } ( @arr1, @arr2 );
    my $half         = int( $#sorted_array / 2 );
    my $median =
      $#sorted_array % 2
      ? ( $sorted_array[$half] + $sorted_array[ $half + 1 ] ) / 2
      : $sorted_array[$half];

    say sprintf( "%0.1f", $median );
}

Examples

$ ./ch-1.py 2 4
3.0

$ ./ch-1.py "1 2 3" "7 8 9 10"
7.0

$ ./ch-1.py "" "10 20 30 40"
25.0

$ ./ch-1.py 100 "1 2 3 4 5 6 7"
4.5

$ ./ch-1.py "1 2 2" "2 2 3"
2.0

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.

My solution

For the Python solution, I define a dataclass called Box, which stores the width and height of each box. This makes the code easier to understand, as I can use the width and height attributes.

from dataclasses import dataclass

@dataclass
class Box:
    width: int
    height: int

I then create a function called stackable_boxes. Given a tuple of Boxes it determines if they can be arranged correctly. It first checks that the widths and heights of the boxes are unique. It then sorts them by width and ensures the corresponding height is also in ascending order.

def stackable_box(boxes) -> int:
    box_count = len(boxes)
    if len(set(box.width for box in boxes)) != box_count:
        return False
    if len(set(box.height for box in boxes)) != box_count:
        return False

    sorted_boxes = sorted(boxes, key=lambda box: box.width)
    heights = [box.height for box in sorted_boxes]
    return heights == sorted(heights)

The main function starts by converting the boxes into a Box object, if it isn't already. For input from the command line, I take pairs of integers as the dimension of each box.

I then have a loop called length. It starts with the number of boxes, and ends at 2. For each length, I use the combinations function from the itertools module to generate all combinations of the specified number of boxes. I call the stackable_boxes function for each combination, and return the length if the boxes can be arranged. If the loop is exhausted, I return 1.

def arrange_box(*boxes) -> int:
    boxes = [box if isinstance(box, Box) else Box(*box) for box in boxes]
    for length in range(len(boxes), 1, -1):
        for box_set in combinations(boxes, length):
            if stackable_box(box_set):
                return length

    return 1

The Perl solution uses similar logic.

Examples

$ ./ch-2.py 1 3 3 5 6 8 2 4
4

$ ./ch-2.py 4 5 4 6 6 7 2 3 4 3
3

$ ./ch-2.py 5 5 5 5 5 5
1

$ ./ch-2.py 2 100 3 200 4 300 5 50 5 400
4

$ ./ch-2.py 10 20 15 10 20 30 12 18 16 25
3