From 6e7a248aae5fd01f8886c8243fbacc6f1f1d1c82 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Sun, 11 Dec 2022 12:25:32 +0100 Subject: [PATCH] Day 11 --- data/day11.input | 55 +++++++++++++++++++ src/day11.rs | 136 +++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 7 +++ 3 files changed, 198 insertions(+) create mode 100644 data/day11.input create mode 100644 src/day11.rs diff --git a/data/day11.input b/data/day11.input new file mode 100644 index 0000000..49a33e8 --- /dev/null +++ b/data/day11.input @@ -0,0 +1,55 @@ +Monkey 0: + Starting items: 99, 63, 76, 93, 54, 73 + Operation: new = old * 11 + Test: divisible by 2 + If true: throw to monkey 7 + If false: throw to monkey 1 + +Monkey 1: + Starting items: 91, 60, 97, 54 + Operation: new = old + 1 + Test: divisible by 17 + If true: throw to monkey 3 + If false: throw to monkey 2 + +Monkey 2: + Starting items: 65 + Operation: new = old + 7 + Test: divisible by 7 + If true: throw to monkey 6 + If false: throw to monkey 5 + +Monkey 3: + Starting items: 84, 55 + Operation: new = old + 3 + Test: divisible by 11 + If true: throw to monkey 2 + If false: throw to monkey 6 + +Monkey 4: + Starting items: 86, 63, 79, 54, 83 + Operation: new = old * old + Test: divisible by 19 + If true: throw to monkey 7 + If false: throw to monkey 0 + +Monkey 5: + Starting items: 96, 67, 56, 95, 64, 69, 96 + Operation: new = old + 4 + Test: divisible by 5 + If true: throw to monkey 4 + If false: throw to monkey 0 + +Monkey 6: + Starting items: 66, 94, 70, 93, 72, 67, 88, 51 + Operation: new = old * 5 + Test: divisible by 13 + If true: throw to monkey 4 + If false: throw to monkey 5 + +Monkey 7: + Starting items: 59, 59, 74 + Operation: new = old + 8 + Test: divisible by 3 + If true: throw to monkey 1 + If false: throw to monkey 3 \ No newline at end of file diff --git a/src/day11.rs b/src/day11.rs new file mode 100644 index 0000000..9ad00bd --- /dev/null +++ b/src/day11.rs @@ -0,0 +1,136 @@ +use std::{str::Lines, collections::VecDeque}; + +use itertools::Itertools; + +#[derive(Debug, Clone)] +enum Operation { + MulOld, + Mul(u64), + Add(u64), +} + +impl Operation { + fn parse(op: &[&str]) -> Self { + match op[1] { + "*" => if op[2] == "old" { Operation::MulOld } else { Operation::Mul(op[2].parse::().unwrap()) }, + "+" => Operation::Add(op[2].parse::().unwrap()), + unknown => panic!("Unknown operation: {}", unknown), + } + } + + fn apply(&self, v: u64) -> u64 { + match self { + Operation::MulOld => v * v, + Operation::Mul(v2) => v * v2, + Operation::Add(v2) => v + v2, + } + } +} + +#[derive(Debug, Clone)] +pub struct Monkey { + items: VecDeque, + operation: Operation, + divisible_test: u64, + monkey_to_throw_if_true: usize, + monkey_to_throw_if_false: usize, +} + +static CHARS_SPLIT: &[char] = &[' ', ',']; + +impl Monkey { + fn parse(lines: &mut Lines) -> Option { + fn split_line(s: &str) -> impl Iterator { + s.trim().split(CHARS_SPLIT).filter(|s| !s.is_empty()) + } + + lines.next()?; // Skip first line (Monkey number). + + Some(Monkey { + items: split_line(lines.next()?).skip(2).map(|v| v.parse::().unwrap()).collect(), + operation: Operation::parse(&split_line(lines.next()?).skip(3).collect::>()), + divisible_test: split_line(lines.next()?).nth(3).unwrap().parse::().unwrap(), + monkey_to_throw_if_true: split_line(lines.next()?).nth(5).unwrap().parse().unwrap(), + monkey_to_throw_if_false: split_line(lines.next()?).nth(5).unwrap().parse().unwrap(), + }) + } +} + +pub fn parse(input: &str) -> Vec { + let mut monkeys = Vec::new(); + let mut lines = input.lines(); + while let Some(m) = Monkey::parse(&mut lines) { + monkeys.push(m); + lines.next(); // Empty line. + } + monkeys +} + +pub fn run(monkeys: &mut [Monkey], nb_rounds: u64, worry_divided: u64) -> u64 { + let mut inspected = vec![0u64; monkeys.len()]; + + let base = monkeys.iter().fold(1, |product, m| product * m.divisible_test); + + for _ in 0..nb_rounds { + for i in 0..monkeys.len() { + while let Some(item) = monkeys[i].items.pop_front() { + inspected[i] += 1; + let new_worry = (monkeys[i].operation.apply(item) / worry_divided) % base; + if new_worry % monkeys[i].divisible_test == 0 { + monkeys[monkeys[i].monkey_to_throw_if_true].items.push_back(new_worry); + } else { + monkeys[monkeys[i].monkey_to_throw_if_false].items.push_back(new_worry); + } + } + } + } + + let most_inspected_items: Vec<&u64> = inspected.iter().sorted().rev().take(2).collect(); + most_inspected_items[0] * most_inspected_items[1] +} + +#[cfg(test)] +mod tests { + use super::*; + + static MONKEYS: &str = + "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"; + + #[test] + fn part1() { + let mut monkeys = parse(MONKEYS); + assert_eq!(run(&mut monkeys, 20, 3), 10605); + } + + #[test] + fn part2() { + let mut monkeys = parse(MONKEYS); + assert_eq!(run(&mut monkeys, 10000, 1), 2713310158); + } +} \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index d7d6d19..0e63823 100644 --- a/src/main.rs +++ b/src/main.rs @@ -11,6 +11,7 @@ mod day07; mod day08; mod day09; mod day10; +mod day11; fn day01() -> String { let f = fs::File::open("data/day01.input").unwrap(); @@ -84,6 +85,11 @@ fn day10() -> String { format!("part1: {}, part2: \n{}", sum_signal_strength, screen.to_ascii()) } +fn day11() -> String { + let monkeys = day11::parse(&fs::read_to_string("data/day11.input").unwrap()); + format!("part1: {}, part2: {}", day11::run(&mut monkeys.clone(), 20, 3), day11::run(&mut monkeys.clone(), 10000, 1)) +} + fn format_micros(t: u128) -> String { if t < 10_000 { format!("{} μs", t) @@ -113,6 +119,7 @@ fn main() { day08, day09, day10, + day11, ); let args: Vec = env::args().skip(1).collect(); -- 2.45.2