path: root/day11b/src/main.rs

/// --- 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:#?}");
}