Perl Weekly Challenge 354 - Minimum Absolute Difference and Grid Shifting

Task 1: Min Abs Diff

"Closest Pairs: Finding the Smallest Gaps!"

This week's first task involves finding pairs of elements with the minimum absolute difference. Given an array of distinct integers, we need to find all pairs [a, b] where a < b and b - a equals the minimum absolute difference among all element pairs in the array.

The Strategy: First, we sort the array. The minimum absolute difference must occur between adjacent elements in the sorted array. We find the minimum difference by comparing adjacent elements, then collect all adjacent pairs that achieve this minimum difference. This approach is efficient with O(n log n) time complexity.

Perl Implementation

sub min_abs_diff_pairs ($ints) {
    ($ints) = $LIST_CHECK->($ints);
    return [] if @$ints < 2;

    my @sorted = sort { $a <=> $b } @$ints;
    my $min_diff = undef;

    for my $i ( 1 .. $#sorted ) {
        my $diff = $sorted[$i] - $sorted[ $i - 1 ];
        $min_diff = $diff if !defined($min_diff) || $diff < $min_diff;
    }

    my @pairs;
    for my $i ( 1 .. $#sorted ) {
        my $diff = $sorted[$i] - $sorted[ $i - 1 ];
        push @pairs, [ $sorted[ $i - 1 ], $sorted[$i] ] if $diff == $min_diff;
    }

    return \\@pairs;
}

Python Implementation

def min_abs_diff_pairs(ints: Sequence[int]) -> list[tuple[int, int]]:
    """Return all (a, b) pairs with minimum absolute difference (a < b)."""
    if len(ints) < 2:
        return []

    sorted_ints = sorted(ints)
    min_diff = min(sorted_ints[i] - sorted_ints[i - 1] for i in range(1, len(sorted_ints)))

    return [
        (sorted_ints[i - 1], sorted_ints[i])
        for i in range(1, len(sorted_ints))
        if sorted_ints[i] - sorted_ints[i - 1] == min_diff
    ]

Task 2: Shift Grid

"Circular Shifts: Rotating the Matrix!"

The second task involves shifting an m x n matrix k times. Each shift moves elements according to specific rules: elements move right within their row, last column elements wrap to the next row's first column, and the bottom-right element wraps to the top-left corner.

The Strategy: We can simplify this by flattening the matrix into a 1D array, performing a circular shift, then reshaping back into the matrix. The shift amount is k modulo the total number of elements. We take the last 'shift' elements and move them to the beginning, effectively rotating the array right by 'shift' positions.

Perl Implementation

sub shift_grid ($matrix, $k) {
    ( $matrix, $k ) = $ARGS_CHECK->( $matrix, $k );
    die 'Expected k > 0' if $k <= 0;
    return [] if !@$matrix;

    my $rows = scalar @$matrix;
    my $cols = scalar @{ $matrix->[0] };
    die 'Non-rectangular matrix' if grep { @$_ != $cols } @$matrix;

    my @flat;
    push @flat, @$_ for @$matrix;

    my $len = @flat;
    my $shift = $k % $len;
    my @shifted =
      $shift == 0
      ? @flat
      : ( @flat[ $len - $shift .. $len - 1 ], @flat[ 0 .. $len - $shift - 1 ] );

    my @out;
    for my $r ( 0 .. $rows - 1 ) {
        push @out, [ @shifted[ $r * $cols .. $r * $cols + $cols - 1 ] ];
    }
    return \\@out;
}

Python Implementation

def shift_grid(matrix: Sequence[Sequence[int]], k: int) -> Matrix:
    """Return the matrix shifted k times following the wrap rules."""
    if k <= 0:
        raise ValueError("Expected k > 0")
    if not matrix:
        return []
    rows = len(matrix)
    cols = len(matrix[0])
    if any(len(row) != cols for row in matrix):
        raise ValueError("Non-rectangular matrix")

    flat = [value for row in matrix for value in row]
    length = len(flat)
    shift = k % length
    if shift:
        flat = flat[-shift:] + flat[:-shift]

    return [flat[r * cols : (r + 1) * cols] for r in range(rows)]