/// Represents one of those mischeivous monkies! Contains fields
/// for the items the monkey is currently holding, the operation
/// performed when the monkey inspects an item, the rule the monkey
/// uses to decide who to throw the item to, and the number of
/// items the monkey has inspected so far.
#[derive(Debug, Clone)]
struct Monkey {
    id: usize,
    items: Vec<u64>,
    operation: Operation,
    rule: Rule,
    inspected: u32,
}

/// Represents the operation performed to determine what happens to your
/// worry level over a particular item inspected by a monkey.
#[derive(Debug, Clone, Copy)]
enum Operation {
    Add(u64),
    Mult(u64),
    Square,
}

/// Represents the rule used by a monkey to determine which other monkey to
/// throw your item to, based on your worry level.
#[derive(Debug, Clone, Copy)]
struct Rule {
    divisor: u64,
    success: usize,
    fail: usize,
}

/// Wraps the parser combinators for parsing our input into a list of pesky monkies.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::{multispace1, newline, one_of, space1, u64},
        combinator::{map, value},
        multi::separated_list1,
        sequence::{delimited, preceded, separated_pair, terminated, tuple},
        Finish, IResult,
    };

    /// Nom parser for "Monkey 3:" -> 3usize
    fn id(s: &str) -> IResult<&str, usize> {
        map(delimited(tag("Monkey "), u64, tag(":")), |n| n as usize)(s)
    }

    /// Nom parser for "Starting items: 1, 2, 3" -> VecDeque<[1, 2, 3]>
    fn items(s: &str) -> IResult<&str, Vec<u64>> {
        let prefix = preceded(space1, tag("Starting items: "));
        let list = separated_list1(tag(", "), u64);
        map(preceded(prefix, list), Vec::from)(s)
    }

    /// Nom parser for "+ 5" -> Operation::Add(5)
    fn add_op(s: &str) -> IResult<&str, Operation> {
        map(preceded(tag("+ "), u64), Operation::Add)(s)
    }

    /// Nom parser for "* 5" -> Operation::Mult(5)
    fn mult_op(s: &str) -> IResult<&str, Operation> {
        map(preceded(tag("* "), u64), Operation::Mult)(s)
    }

    /// Nom parser for "* old" -> Operation::Square
    fn square_op(s: &str) -> IResult<&str, Operation> {
        value(Operation::Square, tag("* old"))(s)
    }

    /// Nom parser to detect the string that comes before the operator
    /// when parsing an operation.
    fn op_prefix(s: &str) -> IResult<&str, &str> {
        preceded(space1, tag("Operation: new = old "))(s)
    }

    /// Nom parser for: 
    /// - "Operation: new = old + 5" -> Operation::Add(5)
    /// - "Operation: new = old * 5" -> Operation::Mult(5)
    /// - "Operation: new = old * old" -> Operation::Square
    fn op(s: &str) -> IResult<&str, Operation> {
        let add = preceded(op_prefix, add_op);
        let mult = preceded(op_prefix, mult_op);
        let square = preceded(op_prefix, square_op);
        alt((add, mult, square))(s)
    }

    /// Nom parser for extracting the relevant values from the three
    /// lines that describe the rules the monkey uses to determine where
    /// to throw your item, used ton construct a `Rule`. For example:
    ///
    ///   Test: divisible by 17 
    ///     If true: throw to monkey 0 
    ///     If false: throw to monkey 5
    ///
    /// becomes
    ///
    /// Rule { divisor: 17, success: 0, fail: 5 }
    fn test_rule(s: &str) -> IResult<&str, Rule> {
        let (s, divisor) = preceded(space1, preceded(tag("Test: divisible by "), u64))(s)?;
        let (s, success) =
            preceded(multispace1, preceded(tag("If true: throw to monkey "), u64))(s)?;
        let (s, fail) = preceded(
            multispace1,
            preceded(tag("If false: throw to monkey "), u64),
        )(s)?;
        let rule = Rule {
            divisor,
            success: success as usize,
            fail: fail as usize,
        };
        Ok((s, rule))
    }

    /// Nom parser for converting a chunk of the input into a `Monkey`.
    fn monkey(s: &str) -> IResult<&str, Monkey> {
        let (s, id) = terminated(id, newline)(s)?;
        let (s, items) = terminated(items, newline)(s)?;
        let (s, operation) = terminated(op, newline)(s)?;
        let (s, rule) = test_rule(s)?;

        let monkey = Monkey {
            id,
            items,
            operation,
            rule,
            inspected: 0,
        };
        Ok((s, monkey))
    }

    /// Splits the input file into chunks based on empty lines and parses
    /// each chunk into a `Monkey`. Returns the list of `Monkey`s if
    /// successful or the relevant nom Error if not.
    pub fn parse(s: &str) -> Result<Vec<Monkey>> {
        let result = separated_list1(tag("\n\n"), monkey)(s);
        let (s, monkeys) = result
            .finish()
            .map_err(|e| anyhow!("Failed to parse monkeys with error {e}"))?;
        Ok(monkeys)
    }
}

const INPUT: &str = include_str!("../../input/11/input.txt");

/// Parse that input!
fn read() -> Vec<Monkey> {
    parser::parse(INPUT).unwrap()
}

use itertools::Itertools;

/// Solve Day 11, Part 1
fn solve(input: &[Monkey]) -> u64 {
    // Initiate a cruel, cruel game played by monkeys
    let mut monkey_game: CruelGame = CruelGame::from(input);

    // "Play" the game for 20 rounds
    (0..20).for_each(|_| monkey_game.play());

    // Return the maximum monkey business, AKA the product of the 
    // number of items handled by the two most rambunctious monkeys.
    monkey_game.max_monkey_business()
}

/// Represents the cruel and insensitive game being played by the monkeys,
/// at your expense. Includes fields for the list of monkeys where their index
/// also indicates their ID and for the items currently flying through the
/// air from one monkey to another.
struct CruelGame {
    items_in_flight: Vec<(u64, usize)>,
    monkeys: Vec<Monkey>,
}

impl CruelGame {
    /// Produce a `CruelGame` from a list of monkeys
    fn from(monkeys: &[Monkey]) -> Self {
        let monkeys = monkeys.to_vec();
        let items_in_flight = Vec::new();
        CruelGame { items_in_flight, monkeys }
    }

    /// "Play" one round of the "game".
    fn play(&mut self) {
        // For each monkey...
        for id in 0..self.monkeys.len() {
            // Have the monkey handle each item it's currently holding, adding
            // items to the list of items in flight after handling each.
            self.monkeys[id].handle_items(&mut self.items_in_flight);

            // For each item in flight, have the monkey it was tossed to deftly
            // snatch it, along with your hopes and dreams, from the air.
            while let Some((item, target)) = self.items_in_flight.pop() {
                self.monkeys[target].catch(item);
            }
        }
    }

    /// Calculate and return the maximum monkey business. Identifies the number
    /// of items handled by each monkey and returns the product of the two
    /// largest totals.
    fn max_monkey_business(&self) -> u64 {
        let monkey_business: Vec<_> = self.monkeys
            .iter()
            .map(|m| m.inspected)
            .sorted_unstable()
            .rev()
            .take(2)
            .collect();
        (monkey_business[0] * monkey_business[1]).into()
    }
}

impl Monkey {
    /// Have a monkey handle your precious items with callous disregard
    /// for your concerns.
    fn handle_items(&mut self, items_in_flight: &mut Vec<(u64, usize)>) {
        // For each item the monkey has...
        while let Some(mut item) = self.items.pop() {
            // Increase your worry over that item according to the puzzle rules.
            item = self.operation.apply(item);

            // Calm down a bit since the monkey didn't break it (this time).
            item /= 3;

            // Have the monkey decide on a target with a mischievous gleam in
            // its beady monkey eyes.
            let target = self.rule.check(item);

            // Toss the item to its intended target.
            items_in_flight.push((item, target));

            // Increment the number of items this monkey has inspected
            self.inspected += 1;
        }
    }

    /// Catch an item thrown from another monkey. Probably pretend to fumble it
    /// or something just to get that human even more riled up.
    pub fn catch(&mut self, item: u64) {
        self.items.push(item);
    }
}

impl Operation {
    /// Apply an operation to an item's worry score.
    pub fn apply(&self, item: u64) -> u64 {
        match self {
            Operation::Add(n) => item + n,
            Operation::Mult(n) => item * n,
            Operation::Square => item * item,
        }
    }
}

impl Rule {
    /// Check an item's worry score and return which monkey ID to throw
    /// the item to.
    pub fn check(&self, item: u64) -> usize {
        if item % self.divisor == 0 {
            self.success
        } else {
            self.fail
        }
    }
}

use itertools::Itertools;

/// Solve Day 11, Part 2
pub fn solve(input: &Input) -> Output {
    // Similar to last time, but somehow worse...
    let mut monkey_game = WorseGame::from(input);

    // One of the ways it's worse is that it goes on for 500x longer
    (0..10_000).for_each(|_| monkey_game.play_rough());

    // Calculate and return the extreme level of monkey business
    monkey_game.max_monkey_business().into()
}

/// Represents the more intense version of the cruel, cruel game being played by
/// these dastardly monkeys. Includes the same fields as the original `CruelGame`,
/// plus the limit where your stress levels become overwhelming and you black out,
/// experiencing short-term memory loss.
pub struct WorseGame {
    items_in_flight: Vec<(u64, usize)>,
    monkeys: Vec<Monkey>,
    absolute_limit: u64,
}

impl WorseGame {
    // Start up a much worse version of the monkey game
    fn from(monkeys: &[Monkey]) -> Self {
        let monkeys = monkeys.to_vec();
        let items_in_flight = Vec::new();

        // In order to keep the computer from blowing its stack, too, we need to 
        // identify the periodicity of the item worry values. This turns out to
        // be the least common multiple of all the monkey rule divisors by which
        // the monkeys check where to fling your things. Since all these divisors
        // are prime, this is the product of all the divisors.
        let absolute_limit = monkeys.iter().map(|m| m.rule.divisor).product();

        WorseGame { items_in_flight, monkeys, absolute_limit }
    }

    // The monkeys have upped their level of maliciousness and now pretend to drop
    // and break your items on each turn. You're pretty sure they've broken a few
    // things already, but they're throwing them so fast you can't tell for sure.
    fn play_rough(&mut self) {
        // For each monkey...
        for id in 0..self.monkeys.len() {
            // Have the monkey handle each item it's currently holding with obnoxious
            // roughness and glee, adding items to the list of items in flight after
            // handling each.
            self.monkeys[id].handle_items_roughly(self.absolute_limit, &mut self.items_in_flight);

            // For each item in flight, have the monkey it was tossed to deftly
            // snatch it, along with your hopes and dreams, from the air.
            while let Some((item, target)) = self.items_in_flight.pop() {
                self.monkeys[target].catch(item);
            }
        }
    }

    /// Calculate and return the maximum monkey business. Identifies the number
    /// of items handled by each monkey and returns the product of the two
    /// largest totals.
    fn max_monkey_business(&self) -> u64 {
        let monkey_business: Vec<_> = self.monkeys
            .iter()
            .map(|m| m.inspected)
            .sorted_unstable()
            .rev()
            .take(2)
            .collect();
        (monkey_business[0] as u64 * monkey_business[1] as u64)
    }
}

impl Monkey {
    /// Have a monkey handle your precious items with exuberant malice, purposely
    /// stoking your alarm.
    fn handle_items_roughly(
        &mut self,
        absolute_limit: u64,
        items_in_flight: &mut Vec<(u64, usize)>,
    ) {
        while let Some(mut item) = self.items.pop() {
            // Increase your worry over that item according to the puzzle rules.
            item = self.operation.apply(item);

            // Black out for a moment from the stress caused by these monkeys
            // tossing your precious things about, experiencing an odd form of
            // amnesia and "resetting" your stress levels a bit.
            item %= absolute_limit;

            // Have the monkey decide on a target with a malicious glint in
            // its beady monkey eyes.
            let target = self.rule.check(item);
            
            // Toss the item to its intended target.
            items_in_flight.push((item, target));

            // Increment the number of items this monkey has inspected
            self.inspected += 1;
        }
    }
}