day 18

3 files changed, 338 insertions, 0 deletions

diff --git a/data/2021/18.txt b/data/2021/18.txt
new file mode 100644
index 0000000..c796c20
--- /dev/null
+++ b/data/2021/18.txt
@@ -0,0 +1,100 @@
+[[[7,[9,4]],[5,8]],7]
+[[[[9,3],[9,0]],[[1,9],2]],4]
+[2,[[[0,6],3],[7,6]]]
+[4,[[[8,9],[4,2]],[[6,8],[2,7]]]]
+[[6,[6,[6,8]]],[[[8,7],8],8]]
+[[5,[[2,7],3]],[[[4,6],9],9]]
+[[8,1],[9,7]]
+[[[[9,3],[8,1]],[[6,6],[7,4]]],[[9,[9,8]],[6,3]]]
+[[[6,0],[1,[1,6]]],[2,[[9,4],7]]]
+[[[9,7],3],[[[8,4],[4,1]],[7,3]]]
+[[[3,7],[[0,0],[3,1]]],[6,[[2,4],6]]]
+[[[[3,0],3],[[9,2],[8,3]]],[[[5,3],[5,1]],[6,[4,6]]]]
+[[7,[[7,6],[4,5]]],[[5,[0,0]],[[9,7],3]]]
+[[[[0,0],8],[7,[6,0]]],[[[0,8],[7,5]],[[2,2],4]]]
+[[[[5,6],[7,9]],1],[[[0,2],[7,9]],[[6,2],6]]]
+[7,[0,5]]
+[[2,[7,8]],[[[3,0],0],[0,8]]]
+[[[[9,2],[4,8]],[1,[8,3]]],[[6,1],[[1,5],[7,3]]]]
+[[[[7,1],6],[3,5]],[[8,[3,8]],[7,3]]]
+[[[[1,7],8],0],[2,[[4,1],9]]]
+[[[[9,2],0],0],[[1,[9,5]],3]]
+[[1,[3,5]],7]
+[[[[7,5],[4,1]],[[6,9],1]],[[0,8],[1,[4,2]]]]
+[[6,[0,[5,4]]],[[4,[6,1]],3]]
+[[[[5,8],4],[0,[1,5]]],[[[0,1],9],[[2,1],6]]]
+[[[[9,5],3],[[1,6],6]],[9,[[1,4],[6,1]]]]
+[[8,[[7,8],[6,1]]],[1,8]]
+[[3,[[6,1],[2,7]]],[0,[3,[1,7]]]]
+[[[[3,3],0],[[6,5],8]],[[[8,3],3],[5,[3,9]]]]
+[[[1,6],9],[[9,4],1]]
+[[[[5,3],[4,3]],[3,5]],[[4,[9,8]],[2,[8,5]]]]
+[[[[7,3],6],7],[[[1,4],9],[3,[7,0]]]]
+[[0,5],[[[4,3],7],[8,[0,3]]]]
+[6,[[[9,4],2],[[8,4],[5,7]]]]
+[[9,[2,[1,7]]],[4,[[7,2],3]]]
+[9,[5,[[9,7],[0,5]]]]
+[[[[1,6],1],[[2,3],[3,3]]],[[5,[8,6]],[[1,3],[8,9]]]]
+[[3,0],[[4,1],[6,[5,7]]]]
+[[[[3,3],[9,0]],[1,[0,0]]],[0,[[6,6],[1,1]]]]
+[[[4,6],[[9,2],[0,5]]],0]
+[9,[[5,5],[8,[4,1]]]]
+[[[[9,2],[9,9]],[[8,7],3]],0]
+[[2,5],[4,8]]
+[[[[9,1],8],[1,2]],[7,[[7,2],5]]]
+[2,7]
+[[[[0,3],0],0],[[1,8],[[5,3],1]]]
+[[[9,8],5],[[0,2],[4,[2,4]]]]
+[[3,[9,[9,4]]],[3,[[3,0],7]]]
+[[6,[5,1]],[4,7]]
+[[5,[8,[4,1]]],[8,[[1,8],[1,7]]]]
+[2,[[7,5],[[9,1],6]]]
+[0,[4,[2,2]]]
+[7,[[[9,5],[7,4]],[[5,0],[5,0]]]]
+[8,[[[5,3],3],[5,[2,0]]]]
+[[[[3,7],7],[[6,0],3]],[[[5,4],8],[[9,3],[2,9]]]]
+[[[[8,1],3],[[8,4],[3,0]]],[2,6]]
+[7,[9,7]]
+[[[[4,9],9],0],[[[3,8],[6,9]],0]]
+[[[[6,1],0],[[5,2],9]],4]
+[[[4,1],[[8,5],8]],[[7,[9,4]],[[7,8],[0,9]]]]
+[[0,2],5]
+[[[5,[7,5]],[6,[7,3]]],[[[7,2],[7,5]],[[3,1],6]]]
+[[[[5,1],[9,1]],[[3,2],[6,7]]],[8,[[3,5],8]]]
+[[[4,[3,9]],[5,1]],[5,[[2,4],[9,0]]]]
+[5,[[[8,5],5],1]]
+[[[7,7],[[8,7],7]],[[9,2],[[3,5],[8,0]]]]
+[[[[2,0],0],[[8,5],7]],[[[3,4],[8,1]],1]]
+[[6,[[0,7],[1,9]]],[[[5,0],5],[7,[1,5]]]]
+[[[0,[6,9]],[6,[9,4]]],[3,1]]
+[[8,[2,9]],[5,[6,9]]]
+[[[[9,4],[7,8]],8],[[[0,3],[8,8]],[[1,7],[8,2]]]]
+[[[[9,5],[0,6]],[6,[3,5]]],5]
+[[[[3,0],[4,9]],[5,4]],[5,[[1,2],[0,3]]]]
+[[[[9,3],8],8],[2,9]]
+[5,[[[8,4],[8,0]],[[9,2],[7,6]]]]
+[[[[4,8],2],[4,0]],[[1,[2,1]],[0,[0,7]]]]
+[3,[[[8,5],[8,6]],2]]
+[[[3,[1,2]],9],[7,[2,[0,6]]]]
+[[[[8,3],1],9],6]
+[[2,[6,8]],[[6,9],[1,[4,9]]]]
+[[[[5,9],3],[9,6]],[[[9,9],6],6]]
+[[[[1,6],1],[2,[8,7]]],[4,[[7,6],3]]]
+[[3,[8,[8,6]]],[[[2,0],3],6]]
+[[[1,[6,5]],6],[7,[3,6]]]
+[[2,[[8,3],3]],[[0,[3,4]],[5,[2,9]]]]
+[[[9,4],[4,[0,1]]],[4,[3,5]]]
+[[[5,[7,3]],[[7,5],[8,9]]],5]
+[[[1,4],[4,5]],[[[4,8],4],0]]
+[[[[9,2],2],[3,0]],[[[4,6],3],[0,7]]]
+[[[[2,2],[0,4]],6],3]
+[[[4,[6,2]],[3,[3,4]]],[[[1,1],0],[0,9]]]
+[[[[8,2],[5,4]],[[4,4],8]],[4,[5,[6,4]]]]
+[[[7,[2,4]],[6,[2,6]]],[[7,6],8]]
+[[[[2,6],3],[6,[2,8]]],2]
+[[[2,[2,9]],[4,[9,0]]],[[8,0],[[4,1],4]]]
+[2,[3,[1,8]]]
+[[[5,9],[[3,4],[1,9]]],[[6,[9,2]],6]]
+[[[[1,5],[2,8]],[[4,1],3]],[[1,[6,3]],[[9,7],8]]]
+[[[[7,8],9],4],2]
+[[[0,[6,8]],6],5]
diff --git a/src/2021/18/mod.rs b/src/2021/18/mod.rs
new file mode 100644
index 0000000..8565069
--- /dev/null
+++ b/src/2021/18/mod.rs
@@ -0,0 +1,234 @@
+#![allow(clippy::collapsible_else_if)]
+
+#[derive(Clone)]
+enum Number {
+    Value(u8),
+    Pair(Box<Number>, Box<Number>),
+}
+
+impl Number {
+    fn parse(s: &str) -> Self {
+        if s.starts_with('[') {
+            Self::parse_pair(s)
+        } else {
+            Self::parse_number(s)
+        }
+    }
+
+    fn parse_pair(s: &str) -> Self {
+        let mut depth = 1;
+        let mut start = 1;
+        let mut children = vec![];
+        for (i, c) in s.chars().enumerate().skip(1) {
+            match c {
+                '[' => {
+                    depth += 1;
+                }
+                ',' => {
+                    if depth == 1 {
+                        children.push(Self::parse(&s[start..i]));
+                        start = i + 1;
+                    }
+                }
+                ']' => {
+                    depth -= 1;
+                }
+                _ => {}
+            }
+            if depth == 0 {
+                children.push(Self::parse(&s[start..i]));
+                break;
+            }
+        }
+        let right = children.pop().unwrap();
+        let left = children.pop().unwrap();
+        Self::Pair(Box::new(left), Box::new(right))
+    }
+
+    fn parse_number(s: &str) -> Self {
+        Self::Value(s.as_bytes()[0] - b'0')
+    }
+
+    fn reduce(&mut self) {
+        loop {
+            if !self.visit_explode() && !self.visit_split() {
+                break;
+            }
+        }
+    }
+
+    fn visit_explode(&mut self) -> bool {
+        let mut idx = 0;
+        if let Some((explode_idx, (left, right))) =
+            self.find_to_explode(0, &mut idx)
+        {
+            idx = 0;
+            self.explode(explode_idx, left, right, &mut idx);
+            true
+        } else {
+            false
+        }
+    }
+
+    fn find_to_explode(
+        &mut self,
+        depth: usize,
+        idx: &mut usize,
+    ) -> Option<(usize, (u8, u8))> {
+        match self {
+            Self::Value(_) => {
+                *idx += 1;
+                None
+            }
+            Self::Pair(left, right) => {
+                if depth == 4 {
+                    let left = if let Self::Value(n) = **left {
+                        n
+                    } else {
+                        panic!("unexpected pair")
+                    };
+                    let right = if let Self::Value(n) = **right {
+                        n
+                    } else {
+                        panic!("unexpected pair")
+                    };
+                    *self = Self::Value(0);
+                    Some((*idx, (left, right)))
+                } else {
+                    left.find_to_explode(depth + 1, idx)
+                        .or_else(|| right.find_to_explode(depth + 1, idx))
+                }
+            }
+        }
+    }
+
+    fn explode(
+        &mut self,
+        explode_idx: usize,
+        left_val: u8,
+        right_val: u8,
+        idx: &mut usize,
+    ) {
+        match self {
+            Self::Value(ref mut n) => {
+                if *idx + 1 == explode_idx {
+                    *n += left_val;
+                } else if *idx == explode_idx + 1 {
+                    *n += right_val;
+                }
+                *idx += 1;
+            }
+            Self::Pair(left, right) => {
+                left.explode(explode_idx, left_val, right_val, idx);
+                right.explode(explode_idx, left_val, right_val, idx);
+            }
+        }
+    }
+
+    fn visit_split(&mut self) -> bool {
+        match self {
+            Self::Value(n) => {
+                if *n >= 10 {
+                    *self = Self::Pair(
+                        Box::new(Self::Value(*n / 2)),
+                        Box::new(Self::Value(*n - *n / 2)),
+                    );
+                    true
+                } else {
+                    false
+                }
+            }
+            Self::Pair(left, right) => {
+                left.visit_split() || right.visit_split()
+            }
+        }
+    }
+
+    fn magnitude(&self) -> i64 {
+        match self {
+            Self::Value(n) => i64::from(*n),
+            Self::Pair(left, right) => {
+                left.magnitude() * 3 + right.magnitude() * 2
+            }
+        }
+    }
+}
+
+impl std::ops::Add for Number {
+    type Output = Number;
+    fn add(self, other: Number) -> Self::Output {
+        let mut ret = Number::Pair(Box::new(self), Box::new(other));
+        ret.reduce();
+        ret
+    }
+}
+
+impl std::ops::Add for &Number {
+    type Output = Number;
+    fn add(self, other: &Number) -> Self::Output {
+        let mut ret =
+            Number::Pair(Box::new(self.clone()), Box::new(other.clone()));
+        ret.reduce();
+        ret
+    }
+}
+
+impl std::ops::AddAssign for Number {
+    fn add_assign(&mut self, other: Number) {
+        *self = self.clone() + other;
+    }
+}
+
+impl std::iter::Sum for Number {
+    fn sum<I>(mut iter: I) -> Self
+    where
+        I: Iterator<Item = Self>,
+    {
+        if let Some(first) = iter.next() {
+            let mut sum = first;
+            for num in iter {
+                sum += num;
+            }
+            sum
+        } else {
+            Number::Value(0)
+        }
+    }
+}
+
+impl std::fmt::Display for Number {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> Result<(), std::fmt::Error> {
+        match self {
+            Self::Value(n) => write!(f, "{}", n),
+            Self::Pair(left, right) => {
+                write!(f, "[{},{}]", left, right)
+            }
+        }
+    }
+}
+
+pub fn part1() -> anyhow::Result<i64> {
+    let sum: Number = data_lines!()?.map(|line| Number::parse(&line)).sum();
+    Ok(sum.magnitude())
+}
+
+pub fn part2() -> anyhow::Result<i64> {
+    let nums: Vec<_> =
+        data_lines!()?.map(|line| Number::parse(&line)).collect();
+    let mut max = 0;
+    for (i, n1) in nums.iter().enumerate() {
+        for (j, n2) in nums.iter().enumerate() {
+            if i == j {
+                continue;
+            }
+            let magnitude = (n1 + n2).magnitude();
+            if magnitude > max {
+                max = magnitude;
+            }
+        }
+    }
+    Ok(max)
+}
diff --git a/src/2021/mod.rs b/src/2021/mod.rs
index e31d57e..b66f03e 100644
--- a/src/2021/mod.rs
+++ b/src/2021/mod.rs
@@ -32,6 +32,8 @@ mod day15;
 mod day16;
 #[path = "17/mod.rs"]
 mod day17;
+#[path = "18/mod.rs"]
+mod day18;
 // NEXT MOD
 
 pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
@@ -70,6 +72,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> {
         (16, 2) => day16::part2(),
         (17, 1) => day17::part1(),
         (17, 2) => day17::part2(),
+        (18, 1) => day18::part1(),
+        (18, 2) => day18::part2(),
         // NEXT PART
         _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)),
     }