The Weekly Challenge #296

String Compression • Matchstick Square
Official Challenge • My Solutions on GitHub

Task 1: String Compression

You are given a string of alphabetic characters. Write a script to compress the string using run-length encoding such that consecutive identical characters are replaced by the count followed by the character if the count is greater than 1, or just the character if the count is 1.

Method Explanation

We can compress the string by traversing it with a pointer or two-pointer technique to count consecutive identical characters:

  • Scan through the string while keeping track of the current character and its run count.
  • When the character changes or the end of the string is reached:
    • If count == 1, append only the character to the result.
    • If count > 1, append count followed by the character.

Additionally, for completeness and testing symmetry, we implement the inverse decompression function: parsing integer counts followed by the repeated character.

Perl Implementation

sub compress_string ($chars) {
    ($chars) = $STR_CHECK->($chars);
    my $compressed = '';
    my @chars      = split //, $chars;
    my $i          = 0;
    my $n          = scalar @chars;

    while ( $i < $n ) {
        my current_char = $chars[$i];
        my $count        = 1;
        while ( $i + 1 < $n && $chars[ $i + 1 ] eq $current_char ) {
            $count++;
            $i++;
        }
        if ( $count > 1 ) {
            $compressed .= $count . $current_char;
        }
        else {
            $compressed .= $current_char;
        }
        $i++;
    }
    return $compressed;
}

sub decompress_string ($compressed) {
    ($compressed) = $STR_CHECK->($compressed);
    my $decompressed = '';
    my @chars        = split //, $compressed;
    my $i            = 0;
    my $n            = scalar @chars;

    while ( $i < $n ) {
        if ( $chars[$i] =~ /\d/ ) {
            my $count = '';
            while ( $i < $n && $chars[$i] =~ /\d/ ) {
                $count .= $chars[$i];
                $i++;
            }
            my $char = $chars[$i];
            $decompressed .= $char x $count;
            $i++;
        }
        else {
            $decompressed .= $chars[$i];
            $i++;
        }
    }
    return $decompressed;
}

Python Implementation

def compress_string(chars: str) -> str:
    """Compress the input string using run-length encoding."""
    compressed = ""
    n = len(chars)
    i = 0
    while i < n:
        current_char = chars[i]
        count = 1
        while i + 1 < n and chars[i + 1] == current_char:
            count += 1
            i += 1
        if count > 1:
            compressed += f"{count}{current_char}"
        else:
            compressed += current_char
        i += 1
    return compressed


def decompress_string(compressed: str) -> str:
    """Decompress the compressed string back to its original form."""
    decompressed = ""
    n = len(compressed)
    i = 0
    while i < n:
        if compressed[i].isdigit():
            count = ""
            while i < n and compressed[i].isdigit():
                count += compressed[i]
                i += 1
            char = compressed[i]
            decompressed += char * int(count)
            i += 1
        else:
            decompressed += compressed[i]
            i += 1
    return decompressed

Task 2: Matchstick Square

You are given an array of integers representing stick lengths. Write a script to determine if it is possible to form a square using all sticks, where each side of the square is formed by combining one or more sticks.

Method Explanation

This problem is an instance of the classic partition problem (specifically $k$-partition where $k = 4$). We can solve it efficiently using depth-first search (DFS) with backtracking and greedy pruning:

  1. Divisibility check: If the sum of all sticks is not divisible by 4, it is impossible to form a square. Let the target side length be target = sum / 4.
  2. Early rejection: If any single stick is strictly longer than target, or if we have fewer than 4 sticks, return false.
  3. Greedy ordering: Sort the sticks in descending order. Placing longer sticks first drastically reduces the branching factor in the search tree.
  4. DFS and symmetry pruning: Maintain an array of 4 side totals. For the current stick, attempt to add it to each side that does not exceed target. If a side has a sum of 0 and the current stick fails to lead to a solution on that side, there is no need to try other empty sides at this depth level (as they are identical).

Perl Implementation

sub can_form_square ($sticks_ref) {
    ($sticks_ref) = $INTS_CHECK->($sticks_ref);
    my @sticks = @$sticks_ref;
    return 'false' if @sticks < 4;

    my $total_length = 0;
    $total_length += $_ for @sticks;

    return 'false' if $total_length % 4 != 0;

    my $side_length = $total_length / 4;

    @sticks = sort { $b <=> $a } @sticks;

    return 'false' if $sticks[0] > $side_length;

    my @sides = ( 0, 0, 0, 0 );
    return _dfs( \@sticks, 0, \@sides, $side_length ) ? 'true' : 'false';
}

sub _dfs ( $sticks_ref, $index, $sides_ref, $target ) {
    if ( $index == @$sticks_ref ) {
        for my $side (@$sides_ref) {
            return 0 if $side != $target;
        }
        return 1;
    }

    my $stick = $sticks_ref->[$index];
    for my $i ( 0 .. 3 ) {
        if ( $sides_ref->[$i] + $stick <= $target ) {
            $sides_ref->[$i] += $stick;
            if ( _dfs( $sticks_ref, $index + 1, $sides_ref, $target ) ) {
                return 1;
            }
            $sides_ref->[$i] -= $stick;
        }

        if ( $sides_ref->[$i] == 0 ) {
            last;
        }
    }
    return 0;
}

Python Implementation

def can_form_square(nums: Sequence[int]) -> bool:
    """Determine if it is possible to form a square using all sticks."""
    if len(nums) < 4:
        return False

    total_length = sum(nums)
    if total_length % 4 != 0:
        return False

    target_side_length = total_length // 4
    sticks = sorted(nums, reverse=True)

    if sticks[0] > target_side_length:
        return False

    sides = [0] * 4

    def dfs(index: int) -> bool:
        if index == len(sticks):
            return all(side == target_side_length for side in sides)
        for i in range(4):
            if sides[i] + sticks[index] <= target_side_length:
                sides[i] += sticks[index]
                if dfs(index + 1):
                    return True
                sides[i] -= sticks[index]
            if sides[i] == 0:
                break
        return False

    return dfs(0)