From 7879301421b00e879320e9f86e14fad89b36540e Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Wed, 14 Dec 2022 12:20:58 -0600 Subject: feat: impl day 11 --- aoc_2022/input/day_11.txt | 55 +++++++ aoc_2022/input/day_11_example.txt | 27 +++ aoc_2022/src/day_11.rs | 339 ++++++++++++++++++++++++++++++++++++++ aoc_2022/src/lib.rs | 1 + aoc_2022/src/main.rs | 3 +- 5 files changed, 424 insertions(+), 1 deletion(-) create mode 100644 aoc_2022/input/day_11.txt create mode 100644 aoc_2022/input/day_11_example.txt create mode 100644 aoc_2022/src/day_11.rs diff --git a/aoc_2022/input/day_11.txt b/aoc_2022/input/day_11.txt new file mode 100644 index 0000000..c567cb6 --- /dev/null +++ b/aoc_2022/input/day_11.txt @@ -0,0 +1,55 @@ +Monkey 0: + Starting items: 62, 92, 50, 63, 62, 93, 73, 50 + Operation: new = old * 7 + Test: divisible by 2 + If true: throw to monkey 7 + If false: throw to monkey 1 + +Monkey 1: + Starting items: 51, 97, 74, 84, 99 + Operation: new = old + 3 + Test: divisible by 7 + If true: throw to monkey 2 + If false: throw to monkey 4 + +Monkey 2: + Starting items: 98, 86, 62, 76, 51, 81, 95 + Operation: new = old + 4 + Test: divisible by 13 + If true: throw to monkey 5 + If false: throw to monkey 4 + +Monkey 3: + Starting items: 53, 95, 50, 85, 83, 72 + Operation: new = old + 5 + Test: divisible by 19 + If true: throw to monkey 6 + If false: throw to monkey 0 + +Monkey 4: + Starting items: 59, 60, 63, 71 + Operation: new = old * 5 + Test: divisible by 11 + If true: throw to monkey 5 + If false: throw to monkey 3 + +Monkey 5: + Starting items: 92, 65 + Operation: new = old * old + Test: divisible by 5 + If true: throw to monkey 6 + If false: throw to monkey 3 + +Monkey 6: + Starting items: 78 + Operation: new = old + 8 + Test: divisible by 3 + If true: throw to monkey 0 + If false: throw to monkey 7 + +Monkey 7: + Starting items: 84, 93, 54 + Operation: new = old + 1 + Test: divisible by 17 + If true: throw to monkey 2 + If false: throw to monkey 1 diff --git a/aoc_2022/input/day_11_example.txt b/aoc_2022/input/day_11_example.txt new file mode 100644 index 0000000..30e09e5 --- /dev/null +++ b/aoc_2022/input/day_11_example.txt @@ -0,0 +1,27 @@ +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 diff --git a/aoc_2022/src/day_11.rs b/aoc_2022/src/day_11.rs new file mode 100644 index 0000000..6741385 --- /dev/null +++ b/aoc_2022/src/day_11.rs @@ -0,0 +1,339 @@ +use std::{fmt::Display, str::FromStr}; + +use anyhow::{anyhow, Context}; +use aoc::{Problem, Solution}; + +use self::{Operator::*, Token::*}; + +type WorryLevel = usize; + +#[derive(Debug, Clone)] +struct Operation { + lhs: Token, + rhs: Token, + operator: Operator, +} + +impl Operation { + fn evaluate(&self, old: usize) -> usize { + self.operator + .evaluate(self.lhs.evaluate(old), self.rhs.evaluate(old)) + } +} + +impl FromStr for Operation { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + let mut tokens = s + .split('=') + .nth(1) + .context("missing rhs of `=`")? + .split_whitespace(); + + Ok(Operation { + lhs: tokens.next().context("missing lhs")?.parse()?, + operator: tokens.next().context("missing operator")?.parse()?, + rhs: tokens.next().context("missing rhs")?.parse()?, + }) + } +} + +impl Display for Operation { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self.operator { + Add => write!(f, "{} {}", self.operator, self.rhs), + Sub => write!(f, "{} {}", self.operator, self.rhs), + Mul => write!(f, "{} {}", self.operator, self.rhs), + Div => write!(f, "{} {}", self.operator, self.rhs), + } + } +} + +#[derive(Debug, Clone)] +enum Operator { + Add, + Sub, + Mul, + Div, +} + +impl Operator { + fn evaluate(&self, lhs: usize, rhs: usize) -> usize { + match self { + Add => lhs + rhs, + Sub => lhs - rhs, + Mul => lhs * rhs, + Div => lhs / rhs, + } + } +} + +impl FromStr for Operator { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + if s.len() > 1 { + Err(anyhow!("Invalid operator: {}", s)) + } else { + s.chars().next().context("Missing operator")?.try_into() + } + } +} + +impl Display for Operator { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Add => write!(f, "increased by"), + Sub => write!(f, "decreases by"), + Mul => write!(f, "multiplied by"), + Div => write!(f, "divided by"), + } + } +} + +impl TryFrom for Operator { + type Error = anyhow::Error; + + fn try_from(value: char) -> Result { + match value { + '+' => Ok(Add), + '-' => Ok(Sub), + '*' => Ok(Mul), + '/' => Ok(Div), + c => Err(anyhow!("Invalid operator: {}", c)), + } + } +} + +#[derive(Debug, Clone)] +enum Token { + Old, + Number(usize), +} + +impl Token { + fn evaluate(&self, old: usize) -> usize { + match self { + Old => old, + Number(n) => *n, + } + } +} + +impl FromStr for Token { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + match s.trim() { + "old" => Ok(Old), + s if s.chars().all(|c| c.is_numeric()) => { + s.parse().map(Number).context("Failed to parse number") + } + s => return Err(anyhow!("unrecognized token: {s}")), + } + } +} + +impl Display for Token { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Old => write!(f, "itself"), + Number(n) => write!(f, "{}", n), + } + } +} + +#[derive(Debug, Clone)] +struct Test { + divisor: usize, + on_true: usize, + on_false: usize, +} + +impl Test { + fn evaluate(&self, item: usize) -> (usize, usize) { + if (item % self.divisor) == 0 { + (item, self.on_true) + } else { + (item, self.on_false) + } + } +} + +impl FromStr for Test { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + let mut lines = s.lines().map(str::trim); + + Ok(Test { + divisor: lines + .next() + .and_then(|s| s.strip_prefix("Test: divisible by ")) + .context("missing test cond")? + .parse()?, + on_true: lines + .next() + .and_then(|s| s.strip_prefix("If true: throw to monkey ")) + .context("missing if true")? + .parse()?, + on_false: lines + .next() + .and_then(|s| s.strip_prefix("If false: throw to monkey ")) + .context("missing if false")? + .parse()?, + }) + } +} + +#[derive(Debug, Clone)] +struct Monkey { + id: usize, + items: Vec, + operation: Operation, + test: Test, + inspects: usize, +} + +impl FromStr for Monkey { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result { + let mut values = s.lines().map(str::trim); + + Ok(Monkey { + id: values + .next() + .and_then(|s| s.strip_prefix("Monkey ")) + .context("invalid id")? + .trim_matches(':') + .parse()?, + items: values + .next() + .and_then(|s| s.strip_prefix("Starting items: ")) + .context("missing items")? + .split(", ") + .map(usize::from_str) + .collect::, _>>()?, + operation: values + .next() + .and_then(|s| s.strip_prefix("Operation: ")) + .context("missing operation")? + .parse()?, + test: values.collect::>().join("\n").parse()?, + inspects: 0, + }) + } +} + +impl Display for Monkey { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let items = self + .items + .iter() + .map(|i| i.to_string()) + .collect::>() + .join(", "); + + write!(f, "Monkey {}: {}", self.id, items)?; + + Ok(()) + } +} + +fn monkey_business(monkeys: &mut Vec, rounds: usize, reduce: impl Fn(usize) -> usize) { + for _ in 0..rounds { + for i in 0..monkeys.len() { + let mut throw_list = Vec::new(); + + let monkey = &mut monkeys[i]; + + while let Some(mut item) = monkey.items.pop() { + item = monkey.operation.evaluate(item); + item = reduce(item); + monkey.inspects += 1; + throw_list.push(monkey.test.evaluate(item)); + } + + for (item, dest) in throw_list { + let monkey = &mut monkeys[dest]; + // println!("throwing {} to {}", item, monkey.id); + monkey.items.push(item); + } + } + } +} + +pub struct Day11; + +impl Problem for Day11 { + const DAY: u8 = 11; + + const INPUT: &'static str = include_str!("../input/day_11.txt"); +} + +impl Solution for Day11 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> Result { + let mut monkeys: Vec = input + .split("\n\n") + .map(Monkey::from_str) + .collect::>>()?; + + monkey_business(&mut monkeys, 20, |item| item / 3); + + monkeys.sort_by_key(|m| m.inspects); + monkeys + .iter() + .rev() + .take(2) + .map(|m| m.inspects) + .try_fold(1, |acc, m| Ok(acc * m)) + } + + fn part_2(input: &str) -> Result { + let mut monkeys: Vec = input + .split("\n\n") + .map(Monkey::from_str) + .collect::>>()?; + + let divisor_lcm = monkeys + .iter() + .cloned() + .map(|m| m.test.divisor) + .reduce(|a, b| a * b) + .context("Failed to get LCM")?; + + monkey_business(&mut monkeys, 10_000, move |item| item % divisor_lcm); + + monkeys.sort_by_key(|m| m.inspects); + monkeys + .iter() + .rev() + .take(2) + .map(|m| m.inspects) + .try_fold(1, |acc, m| Ok(acc * m)) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use pretty_assertions::assert_eq; + + const TEST_INPUT: &str = include_str!("../input/day_11_example.txt"); + + #[test] + fn test_part_1_example() -> Result<(), anyhow::Error> { + Ok(assert_eq!(10605, Day11::part_1(TEST_INPUT)?)) + } + + #[test] + fn test_part_2_example() -> Result<(), anyhow::Error> { + Ok(assert_eq!(2713310158, Day11::part_2(TEST_INPUT)?)) + } +} diff --git a/aoc_2022/src/lib.rs b/aoc_2022/src/lib.rs index df0ce86..f9c7019 100644 --- a/aoc_2022/src/lib.rs +++ b/aoc_2022/src/lib.rs @@ -12,3 +12,4 @@ pub mod day_07; pub mod day_08; pub mod day_09; pub mod day_10; +pub mod day_11; diff --git a/aoc_2022/src/main.rs b/aoc_2022/src/main.rs index a2fd8ae..6a213f3 100644 --- a/aoc_2022/src/main.rs +++ b/aoc_2022/src/main.rs @@ -2,7 +2,7 @@ use anyhow::Result; use aoc::Solution; use aoc_2022::{ day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, day_05::Day05, day_06::Day06, - day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, + day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, day_11::Day11, }; fn main() -> Result<()> { @@ -16,6 +16,7 @@ fn main() -> Result<()> { Day08::solve()?; Day09::solve()?; Day10::solve()?; + Day11::solve()?; Ok(()) } -- cgit v1.2.3-70-g09d2