day 11

3 files changed, 244 insertions, 0 deletions

diff --git a/data/2022/11.txt b/data/2022/11.txt
new file mode 100644
index 0000000..ef22f88
--- /dev/null
+++ b/data/2022/11.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 66, 79
+  Operation: new = old * 11
+  Test: divisible by 7
+    If true: throw to monkey 6
+    If false: throw to monkey 7
+
+Monkey 1:
+  Starting items: 84, 94, 94, 81, 98, 75
+  Operation: new = old * 17
+  Test: divisible by 13
+    If true: throw to monkey 5
+    If false: throw to monkey 2
+
+Monkey 2:
+  Starting items: 85, 79, 59, 64, 79, 95, 67
+  Operation: new = old + 8
+  Test: divisible by 5
+    If true: throw to monkey 4
+    If false: throw to monkey 5
+
+Monkey 3:
+  Starting items: 70
+  Operation: new = old + 3
+  Test: divisible by 19
+    If true: throw to monkey 6
+    If false: throw to monkey 0
+
+Monkey 4:
+  Starting items: 57, 69, 78, 78
+  Operation: new = old + 4
+  Test: divisible by 2
+    If true: throw to monkey 0
+    If false: throw to monkey 3
+
+Monkey 5:
+  Starting items: 65, 92, 60, 74, 72
+  Operation: new = old + 7
+  Test: divisible by 11
+    If true: throw to monkey 3
+    If false: throw to monkey 4
+
+Monkey 6:
+  Starting items: 77, 91, 91
+  Operation: new = old * old
+  Test: divisible by 17
+    If true: throw to monkey 1
+    If false: throw to monkey 7
+
+Monkey 7:
+  Starting items: 76, 58, 57, 55, 67, 77, 54, 99
+  Operation: new = old + 6
+  Test: divisible by 3
+    If true: throw to monkey 2
+    If false: throw to monkey 1
diff --git a/src/2022/11/mod.rs b/src/2022/11/mod.rs
new file mode 100644
index 0000000..8bebb72
--- /dev/null
+++ b/src/2022/11/mod.rs
@@ -0,0 +1,185 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use crate::prelude::*;
+
+pub struct Monkey {
+    items: VecDeque<i64>,
+    op: Box<dyn Fn(i64) -> i64>,
+    divisor: i64,
+    modulo: i64,
+    test: i64,
+    if_true: usize,
+    if_false: usize,
+
+    count: i64,
+}
+
+impl std::fmt::Debug for Monkey {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.debug_struct("Monkey")
+            .field("items", &self.items)
+            .finish()
+    }
+}
+
+impl Monkey {
+    fn parse(mut it: impl Iterator<Item = String>) -> Monkey {
+        let line = it.next().unwrap();
+        let cap = regex_captures!(r"^  Starting items: ([0-9, ]*)$", &line)
+            .unwrap();
+        let items = cap[1].split(", ").map(|s| s.parse().unwrap()).collect();
+
+        let line = it.next().unwrap();
+        let cap = regex_captures!(
+            r"^  Operation: new = old ([+*/-]) (\d+|old)$",
+            &line
+        )
+        .unwrap();
+        let op = if &cap[2] == "old" {
+            match &cap[1] {
+                "+" => Box::new(move |x| x + x) as Box<dyn Fn(i64) -> i64>,
+                "-" => Box::new(move |_| 0.into()),
+                "*" => Box::new(move |x| x * x),
+                "/" => Box::new(move |_| 1.into()),
+                _ => panic!("unknown op {}", &cap[1]),
+            }
+        } else {
+            let n: i64 = cap[2].parse().unwrap();
+            match &cap[1] {
+                "+" => Box::new(move |x| x + n) as Box<dyn Fn(i64) -> i64>,
+                "-" => Box::new(move |x| x - n),
+                "*" => Box::new(move |x| x * n),
+                "/" => Box::new(move |x| x / n),
+                _ => panic!("unknown op {}", &cap[1]),
+            }
+        };
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^  Test: divisible by (\d+)$", &line).unwrap();
+        let test = cap[1].parse().unwrap();
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^    If true: throw to monkey (\d+)$", &line)
+                .unwrap();
+        let if_true = cap[1].parse().unwrap();
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^    If false: throw to monkey (\d+)$", &line)
+                .unwrap();
+        let if_false = cap[1].parse().unwrap();
+
+        assert!(it.next().is_none());
+
+        Self {
+            items,
+            op,
+            divisor: 0,
+            modulo: 0,
+            test,
+            if_true,
+            if_false,
+            count: 0,
+        }
+    }
+
+    fn inspect(&mut self) -> Option<(i64, usize)> {
+        let Some(item) = self.items.pop_front()
+        else { return None };
+        self.count += 1;
+        let item = (self.op)(item);
+        let item = item / self.divisor;
+        let item = item % self.modulo;
+        if item % self.test == 0.into() {
+            Some((item, self.if_true))
+        } else {
+            Some((item, self.if_false))
+        }
+    }
+
+    fn catch(&mut self, item: i64) {
+        self.items.push_back(item);
+    }
+
+    fn set_reduce(&mut self, divisor: i64, modulo: i64) {
+        self.divisor = divisor;
+        self.modulo = modulo;
+    }
+}
+
+#[derive(Debug)]
+pub struct Monkeys {
+    monkeys: Vec<Monkey>,
+}
+
+impl Monkeys {
+    fn parse(it: impl Iterator<Item = String>) -> Self {
+        let mut monkeys = vec![];
+        let mut it = it.peekable();
+        while it.peek().is_some() {
+            let header = it.next().unwrap();
+            let cap = regex_captures!(r"^Monkey (\d+):$", &header).unwrap();
+            let monkey_idx: usize = cap[1].parse().unwrap();
+            assert_eq!(monkey_idx, monkeys.len());
+            monkeys.push(Monkey::parse(parse::chunk(&mut it)));
+        }
+        Self { monkeys }
+    }
+
+    fn round(&mut self) {
+        for i in 0..self.monkeys.len() {
+            while let Some((item, to)) = self.monkeys[i].inspect() {
+                self.monkeys[to].catch(item);
+            }
+        }
+    }
+
+    fn monkey_business(&self) -> i64 {
+        let mut counts: Vec<_> =
+            self.monkeys.iter().map(|m| m.count).collect();
+        counts.sort_unstable();
+        counts[counts.len() - 1] * counts[counts.len() - 2]
+    }
+
+    fn set_reduce(&mut self, divisor: i64) {
+        let modulo = self.monkeys.iter().map(|m| m.test).product();
+        for monkey in &mut self.monkeys {
+            monkey.set_reduce(divisor, modulo);
+        }
+    }
+}
+
+pub fn parse(fh: File) -> Result<Monkeys> {
+    Ok(Monkeys::parse(parse::lines(fh)))
+}
+
+pub fn part1(mut monkeys: Monkeys) -> Result<i64> {
+    monkeys.set_reduce(3);
+    for i in 0..20 {
+        monkeys.round();
+    }
+    Ok(monkeys.monkey_business())
+}
+
+pub fn part2(mut monkeys: Monkeys) -> Result<i64> {
+    monkeys.set_reduce(1);
+    for i in 0..10_000 {
+        monkeys.round();
+    }
+    Ok(monkeys.monkey_business())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(),
+        0
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(),
+        0
+    );
+}
diff --git a/src/2022/mod.rs b/src/2022/mod.rs
index 0afa8bd..5c836a1 100644
--- a/src/2022/mod.rs
+++ b/src/2022/mod.rs
@@ -20,6 +20,8 @@ mod day8;
 mod day9;
 #[path = "10/mod.rs"]
 mod day10;
+#[path = "11/mod.rs"]
+mod day11;
 // NEXT MOD
 
 pub fn run(day: u8, puzzle: u8) -> Result<i64> {
@@ -45,6 +47,8 @@ pub fn run(day: u8, puzzle: u8) -> Result<i64> {
         (9, 2) => day9::part2(day9::parse(parse::data(2022, 9)?)?),
         (10, 1) => day10::part1(day10::parse(parse::data(2022, 10)?)?),
         (10, 2) => day10::part2(day10::parse(parse::data(2022, 10)?)?),
+        (11, 1) => day11::part1(day11::parse(parse::data(2022, 11)?)?),
+        (11, 2) => day11::part2(day11::parse(parse::data(2022, 11)?)?),
         // NEXT PART
         _ => Err(anyhow!("unknown puzzle {}-{}", day, puzzle)),
     }