Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 11
Useful Links
Concepts and Packages Demonstrated
regexdeepcopyTiming with tqdmClassCounterModulo Congruence
Page Navigation
Problem Intro
Naughty monkeys have stolen by stuff! They each have a number of my items. The starting items field of the input data gives tells us how worried I am about each item. The input data looks something 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
They are playing Monkey in the Middle. I’m the one in the midde. How it works:
- For each round of the game, Monkey 0 goes first, then Monkey 1, and so on.
- The monkey inspects the first item it has. This causes my worry score to go up.
- Then my worry score drops, according to the rule: divide by 3 and round down.
- The monkey then throws this item to another monkey, based on the division test.
- The monkey does this inspect-throw cycle, for every item it has, until there are no more items.
Part 1
What is the level of monkey business after 20 rounds of stuff-slinging simian shenanigans?
We need to count how many times each monkey inspects my items. The value of monkey business is given by the product of this count from the two monkeys with the greatest count.
Here’s my approach:
- Create a
Monkeyclass which:- Stores id, items (list), worry operation (str), test divisor, and inspection count.
- Has an
inspect()method which:- Increases this monkey’s inspect count.
- Retrieves the worry score for the first item stored.
- Performs the worry operation, which changes the worry score for this item.
- Performs the relief step, i.e. dividing by 3 and rounding down.
- Performs the division test by checking if the modulus of the divisor is 0, and setting the target monkey accordingly.
class Monkey:
""" The monkey has a bunch of my things.
start_items = worry level for each item, in the order they will be inspectd
worry_op = how worry level changes as the monkey inspects the item
"""
def __init__(self, monkey_id: int, items: list, worry_op: str, div: int, throw_to: list) -> None:
self.monkey_id = monkey_id # E.g. 0
self.start_items = items # E.g. [79, 98]
self._worry_op = worry_op # E.g. old * 19
self.divisor = div # E.g. 13
self._throw_to = throw_to # E.g. [2, 3]
self.inspect_count = 0
def add_item(self, item:int):
self.start_items.append(item)
def inspect(self) -> int:
""" Inspects the next item in the list.
Inspecting causes our worry level to go up, as given by worry_op.
If relief enabled, we then reduce our worry level by //3.
Then we work out who to throw to, by dividing by a divisor.
In part 2:
- relief is disabled and worry level can get VERY LARGE!!
- We can significantly reduce this number by using LCM trick.
"""
self.inspect_count += 1
# turn "old * 19" into "79 * 19"
worry_op = self._worry_op.replace("old", str(self.start_items[0]))
first, the_op, second = re.findall(r"(\w+) (.) (\w+)", worry_op)[0]
ops_dict = {
"+": operator.add,
"*": operator.mul
}
self.start_items[0] = ops_dict[the_op](int(first), int(second))
# Relief. Rule = divide by three and round down
self.start_items[0] //= 3
return self._throw_to[0] if self.start_items[0] % self.divisor == 0 \
else self._throw_to[1]
def throw_to(self, other: Monkey):
other.add_item(self.start_items.pop(0))
def __repr__(self) -> str:
return f"Monkey:(id={self.monkey_id}, items={self.start_items}, " \
+ f"inspect_count={self.inspect_count})"
Next, read in the input data and create a list of Monkeys from this data.
def parse_input(data: str) -> dict[int, Monkey]:
blocks = data.split("\n\n")
monkeys = {}
for block in blocks:
for line in block.splitlines():
if line.startswith("Monkey"):
monkey_id = int(re.findall(r"(\d+)", line)[0])
if "items:" in line:
items = list(map(int, re.findall(r"(\d+)", line)))
if "Operation:" in line:
worry_op = line.split("=")[-1].strip()
if "Test:" in line:
divisor = int(re.findall(r"\d+", line)[0])
if "true:" in line:
to_monkey_true = int(re.findall(r"\d+", line)[0])
if "false:" in line:
to_monkey_false = int(re.findall(r"\d+", line)[0])
monkey = Monkey(monkey_id=monkey_id, items=items,
worry_op=worry_op, div=divisor,
throw_to=[to_monkey_true, to_monkey_false])
monkeys[monkey_id] = monkey
return monkeys
Now we play 20 rounds of the game, as required:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()
monkeys = parse_input(data)
print("\n".join(str(monkey) for id, monkey in monkeys.items()))
# Part 1
monkey_business = play(copy.deepcopy(monkeys), 20)
print(f"Part 1: monkey business={monkey_business}")
def play(monkeys: dict[int, Monkey], rounds_to_play: int) -> int:
""" Play required number of rounds.
Returns 'Monkey Business' = product of the top two inspection counts """
for _ in range(1, rounds_to_play+1):
for monkey in monkeys.values(): # Iterator through monkeys in order
while monkey.start_items: # Monkey inspects and throws until it has no more items
to_monkey = monkeys[monkey.inspect()]
monkey.throw_to(to_monkey)
# Get the two monkeys that have inspected the most
monkey_inspect = Counter({monkey.monkey_id: monkey.inspect_count for monkey in monkeys.values()})
two_most_common = monkey_inspect.most_common(2)
return two_most_common[0][1] * two_most_common[1][1]
That wasn’t too bad!
Part 2
Urgh, I spoke too soon.
We’re told that the worry relief step no longer happens.
What is the level of monkey business after 10000 rounds?
The problem here is that the worry score gets very large, very quickly!! In the output below, I’m printing the worry score of just the first item held by monkey 5, for each round of the game. Look how fast it grows!!
Round 1, monkey 5, first item: 60
Round 2, monkey 5, first item: 65
Round 3, monkey 5, first item: 4357
Round 4, monkey 5, first item: 302501
Round 5, monkey 5, first item: 574565
Round 6, monkey 5, first item: 1132995601
Round 7, monkey 5, first item: 112973965457
Round 8, monkey 5, first item: 66345395777
Round 9, monkey 5, first item: 145983598085
Round 10, monkey 5, first item: 869291291519169243077
Round 11, monkey 5, first item: 194394222161788859717
Round 13, monkey 5, first item: 3707953477216897791636998597
Round 14, monkey 5, first item: 91435749290838899413486607953237309215210917
Round 15, monkey 5, first item: 91435749290838899413486607953237309215210917
Round 16, monkey 5, first item: 475305472147531532905077008835042795254612334925925
Round 17, monkey 5, first item: 10978531075057958773242647614034395559845342277
Round 18, monkey 5, first item: 3327138305032720730335539061845299566782286344481543
Round 19, monkey 5, first item: 3994349693662791921638935654895733812151353491072884187125317
Round 20, monkey 5, first item: 2428899730574776919351574517249403431446194393675444403748819090519729633297989697799769895877
Yeah… So this isn’t going to get anywhere near 10000 rounds!!
The important thing to realise is that we only care about the remainder of the division operation with our worry score. And furthermore, according to modulo arithmetic, there are some rules that are really useful to us:
1. If a ≡ b % m and b = d % m then a ≡ d % m
2. If a ≡ b % m, then a + c ≡ (b + c) % m
3. If a ≡ b % m, then ax ≡ bx % mx
4. a % m = (a % km) % m
Here ≡ means “is congruent to”. So a is congruent to b (mod M).
Going through these one at a time…
1. If a ≡ b % m and b = d % m then a ≡ d % m
Using Mod 5 as an example:
If 11 ≡ 1 % 5 and 1 = 26 % 5 then 11 ≡ 26 % 5
This means that 11 is congruent to 1 % 5. Of course, 1, 6, 11, 16, 21, 26... are all congruent
to 1 % 5, since they all result in a remainder of 1. They are all in the same remainder group.
Next:
2. If a ≡ b % m, then a + c ≡ (b + c) % m
I.e. if a and b are in the same bucket, then the remainder of division is preserved if we add a constant to either. E.g.
If 11 ≡ 26 % 5, then 11+1 ≡ (26+1) % 5
This is obviously true, since 12 % 5 = 2 and 27 % 5 = 2.
Next:
3. If a ≡ b % m, then ax ≡ bx % mx
E.g.
If 11 ≡ 26 % 5, then (11*9) ≡ (26*9) % (5*9)
We can show that 99 ≡ 234 % 45, because 99 % 45 = 9 and 234 % 45 = 9.
And finally:
4. a % m = (a % km) % m
I.e. km must be a multiple of m.
E.g.
k = 2
26 % 5 = (26 % (2*5)) % 5
1 = (26 % 10) % 5
= 6 % 5
= 1
k = 30
26 % 5 = (26 % (30*5)) % 5
1 = (26 % 150) % 5
= 26 % 5
= 1
We see that the value of k becomes irrelevant. All that is important is that the first mod is with a value that is a multiple of m.
In Part 2, we’re told we don’t divide the worry score any more. And our worry operation only ever multiplies or adds to the worry score. This is crucial: modulo congruence is preserved for any multiplication or addition operations. We have demonstrated this with the equations above.
So that means that even after we apply our worry operation, the remainder of our modulo operation will be unchanged. So, because we only need to maintain a value that always returns the same remainder after division, we have an option to store w (mod km) rather than w, for any worry value, w. This is from rule 4 above. I.e.
w % m = (w % km) % m
We do the % m when we perform the test. We just need to a small alternative to w. We know the w % km will be a much smaller number than w and will never grow beyond the size of km.
But what value of km should we use?
As we’ve previously demonstrated, the value needs to be a multiple of our divisor. But it also needs to be a multiple of all our divisors, since our value of w will be passed between monkeys. We can make the value a multiple of all our modulo divisors by using the lowest column multiple of all our divisors, since the LCM will work for every divisor we need to test with. But in the case of this particular problem, all our divisors are prime numbers. And for that reason, the LCM is actually just the product of all our divisors. But, we more generally, we can always just use the math.lcm() function. (Note that this is only available since Python 3.9.)
Demonstrating this with some numbers…
Random worry score, w = 12345678
w % m = 14
Here, m = 23, so:
w % 23 = 14
The product of monkey divisors, p = 23*19*13*17 = 96577
Note that p = mk. I.e. it is a muliple of 23, but a multiple of all the other divisors too.
x = w % p = 80399
x % 23 = 14
So, to summarise:
- We apply a modulo operation to our original worry score
w, using the product of divisors. (Which happens to be the LCM.) Let the result bem. - And
m%23 == w%23. So we can use this as the evaluation for the test!
Putting this all together…
First, we need to change our inspect() method:
def inspect(self, relief=True, lcm=None) -> int:
""" Inspects the next item in the list.
Inspecting causes our worry level to go up, as given by worry_op.
If relief enabled, we then reduce our worry level by //3.
Then we work out who to throw to, by dividing by a divisor.
In part 2:
- relief is disabled and worry level can get VERY LARGE!!
- We can significantly reduce this number by using LCM trick.
"""
self.inspect_count += 1
# turn "old * 19" into "79 * 19"
worry_op = self._worry_op.replace("old", str(self.start_items[0]))
first, the_op, second = re.findall(r"(\w+) (.) (\w+)", worry_op)[0]
ops_dict = {
"+": operator.add,
"*": operator.mul
}
self.start_items[0] = ops_dict[the_op](int(first), int(second))
# Relief. Rule = divide by three and round down
if relief:
self.start_items[0] //= 3
if lcm:
self.start_items[0] %= lcm
return self._throw_to[0] if self.start_items[0] % self.divisor == 0 \
else self._throw_to[1]
Note that I’ve changed the method signature, so that we can perform both Part 1 and Part 2. But what can’t we use the same approach for both parts? The answer: because division does not preserve modulo congruence. And since Part 1 requires us to divide by three, we can’t use the LCM approach for Part 1.
Blimey. That was hard!
Results
The final code:
from __future__ import annotations
from collections import Counter
import copy
import math
import operator
from pathlib import Path
import time
import re
from tqdm import tqdm
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
class Monkey:
""" The monkey has a bunch of my things.
start_items = worry level for each item, in the order they will be inspectd
worry_op = how worry level changes as the monkey inspects the item
"""
def __init__(self, monkey_id: int, items: list, worry_op: str, div: int, throw_to: list) -> None:
self.monkey_id = monkey_id # E.g. 0
self.start_items = items # E.g. [79, 98]
self._worry_op = worry_op # E.g. old * 19
self.divisor = div # E.g. 13
self._throw_to = throw_to # E.g. [2, 3]
self.inspect_count = 0
def add_item(self, item:int):
self.start_items.append(item)
def inspect(self, relief=True, lcm=None) -> int:
""" Inspects the next item in the list.
Inspecting causes our worry level to go up, as given by worry_op.
If relief enabled, we then reduce our worry level by //3.
Then we work out who to throw to, by dividing by a divisor.
In part 2:
- relief is disabled and worry level can get VERY LARGE!!
- We can significantly reduce this number by using LCM trick.
"""
self.inspect_count += 1
# turn "old * 19" into "79 * 19"
worry_op = self._worry_op.replace("old", str(self.start_items[0]))
first, the_op, second = re.findall(r"(\w+) (.) (\w+)", worry_op)[0]
ops_dict = {
"+": operator.add,
"*": operator.mul
}
self.start_items[0] = ops_dict[the_op](int(first), int(second))
# Relief. Rule = divide by three and round down
if relief:
self.start_items[0] //= 3
if lcm:
self.start_items[0] %= lcm
return self._throw_to[0] if self.start_items[0] % self.divisor == 0 \
else self._throw_to[1]
def throw_to(self, other: Monkey):
other.add_item(self.start_items.pop(0))
def __repr__(self) -> str:
return f"Monkey:(id={self.monkey_id}, items={self.start_items}, " \
+ f"inspect_count={self.inspect_count})"
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()
monkeys = parse_input(data)
print("\n".join(str(monkey) for id, monkey in monkeys.items()))
# Part 1
monkey_business = play(copy.deepcopy(monkeys), 20)
print(f"Part 1: monkey business={monkey_business}")
# Part 2
lcm = math.lcm(*[monkey.divisor for monkey in monkeys.values()])
# Note that here, the lcm is actually the product of these numbers, since they are all prime.
# But in general, we would want to use LCM.
monkey_business = play(monkeys, 10000, relief=False, lcm=lcm)
print(f"Part 2: monkey business={monkey_business}")
def play(monkeys: dict[int, Monkey], rounds_to_play: int, relief=True, lcm=None) -> int:
""" Play required number of rounds.
Returns 'Monkey Business' = product of the top two inspection counts """
for _ in tqdm(range(1, rounds_to_play+1)):
for monkey in monkeys.values(): # Iterator through monkeys in order
while monkey.start_items: # Monkey inspects and throws until it has no more items
to_monkey = monkeys[monkey.inspect(relief=relief, lcm=lcm)]
monkey.throw_to(to_monkey)
# Get the two monkeys that have inspected the most
monkey_inspect = Counter({monkey.monkey_id: monkey.inspect_count for monkey in monkeys.values()})
two_most_common = monkey_inspect.most_common(2)
return two_most_common[0][1] * two_most_common[1][1]
def parse_input(data: str) -> dict[int, Monkey]:
blocks = data.split("\n\n")
monkeys = {}
for block in blocks:
for line in block.splitlines():
if line.startswith("Monkey"):
monkey_id = int(re.findall(r"(\d+)", line)[0])
if "items:" in line:
items = list(map(int, re.findall(r"(\d+)", line)))
if "Operation:" in line:
worry_op = line.split("=")[-1].strip()
if "Test:" in line:
divisor = int(re.findall(r"\d+", line)[0])
if "true:" in line:
to_monkey_true = int(re.findall(r"\d+", line)[0])
if "false:" in line:
to_monkey_false = int(re.findall(r"\d+", line)[0])
monkey = Monkey(monkey_id=monkey_id, items=items,
worry_op=worry_op, div=divisor,
throw_to=[to_monkey_true, to_monkey_false])
monkeys[monkey_id] = monkey
return monkeys
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
Note that I’ve wrapped game loop with tqdm to show progress.
Here’s the output:
Monkey:(id=0, items=[64, 89, 65, 95], inspect_count=0)
Monkey:(id=1, items=[76, 66, 74, 87, 70, 56, 51, 66], inspect_count=0)
Monkey:(id=2, items=[91, 60, 63], inspect_count=0)
Monkey:(id=3, items=[92, 61, 79, 97, 79], inspect_count=0)
Monkey:(id=4, items=[93, 54], inspect_count=0)
Monkey:(id=5, items=[60, 79, 92, 69, 88, 82, 70], inspect_count=0)
Monkey:(id=6, items=[64, 57, 73, 89, 55, 53], inspect_count=0)
Monkey:(id=7, items=[62], inspect_count=0)
100%|████████████████████████████████████████████████████████████████████████████| 20/20 [00:00<00:00, 2080.66it/s]
Part 1: monkey business=113232
100%|██████████████████████████████████████████████████████████████████████| 10000/10000 [00:02<00:00, 4702.68it/s]
Part 2: monkey business=29703395016
Execution time: 2.1040 seconds