170 lines
4 KiB
Rust
170 lines
4 KiB
Rust
//! Day 11: Monkey in the Middle
|
|
|
|
use itertools::Itertools;
|
|
|
|
type Wl = u64;
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct Monkey {
|
|
items: Vec<Wl>,
|
|
operation_mult: bool,
|
|
operation_n: Wl,
|
|
test: Wl,
|
|
target_true: usize,
|
|
target_false: usize,
|
|
n_inspected: usize,
|
|
}
|
|
|
|
impl Monkey {
|
|
fn parse(lines: &[String]) -> Self {
|
|
let mut lines = lines.iter();
|
|
lines.next();
|
|
let items = lines
|
|
.next()
|
|
.unwrap()
|
|
.trim()
|
|
.strip_prefix("Starting items: ")
|
|
.unwrap()
|
|
.split(", ")
|
|
.map(|s| s.parse().unwrap())
|
|
.collect();
|
|
let op_str = lines
|
|
.next()
|
|
.unwrap()
|
|
.trim()
|
|
.strip_prefix("Operation: new = old ")
|
|
.unwrap();
|
|
let operation_mult = &op_str[0..1] == "*";
|
|
let operation_n = if &op_str[2..] == "old" {
|
|
0
|
|
} else {
|
|
op_str[2..].parse().unwrap()
|
|
};
|
|
let test = lines
|
|
.next()
|
|
.unwrap()
|
|
.trim()
|
|
.strip_prefix("Test: divisible by ")
|
|
.unwrap()
|
|
.parse()
|
|
.unwrap();
|
|
let target_true = lines
|
|
.next()
|
|
.unwrap()
|
|
.trim()
|
|
.strip_prefix("If true: throw to monkey ")
|
|
.unwrap()
|
|
.parse()
|
|
.unwrap();
|
|
let target_false = lines
|
|
.next()
|
|
.unwrap()
|
|
.trim()
|
|
.strip_prefix("If false: throw to monkey ")
|
|
.unwrap()
|
|
.parse()
|
|
.unwrap();
|
|
|
|
Self {
|
|
items,
|
|
operation_mult,
|
|
operation_n,
|
|
test,
|
|
target_true,
|
|
target_false,
|
|
n_inspected: 0,
|
|
}
|
|
}
|
|
|
|
fn apply_op(&self, item: Wl) -> Wl {
|
|
if self.operation_mult {
|
|
if self.operation_n == 0 {
|
|
item * item
|
|
} else {
|
|
item * self.operation_n
|
|
}
|
|
} else {
|
|
item + self.operation_n
|
|
}
|
|
}
|
|
|
|
fn target(&self, item: Wl) -> usize {
|
|
if item % self.test == 0 {
|
|
self.target_true
|
|
} else {
|
|
self.target_false
|
|
}
|
|
}
|
|
}
|
|
|
|
fn monkey_business(input: &[String], rounds: usize, div: Wl) -> usize {
|
|
let mut monkeys = input
|
|
.split(String::is_empty)
|
|
.map(Monkey::parse)
|
|
.collect::<Vec<_>>();
|
|
|
|
let cf = monkeys.iter().map(|m| m.test).product::<Wl>();
|
|
|
|
for _ in 0..rounds {
|
|
for i in 0..monkeys.len() {
|
|
let monkey = monkeys[i].clone();
|
|
|
|
for item in &monkey.items {
|
|
let mut item = monkey.apply_op(*item);
|
|
if div == 1 {
|
|
item %= cf;
|
|
} else {
|
|
item /= div;
|
|
}
|
|
|
|
let target = monkey.target(item);
|
|
assert!(target != i);
|
|
let target_monkey = monkeys.get_mut(target).unwrap();
|
|
target_monkey.items.push(item);
|
|
}
|
|
let monkey = monkeys.get_mut(i).unwrap();
|
|
monkey.n_inspected += monkey.items.len();
|
|
monkey.items.clear();
|
|
}
|
|
}
|
|
|
|
// dbg!(monkeys);
|
|
|
|
let mut most_activity = monkeys.iter().map(|m| m.n_inspected).sorted().rev();
|
|
most_activity.next().unwrap() * most_activity.next().unwrap()
|
|
}
|
|
|
|
pub fn part1(input: Vec<String>) -> String {
|
|
monkey_business(&input, 20, 3).to_string()
|
|
}
|
|
|
|
pub fn part2(input: Vec<String>) -> String {
|
|
monkey_business(&input, 10000, 1).to_string()
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
const DAY: u8 = 11;
|
|
|
|
#[test]
|
|
fn t_example1() {
|
|
assert_eq!(part1(crate::read_example(DAY)), "10605");
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2() {
|
|
assert_eq!(part2(crate::read_example(DAY)), "2713310158");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part1() {
|
|
assert_eq!(part1(crate::read_input(DAY)), "88208");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part2() {
|
|
assert_eq!(part2(crate::read_input(DAY)), "21115867968");
|
|
}
|
|
}
|