feat: impl day 11

5 files changed, 424 insertions, 1 deletions

diff --git a/aoc_2022/input/day_11.txt b/aoc_2022/input/day_11.txt
new file mode 100644
index 0000000..c567cb6
--- /dev/null
+++ b/aoc_2022/input/day_11.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 62, 92, 50, 63, 62, 93, 73, 50
+  Operation: new = old * 7
+  Test: divisible by 2
+    If true: throw to monkey 7
+    If false: throw to monkey 1
+
+Monkey 1:
+  Starting items: 51, 97, 74, 84, 99
+  Operation: new = old + 3
+  Test: divisible by 7
+    If true: throw to monkey 2
+    If false: throw to monkey 4
+
+Monkey 2:
+  Starting items: 98, 86, 62, 76, 51, 81, 95
+  Operation: new = old + 4
+  Test: divisible by 13
+    If true: throw to monkey 5
+    If false: throw to monkey 4
+
+Monkey 3:
+  Starting items: 53, 95, 50, 85, 83, 72
+  Operation: new = old + 5
+  Test: divisible by 19
+    If true: throw to monkey 6
+    If false: throw to monkey 0
+
+Monkey 4:
+  Starting items: 59, 60, 63, 71
+  Operation: new = old * 5
+  Test: divisible by 11
+    If true: throw to monkey 5
+    If false: throw to monkey 3
+
+Monkey 5:
+  Starting items: 92, 65
+  Operation: new = old * old
+  Test: divisible by 5
+    If true: throw to monkey 6
+    If false: throw to monkey 3
+
+Monkey 6:
+  Starting items: 78
+  Operation: new = old + 8
+  Test: divisible by 3
+    If true: throw to monkey 0
+    If false: throw to monkey 7
+
+Monkey 7:
+  Starting items: 84, 93, 54
+  Operation: new = old + 1
+  Test: divisible by 17
+    If true: throw to monkey 2
+    If false: throw to monkey 1
diff --git a/aoc_2022/input/day_11_example.txt b/aoc_2022/input/day_11_example.txt
new file mode 100644
index 0000000..30e09e5
--- /dev/null
+++ b/aoc_2022/input/day_11_example.txt
@@ -0,0 +1,27 @@
+Monkey 0:
+  Starting items: 79, 98
+  Operation: new = old * 19
+  Test: divisible by 23
+    If true: throw to monkey 2
+    If false: throw to monkey 3
+
+Monkey 1:
+  Starting items: 54, 65, 75, 74
+  Operation: new = old + 6
+  Test: divisible by 19
+    If true: throw to monkey 2
+    If false: throw to monkey 0
+
+Monkey 2:
+  Starting items: 79, 60, 97
+  Operation: new = old * old
+  Test: divisible by 13
+    If true: throw to monkey 1
+    If false: throw to monkey 3
+
+Monkey 3:
+  Starting items: 74
+  Operation: new = old + 3
+  Test: divisible by 17
+    If true: throw to monkey 0
+    If false: throw to monkey 1
diff --git a/aoc_2022/src/day_11.rs b/aoc_2022/src/day_11.rs
new file mode 100644
index 0000000..6741385
--- /dev/null
+++ b/aoc_2022/src/day_11.rs
@@ -0,0 +1,339 @@
+use std::{fmt::Display, str::FromStr};
+
+use anyhow::{anyhow, Context};
+use aoc::{Problem, Solution};
+
+use self::{Operator::*, Token::*};
+
+type WorryLevel = usize;
+
+#[derive(Debug, Clone)]
+struct Operation {
+    lhs: Token,
+    rhs: Token,
+    operator: Operator,
+}
+
+impl Operation {
+    fn evaluate(&self, old: usize) -> usize {
+        self.operator
+            .evaluate(self.lhs.evaluate(old), self.rhs.evaluate(old))
+    }
+}
+
+impl FromStr for Operation {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let mut tokens = s
+            .split('=')
+            .nth(1)
+            .context("missing rhs of `=`")?
+            .split_whitespace();
+
+        Ok(Operation {
+            lhs: tokens.next().context("missing lhs")?.parse()?,
+            operator: tokens.next().context("missing operator")?.parse()?,
+            rhs: tokens.next().context("missing rhs")?.parse()?,
+        })
+    }
+}
+
+impl Display for Operation {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self.operator {
+            Add => write!(f, "{} {}", self.operator, self.rhs),
+            Sub => write!(f, "{} {}", self.operator, self.rhs),
+            Mul => write!(f, "{} {}", self.operator, self.rhs),
+            Div => write!(f, "{} {}", self.operator, self.rhs),
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+enum Operator {
+    Add,
+    Sub,
+    Mul,
+    Div,
+}
+
+impl Operator {
+    fn evaluate(&self, lhs: usize, rhs: usize) -> usize {
+        match self {
+            Add => lhs + rhs,
+            Sub => lhs - rhs,
+            Mul => lhs * rhs,
+            Div => lhs / rhs,
+        }
+    }
+}
+
+impl FromStr for Operator {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        if s.len() > 1 {
+            Err(anyhow!("Invalid operator: {}", s))
+        } else {
+            s.chars().next().context("Missing operator")?.try_into()
+        }
+    }
+}
+
+impl Display for Operator {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Add => write!(f, "increased by"),
+            Sub => write!(f, "decreases by"),
+            Mul => write!(f, "multiplied by"),
+            Div => write!(f, "divided by"),
+        }
+    }
+}
+
+impl TryFrom<char> for Operator {
+    type Error = anyhow::Error;
+
+    fn try_from(value: char) -> Result<Self, Self::Error> {
+        match value {
+            '+' => Ok(Add),
+            '-' => Ok(Sub),
+            '*' => Ok(Mul),
+            '/' => Ok(Div),
+            c => Err(anyhow!("Invalid operator: {}", c)),
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+enum Token {
+    Old,
+    Number(usize),
+}
+
+impl Token {
+    fn evaluate(&self, old: usize) -> usize {
+        match self {
+            Old => old,
+            Number(n) => *n,
+        }
+    }
+}
+
+impl FromStr for Token {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        match s.trim() {
+            "old" => Ok(Old),
+            s if s.chars().all(|c| c.is_numeric()) => {
+                s.parse().map(Number).context("Failed to parse number")
+            }
+            s => return Err(anyhow!("unrecognized token: {s}")),
+        }
+    }
+}
+
+impl Display for Token {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Old => write!(f, "itself"),
+            Number(n) => write!(f, "{}", n),
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Test {
+    divisor: usize,
+    on_true: usize,
+    on_false: usize,
+}
+
+impl Test {
+    fn evaluate(&self, item: usize) -> (usize, usize) {
+        if (item % self.divisor) == 0 {
+            (item, self.on_true)
+        } else {
+            (item, self.on_false)
+        }
+    }
+}
+
+impl FromStr for Test {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let mut lines = s.lines().map(str::trim);
+
+        Ok(Test {
+            divisor: lines
+                .next()
+                .and_then(|s| s.strip_prefix("Test: divisible by "))
+                .context("missing test cond")?
+                .parse()?,
+            on_true: lines
+                .next()
+                .and_then(|s| s.strip_prefix("If true: throw to monkey "))
+                .context("missing if true")?
+                .parse()?,
+            on_false: lines
+                .next()
+                .and_then(|s| s.strip_prefix("If false: throw to monkey "))
+                .context("missing if false")?
+                .parse()?,
+        })
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Monkey {
+    id: usize,
+    items: Vec<WorryLevel>,
+    operation: Operation,
+    test: Test,
+    inspects: usize,
+}
+
+impl FromStr for Monkey {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let mut values = s.lines().map(str::trim);
+
+        Ok(Monkey {
+            id: values
+                .next()
+                .and_then(|s| s.strip_prefix("Monkey "))
+                .context("invalid id")?
+                .trim_matches(':')
+                .parse()?,
+            items: values
+                .next()
+                .and_then(|s| s.strip_prefix("Starting items: "))
+                .context("missing items")?
+                .split(", ")
+                .map(usize::from_str)
+                .collect::<Result<Vec<_>, _>>()?,
+            operation: values
+                .next()
+                .and_then(|s| s.strip_prefix("Operation: "))
+                .context("missing operation")?
+                .parse()?,
+            test: values.collect::<Vec<&str>>().join("\n").parse()?,
+            inspects: 0,
+        })
+    }
+}
+
+impl Display for Monkey {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        let items = self
+            .items
+            .iter()
+            .map(|i| i.to_string())
+            .collect::<Vec<String>>()
+            .join(", ");
+
+        write!(f, "Monkey {}: {}", self.id, items)?;
+
+        Ok(())
+    }
+}
+
+fn monkey_business(monkeys: &mut Vec<Monkey>, rounds: usize, reduce: impl Fn(usize) -> usize) {
+    for _ in 0..rounds {
+        for i in 0..monkeys.len() {
+            let mut throw_list = Vec::new();
+
+            let monkey = &mut monkeys[i];
+
+            while let Some(mut item) = monkey.items.pop() {
+                item = monkey.operation.evaluate(item);
+                item = reduce(item);
+                monkey.inspects += 1;
+                throw_list.push(monkey.test.evaluate(item));
+            }
+
+            for (item, dest) in throw_list {
+                let monkey = &mut monkeys[dest];
+                // println!("throwing {} to {}", item, monkey.id);
+                monkey.items.push(item);
+            }
+        }
+    }
+}
+
+pub struct Day11;
+
+impl Problem for Day11 {
+    const DAY: u8 = 11;
+
+    const INPUT: &'static str = include_str!("../input/day_11.txt");
+}
+
+impl Solution for Day11 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> {
+        let mut monkeys: Vec<Monkey> = input
+            .split("\n\n")
+            .map(Monkey::from_str)
+            .collect::<anyhow::Result<Vec<_>>>()?;
+
+        monkey_business(&mut monkeys, 20, |item| item / 3);
+
+        monkeys.sort_by_key(|m| m.inspects);
+        monkeys
+            .iter()
+            .rev()
+            .take(2)
+            .map(|m| m.inspects)
+            .try_fold(1, |acc, m| Ok(acc * m))
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> {
+        let mut monkeys: Vec<Monkey> = input
+            .split("\n\n")
+            .map(Monkey::from_str)
+            .collect::<anyhow::Result<Vec<_>>>()?;
+
+        let divisor_lcm = monkeys
+            .iter()
+            .cloned()
+            .map(|m| m.test.divisor)
+            .reduce(|a, b| a * b)
+            .context("Failed to get LCM")?;
+
+        monkey_business(&mut monkeys, 10_000, move |item| item % divisor_lcm);
+
+        monkeys.sort_by_key(|m| m.inspects);
+        monkeys
+            .iter()
+            .rev()
+            .take(2)
+            .map(|m| m.inspects)
+            .try_fold(1, |acc, m| Ok(acc * m))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use pretty_assertions::assert_eq;
+
+    const TEST_INPUT: &str = include_str!("../input/day_11_example.txt");
+
+    #[test]
+    fn test_part_1_example() -> Result<(), anyhow::Error> {
+        Ok(assert_eq!(10605, Day11::part_1(TEST_INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<(), anyhow::Error> {
+        Ok(assert_eq!(2713310158, Day11::part_2(TEST_INPUT)?))
+    }
+}
diff --git a/aoc_2022/src/lib.rs b/aoc_2022/src/lib.rs
index df0ce86..f9c7019 100644
--- a/aoc_2022/src/lib.rs
+++ b/aoc_2022/src/lib.rs
@@ -12,3 +12,4 @@ pub mod day_07;
 pub mod day_08;
 pub mod day_09;
 pub mod day_10;
+pub mod day_11;
diff --git a/aoc_2022/src/main.rs b/aoc_2022/src/main.rs
index a2fd8ae..6a213f3 100644
--- a/aoc_2022/src/main.rs
+++ b/aoc_2022/src/main.rs
@@ -2,7 +2,7 @@ use anyhow::Result;
 use aoc::Solution;
 use aoc_2022::{
     day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, day_05::Day05, day_06::Day06,
-    day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10,
+    day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, day_11::Day11,
 };
 
 fn main() -> Result<()> {
@@ -16,6 +16,7 @@ fn main() -> Result<()> {
     Day08::solve()?;
     Day09::solve()?;
     Day10::solve()?;
+    Day11::solve()?;
 
     Ok(())
 }