Day 11

2 files changed, 209 insertions, 0 deletions

diff --git a/2022/inputs/day_11.txt b/2022/inputs/day_11.txt
new file mode 100644
index 0000000..8a2ae29
--- /dev/null
+++ b/2022/inputs/day_11.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 74, 64, 74, 63, 53
+  Operation: new = old * 7
+  Test: divisible by 5
+    If true: throw to monkey 1
+    If false: throw to monkey 6
+
+Monkey 1:
+  Starting items: 69, 99, 95, 62
+  Operation: new = old * old
+  Test: divisible by 17
+    If true: throw to monkey 2
+    If false: throw to monkey 5
+
+Monkey 2:
+  Starting items: 59, 81
+  Operation: new = old + 8
+  Test: divisible by 7
+    If true: throw to monkey 4
+    If false: throw to monkey 3
+
+Monkey 3:
+  Starting items: 50, 67, 63, 57, 63, 83, 97
+  Operation: new = old + 4
+  Test: divisible by 13
+    If true: throw to monkey 0
+    If false: throw to monkey 7
+
+Monkey 4:
+  Starting items: 61, 94, 85, 52, 81, 90, 94, 70
+  Operation: new = old + 3
+  Test: divisible by 19
+    If true: throw to monkey 7
+    If false: throw to monkey 3
+
+Monkey 5:
+  Starting items: 69
+  Operation: new = old + 5
+  Test: divisible by 3
+    If true: throw to monkey 4
+    If false: throw to monkey 2
+
+Monkey 6:
+  Starting items: 54, 55, 58
+  Operation: new = old + 7
+  Test: divisible by 11
+    If true: throw to monkey 1
+    If false: throw to monkey 5
+
+Monkey 7:
+  Starting items: 79, 51, 83, 88, 93, 76
+  Operation: new = old * 3
+  Test: divisible by 2
+    If true: throw to monkey 0
+    If false: throw to monkey 6
diff --git a/2022/src/bin/day_11.rs b/2022/src/bin/day_11.rs
new file mode 100644
index 0000000..ffba6ab
--- /dev/null
+++ b/2022/src/bin/day_11.rs
@@ -0,0 +1,154 @@
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::{line_ending, u64},
+    combinator::{map, value},
+    multi::separated_list1,
+    sequence::{pair, preceded, tuple},
+    IResult,
+};
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_11.txt")?;
+    let troop = MonkeyTroop::parser(&input).unwrap().1;
+
+    {
+        let mut troop_1 = troop.clone();
+        for _ in 0..20 {
+            troop_1.monkey_game_round(true);
+        }
+        dbg!(&troop_1.monkey_business_score());
+    }
+
+    {
+        let mut troop_2 = troop.clone();
+        for _ in 0..10000 {
+            troop_2.monkey_game_round(false);
+        }
+        dbg!(&troop_2.monkey_business_score());
+    }
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct MonkeyTroop {
+    monkeys: Vec<Monkey>,
+    gcd: u64,
+}
+
+#[derive(Debug, Clone)]
+struct Monkey {
+    items: Vec<u64>,
+    operation: Operation,
+    test_denominator: u64,
+    true_target: usize,
+    false_target: usize,
+    inspection_count: usize,
+}
+
+#[derive(Debug, Clone)]
+enum Operation {
+    Add(u64),
+    Multiply(u64),
+    Square,
+}
+
+impl MonkeyTroop {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(pair(line_ending, line_ending), Monkey::parser),
+            |monkeys| MonkeyTroop {
+                gcd: monkeys.iter().map(|m| m.test_denominator).product(),
+                monkeys,
+            },
+        )(input)
+    }
+
+    fn monkey_game_round(&mut self, worry_reduction: bool) {
+        for monkey_i in 0..self.monkeys.len() {
+            self.monkeys[monkey_i].inspect_items(worry_reduction, self.gcd);
+
+            let items = std::mem::take(&mut self.monkeys[monkey_i].items);
+            let test_denominator = self.monkeys[monkey_i].test_denominator.clone();
+            let true_target = self.monkeys[monkey_i].true_target.clone();
+            let false_target = self.monkeys[monkey_i].false_target.clone();
+            for item in items {
+                let target_monkey = if item % test_denominator == 0 {
+                    true_target
+                } else {
+                    false_target
+                };
+                self.monkeys[target_monkey].items.push(item);
+            }
+        }
+    }
+
+    fn monkey_business_score(&self) -> usize {
+        let mut counts: Vec<usize> = self
+            .monkeys
+            .iter()
+            .map(|m| m.inspection_count.clone())
+            .collect();
+        counts.sort();
+        counts.reverse();
+        counts[0] * counts[1]
+    }
+}
+
+impl Monkey {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((
+                preceded(
+                    tuple((
+                        tag("Monkey "),
+                        u64,
+                        tag(":"),
+                        line_ending,
+                        tag("  Starting items: "),
+                    )),
+                    separated_list1(tag(", "), u64),
+                ),
+                preceded(
+                    pair(line_ending, tag("  Operation: new = old ")),
+                    alt((
+                        map(preceded(tag("+ "), u64), Operation::Add),
+                        map(preceded(tag("* "), u64), Operation::Multiply),
+                        value(Operation::Square, tag("* old")),
+                    )),
+                ),
+                preceded(pair(line_ending, tag("  Test: divisible by ")), u64),
+                preceded(pair(line_ending, tag("    If true: throw to monkey ")), u64),
+                preceded(
+                    pair(line_ending, tag("    If false: throw to monkey ")),
+                    u64,
+                ),
+            )),
+            |(items, operation, test_denominator, true_target, false_target)| Monkey {
+                items,
+                operation,
+                test_denominator,
+                true_target: true_target as usize,
+                false_target: false_target as usize,
+                inspection_count: 0,
+            },
+        )(input)
+    }
+
+    fn inspect_items(&mut self, worry_reduction: bool, gcd: u64) {
+        for item in &mut self.items {
+            match self.operation {
+                Operation::Add(i) => *item += i,
+                Operation::Multiply(i) => *item *= i,
+                Operation::Square => *item = *item * *item,
+            };
+            if worry_reduction {
+                *item /= 3;
+            }
+            *item = *item % gcd;
+        }
+        self.inspection_count += self.items.len()
+    }
+}