aoc/year2021/day18.rs
1//! # Snailfish
2//!
3//! The key observation is that snailfish numbers represent
4//! [binary trees](https://en.wikipedia.org/wiki/Binary_tree).
5//!
6//! For example the first four sample numbers on the problem description look like the following
7//! in binary tree form:
8//!
9//! ```text
10//! [1,2] [[1,2],3] [9,[8,7]] [[1,9],[8,5]]
11//! ■ ■ ■ ■
12//! / \ / \ / \ / \
13//! 1 2 ■ 3 9 ■ ■ ■
14//! / \ / \ / \ / \
15//! 1 2 8 7 1 9 8 5
16//! ```
17//!
18//! The addition rules have an important consequence. Exploding removes two leaf nodes at depth 5
19//! and moves them to neighbouring nodes. Since exploding repeatedly happens before splitting until
20//! there are no more values at depth 5 this means that the tree will never exceed a depth of 5.
21//!
22//! Each level of a tree can contain up to 2ⁿ nodes, so the maximum size of a snailfish tree is
23//! 1 + 2 + 4 + 8 + 16 + 32 = 2⁶-1 = 63 nodes.
24//!
25//! This means that we can store each snailfish number as an implicit data structure in a fixed size
26//! array. This is faster, smaller and more convenient than using a traditional struct with pointers.
27//! The root node is stored at index 0. For a node at index `i` its left child is at index
28//! `2i + 1`, right child at index `2i + 2` and parent at index `i / 2`. As leaf nodes are
29//! always greater than or equal to zero, `-1` is used as a special sentinel value for non-leaf nodes.
30use crate::util::parse::*;
31use crate::util::thread::*;
32
33type Snailfish = [i32; 63];
34
35/// The indices for [in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal) of the first
36/// 4 levels of the implicit binary tree stored in an array.
37const IN_ORDER: [usize; 30] = [
38 1, 3, 7, 15, 16, 8, 17, 18, 4, 9, 19, 20, 10, 21, 22, 2, 5, 11, 23, 24, 12, 25, 26, 6, 13, 27,
39 28, 14, 29, 30,
40];
41
42/// Parse a snailfish number into an implicit binary tree stored in an array.
43///
44/// Since no number will greater than 9 initially we can consider each character individually.
45/// `[` means moves down a level to parse children, `,` means move from left to right node,
46/// `]` means move up a level to return to parent and a digit from 0-9 creates a leaf node
47/// with that value.
48pub fn parse(input: &str) -> Vec<Snailfish> {
49 fn helper(bytes: &[u8]) -> Snailfish {
50 let mut tree = [-1; 63];
51 let mut i = 0;
52
53 for &b in bytes {
54 match b {
55 b'[' => i = 2 * i + 1,
56 b',' => i += 1,
57 b']' => i = (i - 1) / 2,
58 b => tree[i] = b.to_decimal() as i32,
59 }
60 }
61
62 tree
63 }
64 input.lines().map(|line| helper(line.as_bytes())).collect()
65}
66
67/// Add all snailfish numbers, reducing to a single magnitude.
68pub fn part1(input: &[Snailfish]) -> i32 {
69 let mut sum = input.iter().copied().reduce(|acc, n| add(&acc, &n)).unwrap();
70 magnitude(&mut sum)
71}
72
73/// Find the largest magnitude of any two snailfish numbers, remembering that snailfish addition
74/// is *not* commutative.
75pub fn part2(input: &[Snailfish]) -> i32 {
76 let mut pairs = Vec::new();
77
78 for (i, a) in input.iter().enumerate() {
79 for (j, b) in input.iter().enumerate() {
80 if i != j {
81 pairs.push((a, b));
82 }
83 }
84 }
85
86 // Use as many cores as possible to parallelize the calculation.
87 let result = spawn_parallel_iterator(&pairs, worker);
88 result.into_iter().max().unwrap()
89}
90
91/// Pair addition is independent so we can parallelize across multiple threads.
92fn worker(iter: ParIter<'_, (&Snailfish, &Snailfish)>) -> i32 {
93 iter.map(|&(a, b)| magnitude(&mut add(a, b))).max().unwrap()
94}
95
96/// Add two snailfish numbers.
97///
98/// The initial step creates a new root node then makes the numbers the left and right children
99/// of this new root node, by copying the respective ranges of the implicit trees.
100///
101/// We can optimize the rules a little. This initial combination is the only time that more than one
102/// pair will be 4 levels deep simultaneously, so we can sweep from left to right on all possible
103/// leaf nodes in one pass.
104fn add(left: &Snailfish, right: &Snailfish) -> Snailfish {
105 let mut tree = [-1; 63];
106
107 tree[3..5].copy_from_slice(&left[1..3]);
108 tree[7..11].copy_from_slice(&left[3..7]);
109 tree[15..23].copy_from_slice(&left[7..15]);
110 tree[31..47].copy_from_slice(&left[15..31]);
111
112 tree[5..7].copy_from_slice(&right[1..3]);
113 tree[11..15].copy_from_slice(&right[3..7]);
114 tree[23..31].copy_from_slice(&right[7..15]);
115 tree[47..63].copy_from_slice(&right[15..31]);
116
117 for pair in (31..63).step_by(2) {
118 if tree[pair] >= 0 {
119 explode(&mut tree, pair);
120 }
121 }
122
123 while split(&mut tree) {}
124 tree
125}
126
127/// Explode a specific pair identified by an index.
128///
129/// Storing the tree as an implicit structure has a nice benefit that finding the next left or right
130/// node is straightforward. We first move to the next left or right leaf node by adding or
131/// subtracting one to the index. If this node is empty then we move to the parent node until we
132/// find a leaf node.
133///
134/// The leaf node at index 31 has no possible nodes to the left and similarly the leaf node at
135/// index 62 has no possible nodes to the right.
136fn explode(tree: &mut Snailfish, pair: usize) {
137 if pair > 31 {
138 let mut i = pair - 1;
139 loop {
140 if tree[i] >= 0 {
141 tree[i] += tree[pair];
142 break;
143 }
144 i = (i - 1) / 2;
145 }
146 }
147
148 if pair < 61 {
149 let mut i = pair + 2;
150 loop {
151 if tree[i] >= 0 {
152 tree[i] += tree[pair + 1];
153 break;
154 }
155 i = (i - 1) / 2;
156 }
157 }
158
159 tree[pair] = -1;
160 tree[pair + 1] = -1;
161 tree[(pair - 1) / 2] = 0;
162}
163
164/// Split a node into two child nodes.
165///
166/// Search the tree in an *in-order* traversal, splitting the first node over `10` found (if any).
167/// We can optimize the rules by immediately exploding if this results in a node 4 levels deep,
168/// as we know that the prior optimzation in the [`add`] function means that this is the only
169/// explosion possible.
170fn split(tree: &mut Snailfish) -> bool {
171 for &i in &IN_ORDER {
172 if tree[i] >= 10 {
173 tree[2 * i + 1] = tree[i] / 2;
174 tree[2 * i + 2] = (tree[i] + 1) / 2;
175 tree[i] = -1;
176
177 if i >= 15 {
178 explode(tree, 2 * i + 1);
179 }
180 return true;
181 }
182 }
183 false
184}
185
186/// Calculate the magnitude of a snailfish number in place without using recursion.
187///
188/// This operation is destructive but much faster than using a recursive approach and acceptable
189/// as we no longer need the original snailfish number afterwards.
190fn magnitude(tree: &mut Snailfish) -> i32 {
191 for i in (0..31).rev() {
192 if tree[i] == -1 {
193 tree[i] = 3 * tree[2 * i + 1] + 2 * tree[2 * i + 2];
194 }
195 }
196 tree[0]
197}