On day 11 of the Advent Of Code series you have been robbed by monkeys. They play with the things from the backpack. In order to get them back it's necessary to predict where the monkeys will throw the items. They throw them based on how worried you are about each item.
The input is a list of monkeys, what their start items are, to which other monkeys they are thrown next and a number of tests that determine the worry level. The information for one monkey looks like:
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
Given this input, monkey (with index 0) has two items to start with (with worry levels 79 & 98). The operation defines how the worry level changes when the monkey inspects one item. The test condition checks which of the boolean statements will be executed, either true or false. This check decides which monkey the item is thrown to next.
The thrown item will then be added to the end of the receiver's list of items. If a monkey is not holding any items
any more its turn ends. The worry level is also divided by three every time.
Part 1
Instead of chasing all monkeys only the two monkeys are considered which have inspected the most items during their game over 20 rounds. Once the most two active monkeys are determined the product of the inspected items are the solution.
Let's start by parsing the input text. Today it's the peg crate again, after a brief excursion in trying to get serde_yaml to work, because the format looks quite like YAML. Unfortunately the input does not adhere to be valid, therefore the parser is quite verbose.
To add a crate let's use the cargo-edit extension for cargo this time. Once installed via cargo install cargo-edit the cargo command has a few new subcommands. One of them is add to install a crate. After running cargo add peg on the command line the crate is added as dependency to the Cargo.toml.
The following grammar with peg is used to parse a block of lines.
peg::parser! {
grammar monkey_parser() for str {
rule number() -> u64
= n:$(['0'..='9']+) {? n.parse().or(Err("Failed to parse number")) }
rule items() -> Vec<u64>
= items:(number() ** ", ") { items }
rule op_add() -> Operation
= "+ " n:number() { Operation::Add(n) }
rule op_mul_number() -> Operation
= "* " n:number() { Operation::Mul(n) }
rule op_mul_self() -> Operation
= "* old" { Operation::MulSelf }
pub(crate) rule id() -> u64
= "Monkey " id:number() ":" { id }
pub(crate) rule starting_itmes() -> Vec<u64>
= " Starting items: " items:items() { items }
pub(crate) rule operation() -> Operation
= " Operation: new = old " op:(op_add() / op_mul_number() / op_mul_self()) { op }
pub(crate) rule test() -> Test
= " Test: divisible by " divisible:number() "\n"
" If true: throw to monkey " if_true:number() "\n"
" If false: throw to monkey " if_false:number()
{
Test {
divisible,
if_true: if_true as usize,
if_false: if_false as usize,
}
}
pub(crate) rule monkey() -> Monkey
= id() "\n"
items:starting_itmes() "\n"
operation:operation() "\n"
test:test() "\n"?
{
Monkey {
items, test, operation, inspections: 0,
}
}
}
}
#[derive(Debug, PartialEq, Eq, Copy, Clone)]
enum Operation {
Mul(u64),
Add(u64),
MulSelf,
}
#[derive(Debug, PartialEq, Eq, Clone)]
struct Test {
divisible: u64,
if_true: usize,
if_false: usize,
}
#[derive(Debug, Clone)]
struct Monkey {
items: Vec<u64>,
operation: Operation,
test: Test,
inspections: u64,
}
The Operation enum is similar to the Instruction struct of yesterday's challenge, it holds the three possible operations: multiply by a value, add a value or multiply by itself. The Test struct keeps the divisible number and both branches for the test condition.
The Monkey struct holds all information and reflects the input format. It also holds the number of inspections to keep track of how many items were handled in total.
The parse method then looks as follows.
fn parse(input: &str) -> Vec<Monkey> {
input
.split("\n\n")
.filter_map(|block| monkey_parser::monkey(block).ok())
.collect::<Vec<Monkey>>()
}
All blocks are split by the separating new lines, then each block is parsed into a Monkey object.
The idea is to play the game, have twenty rounds of monkeys throwing things to each otherm then count the number of inspections & see which two monkeys have the most.
impl Operation {
pub fn apply(&self, level: u64) -> u64 {
match self {
Operation::Mul(value) => level * value,
Operation::Add(value) => level + value,
Operation::MulSelf => level * level,
}
}
}
fn play(mut monkeys: Vec<Monkey>, num_rounds: u32) -> u64 {
let num_monkeys = monkeys.len();
for _ in 0..num_rounds {
for index in 0..num_monkeys {
let items = monkeys[index].items.drain(..).collect::<Vec<_>>();
let operation = monkeys[index].operation;
let test = &monkeys[index].test.clone();
for worry_level in items {
let worry_level = operation.apply(worry_level) / 3;
if worry_level % test.divisible == 0 {
monkeys[test.if_true].items.push(worry_level);
} else {
monkeys[test.if_false].items.push(worry_level);
}
monkeys[index].inspections += 1;
}
}
}
monkeys
.iter()
.map(|m| m.inspections)
.sorted()
.rev()
.take(2)
.product()
}
The main for loop in the play function is the number of rounds to play. For each round all monkeys take turns until their starting items are fully distributed to others. The inner most for loop handles each item, determines the worry level & which monkey the item is given to next.
It also increases the number of inspections. The Operation#apply method evaluates the operation & returns the new worry level.
Once the rounds have ended, lastly the list of monkeys is sorted by number of inspections in decreasing order. Then the top two inspections are multiplied as the solution.
There are a few things that might not be obvious here. The num_monkeys variable holds the size of the Vec, this is necessary or otherwise the borrow checker rightly complains that the monkeys variable is referenced in a mutable & immutable manner. To avoid this the size is stored once. Similarly the Test struct is cloned to avoid also an issue with shared mutability.
Most likely there are other solutions using interior mutability to get around this, but the code is brief enough.
Lastly we set up the test module, the given example input is put into a separate test.txt file.
fn part1(monkeys: Vec<Monkey>) -> u64 {
play(monkeys, 20)
}
#[cfg(test)]
mod tests {
use crate::*;
const INPUT: &str = include_str!("test.txt");
#[test]
fn check_part1() {
assert_eq!(10605, part1(parse(&INPUT)));
}
}
The test should pass & the first solution should be printed when running the program using cargo run.
Part 2
The same game is repeated, but the worry level is not be divided by three anymore when a monkey throws an item & it does not break. This causes the worry level to increase even more, so a different way has to be found to keep it in check. The game also is now expanded to be played for 10.000 rounds.
Naively the existing play function is used for part 2 of the challenge as well.
fn part2(monkeys: Vec<Monkey>) -> u64 {
play(monkeys, 10_000)
}
#[cfg(test)]
mod tests {
#[test]
fn check_part2() {
let monkeys = parse(&INPUT);
assert_eq!(2_713_310_158, part2(monkeys));
}
}
The play function needs to be refactored. For part one a divisible factor of three is used, which is not applied in part 2.
The new Option parameter divisible indicates if the given division is applied or not.
// 👇 use `Some` & `None` to indicate divisor
fn play(mut monkeys: Vec<Monkey>, num_rounds: u32, divisible: Option<u64>) -> u64 {
let num_monkeys = monkeys.len();
for _ in 0..num_rounds {
for index in 0..num_monkeys {
let items = monkeys[index].items.drain(..).collect::<Vec<_>>();
let operation = monkeys[index].operation;
let test = monkeys[index].test.clone();
for worry_level in items {
let mut worry_level = operation.apply(worry_level);
if let Some(divisible) = divisible {
worry_level /= divisible
}
if worry_level % test.divisible == 0 {
monkeys[test.if_true].items.push(worry_level);
} else {
monkeys[test.if_false].items.push(worry_level);
}
monkeys[index].inspections += 1;
}
}
}
monkeys
.iter()
.map(|m| m.inspections)
.sorted()
.rev()
.take(2)
.product()
}
fn part1(monkeys: Vec<Monkey>) -> u64 {
// 👇 indicates divisible by three
play(monkeys, 20, Some(3))
}
fn part2(monkeys: Vec<Monkey>) -> u64 {
// 👇 indicates no division
play(monkeys, 10_000, None)
}
Otherwise the solution is the same, the product of the two busiest monkeys is calculated. A test is added to check the expected result. The test unfortunately fails with the following error:
---- tests::check_part2 stdout ----
thread 'tests::check_part2' panicked at 'attempt to multiply with overflow', src/main.rs:68:35
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
At this point the current logic does not handle the calculations well, bigger integer types won't help here, a different approach is required.
We realize the worry level is not necessarily important, it's taken into account to determine to which monkey an item is thrown next to, it's usedto check if the level is divisble by zero. There are also only eight monkeys in the given input, meaning there are only eight possible values
for the divisible factor.
It should be fine to use the common denominator of all eight divisible values & use this to update the worry level. It's the product of all eight values. Then the modulo result of the worry level with the denominator keeps the level itself in range of the integer type.
One last refactoring of the play function should fix the calculation.
fn play(mut monkeys: Vec<Monkey>, num_rounds: u32, divisible: Option<u64>) -> u64 {
let num_monkeys = monkeys.len();
// 👇 calculate denominator
let common_denominator: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
// play a nmber of N rounds
for _ in 0..num_rounds {
for index in 0..num_monkeys {
let items = monkeys[index].items.drain(..).collect::<Vec<_>>();
let operation = monkeys[index].operation;
let test = monkeys[index].test.clone();
for worry_level in items {
let worry_level = operation.apply(worry_level);
let worry_level = if let Some(divisible) = divisible {
worry_level / divisible
} else {
// 👇 adjust worry level
worry_level % common_denominator
};
if worry_level % test.divisible == 0 {
monkeys[test.if_true].items.push(worry_level);
} else {
monkeys[test.if_false].items.push(worry_level);
}
monkeys[index].inspections += 1;
}
}
}
monkeys
.iter()
.map(|m| m.inspections)
.sorted()
.rev()
.take(2)
.product()
}
The rest of the function is the same as before. All tests should pass now. Running the program also should return the solution for the second part.