If you missed any previous days, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 – 7 Reasons why you should participate. If you’re here to see the solution of Day 11, continue reading 😉
Table of Contents
GitHub Repository
https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2022
I will upload all of my solutions there – in the form of Python (or Scala alternatives) notebooks. You have to use your own input for the “input.txt” since everyone gets their own and everyone needs to provide a different solution based on their input.
Day 11 Puzzle
On day 11 of Advent of Code, we had to track where the monkeys throw our items and which monkeys handle the most of our items so we can catch them. The monkey input looks like this for several monkeys:
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 0As always, I read in all lines:
with open('input.txt', 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]The Monkey class
I created a monkey class to keep track of its rules and items it’s currently holding.
Note: You could have very much handcoded the rules for each monkey, even in the larger input you only get around 7 monkeys. I parsed everything because I go by the rule “rather spend 1h automating something than doing it by hand in 10min”. So this parsing is most of the init method.
class Monkey:
def __init__(self, lines) -> None:
self.number = int(lines[0][-2])
start_items_string = lines[1].replace(':', '').replace(',', '')
self.items = [int(word) for word in start_items_string.split(' ') if word.isdigit()]
self.operation = lines[2].split(' ')[-2]
self.operand = lines[2].split(' ')[-1]
self.test_condition = int(lines[3].split(' ')[-1])
self.true_monkey = int(lines[4].split(' ')[-1])
self.false_monkey = int(lines[5].split(' ')[-1])
self.inspections = 0
def inspect_items(self):
for i, item in enumerate(self.items):
self.inspections += 1
if self.operation == '+':
self.items[i] += int(self.operand)
if self.operation == '*':
if self.operand.isdigit():
self.items[i] *= int(self.operand)
else:
self.items[i] *= item
def reduce_worries(self):
for i, item in enumerate(self.items):
self.items[i] = item // 3
def throw_items(self):
planned_throws = []
for item in self.items:
if item % self.test_condition == 0:
planned_throws.append((item, self.true_monkey))
else:
planned_throws.append((item, self.false_monkey))
self.items = []
return planned_throws
def receive_item(self, item):
self.items.append(item)
def print_monkey_items(self):
print(f"Monkey {self.number}:" + ', '.join([str(item) for item in self.items]))Part 1
Our only task was to simulate 20 rounds of inspecting and throwing and keeping track of the number of inspections each monkey does which is saved in the monkey object.
def solve_part_1(file):
with open(file, 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
monkeys = []
while len(lines) > 0:
monkeys.append(Monkey(lines))
lines = lines[7:] if len(lines) > 7 else []
round = 0
while round < 20:
round += 1
for monkey in monkeys:
monkey.inspect_items()
monkey.reduce_worries()
planned_throws = monkey.throw_items()
for item, target_monkey in planned_throws:
monkeys[target_monkey].receive_item(item)
print(f"After round {round}:")
for monkey in monkeys:
monkey.print_monkey_items()
inspections = [monkey.inspections for monkey in monkeys]
print(np.prod(sorted(inspections, reverse=True)[:2]))At the end we multiply the two highest inspection counts (I used numpy.prod to multiple the two highest entries together, you could do it with * as well) to get the solution.
Part 2
Here the reduce_worries is removed. That means we would run into huuge numbers, likely too high to be saved by an integer. It was up to each puzzle solver to decide how to deal with that.
I noticed it was only important if the worry value was divisible by each monkey’s assessment number. So I used modulo arithmetic.
Modulo arithmetic idea explained
For every item, I don’t save one big number, but instead 1 smaller number per monkey.
# example
Monkey 1 divides by 23
Monkey 2 divides by 19
Monkey 3 divides by 13
Monkey 4 divides by 17
# save value 325 as:
[325 % 23, 325 % 19, 325 % 13, 325 % 17]None of these numbers get higher than 23.
Since you can calculate within modulo (see properties of modulo and modular arithmetic on Wikipedia), but specifically we care about this:
(a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n \\
ab \mod n = [(a \mod n)(b \mod n)] \mod n.What this means: it doesn’t matter if we first take the modulo and then multiply (part 2) or first multiply and then take the modulo (essentially what we did in part 1 to see if the number is divisible by x). Except that first taking the modulo keeps the numbers nice and small 🙂
Code for part 2
MonkeyItem keeps track of all these modulo operations per monkey:
class MonkeyItem:
def __init__(self, divisors, start_value) -> None:
self.values_per_monkey = []
self.divisors = divisors
for divisor in divisors:
self.values_per_monkey.append(start_value % divisor)
def add_value(self, addon):
for i, value in enumerate(self.values_per_monkey):
self.values_per_monkey[i] = (value + addon) % self.divisors[i]
def square_value(self):
for i, value in enumerate(self.values_per_monkey):
self.values_per_monkey[i] = (value**2) % self.divisors[i]
def multiply_value(self, multiplier):
for i, value in enumerate(self.values_per_monkey):
self.values_per_monkey[i] = (value*multiplier) % self.divisors[i]The adapted Monkey class for this new item:
class Monkey2:
def __init__(self, lines) -> None:
self.number = int(lines[0][-2])
start_items_string = lines[1].replace(':', '').replace(',', '')
self.items = [int(word) for word in start_items_string.split(' ') if word.isdigit()]
self.operation = lines[2].split(' ')[-2]
self.operand = lines[2].split(' ')[-1]
self.test_condition = int(lines[3].split(' ')[-1])
self.true_monkey = int(lines[4].split(' ')[-1])
self.false_monkey = int(lines[5].split(' ')[-1])
self.inspections = 0
def convert_item_values(self, divisors):
new_items = []
for item_value in self.items:
new_items.append(MonkeyItem(divisors, item_value))
self.items = new_items
def inspect_items(self):
for i, item in enumerate(self.items):
self.inspections += 1
if self.operation == '+':
self.items[i].add_value(int(self.operand))
if self.operation == '*':
if self.operand.isdigit():
self.items[i].multiply_value(int(self.operand))
else:
self.items[i].square_value()
def throw_items(self):
planned_throws = []
for item in self.items:
if item.values_per_monkey[self.number] == 0:
planned_throws.append((item, self.true_monkey))
else:
planned_throws.append((item, self.false_monkey))
self.items = []
return planned_throws
def receive_item(self, item):
self.items.append(item)
def print_monkey_items(self):
print(f"Monkey {self.number}:" + ', '.join([str(item.values_per_monkey) for item in self.items]))The adapted main loop with the divisors used in modulo operations:
def solve_part_2(file):
with open(file, 'r') as f:
lines = f.readlines()
lines = [entry.strip() for entry in lines]
monkeys = []
while len(lines) > 0:
monkeys.append(Monkey2(lines))
lines = lines[7:] if len(lines) > 7 else []
divisors = test_conditions = [monkey.test_condition for monkey in monkeys]
for monkey in monkeys:
monkey.convert_item_values(divisors)
round = 0
while round < 10000:
round += 1
for monkey in monkeys:
monkey.inspect_items()
planned_throws = monkey.throw_items()
for item, target_monkey in planned_throws:
monkeys[target_monkey].receive_item(item)
inspections = [monkey.inspections for monkey in monkeys]
print(np.prod(sorted(inspections, reverse=True)[:2]))Conclusion
Quite a bit of code, but I LOVED this challenge. Figuring out part 2 made me feel like my math degree was finally useful 😉 I even did some test calculations on paper to make sure I wasn’t making these module rules up, but they all ended up working.
The ring of integers modulo n was one of the first things that completely fascinated me in my math degree and I hope this puzzle makes some of you realize how useful weird abstract math like that can be <3
Thank you for this super elegant solution; I’m a total n00b at Python and I sucked at math in high school, yet you managed to explain this in a way I could follow along. Kudos.