diff options
Diffstat (limited to 'src/day_11.rs')
-rw-r--r-- | src/day_11.rs | 339 |
1 files changed, 339 insertions, 0 deletions
diff --git a/src/day_11.rs b/src/day_11.rs new file mode 100644 index 0000000..5fd09de --- /dev/null +++ b/src/day_11.rs @@ -0,0 +1,339 @@ +use std::{fmt::Display, str::FromStr}; + +use anyhow::{anyhow, Context}; +use crate::{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<Self, Self::Err> { + 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<Self, Self::Err> { + 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<char> for Operator { + type Error = anyhow::Error; + + fn try_from(value: char) -> Result<Self, Self::Error> { + 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<Self, Self::Err> { + 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<Self, Self::Err> { + 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<WorryLevel>, + operation: Operation, + test: Test, + inspects: usize, +} + +impl FromStr for Monkey { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + 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::<Result<Vec<_>, _>>()?, + operation: values + .next() + .and_then(|s| s.strip_prefix("Operation: ")) + .context("missing operation")? + .parse()?, + test: values.collect::<Vec<&str>>().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::<Vec<String>>() + .join(", "); + + write!(f, "Monkey {}: {}", self.id, items)?; + + Ok(()) + } +} + +fn monkey_business(monkeys: &mut Vec<Monkey>, 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<Self::Answer1, anyhow::Error> { + let mut monkeys: Vec<Monkey> = input + .split("\n\n") + .map(Monkey::from_str) + .collect::<anyhow::Result<Vec<_>>>()?; + + 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<Self::Answer2, anyhow::Error> { + let mut monkeys: Vec<Monkey> = input + .split("\n\n") + .map(Monkey::from_str) + .collect::<anyhow::Result<Vec<_>>>()?; + + 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)?)) + } +} |