Module advent_of_code_2021::day_18

This is my solution for Advent of Code - Day 18 - Snailfish

Today was doing convoluted arithmetic on ‘Snailfish Numbers’, which are made up of a binary tree with digits at the leaves. The representation was easy enough, but I had to box the non-leaf nodes to prevent the compiler complaining about the type being potentially infinite. I tried just using references, but it made satisfying the borrow checker very difficult. This resulted in SnailfishNumber and SnailfishNumber::from, a recursive function that parses a line of the input (each is one number).

The main difficulty of today was implementing SnailfishNumber::add. The actual addition is simple, but the resulting checks that the invariants on the new SnailfishNumber hold: no pair deeper than level 4, no leaves that are not single digits, and resolving them if they don’t involved some complex recursion and pointer manipulation. SnailfishNumber::check_depth handles checking if a pair is too deep, and also if it finds one, handles passing the numbers of that pair left/right as it unwinds the recursion. SnailfishNumber::check_digits handles splitting leaves with numbers that are not single digits into the relevant pair.

Finally SnailfishNumber::magnitude implements recursively reducing a SnailfishNumber tree into a single number for calculating the result. With these in place, add_numbers folds each line of the input into the first number using SnailfishNumber::add for the solution to part one. max_sum uses Itertools::permutations to match up each pair of numbers in both orders, map them to the magnitude of the sum, and reduce that to the maximum.

Enums

Direction

When a pair is exploding due to being too deep, the number that still needs to be assigned is passed up to the parent. This indicates which way it is travelling / which half of the pair it came from.

SnailfishNumber

Represents a snailfish number as a binary tree

Functions

add_numbers

The solution to part one - fold the list of numbers into the first and return the resulting number. The puzzle solution then converts this to its magnitude, but returning the full tree allows unit tests to compare this to the expectation.

max_sum

The solution to part two - uses Itertools::permutations to match up each pair of numbers in both orders, map them to the magnitude of the sum, and reduce that to the maximum.

parse_input

Split the input into lines and parse each with SnailfishNumber::from

run

The entry point for running the solutions with the ‘real’ puzzle input.