NickyMeulemanNime
Metadata
  • Date

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 10

  • Newer post

    Advent of Code 2022 Day 12

Table of contents
  1. Day 11: Monkey in the Middle
  2. Parsing
  3. Part 1
    1. Helper functions
    2. Final code
  4. Part 2
    1. Final code
  5. Final code

Advent of Code 2022 Day 11

Day 11: Monkey in the Middle

https://adventofcode.com/2022/day/11

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:

input.txt
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.

  1. the first has worry level 79
  2. 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.

  1. The first operand is always the old worry level.
  2. 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.

day_11.rs
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:

pseudocode.rs
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
}
}
}

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):

day_11.rs
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

day_11.rs
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

day_11.rs
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

day_11.rs
1#[derive(Clone)]
2struct Monkey {
3 items: Vec<u64>,
4 operation: Operation,
5 test: Test,
6}
7
8#[derive(Clone)]
9enum Operation {
10 Mul(Value),
11 Add(Value),
12}
13
14impl Operation {
15 fn apply(&self, old: u64) -> u64 {
16 match &self {
17 Operation::Add(val) => old + val.number(old),
18 Operation::Mul(val) => old * val.number(old),
19 }
20 }
21}
22
23#[derive(Clone)]
24enum Value {
25 Old,
26 Num(u64),
27}
28
29impl Value {
30 fn number(&self, old: u64) -> u64 {
31 match self {
32 Value::Num(n) => *n,
33 Value::Old => old,
34 }
35 }
36}
37
38#[derive(Clone)]
39struct Test {
40 divisible: u64,
41 true_recipient: usize,
42 false_recipient: usize,
43}
44
45fn parse() -> Option<Vec<Monkey>> {
46 let input = std::fs::read_to_string("src/day11.txt").ok()?;
47
48 let mut monkeys = Vec::new();
49 for block in input.split("\n\n") {
50 let mut lines = block.lines().skip(1);
51
52 let (_, items) = lines.next()?.split_once(": ")?;
53 let items = items
54 .split_terminator(", ")
55 .filter_map(|s| s.parse().ok())
56 .collect();
57
58 let (_, operation) = lines.next()?.split_once("= old ")?;
59 let (operator, operand) = operation.split_once(" ")?;
60 let operand = match operand {
61 "old" => Value::Old,
62 _ => {
63 let n = operand.parse().ok()?;
64 Value::Num(n)
65 }
66 };
67
68 let (_, divisible) = lines.next()?.rsplit_once(" ")?;
69 let divisible = divisible.parse().ok()?;
70 let (_, true_recipient) = lines.next()?.rsplit_once(" ")?;
71 let true_recipient = true_recipient.parse().ok()?;
72 let (_, false_recipient) = lines.next()?.rsplit_once(" ")?;
73 let false_recipient = false_recipient.parse().ok()?;
74
75 let operation = match operator {
76 "+" => Operation::Add(operand),
77 "*" => Operation::Mul(operand),
78 _ => panic!("Inalid input"),
79 };
80
81 let test = Test {
82 divisible,
83 true_recipient,
84 false_recipient,
85 };
86
87 let monkey = Monkey {
88 items,
89 operation,
90 test,
91 };
92
93 monkeys.push(monkey);
94 }
95
96 Some(monkeys)
97}
98
99pub fn part_1() -> usize {
100 let mut monkeys = parse().unwrap();
101 let mut inspections = vec![0; monkeys.len()];
102
103 for _ in 0..20 {
104 for idx in 0..monkeys.len() {
105 let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
106 let monkey = monkeys[idx].clone();
107 for old in items {
108 // inspect
109 inspections[idx] += 1;
110 // operation
111 let new = monkey.operation.apply(old);
112 // relieved
113 let new = new / 3;
114 // test
115 let idx = if new % monkey.test.divisible == 0 {
116 monkey.test.true_recipient
117 } else {
118 monkey.test.false_recipient
119 };
120 let receiver = &mut monkeys[idx];
121 // throw
122 receiver.items.push(new);
123 }
124 }
125 }
126
127 inspections.sort_unstable();
128 inspections.iter().rev().take(2).product()
129}
130
131pub fn part_2() -> usize {
132 let mut monkeys = parse().unwrap();
133 let mut inspections = vec![0; monkeys.len()];
134 let common_multiple: u64 = monkeys.iter().map(|monkey| monkey.test.divisible).product();
135
136 for _ in 0..10_000 {
137 for idx in 0..monkeys.len() {
138 let items: Vec<u64> = monkeys[idx].items.drain(..).collect();
139 let monkey = monkeys[idx].clone();
140 for old in items {
141 // inspect
142 inspections[idx] += 1;
143 // operation
144 let new = monkey.operation.apply(old);
145 // not relieved
146 let new = new % common_multiple;
147 // test
148 let idx = if new % monkey.test.divisible == 0 {
149 monkey.test.true_recipient
150 } else {
151 monkey.test.false_recipient
152 };
153 let receiver = &mut monkeys[idx];
154 // throw
155 receiver.items.push(new);
156 }
157 }
158 }
159
160 inspections.sort_unstable();
161 inspections.iter().rev().take(2).product()
162}

Series navigation for: Advent of Code 2022

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.