diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2021-12-18 23:56:51 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2021-12-18 23:56:51 +0200 |
commit | 57f08cb8e8662283d14757dc7ee99811216d5f55 (patch) | |
tree | 4078aad3cb68dab8c2afbba077fb79fc9001b62d | |
parent | 14d2607863d653b6b367e76955bbdde085340738 (diff) |
Day 18
-rw-r--r-- | inputs/day_18.txt | 100 | ||||
-rw-r--r-- | src/bin/day_18.rs | 193 |
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) +} |