Day 18: Snailfish

Day #18 problem description │ Problem input

This problem asks us to parse a nested structure of pairs into a binary tree and then split or combine nodes according to a set of rules. Rather than store the tree as an actual tree, which would be easy (maybe) but would suffer from poor cache locality, we store the nodes in a Vec and record the depth of each node. This makes traversing and manipulating the tree much easier than if they were stored in a “real” tree; the nodes to the left and right of index i are simply those at i-1 and i+1, respectively (if they exist).

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
struct Elem {
	value: u32,
	depth: usize,
}

#[derive(Debug, PartialEq, Eq)]
struct SnailNum<Elems: AsRef<[Elem]>> {
	elems: Elems,
	depth: usize,
}

The operations are performed as follows:

Exploding

A pair is exploded by finding the first flat pair of depth at least four and storing the two values; the first is added to the node to the left and the second is added to the node to the right. The second element of the pair is then deleted.

/// Explodes the first explode-able pair in the list. \
/// Returns the `Option` pair of `Option` indices of the elements to the left and right
/// (the ones being modified), in that order. `None` means there was no pair to explode;
/// `(None, Some(2))` means the exploded pair had no elements to the left of it (it
/// was at index 0), and the element to its right was added to
fn explode_first(&mut self) -> Option<(Option<usize>, Option<usize>)> {
	let elems = &mut self.elems;

	let ((l_idx, l_elem), (r_idx, r_elem)) = elems
		.iter()
		.enumerate()
		.zip(elems.iter().enumerate().skip(1))
		.find_map(|((i1, &e1), (i2, &e2))| {
			if e1.depth > 4 && e1.depth == e2.depth {
				Some(((i1, e1), (i2, e2)))
			} else {
				None
			}
		})?;

	elems[l_idx] = Elem {
		value: 0,
		depth: l_elem.depth - 1,
	};

	let changed_l_idx = if l_idx > 0 {
		let idx = l_idx - 1;
		elems[idx].value += l_elem.value;
		Some(idx)
	} else {
		None
	};

	elems.remove(r_idx);

	let changed_r_idx = if r_idx < elems.len() {
		elems[r_idx].value += r_elem.value;
		Some(r_idx)
	} else {
		None
	};

	Some((changed_l_idx, changed_r_idx))
}
Splitting

An element is split by simply dividing it by 2 twice, rounding down the first time and up the second time, and replacing the element with those two values.

/// Splits the first splittable pair in the list. \
/// Returns the index at which the split occurred, which is now the first element of the
/// resulting pair
fn split_first(&mut self) -> Option<usize> {
	let elems = &mut self.elems;

	let (split_idx, Elem { value, depth }) =
		elems.iter().enumerate().find_map(|(i, &elem)| {
			if elem.value >= 10 {
				Some((i, elem))
			} else {
				None
			}
		})?;

	let new_l_value = value / 2;
	let new_r_value = (value + 1) / 2;

	let new_elem = Elem {
		value: new_l_value,
		depth: depth + 1,
	};
	elems[split_idx] = new_elem;

	elems.insert(
		split_idx + 1,
		Elem {
			value: new_r_value,
			depth: new_elem.depth,
		},
	);

	Some(split_idx)
}
Adding

Two pairs are added by placing them in a containing pair. This is manifested as simply concatenating the two vectors and then incrementing all the depths. Notably, addition is not associative.

fn add(&self, other: &Self) -> SnailNumOwned {
	let elems = self
		.elems
		.as_ref()
		.iter()
		.chain(other.elems.as_ref())
		.map(|&Elem { value, depth }| Elem {
			value,
			depth: depth + 1,
		})
		.collect();

	let mut ans = SnailNumOwned::owning(elems);
	ans.reduce();
	ans
}
Finding Pairs in the Vector

The only somewhat tricky part is determining the tree structure from the vector of depths. A singleton is returned as an Err containing its value. A “flat” pair (a pair whose elements are both atomic) appears as two consecutive elements of the same depth. Non-flat pairs can be found by traversing the nodes from left to right, maintaining a stack of node depths, and, whenever the top two elements of the stack have the same depth dd, collapsing them into a single element with a depth of d−1d-1. When a pair with elements of depth 1 is found, we have split the tree into its two top-level pairs. If desired, we can then recurse on these to split the descendants into deeper pairs.

fn as_pair(&self) -> Result<(SnailNumBorrowed, SnailNumBorrowed), u32> {
	let elems = self.elems.as_ref();
	assert_ne!(elems.len(), 0, "{}", self.depth);

	if elems.len() == 1 {
		return Err(self.elems.as_ref()[0].value);
	}

	let mut depth_stack = vec![];
	for (i, &Elem { depth, .. }) in elems.iter().enumerate() {
		depth_stack.push(depth);

		loop {
			match depth_stack.pop() {
				None => break,
				Some(curr_depth) => {
					if curr_depth == self.depth + 1 {
						let (left, right) = elems.split_at(i + 1);

						return Ok((
							SnailNum::borrowing(left, curr_depth),
							SnailNum::borrowing(right, curr_depth),
						));
					}

					match depth_stack.pop() {
						None => {
							depth_stack.push(curr_depth);
							break;
						}
						Some(prev_depth) => {
							if prev_depth == curr_depth {
								depth_stack.push(curr_depth - 1);
							} else {
								depth_stack.extend([prev_depth, curr_depth]);
								break;
							}
						}
					}
				}
			}
		}
	}
	unreachable!()
}
Magnitude of a Pair

Self explanatory:

fn magnitude(&self) -> u32 {
	match self.as_pair() {
		Ok((left, right)) => 3 * left.magnitude() + 2 * right.magnitude(),
		Err(val) => val,
	}
}

Setup

Functions listed above are omitted here.

use crate::Answer;
use std::fmt::{Debug, Display};

type SnailNumOwned = SnailNum<Vec<Elem>>;
type SnailNumBorrowed<'a> = SnailNum<&'a [Elem]>;

impl SnailNumOwned {
	fn from_line(line: &str) -> Self {
		let mut addends = Vec::<Elem>::new();
		let mut depth = 0;
		let mut prev_was_digit = false;

		for c in line.trim().chars() {
			let mut c_is_digit = false;
			match c {
				'[' => depth += 1,
				']' => depth -= 1,
				'0'..='9' => {
					let digit = c.to_digit(10).unwrap();
					if prev_was_digit {
						let val = addends.last_mut().unwrap();
						val.value = 10 * val.value + digit;
					} else {
						addends.push(Elem {
							value: digit,
							depth,
						});
					}
					c_is_digit = true;
				}
				',' => {}
				_ => {
					panic!("Unexpected character {:?}", c);
				}
			}

			prev_was_digit = c_is_digit;
		}
		SnailNum::owning(addends)
	}

	fn by_adding_lines_in<S: AsRef<str>, I: IntoIterator<Item = S>>(lines: I) -> Self {
		let mut lines = lines.into_iter();
		let mut ans = SnailNumOwned::from_line(lines.next().unwrap().as_ref());
		for line in lines {
			ans = ans.add(&SnailNumOwned::from_line(line.as_ref()));
		}
		ans
	}

	fn from_str(input: &str) -> Self {
		Self::by_adding_lines_in(input.lines())
	}

	fn owning(elems: Vec<Elem>) -> Self {
		Self { elems, depth: 0 }
	}

	fn reduce_once(&mut self) -> bool {
		self.explode_first().is_some() || self.split_first().is_some()
	}

	fn reduce(&mut self) {
		while self.reduce_once() {}
	}

	// Contains explode_first and split_first, which only operate on owned snail nums
}

impl<'a> SnailNumBorrowed<'a> {
	fn borrowing(elems: &'a [Elem], base_depth: usize) -> Self {
		Self {
			elems,
			depth: base_depth,
		}
	}
}

impl<E: AsRef<[Elem]>> SnailNum<E> {
	// Contains add, as_pair, and magnitude
}

fn ans_for_input(input: &str) -> Answer<u32, u32> {
	let snail_num = SnailNumOwned::from_str(input);
	(18, (pt1(&snail_num), pt2(input))).into()
}

pub fn ans() -> Answer<u32, u32> {
	ans_for_input(include_str!("input.txt"))
}

Part 1

Part 1 simply asks to perform addition on the input numbers.

fn pt1<E: AsRef<[Elem]>>(snail_num: &SnailNum<E>) -> u32 {
	snail_num.magnitude()
}

Part 2

Part 2 asks to find the maximum pairwise sum of the input numbers.

fn pt2(input: &str) -> u32 {
	let mut max_mag = u32::MIN;
	let snail_nums = input
		.lines()
		.map(SnailNumOwned::from_line)
		.collect::<Vec<_>>();

	for (i, sn1) in snail_nums.iter().enumerate() {
		for sn2 in snail_nums.iter().skip(i + 1) {
			let mag1 = sn1.add(sn2).magnitude();
			let mag2 = sn2.add(sn1).magnitude();

			max_mag = max_mag.max(mag1).max(mag2);
		}
	}

	max_mag
}

This page was built using Antora with a theme forked from the default UI. Search is powered by Lunr.

The source code for this UI is licensed under the terms of the MPL-2.0 license.