diff options
| -rw-r--r-- | input/day11.txt | 55 | ||||
| -rw-r--r-- | input/day11_ex.txt | 27 | ||||
| -rw-r--r-- | src/day11.rs | 159 | ||||
| -rw-r--r-- | src/main.rs | 4 |
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!")); } |