complete day 11

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