day11

This one took a lot longer than I'd like!

4 files changed, 245 insertions, 0 deletions

diff --git a/input/day11.txt b/input/day11.txt
new file mode 100644
index 0000000..d7d0e90
--- /dev/null
+++ b/input/day11.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 91, 54, 70, 61, 64, 64, 60, 85
+  Operation: new = old * 13
+  Test: divisible by 2
+    If true: throw to monkey 5
+    If false: throw to monkey 2
+
+Monkey 1:
+  Starting items: 82
+  Operation: new = old + 7
+  Test: divisible by 13
+    If true: throw to monkey 4
+    If false: throw to monkey 3
+
+Monkey 2:
+  Starting items: 84, 93, 70
+  Operation: new = old + 2
+  Test: divisible by 5
+    If true: throw to monkey 5
+    If false: throw to monkey 1
+
+Monkey 3:
+  Starting items: 78, 56, 85, 93
+  Operation: new = old * 2
+  Test: divisible by 3
+    If true: throw to monkey 6
+    If false: throw to monkey 7
+
+Monkey 4:
+  Starting items: 64, 57, 81, 95, 52, 71, 58
+  Operation: new = old * old
+  Test: divisible by 11
+    If true: throw to monkey 7
+    If false: throw to monkey 3
+
+Monkey 5:
+  Starting items: 58, 71, 96, 58, 68, 90
+  Operation: new = old + 6
+  Test: divisible by 17
+    If true: throw to monkey 4
+    If false: throw to monkey 1
+
+Monkey 6:
+  Starting items: 56, 99, 89, 97, 81
+  Operation: new = old + 1
+  Test: divisible by 7
+    If true: throw to monkey 0
+    If false: throw to monkey 2
+
+Monkey 7:
+  Starting items: 68, 72
+  Operation: new = old + 8
+  Test: divisible by 19
+    If true: throw to monkey 6
+    If false: throw to monkey 0
\ No newline at end of file
diff --git a/input/day11_ex.txt b/input/day11_ex.txt
new file mode 100644
index 0000000..c04eddb
--- /dev/null
+++ b/input/day11_ex.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
\ No newline at end of file
diff --git a/src/day11.rs b/src/day11.rs
new file mode 100644
index 0000000..8040ccb
--- /dev/null
+++ b/src/day11.rs
@@ -0,0 +1,159 @@
+use std::{str::FromStr, collections::VecDeque};
+
+use regex::Regex;
+use simple_error::{bail, SimpleError};
+
+#[derive(Debug)]
+enum Op { Add, Sub, Mul, Div }
+
+#[derive(Debug)]
+enum Var { C(u64), A }
+
+#[derive(Debug)]
+struct Monkey {
+    items: VecDeque<u64>,
+    op: Op,
+    arg1: Var,
+    arg2: Var,
+    test: u64, // divisible by this number
+    target_true: usize, // monkey to throw to on true
+    target_false: usize, // monkey to throw to on false
+
+    inspections: usize, // how many inspections has this monkey made?
+}
+
+impl Monkey {
+    fn op(self: &Monkey, x: u64) -> u64 {
+        let a: u64 = match self.arg1 {
+            Var::C(c) => c,
+            Var::A => x,
+        };
+        let b = match self.arg2 {
+            Var::C(c)=> c,
+            Var::A => x,
+        };
+        match self.op {
+            Op::Add => a + b,
+            Op::Sub => a - b,
+            Op::Mul => a * b,
+            Op::Div => a / b,
+        }
+    }
+    fn test(self: &Monkey, x: u64) -> bool {
+        x % self.test == 0
+    }
+    fn business(monkeys: &mut [Monkey]) {
+        let worry_level_modulo: u64 = monkeys.iter().map(|m| {m.test}).product();
+        for ix in 0..monkeys.len() {
+            // TODO can probably change this, use a block 
+            // to scope the mutable borrow of the first monkey, 
+            // and give it back before mutably borrowing the second.
+            // Instead use nightly API usage to get several mutable monkeys
+            let idxs = [ix, monkeys[ix].target_true, monkeys[ix].target_false];
+            let [m, mut mtt, mut mtf] = monkeys.get_many_mut(idxs).unwrap();
+            // Start turn
+            // Inspect all items, one at a time, from the start of the list
+            while let Some(mut i) = m.items.pop_front() {
+                // Increase the count of inspections this monkey has made
+                m.inspections += 1;
+                // Worry level increases...
+                i = m.op(i);
+                // Worry level decreases...
+                // Uh oh, not any more!
+                //i = i / 3;
+                // instead, modulo the worry level by the ... 
+                // prod of all the monkeys divisors? to prevent integer overflow, 
+                // without changing the result
+                i = i % worry_level_modulo;
+                // Test the item, decide who it goes to
+                let target = if m.test(i) { &mut mtt } else { &mut mtf };
+                // Throw it to the other monkey, on the end of their list
+                target.items.push_back(i);
+            }
+        }
+    }
+}
+
+fn nfrg<T: FromStr>(c: regex::Captures, index:usize) -> Result<T, SimpleError> {
+    let x = c.get(index).ok_or(SimpleError::new("missed capture group"))?;
+    x.as_str().parse().map_err(|_| { SimpleError::new("wasn't a number")})
+}
+
+impl FromStr for Monkey {
+    type Err = simple_error::SimpleError;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let ll: Vec<&str> = s.lines().collect();
+        if ll.len() != 6 {
+            bail!("expected 6 lines for a monkey!");
+        }
+        // Parse the starting items line
+        let r1 = Regex::new(r"^  Starting items: ([0-9, ]+)$").unwrap();
+        let l1c = r1.captures(ll[1]).ok_or(SimpleError::new("starting regex no match"))?;
+        let l1d = l1c.get(1).ok_or(SimpleError::new("starting no group"))?;
+        let items: VecDeque<u64> = l1d.as_str().split(", ").map(|t| { t.parse() })
+            .try_collect().map_err(|_| SimpleError::new("error parsing items"))?;
+
+        // Parse the operation / args line
+        let r2 = Regex::new(r"^  Operation: new = ([a-z0-9]+) ([+\-*/]) ([a-z0-9]+)$").unwrap();
+        let l2c = r2.captures(ll[2]).ok_or(SimpleError::new("operation/args didn't match regex"))?;
+        let l2t1 = l2c.get(1).ok_or(SimpleError::new("error parsing op"))?;
+        let l2t2 = l2c.get(2).ok_or(SimpleError::new("error parsing op"))?;
+        let l2t3 = l2c.get(3).ok_or(SimpleError::new("error parsing op"))?;
+        let arg1 = match l2t1.as_str() {
+            "old" => Ok(Var::A),
+            st => st.parse().map(|i| {Var::C(i)})
+        }.map_err(|_| {SimpleError::new("error parsing arg1")})?;
+        let op = match l2t2.as_str() {
+            "+" => Ok(Op::Add),
+            "-" => Ok(Op::Sub),
+            "*" => Ok(Op::Mul),
+            "/" => Ok(Op::Div),
+            _ => Err(SimpleError::new("unexpected operator"))
+        }?;
+        let arg2 = match l2t3.as_str() {
+            "old" => Ok(Var::A),
+            st => st.parse().map(|i| {Var::C(i)})
+        }.map_err(|_| {SimpleError::new("error parsing arg1")})?;
+
+        // Parse the test line
+        let r3 = Regex::new(r"^  Test: divisible by (\d+)$").unwrap();
+        let l3c = r3.captures(ll[3]).ok_or(SimpleError::new("no match line 3"))?;
+        let test = nfrg(l3c, 1)?;
+
+        // Parse the target lines
+        let r4 = Regex::new(r"^    If true: throw to monkey (\d+)$").unwrap();
+        let l4c = r4.captures(ll[4]).ok_or(SimpleError::new("no match line 4"))?;
+        let target_true = nfrg(l4c, 1)?;
+        let r5 = Regex::new(r"^    If false: throw to monkey (\d+)$").unwrap();
+        let l5c = r5.captures(ll[5]).ok_or(SimpleError::new("no match line 5"))?;
+        let target_false = nfrg(l5c, 1)?;
+
+        let inspections = 0;
+        Ok(Monkey{
+            items,
+            op,
+            arg1,
+            arg2,
+            test,
+            target_true,
+            target_false,
+            inspections,
+        })
+    }
+}
+
+pub fn run(input: String) {
+    let mut monkeys: Vec<Monkey> = input.split("\n\n")
+        .map(|s| {Monkey::from_str(s).expect("couldn't parse monkey!")})
+        .collect();
+    //println!("{:?}", monkeys);
+    //for _ in 0..20 {
+    for _ in 0..10000 {
+        Monkey::business(&mut monkeys);
+    }
+    monkeys.sort_by(|a, b| { a.inspections.cmp(&b.inspections).reverse() });
+    let m1 = &monkeys[0];
+    let m2 = &monkeys[1];
+    println!("Day 11: {}", m1.inspections*m2.inspections);
+}
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 31bb9ea..0d64697 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,5 @@
+#![feature(get_many_mut)]
+#![feature(iterator_try_collect)]
 use std::fs;
 
 mod day1;
@@ -10,6 +12,7 @@ mod day7;
 mod day8;
 mod day9;
 mod day10;
+mod day11;
 
 fn main() {
     day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!"));
@@ -22,4 +25,5 @@ fn main() {
     day8::run(fs::read_to_string("input/day8.txt").expect("Failed to read input file!"));
     day9::run(fs::read_to_string("input/day9.txt").expect("Failed to read input file!"));
     day10::run(fs::read_to_string("input/day10.txt").expect("Failed to read input file!"));
+    day11::run(fs::read_to_string("input/day11.txt").expect("Failed to read input file!"));
 }