Module day18 

Snailfish

The key observation is that snailfish numbers represent binary trees.

For example, the first four sample numbers on the problem description look like the following in binary tree form:

[1,2]    [[1,2],3]    [9,[8,7]]    [[1,9],[8,5]]
  ■          ■            ■              ■
 / \        / \          / \           /   \
1   2      ■   3        9   ■         ■     ■
          / \              / \       / \   / \
         1   2            8   7     1   9 8   5

The addition rules have an important consequence. Exploding removes two leaf nodes at depth 5 and moves them to neighboring nodes. Since exploding repeatedly happens before splitting until there are no more values at depth 5 this means that the tree will never exceed a depth of 5, and even then a depth of 5 is transient.

Each level of a tree can contain up to 2ⁿ nodes, so the maximum size of a non-transient snailfish tree is 1 + 2 + 4 + 8 + 16 = 2⁵ - 1 = 31 nodes.

This means that we can store each snailfish number as an implicit data structure in a fixed-size array. This is faster, smaller and more convenient than using a traditional struct with pointers. The root node is stored at index 1 (index 0 is unused). For a node at index i its left child is at index 2i, right child at index 2i + 1 and parent at index i / 2. As leaf nodes are always greater than or equal to zero, -1 is used as a special sentinel value for non-leaf nodes.

Another optimization is realizing that all of the explode actions before the first split can be pre-computed. Instead of passing two depth-4 numbers to add(), we can simplify any depth-4 number into depth-3 via explode actions, and track what values it would have spilled left or right had it been part of a larger add(). The resulting Compressed object is then ready to slide into the left or right half of a new depth-4 tree at the start of add(), and all further reduce actions on the sum will be just splits of leaf nodes larger than 9, followed by an explode if the split happened at depth 4.

Structs

Compressed

Functions

add 🔒

Add two snailfish numbers.

augment_leaf 🔒

Augment the correct leaf by the given non-negative value. Walks up the tree starting at the given index until finding a leaf node. Storing the tree as an implicit structure has a nice benefit that finding the next left or right node is straightforward.

compress 🔒

Perform all initial explodes to create a compressed number from a snailfish number. This is a destructive operation, as no caller needs the original afterwards.

magnitude 🔒

Calculate the magnitude of a snailfish number in place without using recursion.

parse

Parse a snailfish number into an implicit binary tree stored in an array.

part1

Add all snailfish numbers, reducing to a single magnitude.

part2

Find the largest magnitude of any two snailfish numbers, remembering that snailfish addition is not commutative.

split 🔒

Split a node into two child nodes.

Type Aliases

Snailfish 🔒