/// --- Part Two --- /// /// You're worried you might not ever get your items back. So worried, in fact, that your relief /// that a monkey's inspection didn't damage an item no longer causes your worry level to be /// divided by three. /// /// Unfortunately, that relief was all that was keeping your worry levels from reaching ridiculous /// levels. You'll need to find another way to keep your worry levels manageable. /// /// At this rate, you might be putting up with these monkeys for a very long time - possibly 10000 /// rounds! /// /// With these new rules, you can still figure out the monkey business after 10000 rounds. Using /// the same example above: /// /// ``` /// == After round 1 == /// Monkey 0 inspected items 2 times. /// Monkey 1 inspected items 4 times. /// Monkey 2 inspected items 3 times. /// Monkey 3 inspected items 6 times. /// /// == After round 20 == /// Monkey 0 inspected items 99 times. /// Monkey 1 inspected items 97 times. /// Monkey 2 inspected items 8 times. /// Monkey 3 inspected items 103 times. /// /// == After round 1000 == /// Monkey 0 inspected items 5204 times. /// Monkey 1 inspected items 4792 times. /// Monkey 2 inspected items 199 times. /// Monkey 3 inspected items 5192 times. /// /// == After round 2000 == /// Monkey 0 inspected items 10419 times. /// Monkey 1 inspected items 9577 times. /// Monkey 2 inspected items 392 times. /// Monkey 3 inspected items 10391 times. /// /// == After round 3000 == /// Monkey 0 inspected items 15638 times. /// Monkey 1 inspected items 14358 times. /// Monkey 2 inspected items 587 times. /// Monkey 3 inspected items 15593 times. /// /// == After round 4000 == /// Monkey 0 inspected items 20858 times. /// Monkey 1 inspected items 19138 times. /// Monkey 2 inspected items 780 times. /// Monkey 3 inspected items 20797 times. /// /// == After round 5000 == /// Monkey 0 inspected items 26075 times. /// Monkey 1 inspected items 23921 times. /// Monkey 2 inspected items 974 times. /// Monkey 3 inspected items 26000 times. /// /// == After round 6000 == /// Monkey 0 inspected items 31294 times. /// Monkey 1 inspected items 28702 times. /// Monkey 2 inspected items 1165 times. /// Monkey 3 inspected items 31204 times. /// /// == After round 7000 == /// Monkey 0 inspected items 36508 times. /// Monkey 1 inspected items 33488 times. /// Monkey 2 inspected items 1360 times. /// Monkey 3 inspected items 36400 times. /// /// == After round 8000 == /// Monkey 0 inspected items 41728 times. /// Monkey 1 inspected items 38268 times. /// Monkey 2 inspected items 1553 times. /// Monkey 3 inspected items 41606 times. /// /// == After round 9000 == /// Monkey 0 inspected items 46945 times. /// Monkey 1 inspected items 43051 times. /// Monkey 2 inspected items 1746 times. /// Monkey 3 inspected items 46807 times. /// /// == After round 10000 == /// Monkey 0 inspected items 52166 times. /// Monkey 1 inspected items 47830 times. /// Monkey 2 inspected items 1938 times. /// Monkey 3 inspected items 52013 times. /// ``` /// /// After 10000 rounds, the two most active monkeys inspected items 52166 and 52013 times. /// Multiplying these together, the level of monkey business in this situation is now 2713310158. /// /// Worry levels are no longer divided by three after each item is inspected; you'll need to find /// another way to keep your worry levels manageable. Starting again from the initial state in /// your puzzle input, what is the level of monkey business after 10000 rounds? use clap::Parser; use itertools::Itertools; use nom::branch::alt; use nom::bytes::complete::tag; use nom::character::complete::{i64, newline, u8}; use nom::combinator::{map, opt}; use nom::error::{ContextError, ErrorKind as NomErrorKind, ParseError}; use nom::multi::{many0, many1}; use nom::sequence::{delimited, preceded, terminated, tuple}; use nom::IResult; use std::collections::VecDeque; use std::fs::File; use std::io::prelude::*; use std::io::BufReader; use std::path::PathBuf; const FILEPATH: &'static str = "examples/input.txt"; const ROUNDS: u32 = 10000; pub type Input<'a> = &'a str; pub type Result<'a, T> = IResult, T, Error>>; #[derive(Clone, Debug, PartialEq, Eq)] pub enum ErrorKind { Nom(NomErrorKind), Context(&'static str), Custom(String), } #[derive(Parser, Debug)] #[clap(author, version, about, long_about = None)] struct Cli { #[clap(short, long, default_value = FILEPATH)] file: PathBuf, } #[derive(Clone, Debug, PartialEq, Eq)] pub struct Error { pub errors: Vec<(I, ErrorKind)>, } #[derive(Clone, Debug, PartialEq, Eq)] enum Operation { Add(i64), Multiply(i64), Square, } #[derive(Copy, Clone, Debug)] struct Test { divisor: i64, true_throw: u8, false_throw: u8, } #[derive(Clone, Debug)] struct Monkey { id: u8, items: VecDeque, operation: Operation, test: Test, ins_count: u64, } impl ParseError for Error { fn from_error_kind(input: I, kind: NomErrorKind) -> Self { let errors = vec![(input, ErrorKind::Nom(kind))]; Self { errors } } fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self { other.errors.push((input, ErrorKind::Nom(kind))); other } } impl ContextError for Error { fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self { other.errors.push((input, ErrorKind::Context(ctx))); other } } fn parse_id(input: &str) -> Result { delimited(tag("Monkey "), u8, tuple((tag(":"), newline)))(input) } fn parse_starting(input: &str) -> Result> { delimited( tag(" Starting items: "), many0(terminated(i64, opt(tag(", ")))), newline, )(input) } fn parse_operation(input: &str) -> Result { delimited( tag(" Operation: new = old "), alt(( map(preceded(tag("* "), i64), |x: i64| Operation::Multiply(x)), map(preceded(tag("+ "), i64), |x: i64| Operation::Add(x)), map(preceded(tag("* "), tag("old")), |_| Operation::Square), )), newline, )(input) } fn parse_test(input: &str) -> Result { let (input, divisor) = delimited(tag(" Test: divisible by "), i64, newline)(input)?; let (input, true_throw) = delimited(tag(" If true: throw to monkey "), u8, newline)(input)?; let (input, false_throw) = delimited(tag(" If false: throw to monkey "), u8, opt(newline))(input)?; Ok(( input, Test { divisor, true_throw, false_throw, }, )) } fn parse_monkey(input: &str) -> Result { map( tuple((parse_id, parse_starting, parse_operation, parse_test)), |(id, items, operation, test)| Monkey { id, items: items.into(), operation, test, ins_count: 0, }, )(input) } fn parse(input: &str) -> Result> { many1(terminated(parse_monkey, opt(newline)))(input) } fn main() { let args = Cli::parse(); let file = File::open(&args.file).unwrap(); let mut reader = BufReader::new(file); let mut buf = String::new(); let _ = reader.read_to_string(&mut buf).unwrap(); let (input, mut monkeys) = parse(&buf).unwrap(); assert_eq!(input.len(), 0); let common_factor: i64 = monkeys.iter().map(|m: &Monkey| m.test.divisor).product(); for _ in 0..ROUNDS { for idx in 0..monkeys.len() { assert_eq!(idx, monkeys[idx].id as usize); loop { if monkeys[idx].items.is_empty() { break; } let monkey = &mut monkeys[idx]; monkey.ins_count += 1; let item = monkey.items.pop_front().unwrap(); let bo_item = match monkey.operation { Operation::Add(val) => item + val, Operation::Multiply(val) => item * val, Operation::Square => item * item, } % common_factor; let test = monkeys[idx].test.clone(); match bo_item % test.divisor { 0 => monkeys[test.true_throw as usize].items.push_back(bo_item), _ => monkeys[test.false_throw as usize].items.push_back(bo_item), } } } } let res: u64 = monkeys .into_iter() .map(|m: Monkey| m.ins_count) .sorted() .rev() .take(2) .product(); println!("{res:#?}"); }