From 6d72191e2ce5d423ca03c894d2dad1d3061bd4f3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:27:29 +0200 Subject: Refile for merging repos --- 2021/src/bin/day_18.rs | 193 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 2021/src/bin/day_18.rs (limited to '2021/src/bin/day_18.rs') diff --git a/2021/src/bin/day_18.rs b/2021/src/bin/day_18.rs new file mode 100644 index 0000000..b77f1f1 --- /dev/null +++ b/2021/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> { + 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, Box), +} + +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 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> { + 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) +} -- cgit v1.2.3