Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

Advent of Code - 2022

This is a solution to Day 13 of Advent of Code 2022.

Day 13 - Distress Signal

You climb the hill and again try contacting the Elves. However, you instead receive a signal you weren't expecting: a distress signal.

Your handheld device must still not be working properly; the packets from the distress signal got decoded out of order. You'll need to re-order the list of received packets (your puzzle input) to decode the message.

Your list consists of pairs of packets; pairs are separated by a blank line. You need to identify how many pairs of packets are in the right order.

For example:

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

Packet data consists of lists and integers. Each list starts with [, ends with ], and contains zero or more comma-separated values (either integers or other lists). Each packet is always a list and appears on its own line.

When comparing two values, the first value is called left and the second value is called right. Then:

  • If both values are integers, the lower integer should come first. If the left integer is lower than the right integer, the inputs are in the right order. If the left integer is higher than the right integer, the inputs are not in the right order. Otherwise, the inputs are the same integer; continue checking the next part of the input.
  • If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.
  • If exactly one value is an integer, convert the integer to a list which contains that integer as its only value, then retry the comparison. For example, if comparing [0,0,0] and 2, convert the right value to [2] (a list containing 2); the result is then found by instead comparing [0,0,0] and [2].

Using these rules, you can determine which of the pairs in the example are in the right order:

== Pair 1 ==
- Compare [1,1,3,1,1] vs [1,1,5,1,1]
 - Compare 1 vs 1
 - Compare 1 vs 1
 - Compare 3 vs 5
   - Left side is smaller, so inputs are in the right order

== Pair 2 ==
- Compare [[1],[2,3,4]] vs [[1],4]
 - Compare [1] vs [1]
   - Compare 1 vs 1
 - Compare [2,3,4] vs 4
   - Mixed types; convert right to [4] and retry comparison
   - Compare [2,3,4] vs [4]
     - Compare 2 vs 4
       - Left side is smaller, so inputs are in the right order

== Pair 3 ==
- Compare [9] vs [[8,7,6]]
 - Compare 9 vs [8,7,6]
   - Mixed types; convert left to [9] and retry comparison
   - Compare [9] vs [8,7,6]
     - Compare 9 vs 8
       - Right side is smaller, so inputs are not in the right order

== Pair 4 ==
- Compare [[4,4],4,4] vs [[4,4],4,4,4]
 - Compare [4,4] vs [4,4]
   - Compare 4 vs 4
   - Compare 4 vs 4
 - Compare 4 vs 4
 - Compare 4 vs 4
 - Left side ran out of items, so inputs are in the right order

== Pair 5 ==
- Compare [7,7,7,7] vs [7,7,7]
 - Compare 7 vs 7
 - Compare 7 vs 7
 - Compare 7 vs 7
 - Right side ran out of items, so inputs are not in the right order

== Pair 6 ==
- Compare [] vs [3]
 - Left side ran out of items, so inputs are in the right order

== Pair 7 ==
- Compare [[[]]] vs [[]]
 - Compare [[]] vs []
   - Right side ran out of items, so inputs are not in the right order

== Pair 8 ==
- Compare [1,[2,[3,[4,[5,6,7]]]],8,9] vs [1,[2,[3,[4,[5,6,0]]]],8,9]
 - Compare 1 vs 1
 - Compare [2,[3,[4,[5,6,7]]]] vs [2,[3,[4,[5,6,0]]]]
   - Compare 2 vs 2
   - Compare [3,[4,[5,6,7]]] vs [3,[4,[5,6,0]]]
     - Compare 3 vs 3
     - Compare [4,[5,6,7]] vs [4,[5,6,0]]
       - Compare 4 vs 4
       - Compare [5,6,7] vs [5,6,0]
         - Compare 5 vs 5
         - Compare 6 vs 6
         - Compare 7 vs 0
           - Right side is smaller, so inputs are not in the right order

What are the indices of the pairs that are already in the right order? (The first pair has index 1, the second pair has index 2, and so on.) In the above example, the pairs in the right order are 1, 2, 4, and 6; the sum of these indices is 13.

Determine which pairs of packets are already in the right order. What is the sum of the indices of those pairs?

Read input

Our input today consists of multiple pairs of valid JSON arrays. So first I read each section (my read_multisection_input kinda broke at some point and I'm afraid to touch it because I don't remember which of this year's solutions broke it) and then parse them as JSON into pairs.

from utils import read_multisection_input
import json

def transformer(section):
    lines = section.split('\n')
    return [json.loads(line) for line in lines]

sections = read_multisection_input(13, str)
pairs = [transformer(section) for section in sections]

Part 1

First, we need a compare function. As you can maybe see from the docstring, I built this in a very TDD-manner and that was a blessing since it helped me increase the complexity little by little without having to worry if everything was still working correctly. Especially because my solution is recursive and if you've been following along, that's a challenge for me.

I started with the basic rules provided by the instruction, then followed them with tests for the example input and once everything passed, I was good to go.

Originally, my part 1 compare function returned True/False/None (probably should have realized at that point that an integer solution was the way to go). When I learned about part 2, I refactored it to function as a proper compare function.

Originally I handled the "unequal lengths" case with catching an IndexError and in that case, comparing the lengths of the two lists. But I then refactored it to use itertools.zip_longest with fillvalue=None so I can just check if either element in pair is None and act accordingly.

How do compare functions work?

A compare function (I guess in most languages?) work in a way that it takes two inputs, in this case left and right and returns a negative number if left is smaller, a positive number if right is smaller and 0 if they are equal.

With integers here (either number itself or length of a list), we can just do subtract operations. That cleans up that code a lot. I used to have if/elif/else cases in the original solution where I now have a single subtract.

Test-Driven Development

Today is a good day to talk about test-driven development. It's hard to see from the output alone that it is indeed what I have done but I use it especially with these kind of cases: rather small function with potentially lots of complexity hidden inside.

In TDD, you first create a test case (I use doctest here but there are other options too), fail it, then make it pass and then refactor.

For example, I started by defining that my compare function with inputs 1 and 2 would return -1 (actually, when I started, it return True and then later refactored to this). I would then implement the function body as something that makes it work (for example, if left < right: return True). Some purists would argue that just returning True would be the right approach but I'm okay with skipping steps in a case like this where I know what direction we're going.

I then added the second case, made that work and refactored the code. Next case, make it work, make it pretty. And continue until every case you have passes.

I don't practice TDD religiously but I tend to use it for more complex functions in Advent of Code (and occasionally in real life too) and really like it. It helps me get to the right result one small step at the time.

And once everything works, you have the test cases so doing bigger refactorings is safe(r) too.

Bring in the walrus :=

On my latest refactoring of this code, I got to use Python's walrus operator (:=) for the first time. Walrus operator got added to Python in 3.8 but I've never been to keen on assigning in if statements. I decided to give it a try finally today.

Most importantly, it's called walrus operator because := looks a bit like walrus.

Secondly, the way it works is that it allows you to assign a value inside an if (or while) statement and then it uses that value in the comparison.

Effectively, it allows you to do this:

res = compare(l, r)
if res != 0:
    return res

in more compact way:

if (res := compare(l, r)) != 0:
    return res

The "What's New in Python 3.8" document makes a good note about walrus:

Try to limit use of the walrus operator to clean cases that reduce complexity and improve readability.

I'm not sure if my use of walrus today improved the readability of my code. I guess it's a matter of how used to the operator you are and how much you like assigning in if conditions.

I used it here because I wanted to learn it and get more comfortable with something that's been in the language for over 3 years already (oh how time flies).

Solution

from itertools import zip_longest

def compare(left, right):
    """
    >>> compare(1, 2)
    -1
    >>> compare(2, 1)
    1
    >>> compare([2, 2], [2, 1])
    1
    >>> compare([1, 1], [1, 2])
    -1
    >>> compare([1], [1, 2])
    -1
    >>> compare([1, 2], [1])
    1
    >>> compare(1, [2])
    -1
    >>> compare([1], 2)
    -1
    >>> compare(2, [1])
    1
    >>> compare([2], 1)
    1
    >>> compare([1,1,3,1,1], [1,1,5,1,1])
    -2
    >>> compare([[1],[2,3,4]], [[1],4])
    -2
    >>> compare([9], [[8,7,6]])
    1
    >>> compare([[4,4],4,4], [[4,4],4,4,4])
    -1
    >>> compare([7,7,7,7], [7,7,7])
    1
    >>> compare([], [3])
    -1
    >>> compare([[[]]], [[]])
    1
    >>> compare([1,[2,[3,[4,[5,6,7]]]],8,9], [1,[2,[3,[4,[5,6,0]]]],8,9])
    7
    """
    match (left, right):
        case int(left), int(right):
            return left - right
        case int(left), list(right):
            return compare([left], right)
        case list(left), int(right):
            return compare(left, [right])
        case None, right:
            return -1
        case left, None:
            return 1
        case list(left), list(right):
            for l, r in zip_longest(left, right, fillvalue=None):
                if (res := compare(l, r)) != 0:
                    return res
            return 0
results = [compare(*pair) for pair in pairs]
sum_of_indices = sum(i+1 for i, res in enumerate(results) if res < 0)

print(f'Part 1: {sum_of_indices}')
assert sum_of_indices == 6235

Part 2

Now, you just need to put all of the packets in the right order. Disregard the blank lines in your list of received packets.

The distress signal protocol also requires that you include two additional divider packets:

[[2]]
[[6]]

Using the same rules as before, organize all packets - the ones in your list of received packets as well as the two divider packets - into the correct order.

For the example above, the result of putting the packets in the correct order is:

[]
[[]]
[[[]]]
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[1,[2,[3,[4,[5,6,0]]]],8,9]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[[1],4]
[[2]]
[3]
[[4,4],4,4]
[[4,4],4,4,4]
[[6]]
[7,7,7]
[7,7,7,7]
[[8,7,6]]
[9]

Afterward, locate the divider packets. To find the decoder key for this distress signal, you need to determine the indices of the two divider packets and multiply them together. (The first packet is at index 1, the second packet is at index 2, and so on.) In this example, the divider packets are 10th and 14th, and so the decoder key is 140.

Organize all of the packets into the correct order. What is the decoder key for the distress signal?

For the second part, I created a function that combines all the pairs into a single list and adds our dividers.

Then, using functools.cmp_to_key, I used my custom compare function to sort the values.

from functools import cmp_to_key

DIVIDER_1 = [[2]]
DIVIDER_2 = [[6]]

def create_signal_list(pairs):
    all_signals = [DIVIDER_1, DIVIDER_2]
    for a, b in pairs:
        all_signals.append(a)
        all_signals.append(b)
    return all_signals

correct_signals = sorted(create_signal_list(pairs), key=cmp_to_key(compare))

decoder_key = (correct_signals.index(DIVIDER_1) + 1) * (correct_signals.index(DIVIDER_2) + 1)

print(f'Part 2: {decoder_key}')
assert decoder_key == 22866