Perl Weekly Challenge 344 - Array Form Compute and Array Formation

Task 1: Array Form Compute

"Adding Digits Like a Pro: Big Integer in Disguise!"

Given an array of digits representing a number (most significant digit first) and an integer x, add x to the number and return the result as an array of digits.

The Strategy: Process digits from right to left, adding x as the carry. For each position, compute sum = carry + digit, store sum % 10 as the result, and carry = sum / 10. Continue while there are digits remaining or carry is non-zero. This naturally handles arbitrarily large arrays.

Perl Implementation

sub array_form_compute ( $digits_ref, $x ) {
    my @digits = $digits_ref->@*;
    my @result;
    my $index = $#digits;
    my $carry = $x;

    while ( $index >= 0 || $carry > 0 ) {
        my $sum = $carry;
        if ( $index >= 0 ) {
            $sum += $digits[$index];
            $index--;
        }

        unshift @result, $sum % 10;
        $carry = int( $sum / 10 );
    }

    return @result ? @result : (0);
}

Python Implementation

def array_form_compute(digits: list[int], x: int) -> list[int]:
    """Add integer x to the array-form representation of a number."""
    result = []
    index = len(digits) - 1
    carry = x

    while index >= 0 or carry > 0:
        total = carry
        if index >= 0:
            total += digits[index]
            index -= 1

        result.append(total % 10)
        carry = total // 10

    return list(reversed(result)) if result else [0]

Task 2: Array Formation

"Puzzle Pieces: Can You Assemble the Target?"

Given a list of subarrays and a target array, determine whether the target can be formed by concatenating the subarrays in some order without changing their internal elements.

The Strategy: Greedily match from left to right. At each position in the target, find an unused subarray whose first element matches the current target element and whose entire sequence fits. If matched, advance the position and mark the subarray as used. If no subarray fits, return false.

Perl Implementation

sub array_formation ( $source_ref, $target_ref ) {
    my @source        = $source_ref->@*;
    my @target        = $target_ref->@*;
    my $target_length = @target;
    my @used          = (0) x @source;
    my $index         = 0;

    while ( $index < $target_length ) {
        my $matched = 0;

        for my $i ( 0 .. $#source ) {
            next if $used[$i];
            my @piece = $source[$i]->@*;
            next unless @piece;
            next unless $piece[0] == $target[$index];

            my $len = @piece;
            next if $index + $len > $target_length;

            my $fits = 1;
            for my $offset ( 0 .. $len - 1 ) {
                if ( $piece[$offset] != $target[ $index + $offset ] ) {
                    $fits = 0;
                    last;
                }
            }

            next unless $fits;
            $used[$i] = 1;
            $index += $len;
            $matched = 1;
            last;
        }

        return 'false' unless $matched;
    }

    return 'true';
}

Python Implementation

def array_formation(source: list[list[int]], target: list[int]) -> str:
    """Return 'true' if target can be assembled from source subarrays."""
    used = [False] * len(source)
    index = 0

    while index < len(target):
        matched = False
        for i, piece in enumerate(source):
            if used[i] or not piece:
                continue
            if piece[0] != target[index]:
                continue
            if index + len(piece) > len(target):
                continue
            if target[index:index + len(piece)] != piece:
                continue

            used[i] = True
            index += len(piece)
            matched = True
            break

        if not matched:
            return "false"

    return "true"