commit 621e1341fae3ec25714d1719caa590af0d012a0a
parent c6a137276db40b5d7989702f7541aa95bfb29bfd
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sat, 18 Dec 2021 12:10:22 -0600
Add 2021 day 18
Diffstat:
| A | 2021/day18/input.txt | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day18/main.rs | | | 181 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 281 insertions(+), 0 deletions(-)
diff --git a/2021/day18/input.txt b/2021/day18/input.txt
@@ -0,0 +1,100 @@
+[[[[3,0],[0,0]],1],4]
+[[[[3,4],0],[7,7]],[1,6]]
+[[[[2,0],5],7],[[[3,1],[2,6]],[[0,8],6]]]
+[[[[5,5],0],1],[[[0,0],1],[[0,6],[0,9]]]]
+[[0,[0,[1,7]]],[3,[1,[7,6]]]]
+[[[9,[5,2]],[[5,2],[6,8]]],[[[7,0],7],[[2,3],[9,4]]]]
+[[[[3,8],7],[[0,7],[2,0]]],[0,[[2,9],0]]]
+[[[7,[2,2]],[3,4]],[6,7]]
+[8,[[[3,3],8],[[7,1],[6,7]]]]
+[[9,[9,8]],[[1,[9,1]],[2,5]]]
+[[[7,8],[[1,2],[2,6]]],[[9,7],[6,[7,0]]]]
+[[[3,3],[[5,6],5]],[[[2,8],1],9]]
+[[[2,[5,0]],[[9,9],[4,0]]],[0,5]]
+[[[9,3],[[9,4],[5,8]]],[[[3,2],[7,1]],[[3,8],1]]]
+[[3,2],[[6,[0,9]],[8,3]]]
+[[[5,7],[[7,4],[4,6]]],[[[9,8],3],3]]
+[[[4,[2,8]],9],[[[8,5],[9,7]],[[8,9],[2,6]]]]
+[[[1,[2,4]],6],[[8,[5,2]],[[0,7],[4,1]]]]
+[[[[4,3],6],[[6,4],[4,2]]],[[9,0],[[5,9],9]]]
+[[[[3,0],6],[4,[7,5]]],4]
+[[[[1,0],[7,1]],0],[[[8,5],8],2]]
+[[[[2,9],[4,1]],[[8,9],[3,3]]],[9,[[0,7],2]]]
+[[1,[4,[4,2]]],[[[3,5],[8,8]],2]]
+[[[8,[1,4]],[[6,5],5]],[[7,[4,7]],4]]
+[[[[0,5],2],[[9,2],0]],0]
+[[[[6,2],[2,4]],[0,[7,3]]],[9,[8,[5,9]]]]
+[[8,0],2]
+[[[[0,2],2],[[9,2],[8,1]]],[[[7,6],[5,3]],6]]
+[[[[8,7],[5,3]],[[3,0],8]],[[[8,4],[2,2]],[[8,1],2]]]
+[[[[1,5],[4,6]],[[4,0],[2,4]]],[[1,1],[[0,7],[7,3]]]]
+[[7,2],[[7,[6,7]],[8,5]]]
+[[[9,7],[[6,6],9]],8]
+[[4,2],[[[1,0],[9,1]],[[0,7],[8,0]]]]
+[[[[5,9],5],[8,9]],[[2,4],[[5,2],[8,3]]]]
+[[[[4,5],[7,0]],[4,5]],[[7,[6,4]],[[1,7],[6,3]]]]
+[[2,0],4]
+[[2,[[5,1],[2,1]]],[[5,[7,2]],[[2,3],[7,0]]]]
+[[4,[4,9]],[9,[6,8]]]
+[[[[6,1],[1,5]],[0,[4,0]]],[[[7,0],2],4]]
+[[[[3,3],[2,2]],[[2,4],2]],[[8,[1,1]],4]]
+[[[[1,5],8],[[9,4],[7,7]]],[[[8,7],[7,2]],[0,[7,3]]]]
+[9,[[7,[0,4]],4]]
+[4,[0,8]]
+[[[[2,6],1],[8,[8,4]]],[[8,2],[1,[8,4]]]]
+[[7,[8,[8,8]]],[4,1]]
+[[0,6],[[7,[5,9]],[[7,1],8]]]
+[4,6]
+[[[[3,2],[5,6]],[0,7]],[8,[7,[9,5]]]]
+[[[3,7],[4,5]],6]
+[[[0,[3,9]],[9,1]],6]
+[[[[7,3],8],[6,7]],[[1,0],[1,7]]]
+[[[5,[4,8]],2],[[[7,1],6],[[0,3],2]]]
+[[1,0],[[1,2],[[2,0],1]]]
+[[8,[[6,1],[7,1]]],0]
+[[9,[2,0]],[[7,[6,2]],4]]
+[[[9,[9,4]],[[4,8],3]],[[9,0],[[2,2],[0,6]]]]
+[[[7,5],[[2,9],6]],[[2,4],[[1,1],[8,2]]]]
+[[[1,[6,3]],[[2,2],[1,8]]],[[[7,3],[6,0]],[4,[7,6]]]]
+[6,5]
+[[3,[9,[4,4]]],[[6,9],[4,5]]]
+[[[4,[1,8]],[[4,0],6]],[[[9,0],[8,3]],[[8,6],[3,2]]]]
+[[[8,[1,2]],[[3,9],6]],[[3,0],1]]
+[[1,[2,[4,0]]],6]
+[0,[[[1,3],[9,1]],[[3,8],[9,4]]]]
+[2,[2,[[2,7],[7,8]]]]
+[[[3,0],[[4,6],2]],[9,2]]
+[[[5,[2,2]],[[2,7],[9,9]]],[[3,[4,4]],[8,[9,8]]]]
+[[[[7,5],[7,9]],[[8,5],6]],[[1,[8,4]],[8,2]]]
+[[[6,4],[5,5]],[[[8,1],5],[[6,4],[6,9]]]]
+[[[[8,9],0],[[4,6],7]],[[[3,9],[6,4]],[8,[7,4]]]]
+[4,[[7,7],4]]
+[[[[4,9],[1,2]],[8,[4,7]]],[[8,[4,8]],[0,[5,4]]]]
+[1,[7,9]]
+[[[5,[2,0]],[[4,3],[6,8]]],[9,9]]
+[[[[3,9],9],[4,3]],[1,[3,[8,1]]]]
+[[[[8,7],[6,1]],[3,9]],[5,[[8,0],4]]]
+[[[[8,2],[4,6]],[6,[9,9]]],[1,[[7,7],4]]]
+[[7,5],[[5,0],[0,3]]]
+[[[6,0],[9,1]],[[[4,3],[5,0]],[[9,5],[0,0]]]]
+[8,[[3,6],3]]
+[[[[9,3],7],[1,3]],[[[6,4],[8,4]],[1,5]]]
+[[[[3,8],2],[5,4]],[[[1,8],5],[2,[2,7]]]]
+[[2,9],[6,[0,2]]]
+[[2,[7,9]],[[4,1],[[9,2],[0,7]]]]
+[[0,[6,4]],[[9,2],[0,[0,7]]]]
+[[[[7,2],[8,6]],[6,2]],[[[1,6],[2,2]],1]]
+[[1,6],[[[4,3],[8,2]],[3,[9,4]]]]
+[[9,[7,3]],[[[7,0],4],[[1,7],[2,2]]]]
+[[7,[5,[9,8]]],[[[7,5],[7,6]],[7,[9,8]]]]
+[[[[6,1],[4,3]],4],[[[5,9],4],2]]
+[[[[5,1],[2,5]],0],[[7,[5,7]],[[4,4],9]]]
+[9,2]
+[4,[[[6,6],5],7]]
+[[8,[[7,3],[0,7]]],8]
+[[[3,4],[[2,3],0]],[[[9,6],[1,1]],[4,[0,4]]]]
+[[[[3,3],[2,3]],[2,5]],[[4,[2,7]],3]]
+[[[8,[0,3]],2],[4,4]]
+[[[3,5],[[2,1],[3,4]]],[[0,3],4]]
+[[[[4,1],4],2],[[[3,7],2],[[8,1],3]]]
+[[[[0,6],[7,3]],[5,[3,9]]],[7,[[4,1],8]]]
diff --git a/2021/day18/main.rs b/2021/day18/main.rs
@@ -0,0 +1,181 @@
+use std::collections::VecDeque;
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Pos {
+ Left,
+ Right,
+}
+
+impl Pos {
+ fn calc_mult(pos_stack: &VecDeque<Pos>) -> u64 {
+ pos_stack
+ .iter()
+ .map(|p| match p {
+ Self::Left => 3,
+ Self::Right => 2,
+ })
+ .product()
+ }
+}
+
+#[derive(Debug, Clone, Copy)]
+struct Snailfish {
+ value: u32,
+ depth: i32,
+ pos: Pos,
+}
+
+impl Snailfish {
+ fn parse(s: &str) -> Vec<Snailfish> {
+ let mut res = Vec::new();
+ let mut prev_char = None;
+ let mut curr_depth = 0;
+ for c in s.chars() {
+ match (prev_char, c.to_digit(10)) {
+ (Some('['), Some(v)) => res.push(Snailfish {
+ value: v,
+ depth: curr_depth,
+ pos: Pos::Left,
+ }),
+ (Some(','), Some(v)) => res.push(Snailfish {
+ value: v,
+ depth: curr_depth,
+ pos: Pos::Right,
+ }),
+ (_, None) => match c {
+ '[' => curr_depth += 1,
+ ']' => curr_depth -= 1,
+ _ => (),
+ },
+ _ => (),
+ }
+ prev_char = Some(c);
+ }
+ res
+ }
+
+ fn sum(a: &Vec<Snailfish>, b: &Vec<Snailfish>) -> Vec<Snailfish> {
+ let mut sum = a
+ .iter()
+ .chain(b.iter())
+ .map(|&v| v)
+ .collect::<Vec<Snailfish>>();
+ for v in sum.iter_mut() {
+ v.depth += 1;
+ }
+ Self::reduce(sum)
+ }
+
+ fn reduce(mut val: Vec<Snailfish>) -> Vec<Snailfish> {
+ loop {
+ let mut new_val = Vec::<Snailfish>::new();
+ let mut reduced = false;
+ // explode
+ let mut carry = 0;
+ for mut v in val.into_iter() {
+ if !reduced && v.pos == Pos::Right && v.depth > 4 {
+ reduced = true;
+ let left = new_val.pop().unwrap();
+ let mut pair_pos = Pos::Left;
+ if let Some(last) = new_val.last_mut() {
+ last.value += left.value;
+ if last.pos == Pos::Left && v.depth - 1 == last.depth {
+ pair_pos = Pos::Right;
+ }
+ }
+ new_val.push(Snailfish {
+ value: 0,
+ depth: v.depth - 1,
+ pos: pair_pos,
+ });
+ carry = v.value;
+ } else {
+ v.value += carry;
+ carry = 0;
+ new_val.push(v);
+ }
+ }
+ val = new_val;
+ if reduced {
+ continue;
+ }
+ // split
+ // need to be a separate loop as first rule only triggers on Right elem
+ let mut new_val = Vec::<Snailfish>::new();
+ for v in val.into_iter() {
+ if !reduced && v.value >= 10 {
+ reduced = true;
+ new_val.push(Snailfish {
+ value: v.value / 2,
+ depth: v.depth + 1,
+ pos: Pos::Left,
+ });
+ new_val.push(Snailfish {
+ value: (v.value + 1) / 2,
+ depth: v.depth + 1,
+ pos: Pos::Right,
+ });
+ } else {
+ new_val.push(v);
+ }
+ }
+ val = new_val;
+ if !reduced {
+ break;
+ }
+ }
+ val
+ }
+
+ fn magnitude(val: &Vec<Snailfish>) -> u64 {
+ let mut res = 0;
+ let mut pos = std::collections::VecDeque::<Pos>::new();
+ for v in val {
+ while pos.len() < v.depth as usize {
+ pos.push_back(Pos::Left);
+ }
+ *pos.back_mut().unwrap() = v.pos;
+ res += v.value as u64 * Pos::calc_mult(&pos);
+ while let Some(&Pos::Right) = pos.back() {
+ pos.pop_back();
+ }
+ if let Some(back) = pos.back_mut() {
+ *back = Pos::Right;
+ }
+ }
+ res
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| Snailfish::parse(s))
+ .collect::<Vec<Vec<_>>>();
+ // 4207
+ println!("Part 1: {}", part_1(&input));
+ // 4635
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn part_1(input: &Vec<Vec<Snailfish>>) -> u64 {
+ let sum = input
+ .clone()
+ .into_iter()
+ .reduce(|a, b| Snailfish::sum(&a, &b))
+ .unwrap();
+ Snailfish::magnitude(&sum)
+}
+
+fn part_2(input: &Vec<Vec<Snailfish>>) -> u64 {
+ let mut max_magnitude = 0;
+ for a in input.iter() {
+ for b in input.iter() {
+ max_magnitude = max_magnitude.max(Snailfish::magnitude(&Snailfish::sum(a, b)));
+ }
+ }
+
+ max_magnitude
+}