Matchstick compression

Weekly Challenge 296

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. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: String Compression

Task

You are given a string of alphabetic characters, $chars.

Write a script to compress the string with run-length encoding, as shown in the examples.

A compressed unit can be either a single character or a count followed by a character.

BONUS: Write a decompression function.

My solution

Thanks to the power of regular expressions, this is a pretty straight forward task. Both Python and Perl allow the replacement value to be a function. Therefore I have a function called sc that will convert multiple letters into a number and the letter. For example if the input was aaa, it would return 3a.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

Then it is a matter of calling this function as required.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])\2+)', sc, s)

The decompress function (Python only) works in a similar fashion. It takes a pattern of a number followed by a letter and changes it to the letter repeated the specified number of occurrences.

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

For execution from the command line, I use the argparse module to see if the --decompress option is specified.

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

Examples

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

Task 2: Matchstick Square

Task

You are given an array of integers, @ints.

Write a script to find if it is possible to make one square using the sticks as in the given array @ints where $ints[ì] is the length of i-th stick.

My solution

This is going to be a little long, so strap yourself in. The first thing I check is the sum of the sticks is divisible by four. If it isn't, there is no possible solution and I can return false

I can also check that no single stick is longer than one side. If this occurs, I also return false.

With these two checks, all the examples would give the correct result. However, it would erroneously report that 4 3 3 3 3 is true when in fact it is not.

Attempt two

Looking at the examples and my own thinking, I thought the solution would be to match a pair of values to match each side. So for the example 3 4 1 4 3 1 we have two pairs of 3 and 1 sticks that makes four. This would solve the 4 3 3 3 3 issue, because three doesn't have a matching one.

But this wouldn't work if the sticks were 4 4 3 1 2 1 1, as one side uses three sticks (one 2 and two 1s)

Attempt three

So my next attempt was a little more complicated, and I thought was a good solution ... until it wasn't. For this attempt, I started with the longest stick. If it wasn't the length of the side, I then took the next longest stick required to complete the side, and repeated until there was no possible solution. Using this method the following solutions were true.

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

I thought this was the solution, until I realised that 9 5 3 1 5 2 2 3 3 3 would not work. First side is 9, next side is 5 3 1, and the third side would fail with 5 3 and no 1.

Attempt four

At this point, I started to wonder if it was even possible to come up with a solution that didn't involve brute force. So I slept on it, scribbled down lots of things in on my tablet (I'm on holiday so can't use my white board), and slept on it again. My conclusion is that using a recursive function is the only solution.

Maybe I'm just overthinking all of this, or maybe there is a real simple solution that I just have thought of (as was the case last week).

The final code

Still reading? Well done :)

For this task, I have a recursive function called make_side. It takes a list (arrayref in Perl) of sticks remaining, and the length required. It then goes though the remaining sticks (highest first). Then one of three things happen:

• If the stick is longer than the required length, I skip it.
• If it is the required length, I return it.
• If it is short, I use it and call the function again to use another stick. The call removes the used stick, and reduces the required length by the length of the used stick.

The function will return a list of the sticks used, or None (undef in Perl) if no valid combination of sticks is found.

def make_side(sticks: list, l: int) -> list:
    pieces = sorted(set(sticks), reverse=True)
    for piece in pieces:
        if piece > l:
            continue

        if piece == l:
            return [piece]

        sticks_copy = sticks.copy()
        sticks_copy.remove(piece)
        result = make_side(sticks_copy, l - piece)
        if result:
            # We have a solution. Send it upstream
            return [piece, *result]

    return False

The final piece of the puzzle, I perform the checks mentioned in the first part (sum is divisible by four, no stick longer than a side), and then call the above function. If that returns None, I return false. If all the sticks are used, I return true.

def matchstick_square(sticks: list) -> str:
    if sum(sticks) % 4:
        return False

    side_length = sum(sticks) // 4

    if any(i > side_length for i in sticks):
        return False

    while sticks:
        side = make_side(sticks, side_length)
        if not side:
            return False
        for stick in side:
            sticks.remove(stick)

    return True

Examples

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

$ ./ch-2.py 2 2 2 4
False

$ ./ch-2.py 2 2 2 2 4
False

$ ./ch-2.py 3 4 1 4 3 1
True

$ ./ch-2.py 9 5 3 1 5 2 2 3 3 3
True