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, appendcountfollowed by the character.
- If
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:
- 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. - Early rejection: If any single stick is strictly longer than
target, or if we have fewer than 4 sticks, return false. - Greedy ordering: Sort the sticks in descending order. Placing longer sticks first drastically reduces the branching factor in the search tree.
- 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)