summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJustin Wernick <justin@worthe-it.co.za>2021-12-18 23:56:51 +0200
committerJustin Wernick <justin@worthe-it.co.za>2021-12-18 23:56:51 +0200
commit57f08cb8e8662283d14757dc7ee99811216d5f55 (patch)
tree4078aad3cb68dab8c2afbba077fb79fc9001b62d
parent14d2607863d653b6b367e76955bbdde085340738 (diff)
Day 18
-rw-r--r--inputs/day_18.txt100
-rw-r--r--src/bin/day_18.rs193
2 files changed, 293 insertions, 0 deletions
diff --git a/inputs/day_18.txt b/inputs/day_18.txt
new file mode 100644
index 0000000..cc88c31
--- /dev/null
+++ b/inputs/day_18.txt
@@ -0,0 +1,100 @@
+[[[0,6],[[8,9],[3,7]]],[[[3,4],[7,0]],[[6,9],[4,8]]]]
+[[2,2],[[[7,7],5],[[0,7],2]]]
+[6,[9,[[7,9],7]]]
+[[[[5,1],[9,3]],8],[4,[2,[6,6]]]]
+[[[4,3],[0,4]],[[[4,5],[9,3]],3]]
+[[[[2,7],7],[[6,5],6]],[[[2,3],[7,9]],[0,3]]]
+[[[3,[6,2]],[7,[9,4]]],3]
+[[[[9,3],4],[3,9]],8]
+[[[7,8],[[2,6],1]],[[[1,7],5],[[5,6],[6,1]]]]
+[[[[0,7],9],[[6,6],[8,4]]],[[[9,2],[4,8]],[[8,5],[0,6]]]]
+[[6,[[5,6],[3,8]]],[[8,9],[4,3]]]
+[[[[0,6],1],[[2,4],[1,4]]],[[7,5],[8,3]]]
+[[[[0,7],1],[[5,7],7]],[[[3,3],[6,7]],[[2,8],[2,9]]]]
+[[7,7],[[1,[3,7]],9]]
+[[8,[[3,0],0]],[[[8,3],0],9]]
+[[[[6,2],[2,6]],3],[6,[[4,7],2]]]
+[[[5,[2,3]],[8,[8,7]]],[[0,0],2]]
+[[1,6],[7,[7,[9,0]]]]
+[[[7,[7,6]],[7,4]],[[7,2],[6,5]]]
+[1,[[8,[9,5]],2]]
+[[[[8,2],[6,5]],[4,[9,2]]],[[0,[2,6]],[6,6]]]
+[[1,[[7,2],5]],[[[6,0],[8,1]],8]]
+[[[[0,6],[6,6]],2],[[4,2],[2,4]]]
+[[5,[9,0]],[2,5]]
+[7,[[9,7],[[9,9],4]]]
+[[5,[[6,4],7]],[8,[[4,4],[9,0]]]]
+[2,[[[3,2],[1,9]],[[3,8],[7,5]]]]
+[[[[8,2],0],[5,[4,3]]],0]
+[[[0,[7,8]],[[9,6],7]],[[7,[1,0]],[[0,3],7]]]
+[[[[8,3],0],[[4,8],[7,9]]],[[7,1],[[8,4],[4,4]]]]
+[[[2,0],[[6,6],7]],[[2,[3,9]],[[5,6],[4,6]]]]
+[[[[1,4],8],[9,6]],8]
+[[7,[9,1]],[1,[[8,5],[6,8]]]]
+[8,[[2,6],5]]
+[[[9,[7,8]],[[7,8],6]],3]
+[1,[[[2,1],7],[[2,6],7]]]
+[[7,[4,[6,1]]],[[[4,9],8],[[0,1],[1,7]]]]
+[[[7,9],[[2,6],[2,4]]],[[2,[1,7]],[[3,9],[8,9]]]]
+[[[[4,5],[4,7]],[[4,0],[9,9]]],0]
+[3,[[[6,9],2],[5,3]]]
+[1,[8,[[0,8],[1,3]]]]
+[[[7,[9,2]],[4,[0,3]]],2]
+[3,[[[7,7],6],[[8,4],1]]]
+[[[[6,3],[2,6]],[[6,9],[8,1]]],[[[2,1],[7,5]],[[7,3],[7,3]]]]
+[[[1,6],[[5,1],[5,0]]],[[1,0],[6,9]]]
+[[[[8,6],[3,3]],[[2,1],[4,1]]],[1,[[7,7],[8,5]]]]
+[[1,5],[6,[[2,3],[2,4]]]]
+[[0,[7,[9,0]]],[9,0]]
+[[[5,[1,9]],[0,[9,8]]],[[[6,7],[6,3]],[8,1]]]
+[[[4,7],[6,[2,1]]],5]
+[[3,[4,0]],[2,[4,5]]]
+[[[4,0],[6,[8,3]]],[[0,6],8]]
+[[[[9,9],0],[[1,8],0]],[[1,6],[3,4]]]
+[[[[4,3],4],1],[0,[[2,1],[3,9]]]]
+[[[8,[6,2]],[6,0]],7]
+[[9,[6,[3,1]]],[[[5,9],0],[4,5]]]
+[4,[7,[[2,5],4]]]
+[[2,[8,[2,9]]],[[[0,1],[3,5]],1]]
+[[[7,9],[7,3]],[[1,[7,1]],[1,2]]]
+[[[7,0],[[1,0],8]],[[9,[7,6]],[9,[7,2]]]]
+[[[8,1],[[0,6],2]],[9,[[1,8],[5,4]]]]
+[6,[[[9,5],[5,4]],3]]
+[[4,[[6,8],[8,3]]],[[9,[0,9]],7]]
+[[[6,9],[[2,3],8]],[[9,[5,1]],[[7,6],5]]]
+[[0,1],5]
+[[4,[1,9]],[[8,0],8]]
+[[5,[0,6]],[1,8]]
+[[[[9,2],7],7],[4,[1,[5,6]]]]
+[[7,[9,[6,5]]],[[6,9],1]]
+[[[5,2],[0,[1,4]]],[[0,4],[[9,4],8]]]
+[[[[7,1],[4,9]],3],[[[4,5],8],[7,[0,4]]]]
+[[[9,[8,0]],7],[[[4,5],8],[[4,3],[8,5]]]]
+[[9,[7,0]],[[3,[1,7]],[[7,0],7]]]
+[[2,[[6,2],6]],8]
+[[[8,[9,6]],[[5,8],[7,2]]],[4,[9,9]]]
+[[[[0,5],0],[[8,4],4]],[[7,9],8]]
+[[[0,[0,3]],[0,[8,8]]],[[[2,1],3],4]]
+[0,[[4,1],[[9,9],2]]]
+[[3,[7,[6,7]]],[0,2]]
+[7,2]
+[0,[3,[[3,4],[4,4]]]]
+[[[[0,1],[5,9]],[[4,2],7]],[5,[1,8]]]
+[[7,1],[[1,[9,9]],[[8,4],8]]]
+[[[1,[8,3]],[[3,7],0]],[[2,0],[[1,6],[9,9]]]]
+[[[1,4],[1,4]],[[2,[2,7]],[2,[7,1]]]]
+[[1,[[6,8],[8,6]]],[0,[8,0]]]
+[1,[[2,0],7]]
+[[[[6,0],9],[[6,9],[8,3]]],[[3,[9,9]],6]]
+[[[[9,8],[2,8]],[2,3]],[6,2]]
+[[[6,[2,2]],7],[[3,[7,8]],7]]
+[[[5,[3,7]],1],[[[4,0],3],[5,4]]]
+[[[7,[4,3]],[9,[4,4]]],7]
+[[2,[[1,5],6]],[[2,3],[[2,5],[7,1]]]]
+[[[[3,9],[1,9]],3],[5,[[0,6],[3,2]]]]
+[[[3,[7,5]],[[7,7],[2,8]]],[4,[1,[0,0]]]]
+[[4,[2,[8,7]]],[[[0,5],0],9]]
+[9,[9,[6,4]]]
+[[5,[[4,9],2]],[9,9]]
+[[1,[[6,0],[9,9]]],[[[8,4],1],[[5,2],[6,1]]]]
+[[1,[[9,0],8]],6]
diff --git a/src/bin/day_18.rs b/src/bin/day_18.rs
new file mode 100644
index 0000000..b77f1f1
--- /dev/null
+++ b/src/bin/day_18.rs
@@ -0,0 +1,193 @@
+use nom::{
+ branch::alt,
+ character::complete::{char as nom_char, line_ending, u8 as nom_u8},
+ combinator::map,
+ multi::separated_list1,
+ sequence::tuple,
+ IResult,
+};
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+ let input = fs::read_to_string("inputs/day_18.txt")?;
+ let snail_nums = parse_snail_nums(&input).unwrap().1;
+ {
+ let mut snail_nums_iter = snail_nums.clone().into_iter();
+ let sum = snail_nums_iter
+ .next()
+ .map(|first_num| snail_nums_iter.fold(first_num, |acc, next| acc + next))
+ .expect("Expected at least one snail number");
+
+ dbg!(&sum);
+ dbg!(sum.magnitude());
+ }
+
+ let mut max_magnitude = 0;
+ for i in 0..snail_nums.len() {
+ for j in 0..snail_nums.len() {
+ if i != j {
+ let new_magnitude = (snail_nums[i].clone() + snail_nums[j].clone()).magnitude();
+ if new_magnitude > max_magnitude {
+ max_magnitude = new_magnitude;
+ }
+ }
+ }
+ }
+ dbg!(max_magnitude);
+
+ Ok(())
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum SnailNum {
+ Regular(u8),
+ Pair(Box<SnailNum>, Box<SnailNum>),
+}
+
+impl Default for SnailNum {
+ fn default() -> SnailNum {
+ SnailNum::Regular(0)
+ }
+}
+
+#[derive(PartialEq, Eq)]
+enum NormalizeResult {
+ AlreadyNormalized,
+ NormalizeActionHandledInternally,
+ Explode(u8, u8),
+}
+
+impl SnailNum {
+ fn unwrap_val(&self) -> u8 {
+ match self {
+ SnailNum::Regular(val) => *val,
+ SnailNum::Pair(_, _) => panic!("unwrapped the val on a pair"),
+ }
+ }
+ fn add_to_left(&mut self, add: u8) {
+ match self {
+ Self::Regular(val) => *val += add,
+ Self::Pair(left, _) => left.add_to_left(add),
+ }
+ }
+ fn add_to_right(&mut self, add: u8) {
+ match self {
+ Self::Regular(val) => *val += add,
+ Self::Pair(_, right) => right.add_to_right(add),
+ }
+ }
+ fn normalize_split_pass(&mut self) -> NormalizeResult {
+ match self {
+ Self::Regular(val) => {
+ if *val > 9 {
+ let half = *val / 2;
+ *self = SnailNum::Pair(
+ Box::new(SnailNum::Regular(half)),
+ Box::new(SnailNum::Regular(if *val % 2 == 0 {
+ half
+ } else {
+ half + 1
+ })),
+ );
+ return NormalizeResult::NormalizeActionHandledInternally;
+ }
+ }
+ Self::Pair(left, right) => {
+ match left.normalize_split_pass() {
+ NormalizeResult::AlreadyNormalized => {}
+ _ => {
+ return NormalizeResult::NormalizeActionHandledInternally;
+ }
+ }
+ match right.normalize_split_pass() {
+ NormalizeResult::AlreadyNormalized => {}
+ _ => {
+ return NormalizeResult::NormalizeActionHandledInternally;
+ }
+ }
+ }
+ }
+ NormalizeResult::AlreadyNormalized
+ }
+ fn normalize_explode_pass(&mut self, current_depth: u8) -> NormalizeResult {
+ match self {
+ Self::Regular(_val) => {}
+ Self::Pair(left, right) => {
+ if current_depth >= 4 {
+ let result = NormalizeResult::Explode(left.unwrap_val(), right.unwrap_val());
+ *self = SnailNum::Regular(0);
+ return result;
+ }
+ match left.normalize_explode_pass(current_depth + 1) {
+ NormalizeResult::AlreadyNormalized => {}
+ NormalizeResult::NormalizeActionHandledInternally => {
+ return NormalizeResult::NormalizeActionHandledInternally;
+ }
+ NormalizeResult::Explode(leftadd, rightadd) => {
+ right.add_to_left(rightadd);
+ return NormalizeResult::Explode(leftadd, 0);
+ }
+ }
+ match right.normalize_explode_pass(current_depth + 1) {
+ NormalizeResult::AlreadyNormalized => {}
+ NormalizeResult::NormalizeActionHandledInternally => {
+ return NormalizeResult::NormalizeActionHandledInternally;
+ }
+ NormalizeResult::Explode(leftadd, rightadd) => {
+ left.add_to_right(leftadd);
+ return NormalizeResult::Explode(0, rightadd);
+ }
+ }
+ }
+ }
+ NormalizeResult::AlreadyNormalized
+ }
+
+ fn normalize(&mut self) {
+ let mut normalized = false;
+ while !normalized {
+ let explode_result = self.normalize_explode_pass(0);
+ if explode_result == NormalizeResult::AlreadyNormalized {
+ let split_result = self.normalize_split_pass();
+ if split_result == NormalizeResult::AlreadyNormalized {
+ normalized = true;
+ }
+ }
+ }
+ }
+ fn magnitude(&self) -> u64 {
+ match self {
+ Self::Regular(val) => *val as u64,
+ Self::Pair(left, right) => 3 * left.magnitude() + 2 * right.magnitude(),
+ }
+ }
+}
+
+impl std::ops::Add<SnailNum> for SnailNum {
+ type Output = SnailNum;
+ fn add(self, other: SnailNum) -> SnailNum {
+ let mut result = SnailNum::Pair(Box::new(self), Box::new(other));
+ result.normalize();
+ result
+ }
+}
+
+fn parse_snail_nums(input: &str) -> IResult<&str, Vec<SnailNum>> {
+ separated_list1(line_ending, parse_snail_num)(input)
+}
+
+fn parse_snail_num(input: &str) -> IResult<&str, SnailNum> {
+ alt((
+ map(nom_u8, SnailNum::Regular),
+ map(
+ tuple((
+ nom_char('['),
+ parse_snail_num,
+ nom_char(','),
+ parse_snail_num,
+ nom_char(']'),
+ )),
+ |(_, left, _, right, _)| SnailNum::Pair(Box::new(left), Box::new(right)),
+ ),
+ ))(input)
+}