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