From 179467096141b7e8f67d63b89fd21e779a564fe6 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Sun, 11 Dec 2022 02:56:40 -0500 Subject: day 11 --- data/2022/11.txt | 55 ++++++++++++++++ src/2022/11/mod.rs | 185 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/2022/mod.rs | 4 ++ 3 files changed, 244 insertions(+) create mode 100644 data/2022/11.txt create mode 100644 src/2022/11/mod.rs 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, + op: Box 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) -> 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 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 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, +} + +impl Monkeys { + fn parse(it: impl Iterator) -> 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 { + Ok(Monkeys::parse(parse::lines(fh))) +} + +pub fn part1(mut monkeys: Monkeys) -> Result { + monkeys.set_reduce(3); + for i in 0..20 { + monkeys.round(); + } + Ok(monkeys.monkey_business()) +} + +pub fn part2(mut monkeys: Monkeys) -> Result { + 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 { @@ -45,6 +47,8 @@ pub fn run(day: u8, puzzle: u8) -> Result { (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)), } -- cgit v1.2.3-54-g00ecf