Day 11: Monkey in the Middle
https://adventofcode.com/2022/day/11
TL;DR: my solution in Rust
Monkeys have your belongings and are throwing them to each other!
Each monkey follows a few rules that determine to which other monkey they throw an item.
The monkeys are numbered, and they take turns throwing all their items.
When a monkey throws items, it throws them in order, from oldest to newest.
A determining factor in those rules is how worried you are about an item (expressed as a number, the worry level).
Today's input is a list of monkeys with the rules that each one follows.
An example input looks like this:
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
Monkey 0 starts with 2 items.
- the first has worry level 79
- the second has worry level 98
Whenever a monkey inspects an item, they apply their operation.
This operation changes an item's worry level.
Monkey 0 multiplies the worry level of the inspected item by 19.
Before a monkey thows an item, it applies a test to the current worry level.
Monkey 0 checks if the worry level is divisible by 23.
- if it is, it throws the item to monkey 2
- if it is not, it throws the item to monkey 3
Parsing
I decided to parse the input into a list of Monkeys.
A Monkey directly maps to a monkey in the input.
struct Monkey {
items: Vec<u64>,
operation: Operation,
test: Test,
}
An operation is always either a multiplication or an addition.
- The first operand is always the old worry level.
- The second operand is either the old worry level or a literal number.
Since the second one is the only one that ever changes, that's the one I store.
enum Operation {
Mul(Value),
Add(Value),
}
enum Value {
Old,
Num(u64),
}
The test has three parts, the divisibility check, which monkey to throw to if it succeeds, and which to throw to if it fails.
struct Test {
divisible: u64,
true_recipient: usize,
false_recipient: usize,
}
The parsing code is quite boring, I turn the input into blocks for each monkey.
Every block, I parse into a Monkey and add it to the monkeys list.
To do this I turn each string block into lines, and per line consumed, I extract the wanted info from it.
Those questionmarks in my code, I affectionately refer to those as the Annie operator.
Read the blogpost about what they do, and why I call it the Annie operator
fn parse() -> Option<Vec<Monkey>> {
let input = std::fs::read_to_string("src/day11.txt").ok()?;
let mut monkeys = Vec::new();
for block in input.split("\n\n") {
let mut lines = block.lines().skip(1);
let (_, items) = lines.next()?.split_once(": ")?;
let items = items
.split_terminator(", ")
.filter_map(|s| s.parse().ok())
.collect();
let (_, operation) = lines.next()?.split_once("= old ")?;
let (operator, operand) = operation.split_once(" ")?;
let operand = match operand {
"old" => Value::Old,
_ => {
let n = operand.parse().ok()?;
Value::Num(n)
}
};
let (_, divisible) = lines.next()?.rsplit_once(" ")?;
let divisible = divisible.parse().ok()?;
let (_, true_recipient) = lines.next()?.rsplit_once(" ")?;
let true_recipient = true_recipient.parse().ok()?;
let (_, false_recipient) = lines.next()?.rsplit_once(" ")?;
let false_recipient = false_recipient.parse().ok()?;
let operation = match operator {
"+" => Operation::Add(operand),
"*" => Operation::Mul(operand),
_ => panic!("Inalid input"),
};
let test = Test {
divisible,
true_recipient,
false_recipient,
};
let monkey = Monkey {
items,
operation,
test,
};
monkeys.push(monkey);
}
Some(monkeys)
}
Part 1
After each monkey inspects an item but before it tests your worry level,
your relief that the monkey's inspection didn't damage the item causes your worry level to be divided by three and rounded down to the nearest integer.
You track the amount of times a monkey inspects any item.
The product of the 2 largest amounts is called the monkey business.
The question asks what the level of monkey business is after 20 rounds.
Starting skeleton code for part1:
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {
for idx in 0..monkeys.len() {
let monkey = monkeys[idx];
for item in monkey.items {
// remove item from inventory
// monkey inspects item
// monkey does operation
// you are relieved
// monkey tests worry level
// monkey throws item to other monkey
}
}
}
If you are also doing this problem in Rust, the code I just wrote will create warnings relating to the borrow checker.
The Primeagen has a great explainer video on what it does and why.
Helper functions
To make write out those steps a bit clearer, I created a few helpers.
A method on Value gets a number for one whenever you give it the old worry level.
impl Value {
fn number(&self, old: u64) -> u64 {
match self {
Value::Num(n) => *n,
Value::Old => old,
}
}
}
A method on Operation does a monkey's operation.
It calculated the new worry level if you give it the old worry level.
impl Operation {
fn apply(&self, old: u64) -> u64 {
match &self {
Operation::Add(val) => old + val.number(old),
Operation::Mul(val) => old * val.number(old),
}
}
}
Filling in the code from before (and catching the borrow checker issue):
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {
for idx in 0..monkeys.len() {
// clear the monkey's inventory
let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
let monkey = monkeys[idx].clone();
for old in items {
// inspect
inspections[idx] += 1;
// operation
let new = monkey.operation.apply(old);
// relieved
let new = new / 3;
// test
let idx = if new % monkey.test.divisible == 0 {
monkey.test.true_recipient
} else {
monkey.test.false_recipient
};
let receiver = &mut monkeys[idx];
// throw
receiver.items.push(new);
}
}
}
// calculate monkey business
inspections.sort_unstable();
inspections.iter().rev().take(2).product()
It works, that's part1 done!
Final code
pub fn part_1() -> usize {
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {
for idx in 0..monkeys.len() {
let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
let monkey = monkeys[idx].clone();
for old in items {
// inspect
inspections[idx] += 1;
// operation
let new = monkey.operation.apply(old);
// relieved
let new = new / 3;
// test
let idx = if new % monkey.test.divisible == 0 {
monkey.test.true_recipient
} else {
monkey.test.false_recipient
};
let receiver = &mut monkeys[idx];
// throw
receiver.items.push(new);
}
}
}
inspections.sort_unstable();
inspections.iter().rev().take(2).product()
}
Part 2
You are no longer relieved after a monkey inspects an item.
The question asks what the level of monkey business is after 10000 rounds.
Ah, this will be easy, change the 20 to 10000 and remove the / 3 part
- me
Well, I was right, but there's one very minor, serious problem of needing a supercomputer for this to finish in a reasonable timeframe.
The worry levels get huge.
Absolutely massive.
Gigantic.
I'm in awe of the size of these numbers.
I took a common multiple of all divisibility checks, and took the modulus of the new worry level with that common multiple before I throw the item.
This will not affect any future divisibility checks.
Why doesn't it matter?:
The future checked item was %ed with a multiple of its divisibility check, this doesn't affect the result of such a check.
in code:
let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
// bla, bla, bla
// operation
let new = monkey.operation.apply(old);
// not relieved
let new = new % common_multiple;
// bla, bla, bla
receiver.items.push(new);
And with those changes, part2 is solved!
Final code
pub fn part_2() -> usize {
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
for _ in 0..10_000 {
for idx in 0..monkeys.len() {
let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
let monkey = monkeys[idx].clone();
for old in items {
// inspect
inspections[idx] += 1;
// operation
let new = monkey.operation.apply(old);
// not relieved
let new = new % common_multiple;
// test
let idx = if new % monkey.test.divisible == 0 {
monkey.test.true_recipient
} else {
monkey.test.false_recipient
};
let receiver = &mut monkeys[idx];
// throw
receiver.items.push(new);
}
}
}
inspections.sort_unstable();
inspections.iter().rev().take(2).product()
}
Final code
#[derive(Clone)]
struct Monkey {
items: Vec<u64>,
operation: Operation,
test: Test,
}
#[derive(Clone)]
enum Operation {
Mul(Value),
Add(Value),
}
impl Operation {
fn apply(&self, old: u64) -> u64 {
match &self {
Operation::Add(val) => old + val.number(old),
Operation::Mul(val) => old * val.number(old),
}
}
}
#[derive(Clone)]
enum Value {
Old,
Num(u64),
}
impl Value {
fn number(&self, old: u64) -> u64 {
match self {
Value::Num(n) => *n,
Value::Old => old,
}
}
}
#[derive(Clone)]
struct Test {
divisible: u64,
true_recipient: usize,
false_recipient: usize,
}
fn parse() -> Option<Vec<Monkey>> {
let input = std::fs::read_to_string("src/day11.txt").ok()?;
let mut monkeys = Vec::new();
for block in input.split("\n\n") {
let mut lines = block.lines().skip(1);
let (_, items) = lines.next()?.split_once(": ")?;
let items = items
.split_terminator(", ")
.filter_map(|s| s.parse().ok())
.collect();
let (_, operation) = lines.next()?.split_once("= old ")?;
let (operator, operand) = operation.split_once(" ")?;
let operand = match operand {
"old" => Value::Old,
_ => {
let n = operand.parse().ok()?;
Value::Num(n)
}
};
let (_, divisible) = lines.next()?.rsplit_once(" ")?;
let divisible = divisible.parse().ok()?;
let (_, true_recipient) = lines.next()?.rsplit_once(" ")?;
let true_recipient = true_recipient.parse().ok()?;
let (_, false_recipient) = lines.next()?.rsplit_once(" ")?;
let false_recipient = false_recipient.parse().ok()?;
let operation = match operator {
"+" => Operation::Add(operand),
"*" => Operation::Mul(operand),
_ => panic!("Inalid input"),
};
let test = Test {
divisible,
true_recipient,
false_recipient,
};
let monkey = Monkey {
items,
operation,
test,
};
monkeys.push(monkey);
}
Some(monkeys)
}
pub fn part_1() -> usize {
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
for _ in 0..20 {
for idx in 0..monkeys.len() {
let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
let monkey = monkeys[idx].clone();
for old in items {
// inspect
inspections[idx] += 1;
// operation
let new = monkey.operation.apply(old);
// relieved
let new = new / 3;
// test
let idx = if new % monkey.test.divisible == 0 {
monkey.test.true_recipient
} else {
monkey.test.false_recipient
};
let receiver = &mut monkeys[idx];
// throw
receiver.items.push(new);
}
}
}
inspections.sort_unstable();
inspections.iter().rev().take(2).product()
}
pub fn part_2() -> usize {
let mut monkeys = parse().unwrap();
let mut inspections = vec![0; monkeys.len()];
let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
for _ in 0..10_000 {
for idx in 0..monkeys.len() {
let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
let monkey = monkeys[idx].clone();
for old in items {
// inspect
inspections[idx] += 1;
// operation
let new = monkey.operation.apply(old);
// not relieved
let new = new % common_multiple;
// test
let idx = if new % monkey.test.divisible == 0 {
monkey.test.true_recipient
} else {
monkey.test.false_recipient
};
let receiver = &mut monkeys[idx];
// throw
receiver.items.push(new);
}
}
}
inspections.sort_unstable();
inspections.iter().rev().take(2).product()
}
Top comments (0)