AoC 2021 Day 18: Pairs of Pairs

Source: Snailfish

Part 1: Given the following definition of Snailfish numbers, add a series of Snailfish numbers and return the magnitude of the result.

  • A Snailfish number is defined as a pair \langle a, b \rangle where a and b can either by integers or nested Snailfish number
  • To add two Snailfish numbers, c + d = \langle c, d \rangle
  • To reduce a Snailfish number to simplest form:
    • If there are any pairs (of integers \langle e, f \rangle ) nested 5+ levels deep, explode the leftmost one
      • e is added to the rightmost node left of the exploded pair (if possible)
      • f is added to the leftmost node right of the exploded pair (if possible)
      • Replace the original pair with a 0 (I missed this for a while…)
    • If there are no such pairs and there is at least one integer g greater than or equal to 10, split it into a pair \langle h, i \rangle such that h = \left \lfloor \frac{g}{2} \right \rfloor, i = \left \lceil \frac{g}{2} \right \rceil .
  • The magnitude of |\langle j, k \rangle| = 3|j|+2|k|

Yeah… that took a bit to figure out.

To just parse the numbers, do addition, and do split, the most natural data structure is going to be a tree:

class Snailfish():
    left: Union[int, 'Snailfish']
    right: Union[int, 'Snailfish']

    def read(text: TextIO) -> Optional[Union[int, 'Snailfish']]:
        '''Read a snailfish from the given filelike object'''

        c =
        while not c.isdigit() and not c in '[':
            c =

        if c == '[':
            left =
            right =

            assert left is not None
            assert right is not None

            return Snailfish(left, right)

        elif c.isdigit():
            the_once_and_future_number = []

            while c.isdigit():
                c =

            assert(c == ',' or c == ']')

            return int(''.join(the_once_and_future_number))

        return None

    def reduce(self) -> 'Snailfish':
        '''Convert this snailfish to minimum form using the result for explosing and splitting.'''

        # TODO

    def magnitude(self) -> int:
        '''Calculate the magnitude of a snailfish number.'''

        def f(sf: Union[int, 'Snailfish']) -> int:
            if isinstance(sf, int):
                return sf
                return 3 * f(sf.left) + 2 * f(sf.right)

        return f(self)

    def __add__(self, other):
        '''Add two Snailfish by making a larger pair and then reducing it.'''

        return Snailfish(self, other).reduce()

    def __repr__(self):
        return f'{{{self.left}, {self.right}}}'

But… it’s really quite tricky to use a tree and deal with exploding. You can probably recur up the tree and back down to find the rightmost left node… but why? Instead, we’re going to swap back and forth to another similar data structure: a depthlist (is there another name for this?). For each leaf node / integer value in the Snailfish tree, represent that number as a pair (value, depth). So

\langle \langle 1, \langle 2, \langle 3, 4 \rangle \rangle \rangle, 5 \rangle would be [(1, 2), (2, 3), (3, 4), (4, 4), (5, 1)].

class Snailfish():

    def to_depthlist(self) -> List[Tuple[int, int]]:
        '''Convert to list of (value, depth).'''

        def g(sf: Union[int, 'Snailfish'], depth: int) -> Generator[Tuple[int, int], None, None]:
            if isinstance(sf, int):
                yield (sf, depth)
                yield from g(sf.left, depth + 1)
                yield from g(sf.right, depth + 1)

        return list(g(self, 0))

Converting back is a bit trickier, but actually similar to parsing (repeatedly combine pairs at the same depth until everything is combined):

class Snailfish():

    def from_depthlist(dls: List[Tuple[int, int]]) -> 'Snailfish':
        '''Convert from a list of (value, depth).'''

        # To make typing happy, copy to a list that can have either
        mixedls: List[Tuple[Union[int, 'Snailfish'], int]] = [
            (value, depth)
            for (value, depth)
            in dls

        while len(mixedls) > 1:
            for index, ((left, left_depth), (right, right_depth)) in enumerate(zip(mixedls, mixedls[1:])):
                if left_depth == right_depth:
                    mixedls[index] = (Snailfish(left, right), left_depth - 1)
                    del mixedls[index+1]


        assert isinstance(mixedls[0][0], Snailfish)
        return mixedls[0][0]

Using this data structure, it’s much easier to deal with explode:

  • Find the first pair of numbers with the same depth (4 in this case) that are deep enough
  • Move the two values over one each
  • Add a 0 at depth-1

And splitting is just as easy:

  • Find the value to split, replace it with two nodes (ceiling and floor of division by 2)
class Snailfish():

    def reduce(self) -> 'Snailfish':
        '''Convert this snailfish to minimum form using the result for explosing and splitting.'''

        # Much easier to work with mutable depthlists...
        dls = self.to_depthlist()

        reducing = True
        while reducing:
            reducing = False
            logging.debug(f'Reducing: dls={dls}, sf={Snailfish.from_depthlist(dls)}')

            # Check for any pairs that needs exploding
            for index, (value, depth) in enumerate(dls):
                if depth > 4 and index < len(dls) - 1 and depth == dls[index + 1][1]:
                    logging.debug(f' - Exploding at {index=} with {value=} and {depth=}')

                    prefix = dls[:index]
                    infix = [(0, depth-1)]
                    suffix = dls[index+2:]

                    # Increase the previous value by one (if it exists)
                    if prefix:
                        prefix[-1] = (prefix[-1][0] + value, prefix[-1][1])

                    # Increase the next value by one (if it exists)
                    if suffix:
                        suffix[0] = (suffix[0][0] + dls[index+1][0], suffix[0][1])

                    dls = prefix + infix + suffix

                    reducing = True

            if reducing:

            # If not exploding, check for any value that needs splitting
            for index, (value, depth) in enumerate(dls):
                if value >= 10:
                    logging.debug(f' - Splitting at {index=} with {value=}')

                    dls = (
                        + [
                            (math.floor(value / 2), depth + 1),
                            (math.ceil(value / 2), depth + 1),
                        + dls[index+1:]

                    reducing = True

        return Snailfish.from_depthlist(dls)

It’s a bit messy, but it works great.

And now that we have all that… we can actually do the problem.

def part1(file: typer.FileText):

    sum: Optional[Snailfish] = None

    while sf :='Adding: {sf} to {sum}')
        assert isinstance(sf, Snailfish)

        if sum is None:
            sum = sf
            sum += sf

    assert sum is not None'Final result: {sum}')


$ python3 part1 input.txt
# time 443584917ns / 0.44s

That was a … very strange/convoluted problem, but it was an interesting example of why data structures (and being able to convert between one another) is worthwhile.

Part 2: Find the pair of Snailfish numbers in your input with the largest magnitude of their sums.

I’m not sure there’s a better way that just brute forcing it:

def part2(file: typer.FileText):

    sfes: List[Snailfish] = []
    while sf :=
        assert isinstance(sf, Snailfish)

        (sf1 + sf2).magnitude()
        for sf1 in sfes
        for sf2 in sfes
        if sf1 != sf2

And it works fine:

$ python3 part2 input.txt
# time 5653670916ns / 5.65s

It’s a bit slower than I’d like… but I have spent far more than enough time on this problem…