path: root/day11a/src/main.rs

/// --- Day 11: Monkey in the Middle ---
///
/// As you finally start making your way upriver, you realize your pack is much lighter than you
/// remember.  Just then, one of the items from your pack goes flying overhead.  Monkeys are
/// playing Keep Away with your missing things!
///
/// To get your stuff back, you need to be able to predict where the monkeys will throw your
/// items.  After some careful observation, you realize the monkeys operate based on how worried
/// you are about each item.
///
/// You take some notes (your puzzle input) on the items each monkey currently has, how worried you
/// are about those items, and how the monkey makes decisions based on your worry level.  For
/// example:
///
/// ```
/// 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
/// ```
///
/// Each monkey has several attributes:
///
///     Starting items lists your worry level for each item the monkey is currently holding in the
///     order they will be inspected.
///     Operation shows how your worry level changes as that monkey inspects an item.  (An operation
///     like new = old * 5 means that your worry level after the monkey inspected the item is five
///     times whatever your worry level was before inspection.)
///     Test shows how the monkey uses your worry level to decide where to throw an item next.
///         If true shows what happens with an item if the Test was true.
///         If false shows what happens with an item if the Test was false.
///
/// After each monkey inspects an item but before it tests your worry level, your relief that the
/// monkey's inspection didn't damage the item causes your worry level to be divided by three and
/// rounded down to the nearest integer.
///
/// The monkeys take turns inspecting and throwing items.  On a single monkey's turn, it inspects
/// and throws all of the items it is holding one at a time and in the order listed.  Monkey 0 goes
/// first, then monkey 1, and so on until each monkey has had one turn.  The process of each monkey
/// taking a single turn is called a round.
///
/// When a monkey throws an item to another monkey, the item goes on the end of the recipient
/// monkey's list.  A monkey that starts a round with no items could end up inspecting and throwing
/// many items by the time its turn comes around.  If a monkey is holding no items at the start of
/// its turn, its turn ends.
///
/// In the above example, the first round proceeds as follows:
///
/// ```
/// Monkey 0:
///   Monkey inspects an item with a worry level of 79.
///     Worry level is multiplied by 19 to 1501.
///     Monkey gets bored with item. Worry level is divided by 3 to 500.
///     Current worry level is not divisible by 23.
///     Item with worry level 500 is thrown to monkey 3.
///   Monkey inspects an item with a worry level of 98.
///     Worry level is multiplied by 19 to 1862.
///     Monkey gets bored with item. Worry level is divided by 3 to 620.
///     Current worry level is not divisible by 23.
///     Item with worry level 620 is thrown to monkey 3.
/// Monkey 1:
///   Monkey inspects an item with a worry level of 54.
///     Worry level increases by 6 to 60.
///     Monkey gets bored with item. Worry level is divided by 3 to 20.
///     Current worry level is not divisible by 19.
///     Item with worry level 20 is thrown to monkey 0.
///   Monkey inspects an item with a worry level of 65.
///     Worry level increases by 6 to 71.
///     Monkey gets bored with item. Worry level is divided by 3 to 23.
///     Current worry level is not divisible by 19.
///     Item with worry level 23 is thrown to monkey 0.
///   Monkey inspects an item with a worry level of 75.
///     Worry level increases by 6 to 81.
///     Monkey gets bored with item. Worry level is divided by 3 to 27.
///     Current worry level is not divisible by 19.
///     Item with worry level 27 is thrown to monkey 0.
///   Monkey inspects an item with a worry level of 74.
///     Worry level increases by 6 to 80.
///     Monkey gets bored with item. Worry level is divided by 3 to 26.
///     Current worry level is not divisible by 19.
///     Item with worry level 26 is thrown to monkey 0.
/// Monkey 2:
///   Monkey inspects an item with a worry level of 79.
///     Worry level is multiplied by itself to 6241.
///     Monkey gets bored with item. Worry level is divided by 3 to 2080.
///     Current worry level is divisible by 13.
///     Item with worry level 2080 is thrown to monkey 1.
///   Monkey inspects an item with a worry level of 60.
///     Worry level is multiplied by itself to 3600.
///     Monkey gets bored with item. Worry level is divided by 3 to 1200.
///     Current worry level is not divisible by 13.
///     Item with worry level 1200 is thrown to monkey 3.
///   Monkey inspects an item with a worry level of 97.
///     Worry level is multiplied by itself to 9409.
///     Monkey gets bored with item. Worry level is divided by 3 to 3136.
///     Current worry level is not divisible by 13.
///     Item with worry level 3136 is thrown to monkey 3.
/// Monkey 3:
///   Monkey inspects an item with a worry level of 74.
///     Worry level increases by 3 to 77.
///     Monkey gets bored with item. Worry level is divided by 3 to 25.
///     Current worry level is not divisible by 17.
///     Item with worry level 25 is thrown to monkey 1.
///   Monkey inspects an item with a worry level of 500.
///     Worry level increases by 3 to 503.
///     Monkey gets bored with item. Worry level is divided by 3 to 167.
///     Current worry level is not divisible by 17.
///     Item with worry level 167 is thrown to monkey 1.
///   Monkey inspects an item with a worry level of 620.
///     Worry level increases by 3 to 623.
///     Monkey gets bored with item. Worry level is divided by 3 to 207.
///     Current worry level is not divisible by 17.
///     Item with worry level 207 is thrown to monkey 1.
///   Monkey inspects an item with a worry level of 1200.
///     Worry level increases by 3 to 1203.
///     Monkey gets bored with item. Worry level is divided by 3 to 401.
///     Current worry level is not divisible by 17.
///     Item with worry level 401 is thrown to monkey 1.
///   Monkey inspects an item with a worry level of 3136.
///     Worry level increases by 3 to 3139.
///     Monkey gets bored with item. Worry level is divided by 3 to 1046.
///     Current worry level is not divisible by 17.
///     Item with worry level 1046 is thrown to monkey 1.
/// ```
///
/// After round 1, the monkeys are holding items with these worry levels:
///
/// ```
/// Monkey 0: 20, 23, 27, 26
/// Monkey 1: 2080, 25, 167, 207, 401, 1046
/// Monkey 2:
/// Monkey 3:
/// ```
///
/// Monkeys 2 and 3 aren't holding any items at the end of the round; they both inspected items
/// during the round and threw them all before the round ended.
///
/// This process continues for a few more rounds:
///
/// ```
/// After round 2, the monkeys are holding items with these worry levels:
/// Monkey 0: 695, 10, 71, 135, 350
/// Monkey 1: 43, 49, 58, 55, 362
/// Monkey 2:
/// Monkey 3:
///
/// After round 3, the monkeys are holding items with these worry levels:
/// Monkey 0: 16, 18, 21, 20, 122
/// Monkey 1: 1468, 22, 150, 286, 739
/// Monkey 2:
/// Monkey 3:
///
/// After round 4, the monkeys are holding items with these worry levels:
/// Monkey 0: 491, 9, 52, 97, 248, 34
/// Monkey 1: 39, 45, 43, 258
/// Monkey 2:
/// Monkey 3:
///
/// After round 5, the monkeys are holding items with these worry levels:
/// Monkey 0: 15, 17, 16, 88, 1037
/// Monkey 1: 20, 110, 205, 524, 72
/// Monkey 2:
/// Monkey 3:
///
/// After round 6, the monkeys are holding items with these worry levels:
/// Monkey 0: 8, 70, 176, 26, 34
/// Monkey 1: 481, 32, 36, 186, 2190
/// Monkey 2:
/// Monkey 3:
///
/// After round 7, the monkeys are holding items with these worry levels:
/// Monkey 0: 162, 12, 14, 64, 732, 17
/// Monkey 1: 148, 372, 55, 72
/// Monkey 2:
/// Monkey 3:
///
/// After round 8, the monkeys are holding items with these worry levels:
/// Monkey 0: 51, 126, 20, 26, 136
/// Monkey 1: 343, 26, 30, 1546, 36
/// Monkey 2:
/// Monkey 3:
///
/// After round 9, the monkeys are holding items with these worry levels:
/// Monkey 0: 116, 10, 12, 517, 14
/// Monkey 1: 108, 267, 43, 55, 288
/// Monkey 2:
/// Monkey 3:
///
/// After round 10, the monkeys are holding items with these worry levels:
/// Monkey 0: 91, 16, 20, 98
/// Monkey 1: 481, 245, 22, 26, 1092, 30
/// Monkey 2:
/// Monkey 3:
///
/// ...
///
/// After round 15, the monkeys are holding items with these worry levels:
/// Monkey 0: 83, 44, 8, 184, 9, 20, 26, 102
/// Monkey 1: 110, 36
/// Monkey 2:
/// Monkey 3:
///
/// ...
///
/// After round 20, the monkeys are holding items with these worry levels:
/// Monkey 0: 10, 12, 14, 26, 34
/// Monkey 1: 245, 93, 53, 199, 115
/// Monkey 2:
/// Monkey 3:
/// ```
///
/// Chasing all of the monkeys at once is impossible; you're going to have to focus on the two most
/// active monkeys if you want any hope of getting your stuff back.  Count the total number of times
/// each monkey inspects items over 20 rounds:
///
/// ```
/// Monkey 0 inspected items 101 times.
/// Monkey 1 inspected items 95 times.
/// Monkey 2 inspected items 7 times.
/// Monkey 3 inspected items 105 times.
/// ```
///
/// In this example, the two most active monkeys inspected items 101 and 105 times.  The level of
/// monkey business in this situation can be found by multiplying these together: 10605.
///
/// Figure out which monkeys to chase by counting how many items they inspect over 20 rounds.  What
/// is the level of monkey business after 20 rounds of stuff-slinging simian shenanigans?
use clap::Parser;
use itertools::Itertools;
use nom::branch::alt;
use nom::bytes::complete::tag;
use nom::character::complete::{i32, 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: u8 = 20;

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(i32),
    Multiply(i32),
    Square,
}

#[derive(Copy, Clone, Debug)]
struct Test {
    divisor: i32,
    true_throw: u8,
    false_throw: u8,
}

#[derive(Clone, Debug)]
struct Monkey {
    id: u8,
    items: VecDeque<i32>,
    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<i32>> {
    delimited(
        tag("  Starting items: "),
        many0(terminated(i32, opt(tag(", ")))),
        newline,
    )(input)
}

fn parse_operation(input: &str) -> Result<Operation> {
    delimited(
        tag("  Operation: new = old "),
        alt((
            map(preceded(tag("* "), i32), |x: i32| Operation::Multiply(x)),
            map(preceded(tag("+ "), i32), |x: i32| 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 "), i32, 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);

    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 op_item = match monkey.operation {
                    Operation::Add(val) => item + val,
                    Operation::Multiply(val) => item * val,
                    Operation::Square => item * item,
                };
                let bo_item = op_item / 3;

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