diff options
Diffstat (limited to 'day11b/src/main.rs')
| -rw-r--r-- | day11b/src/main.rs | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/day11b/src/main.rs b/day11b/src/main.rs new file mode 100644 index 0000000..ddeaa3d --- /dev/null +++ b/day11b/src/main.rs @@ -0,0 +1,284 @@ +/// --- 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<Input<'a>, T, Error<Input<'a>>>; + +#[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<I> { + 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<i64>, + operation: Operation, + test: Test, + ins_count: u64, +} + +impl<I> ParseError<I> for Error<I> { + 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<I> ContextError<I> for Error<I> { + 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<u8> { + delimited(tag("Monkey "), u8, tuple((tag(":"), newline)))(input) +} + +fn parse_starting(input: &str) -> Result<Vec<i64>> { + delimited( + tag(" Starting items: "), + many0(terminated(i64, opt(tag(", ")))), + newline, + )(input) +} + +fn parse_operation(input: &str) -> Result<Operation> { + 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<Test> { + 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<Monkey> { + 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<Vec<Monkey>> { + 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:#?}"); +} |