Expand description
§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 neighbouring 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.
Each level of a tree can contain up to 2ⁿ nodes, so the maximum size of a snailfish tree is 1 + 2 + 4 + 8 + 16 + 32 = 2⁶-1 = 63 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 0. For a node at index i its left child is at index
2i + 1, right child at index 2i + 2 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.
Constants§
- IN_
ORDER 🔒The indices for in-order traversal of the first 4 levels of the implicit binary tree stored in an array.
Functions§
- add 🔒Add two snailfish numbers.
- explode 🔒Explode a specific pair identified by an index.
- Calculate the magnitude of a snailfish number in place without using recursion.
- Parse a snailfish number into an implicit binary tree stored in an array.
- Add all snailfish numbers, reducing to a single magnitude.
- Find the largest magnitude of any two snailfish numbers, remembering that snailfish addition is not commutative.
- split 🔒Split a node into two child nodes.
- worker 🔒Pair addition is independent so we can parallelize across multiple threads.