commit dd2922f82a453544355fe683e3bd66bc0c21b4ee
parent 36b32528b80b0f6f4016e6b5b68880006b27dc10
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 15 Apr 2023 01:10:22 -0400
Add day 18 solution
Diffstat:
8 files changed, 793 insertions(+), 0 deletions(-)
diff --git a/src/18/.gdb_history b/src/18/.gdb_history
@@ -0,0 +1,44 @@
+r
+f
+f
+f 9
+f 8
+f 7
+f 10
+f 11
+f 12
+f 13
+f 14
+f 15
+f 16
+f 18
+f 20
+f 30
+f 50
+f 100
+frame
+frames
+show frame
+show frames
+frame info
+info frame
+info frame all
+f 1
+f 2
+f 3
+f 5
+f 10
+f 11
+f 12
+f 13
+f 14
+f 15
+f 16
+f 17
+f 300
+f 299
+f 298
+f 297
+f 296
+f 295
+f 294
diff --git a/src/18/Cargo.toml b/src/18/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day18"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/18/input b/src/18/input
@@ -0,0 +1,101 @@
+[4,[3,[9,[9,0]]]]
+[[[7,6],[2,[2,5]]],[5,[[7,3],8]]]
+[4,[4,6]]
+[[0,[5,6]],[[[1,3],[2,7]],[[0,6],4]]]
+[6,[[3,[6,0]],3]]
+[[7,[9,[8,5]]],[6,7]]
+[[[[2,6],1],2],[3,[8,4]]]
+[4,[[[5,4],[2,7]],[[8,0],[2,3]]]]
+[[[[4,3],2],[[3,6],[2,5]]],[[[3,7],8],0]]
+[[[8,[0,7]],1],[[9,[3,9]],9]]
+[[[[3,0],[1,3]],[[0,9],8]],[[[7,2],9],[[1,4],[3,5]]]]
+[[[[9,6],[4,4]],[1,3]],[[4,3],[[6,4],[8,4]]]]
+[[[1,2],[[7,6],[2,3]]],[[4,6],[4,2]]]
+[[[4,8],[[5,8],1]],[2,3]]
+[[[5,2],[3,[5,7]]],[[2,9],5]]
+[[[6,[3,2]],[2,6]],[[8,[4,2]],[[5,2],7]]]
+[[[[2,6],[0,1]],[7,[3,6]]],[[1,6],[[7,9],0]]]
+[[[0,3],[8,1]],[[[9,0],3],[0,2]]]
+[[8,[[7,1],[4,7]]],[[0,[1,3]],[8,2]]]
+[[[[2,3],4],[[0,8],[9,0]]],[1,[[5,3],4]]]
+[[[[7,2],2],[[1,3],[8,3]]],[4,[[7,9],[0,6]]]]
+[[[[2,2],[3,4]],[[1,5],[4,3]]],[6,[[7,2],1]]]
+[1,[[[5,7],0],[9,[8,8]]]]
+[[[[9,2],[0,9]],[4,[7,8]]],[[4,8],[[1,8],[4,9]]]]
+[[[[4,7],2],2],4]
+[1,[[2,[4,2]],1]]
+[[[[7,2],[3,8]],[0,[1,3]]],[[[4,4],[2,4]],[8,2]]]
+[[[[1,0],[0,5]],2],[[9,[5,0]],[[1,6],5]]]
+[4,[[[8,1],[1,4]],[7,[1,3]]]]
+[[[6,[0,4]],[[4,6],[2,4]]],[9,[1,5]]]
+[[[[3,6],[3,3]],1],[0,[[8,8],2]]]
+[[7,[5,[2,6]]],[[[7,9],6],[0,[3,6]]]]
+[[[[6,7],4],[[2,9],2]],3]
+[[[7,[1,7]],[5,4]],[[[1,1],[0,1]],5]]
+[[6,[[1,0],6]],[0,[6,[0,5]]]]
+[[[[2,4],[4,6]],9],[4,[[8,0],7]]]
+[[[[9,9],[5,7]],[9,[8,6]]],[[3,[2,3]],0]]
+[[0,[1,[5,3]]],[3,[8,[3,4]]]]
+[[[[4,3],8],[2,9]],[[1,[6,5]],[[5,7],2]]]
+[[[0,[7,4]],[9,[9,6]]],[[8,[5,5]],[[6,4],1]]]
+[[[[7,3],[7,9]],[8,[6,2]]],[[8,[4,5]],[[6,4],[6,7]]]]
+[[7,[[9,0],[9,0]]],[[[0,8],2],[8,[8,3]]]]
+[4,[7,[5,6]]]
+[7,[[[3,8],8],3]]
+[[[4,[6,6]],0],[9,0]]
+[[[[7,4],8],8],[[0,1],[[0,0],[2,4]]]]
+[7,[1,[[9,4],[3,6]]]]
+[[[[2,8],9],[[8,6],[2,2]]],[[[5,1],9],[2,[0,7]]]]
+[8,7]
+[[[[0,8],4],[[9,9],[9,9]]],[[[4,3],[1,0]],[6,8]]]
+[[[[8,3],[8,9]],1],[[4,[1,0]],[[4,0],[2,3]]]]
+[[[[4,7],[1,3]],[6,9]],[[1,0],[[1,8],5]]]
+[[2,[4,[6,5]]],[3,[[9,9],5]]]
+[[[[7,6],4],9],[8,[4,5]]]
+[[[0,[6,6]],[7,[8,9]]],[[[0,0],[3,4]],[4,[1,8]]]]
+[[[9,[7,0]],[5,8]],[6,[[5,0],[0,6]]]]
+[[[[4,0],[1,9]],[7,[3,6]]],[[2,[8,6]],[[2,8],[8,2]]]]
+[[[9,6],8],[[[5,5],[4,8]],0]]
+[[[[1,7],1],2],[[[6,8],3],[[3,3],5]]]
+[3,[5,[[3,8],6]]]
+[3,[[[9,6],[5,8]],[9,2]]]
+[[6,1],[6,4]]
+[[2,6],[[[1,2],2],8]]
+[[[[1,7],[3,6]],[2,[0,2]]],[[3,0],9]]
+[1,[[0,[4,9]],5]]
+[[[[5,5],[5,2]],[0,[6,4]]],8]
+[0,[7,[[6,9],[6,0]]]]
+[[[[2,2],[4,7]],[[7,4],6]],[[0,[1,7]],[[3,2],6]]]
+[[9,8],0]
+[[[[5,4],[4,8]],2],[3,[8,9]]]
+[[[[7,0],8],5],[2,6]]
+[[[5,[0,8]],5],[[[5,0],[1,8]],[[0,2],7]]]
+[[[[9,4],8],[[6,5],4]],[[5,[8,9]],[4,[0,4]]]]
+[[[[3,6],7],[[9,3],7]],[7,[[8,3],9]]]
+[[[[0,7],5],[[5,7],2]],[[2,[9,5]],[[7,7],[5,0]]]]
+[[[[7,5],2],[8,6]],[[2,[6,2]],[5,[3,1]]]]
+[[9,[9,1]],6]
+[[[0,7],[[5,9],2]],3]
+[[[9,3],[8,8]],[0,[4,5]]]
+[[[[6,2],5],[4,[3,1]]],[9,[2,8]]]
+[[[1,[9,4]],[[0,0],2]],[[1,[2,1]],[[7,8],[3,2]]]]
+[[[[0,6],[8,9]],[[4,7],[5,6]]],[[[1,4],[8,7]],[4,6]]]
+[[[[6,4],[1,5]],[0,8]],[[[9,7],[1,2]],[9,4]]]
+[[[[4,5],[0,7]],[9,[1,8]]],[[[5,0],6],7]]
+[[[0,[6,9]],[5,[5,6]]],7]
+[[4,5],[[7,[6,5]],1]]
+[[[7,9],[6,7]],[4,1]]
+[[[[9,6],1],[[3,1],[9,7]]],[1,[7,1]]]
+[[[0,[2,0]],5],[[8,[7,6]],[[7,3],4]]]
+[[[6,[1,7]],[9,[2,7]]],3]
+[[[6,[8,2]],5],[4,[[1,3],[5,1]]]]
+[[[4,[3,3]],[4,[2,4]]],[5,4]]
+[[[1,6],[4,[4,0]]],[[8,[2,2]],[[8,1],[4,7]]]]
+[[2,0],[[2,1],[[4,8],[2,7]]]]
+[9,[[8,4],0]]
+[[1,6],[[5,[1,3]],[9,[0,9]]]]
+[[[0,[3,5]],3],[[2,[8,0]],[[2,0],[4,3]]]]
+[[[1,[1,9]],[9,[7,9]]],[[2,2],[[6,7],[0,7]]]]
+[[[4,6],[[6,2],[0,9]]],[[1,0],[1,[6,7]]]]
+[9,[[[0,1],4],[[9,3],3]]]
+
diff --git a/src/18/part1 b/src/18/part1
@@ -0,0 +1,211 @@
+--- Day 18: Snailfish ---
+
+You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys!
+They'll even tell you which direction the keys went if you help one of the smaller snailfish with
+his [1m[97mmath homework[0m.
+
+Snailfish numbers aren't like regular numbers. Instead, every snailfish number is a
+[1m[97mpair[0m - an ordered list of two elements. Each element of the pair can be either a regular number or
+another pair.
+
+Pairs are written as [x,y], where x and y are the elements within the pair. Here are some example
+snailfish numbers, one snailfish number per line:
+
+[1,2]
+[[1,2],3]
+[9,[8,7]]
+[[1,9],[8,5]]
+[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
+[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
+[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]
+
+This snailfish homework is about [1m[97maddition[0m. To add two snailfish numbers, form a pair from the left
+and right parameters of the addition operator. For example, [1,2] + [[3,4],5] becomes
+[[1,2],[[3,4],5]].
+
+There's only one problem: [1m[97msnailfish numbers must always be reduced[0m, and the process of adding two
+snailfish numbers can result in snailfish numbers that need to be reduced.
+
+To [1m[97mreduce a snailfish number[0m, you must repeatedly do the first action in this list that applies to
+the snailfish number:
+
+
+ - If any pair is [1m[97mnested inside four pairs[0m, the leftmost such pair [1m[97mexplodes[0m.
+
+ - If any regular number is [1m[97m10 or greater[0m, the leftmost such regular number [1m[97msplits[0m.
+
+
+Once no action in the above list applies, the snailfish number is reduced.
+
+During reduction, at most one action applies, after which the process returns to the top of the list
+of actions. For example, if [1m[97msplit[0m produces a pair that meets the [1m[97mexplode[0m criteria, that pair
+[1m[97mexplodes[0m before other [1m[97msplits[0m occur.
+
+To [1m[97mexplode[0m a pair, the pair's left value is added to the first regular number to the left of the
+exploding pair (if any), and the pair's right value is added to the first regular number to the
+right of the exploding pair (if any). Exploding pairs will always consist of two regular numbers.
+Then, the entire exploding pair is replaced with the regular number 0.
+
+Here are some examples of a single explode action:
+
+
+ - [[[[[1m[97m[9,8][0m,1],2],3],4] becomes [[[[[1m[97m0[0m,[1m[97m9[0m],2],3],4] (the 9 has no regular number to its left, so it
+is not added to any regular number).
+
+ - [7,[6,[5,[4,[1m[97m[3,2][0m]]]] becomes [7,[6,[5,[[1m[97m7[0m,[1m[97m0[0m]]]] (the 2 has no regular number to its right, and so
+it is not added to any regular number).
+
+ - [[6,[5,[4,[1m[97m[3,2][0m]]],1] becomes [[6,[5,[[1m[97m7[0m,[1m[97m0[0m]]],[1m[97m3[0m].
+
+ - [[3,[2,[1,[1m[97m[7,3][0m]]],[6,[5,[4,[3,2]]]]] becomes
+[[3,[2,[[1m[97m8[0m,[1m[97m0[0m]]],[[1m[97m9[0m,[5,[4,[3,2]]]]] (the pair [3,2] is unaffected because the pair [7,3] is further to
+the left; [3,2] would explode on the next action).
+
+ - [[3,[2,[8,0]]],[9,[5,[4,[1m[97m[3,2][0m]]]] becomes
+[[3,[2,[8,0]]],[9,[5,[[1m[97m7[0m,[1m[97m0[0m]]]].
+
+
+To [1m[97msplit[0m a regular number, replace it with a pair; the left element of the pair should be the
+regular number divided by two and rounded [1m[97mdown[0m, while the right element of the pair should be the
+regular number divided by two and rounded [1m[97mup[0m. For example, 10 becomes [5,5], 11 becomes [5,6], 12
+becomes [6,6], and so on.
+
+Here is the process of finding the reduced result of [[[[4,3],4],4],[7,[[8,4],9]]] + [1,1]:
+
+after addition: [[[[[1m[97m[4,3][0m,4],4],[7,[[8,4],9]]],[1,1]]
+after explode: [[[[0,7],4],[7,[[1m[97m[8,4][0m,9]]],[1,1]]
+after explode: [[[[0,7],4],[[1m[97m15[0m,[0,13]]],[1,1]]
+after split: [[[[0,7],4],[[7,8],[0,[1m[97m13[0m]]],[1,1]]
+after split: [[[[0,7],4],[[7,8],[0,[1m[97m[6,7][0m]]],[1,1]]
+after explode: [[[[0,7],4],[[7,8],[6,0]]],[8,1]]
+
+Once no reduce actions apply, the snailfish number that remains is the actual result of the addition
+operation: [[[[0,7],4],[[7,8],[6,0]]],[8,1]].
+
+The homework assignment involves adding up a [1m[97mlist of snailfish numbers[0m (your puzzle input). The
+snailfish numbers are each listed on a separate line. Add the first snailfish number and the second,
+then add that result and the third, then add that result and the fourth, and so on until all numbers
+in the list have been used once.
+
+For example, the final sum of this list is [[[[1,1],[2,2]],[3,3]],[4,4]]:
+
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+
+The final sum of this list is [[[[3,0],[5,3]],[4,4]],[5,5]]:
+
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+[5,5]
+
+The final sum of this list is [[[[5,0],[7,4]],[5,5]],[6,6]]:
+
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+[5,5]
+[6,6]
+
+Here's a slightly larger example:
+
+[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
+[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
+[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
+[7,[5,[[3,8],[1,4]]]]
+[[2,[2,2]],[8,[8,1]]]
+[2,9]
+[1,[[[9,3],9],[[9,0],[0,7]]]]
+[[[5,[7,4]],7],1]
+[[[[4,2],2],6],[8,7]]
+
+The final sum [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] is found after adding up the
+above snailfish numbers:
+
+ [[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
++ [7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
+= [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
+
+ [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
++ [[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
+= [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
+
+ [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
++ [[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
+= [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
+
+ [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
++ [7,[5,[[3,8],[1,4]]]]
+= [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
+
+ [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
++ [[2,[2,2]],[8,[8,1]]]
+= [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
+
+ [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
++ [2,9]
+= [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
+
+ [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
++ [1,[[[9,3],9],[[9,0],[0,7]]]]
+= [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
+
+ [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
++ [[[5,[7,4]],7],1]
+= [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
+
+ [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
++ [[[[4,2],2],6],[8,7]]
+= [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]
+
+To check whether it's the right answer, the snailfish teacher only checks the [1m[97mmagnitude[0m of the final
+sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude
+of its right element. The magnitude of a regular number is just that number.
+
+For example, the magnitude of [9,1] is 3*9 + 2*1 = [1m[97m29[0m; the magnitude of [1,9] is 3*1 + 2*9 =
+[1m[97m21[0m. Magnitude calculations are recursive: the magnitude of [[9,1],[1,9]] is 3*29 + 2*21 =
+[1m[97m129[0m.
+
+Here are a few more magnitude examples:
+
+
+ - [[1,2],[[3,4],5]] becomes [1m[97m143[0m.
+
+ - [[[[0,7],4],[[7,8],[6,0]]],[8,1]] becomes [1m[97m1384[0m.
+
+ - [[[[1,1],[2,2]],[3,3]],[4,4]] becomes [1m[97m445[0m.
+
+ - [[[[3,0],[5,3]],[4,4]],[5,5]] becomes [1m[97m791[0m.
+
+ - [[[[5,0],[7,4]],[5,5]],[6,6]] becomes [1m[97m1137[0m.
+
+ - [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] becomes [1m[97m3488[0m.
+
+
+So, given this example homework assignment:
+
+[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
+[[[5,[2,8]],4],[5,[[9,9],0]]]
+[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
+[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
+[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
+[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
+[[[[5,4],[7,7]],8],[[8,3],8]]
+[[9,3],[[9,9],[6,[4,9]]]]
+[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
+[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]
+
+The final sum is:
+
+[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]
+The magnitude of this final sum is [1m[97m4140[0m.
+
+Add up all of the snailfish numbers from the homework assignment in the order they appear.
+[1m[97mWhat is the magnitude of the final sum?[0m
+
+
diff --git a/src/18/part2 b/src/18/part2
@@ -0,0 +1,31 @@
+--- Part Two ---
+
+You notice a second question on the back of the homework assignment:
+
+What is the largest magnitude you can get from adding only two of the snailfish numbers?
+
+Note that snailfish addition is not commutative - that is, x + y and y + x can produce different
+results.
+
+Again considering the last example homework assignment above:
+
+[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
+[[[5,[2,8]],4],[5,[[9,9],0]]]
+[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
+[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
+[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
+[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
+[[[[5,4],[7,7]],8],[[8,3],8]]
+[[9,3],[[9,9],[6,[4,9]]]]
+[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
+[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]
+
+The largest magnitude of the sum of any two snailfish numbers in this list is [1m[97m3993[0m. This is the
+magnitude of [[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] +
+[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]], which reduces to
+[[[[7,8],[6,6]],[[6,0],[7,7]]],[[[7,8],[8,8]],[[7,9],[0,6]]]].
+
+[1m[97mWhat is the largest magnitude of any sum of two different snailfish numbers from the homework
+assignment?[0m
+
+
diff --git a/src/18/src/main.rs b/src/18/src/main.rs
@@ -0,0 +1,392 @@
+use std::rc::Rc;
+use std::cell::RefCell;
+
+#[derive(PartialEq,Eq,Clone)]
+enum NodeData {
+ Children(Vec<Rc<RefCell<Node>>>),
+ Value(usize)
+}
+
+#[derive(PartialEq,Eq,Clone)]
+struct Node {
+ data: NodeData,
+ par: Option<Rc<RefCell<Node>>>
+}
+
+struct NodeIterState {
+ ent: Rc<RefCell<Node>>,
+ idx: usize,
+ depth: usize
+}
+
+struct NodeIter {
+ states: Vec<NodeIterState>
+}
+
+fn node_entry(children: Vec<Rc<RefCell<Node>>>,
+ par: Option<Rc<RefCell<Node>>>) -> Rc<RefCell<Node>> {
+ Rc::new(RefCell::new(Node { data: NodeData::Children(children), par }))
+}
+
+fn value_entry(value: usize,
+ par: Option<Rc<RefCell<Node>>>) -> Rc<RefCell<Node>> {
+ Rc::new(RefCell::new(Node { data: NodeData::Value(value), par }))
+}
+
+fn to_children(ent: &Node) -> &Vec<Rc<RefCell<Node>>> {
+ match &ent.data {
+ NodeData::Children(p) => p,
+ _ => unreachable!()
+ }
+}
+
+fn to_children_mut(ent: &mut Node) -> &mut Vec<Rc<RefCell<Node>>> {
+ match &mut ent.data {
+ NodeData::Children(p) => p,
+ _ => unreachable!()
+ }
+}
+
+fn to_value(ent: &Node) -> &usize {
+ match &ent.data {
+ NodeData::Value(v) => v,
+ _ => unreachable!()
+ }
+}
+
+fn to_value_mut(ent: &mut Node) -> &mut usize {
+ match &mut ent.data {
+ NodeData::Value(v) => v,
+ _ => unreachable!()
+ }
+}
+
+fn has_children(ent: &Node) -> bool {
+ match &ent.data {
+ NodeData::Children(_) => true,
+ _ => false
+ }
+}
+
+fn parse_snail(line: &str) -> Rc<RefCell<Node>> {
+ let top = node_entry(vec![], None);
+
+ let mut cur = top.clone();
+ for c in line.chars() {
+ if c == '[' {
+ let cpy = cur.clone();
+ let borrow = &mut cpy.as_ref().borrow_mut();
+ let children = to_children_mut(borrow);
+ children.push(node_entry(vec![], Some(cur.clone())));
+ cur = children.last_mut().unwrap().clone();
+ } else if c == ']' {
+ {
+ let borrow = &mut (*cur).borrow_mut();
+ let children = to_children_mut(borrow);
+ assert!(children.len() == 2);
+ children.shrink_to_fit();
+ }
+ if cur.borrow().par.is_none() { break; }
+ let par = cur.borrow().par.as_ref().unwrap().clone();
+ cur = par;
+ } else {
+ let cpy = cur.clone();
+ let borrow = &mut cpy.as_ref().borrow_mut();
+ let children = to_children_mut(borrow);
+ if c == ',' { continue; }
+ let val = c.to_digit(10).unwrap() as usize;
+ children.push(value_entry(val, Some(cur.clone())));
+ }
+ }
+
+ return to_children(&top.borrow())[0].clone();
+}
+
+fn tree_iter(node: &Rc<RefCell<Node>>) -> NodeIter {
+ let mut states: Vec<NodeIterState> = Vec::new();
+ states.push(NodeIterState { ent: node.clone(), idx: 0, depth: 0 });
+ return NodeIter { states };
+}
+
+impl Iterator for NodeIter {
+ type Item = (Rc<RefCell<Node>>,usize);
+
+ fn next(&mut self) -> Option<(Rc<RefCell<Node>>,usize)> {
+ while !self.states.is_empty() {
+ let last = self.states.last_mut().unwrap();
+ let depth = last.depth;
+ if has_children(&last.ent.borrow()) {
+ match last.idx {
+ 0 | 1 => {
+ let ent = last.ent.clone();
+ let borrow = &ent.borrow();
+ let left = to_children(&borrow)[last.idx].clone();
+ last.idx += 1;
+ self.states.push(NodeIterState {
+ ent: left,
+ idx: 0,
+ depth: depth + 1
+ });
+ },
+ _ => {
+ let ent = last.ent.clone();
+ self.states.pop();
+ return Some((ent,depth));
+ }
+ };
+ } else {
+ let ent = last.ent.clone();
+ self.states.pop();
+ return Some((ent,depth));
+ }
+ }
+
+ return None;
+ }
+}
+
+fn find_left_pair(top: &Rc<RefCell<Node>>, target_depth: usize)
+ -> Option<Rc<RefCell<Node>>> {
+ for (ent,depth) in tree_iter(top) {
+ let borrow = &ent.borrow();
+ if depth == target_depth && has_children(borrow) {
+ return Some(ent.clone());
+ }
+ }
+ return None;
+}
+
+fn find_split_num(top: &Rc<RefCell<Node>>)
+ -> Option<Rc<RefCell<Node>>> {
+ for (ent,_) in tree_iter(top) {
+ let borrow = &ent.borrow();
+ if !has_children(borrow) {
+ if *to_value(borrow) >= 10 {
+ return Some(ent.clone());
+ }
+ }
+ }
+ return None;
+}
+
+fn find_left(cur: &Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
+ let mut iter = cur.clone();
+ loop {
+ if iter.borrow().par.is_none() { return None };
+ let cpy = iter.clone();
+ let borrow = cpy.borrow();
+ let par = &borrow.par.as_ref().unwrap().borrow();
+ if to_children(&par)[1].as_ptr() == iter.as_ptr() {
+ aoc::debugln!("LEFT {}", to_children(&par).len());
+ iter = to_children(&par)[0].clone();
+ break;
+ }
+ iter = borrow.par.as_ref().unwrap().clone();
+ }
+ loop {
+ if !has_children(&iter.borrow()) { break; }
+ let cpy = iter.clone();
+ let borrow = &cpy.borrow();
+ iter = to_children(&borrow)[1].clone();
+ }
+ return Some(iter);
+}
+
+fn find_right(cur: &Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
+ let mut iter = cur.clone();
+ loop {
+ if iter.borrow().par.is_none() { return None };
+ let cpy = iter.clone();
+ let borrow = cpy.borrow();
+ let par = &borrow.par.as_ref().unwrap().borrow();
+ if to_children(&par)[0].as_ptr() == iter.as_ptr() {
+ aoc::debugln!("RIGHT {}", to_children(&par).len());
+ iter = to_children(&par)[1].clone();
+ break;
+ }
+ iter = borrow.par.as_ref().unwrap().clone();
+ }
+ loop {
+ if !has_children(&iter.borrow()) { break; }
+ let cpy = iter.clone();
+ let borrow = &cpy.borrow();
+ iter = to_children(&borrow)[0].clone();
+ }
+ return Some(iter);
+}
+
+fn snail_add(a: Rc<RefCell<Node>>, b: Rc<RefCell<Node>>,
+ par: Option<Rc<RefCell<Node>>>) -> Rc<RefCell<Node>> {
+ let new = node_entry(vec![a, b], par);
+ let cpy = new.clone();
+ let borrow = &mut cpy.borrow_mut();
+ let pair = to_children_mut(borrow);
+ (*pair[0]).borrow_mut().par = Some(new.clone());
+ (*pair[1]).borrow_mut().par = Some(new.clone());
+ return new;
+}
+
+fn snail_print(title: &str, top: &Rc<RefCell<Node>>) {
+ aoc::debug!("{} ", title);
+ let mut last_depth = 0;
+ for (ent,depth) in tree_iter(top) {
+ if last_depth > 0 && depth >= last_depth {
+ aoc::debug!(",");
+ }
+
+ if depth > last_depth {
+ for _ in last_depth..depth {
+ aoc::debug!("[");
+ }
+ }
+
+ let borrow = &ent.borrow();
+ if !has_children(borrow) {
+ aoc::debug!("{}", *to_value(borrow));
+ }
+
+ if last_depth > depth {
+ for _ in depth..last_depth {
+ aoc::debug!("]");
+ }
+ }
+
+ last_depth = depth;
+ }
+ aoc::debugln!("");
+}
+
+fn snail_reduce(top: &Rc<RefCell<Node>>) {
+ loop {
+ let explode = find_left_pair(top, 4);
+ if explode.is_some() {
+ aoc::debugln!("EXPLODE");
+
+ let explode = explode.unwrap();
+
+ {
+ let explode_borrow = &explode.borrow();
+ assert!(!has_children(&to_children(explode_borrow)[0].borrow()));
+ assert!(!has_children(&to_children(explode_borrow)[1].borrow()));
+ aoc::debugln!("{} {}",
+ *to_value(&to_children(explode_borrow)[0].borrow()),
+ *to_value(&to_children(explode_borrow)[0].borrow()));
+
+ let left = find_left(&explode);
+ if left.is_some() {
+ let left = left.unwrap();
+ let borrow = &mut (*left).borrow_mut();
+ assert!(!has_children(borrow));
+ let addend = *to_value(&to_children(explode_borrow)[0].borrow());
+ *to_value_mut(borrow) += addend;
+ }
+
+ let right = find_right(&explode);
+ if right.is_some() {
+ let right = right.unwrap();
+ let borrow = &mut (*right).borrow_mut();
+ assert!(!has_children(borrow));
+ let addend = *to_value(&to_children(explode_borrow)[1].borrow());
+ *to_value_mut(borrow) += addend;
+ }
+ }
+
+ let explode_borrow = &mut explode.borrow_mut();
+ explode_borrow.data = NodeData::Value(0);
+
+ continue;
+ }
+
+ let split = find_split_num(top);
+ if split.is_some() {
+ aoc::debugln!("SPLIT");
+
+ let split = split.unwrap();
+
+ let old = {
+ let split_borrow = &split.borrow();
+ *to_value(split_borrow)
+ };
+
+ let leftv = f32::floor((old as f32) / 2.0) as usize;
+ let left = value_entry(leftv, Some(split.clone()));
+
+ let rightv = f32::ceil((old as f32) / 2.0) as usize;
+ let right = value_entry(rightv, Some(split.clone()));
+
+ (*split).borrow_mut().data = NodeData::Children(vec![left, right]);
+
+ continue;
+ }
+
+ break;
+ }
+}
+
+fn snail_magnitude(top: &mut Rc<RefCell<Node>>) -> usize {
+ let mut values: Vec<usize> = Vec::new();
+
+ for (pos,_) in tree_iter(top) {
+ match &pos.borrow().data {
+ NodeData::Value(v) => {
+ values.push(*v);
+ },
+ NodeData::Children(_) => {
+ let right = values.pop().unwrap();
+ let left = values.pop().unwrap();
+ values.push(3 * left + 2 * right);
+ }
+ }
+ }
+
+ assert!(values.len() == 1);
+ return *values.first().unwrap();
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let mut top: Option<Rc<RefCell<Node>>> = None;
+ for line in aoc.input.lines() {
+ if line.is_empty() { continue; }
+ if top.is_none() {
+ let snail = parse_snail(line);
+ snail_print("FIRST", &snail);
+ top = Some(snail);
+ } else {
+ let addend = parse_snail(line);
+ snail_print("ADDEND", &addend);
+ top = Some(snail_add(top.unwrap(), addend, None));
+ snail_print("ADDED", &top.as_ref().unwrap());
+ }
+ snail_reduce(top.as_ref().unwrap());
+ snail_print("REDUCED", &top.as_ref().unwrap());
+ }
+
+ let answer = snail_magnitude(&mut top.unwrap());
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("4173");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let lines: Vec<String> = aoc.input.lines()
+ .filter(|x| !x.is_empty()).map(|x| x.to_string()).collect();
+ let mut answer: usize = 0;
+ for l1i in 0..lines.len() {
+ for l2i in 0..lines.len() {
+ if l1i == l2i { continue; }
+ let n1 = parse_snail(&lines[l1i]);
+ let n2 = parse_snail(&lines[l2i]);
+ let mut res = Some(snail_add(n1, n2, None));
+ snail_reduce(res.as_ref().unwrap());
+ let mag = snail_magnitude(res.as_mut().unwrap());
+ answer = usize::max(answer, mag);
+ }
+ }
+
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("4706");
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/18/test1 b/src/18/test1
@@ -0,0 +1,5 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+
diff --git a/src/18/test2 b/src/18/test2
@@ -0,0 +1,2 @@
+[[[[4,3],4],4],[7,[[8,4],9]]]
+[1,1]
