As you finally start making your way upriver, you realize your pack is much lighter than you remember. Just then, one of the items from your pack goes flying overhead. Monkeys are playing Keep Away with your missing things!
To get your stuff back, you need to be able to predict where the monkeys will throw your items. After some careful observation, you realize the monkeys operate based on how worried you are about each item.
You take some notes (your puzzle input) on the items each monkey currently has, how worried you are about those items, and how the monkey makes decisions based on your worry level. For example:
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
Each monkey has several attributes:
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.
The monkeys take turns inspecting and throwing items. On a single monkey's turn, it inspects and throws all of the items it is holding one at a time and in the order listed. Monkey 0 goes first, then monkey 1, and so on until each monkey has had one turn. The process of each monkey taking a single turn is called a round.
When a monkey throws an item to another monkey, the item goes on the end of the recipient monkey's list. A monkey that starts a round with no items could end up inspecting and throwing many items by the time its turn comes around. If a monkey is holding no items at the start of its turn, its turn ends.
In the above example, the first round proceeds as follows:
Monkey 0:
Monkey inspects an item with a worry level of 79.
Worry level is multiplied by 19 to 1501.
Monkey gets bored with item. Worry level is divided by 3 to 500.
Current worry level is not divisible by 23.
Item with worry level 500 is thrown to monkey 3.
Monkey inspects an item with a worry level of 98.
Worry level is multiplied by 19 to 1862.
Monkey gets bored with item. Worry level is divided by 3 to 620.
Current worry level is not divisible by 23.
Item with worry level 620 is thrown to monkey 3.
Monkey 1:
Monkey inspects an item with a worry level of 54.
Worry level increases by 6 to 60.
Monkey gets bored with item. Worry level is divided by 3 to 20.
Current worry level is not divisible by 19.
Item with worry level 20 is thrown to monkey 0.
Monkey inspects an item with a worry level of 65.
Worry level increases by 6 to 71.
Monkey gets bored with item. Worry level is divided by 3 to 23.
Current worry level is not divisible by 19.
Item with worry level 23 is thrown to monkey 0.
Monkey inspects an item with a worry level of 75.
Worry level increases by 6 to 81.
Monkey gets bored with item. Worry level is divided by 3 to 27.
Current worry level is not divisible by 19.
Item with worry level 27 is thrown to monkey 0.
Monkey inspects an item with a worry level of 74.
Worry level increases by 6 to 80.
Monkey gets bored with item. Worry level is divided by 3 to 26.
Current worry level is not divisible by 19.
Item with worry level 26 is thrown to monkey 0.
Monkey 2:
Monkey inspects an item with a worry level of 79.
Worry level is multiplied by itself to 6241.
Monkey gets bored with item. Worry level is divided by 3 to 2080.
Current worry level is divisible by 13.
Item with worry level 2080 is thrown to monkey 1.
Monkey inspects an item with a worry level of 60.
Worry level is multiplied by itself to 3600.
Monkey gets bored with item. Worry level is divided by 3 to 1200.
Current worry level is not divisible by 13.
Item with worry level 1200 is thrown to monkey 3.
Monkey inspects an item with a worry level of 97.
Worry level is multiplied by itself to 9409.
Monkey gets bored with item. Worry level is divided by 3 to 3136.
Current worry level is not divisible by 13.
Item with worry level 3136 is thrown to monkey 3.
Monkey 3:
Monkey inspects an item with a worry level of 74.
Worry level increases by 3 to 77.
Monkey gets bored with item. Worry level is divided by 3 to 25.
Current worry level is not divisible by 17.
Item with worry level 25 is thrown to monkey 1.
Monkey inspects an item with a worry level of 500.
Worry level increases by 3 to 503.
Monkey gets bored with item. Worry level is divided by 3 to 167.
Current worry level is not divisible by 17.
Item with worry level 167 is thrown to monkey 1.
Monkey inspects an item with a worry level of 620.
Worry level increases by 3 to 623.
Monkey gets bored with item. Worry level is divided by 3 to 207.
Current worry level is not divisible by 17.
Item with worry level 207 is thrown to monkey 1.
Monkey inspects an item with a worry level of 1200.
Worry level increases by 3 to 1203.
Monkey gets bored with item. Worry level is divided by 3 to 401.
Current worry level is not divisible by 17.
Item with worry level 401 is thrown to monkey 1.
Monkey inspects an item with a worry level of 3136.
Worry level increases by 3 to 3139.
Monkey gets bored with item. Worry level is divided by 3 to 1046.
Current worry level is not divisible by 17.
Item with worry level 1046 is thrown to monkey 1.
After round 1, the monkeys are holding items with these worry levels:
Monkey 0: 20, 23, 27, 26
Monkey 1: 2080, 25, 167, 207, 401, 1046
Monkey 2:
Monkey 3:
Monkeys 2 and 3 aren't holding any items at the end of the round; they both inspected items during the round and threw them all before the round ended.
This process continues for a few more rounds:
After round 2, the monkeys are holding items with these worry levels:
Monkey 0: 695, 10, 71, 135, 350
Monkey 1: 43, 49, 58, 55, 362
Monkey 2:
Monkey 3:
After round 3, the monkeys are holding items with these worry levels:
Monkey 0: 16, 18, 21, 20, 122
Monkey 1: 1468, 22, 150, 286, 739
Monkey 2:
Monkey 3:
After round 4, the monkeys are holding items with these worry levels:
Monkey 0: 491, 9, 52, 97, 248, 34
Monkey 1: 39, 45, 43, 258
Monkey 2:
Monkey 3:
After round 5, the monkeys are holding items with these worry levels:
Monkey 0: 15, 17, 16, 88, 1037
Monkey 1: 20, 110, 205, 524, 72
Monkey 2:
Monkey 3:
After round 6, the monkeys are holding items with these worry levels:
Monkey 0: 8, 70, 176, 26, 34
Monkey 1: 481, 32, 36, 186, 2190
Monkey 2:
Monkey 3:
After round 7, the monkeys are holding items with these worry levels:
Monkey 0: 162, 12, 14, 64, 732, 17
Monkey 1: 148, 372, 55, 72
Monkey 2:
Monkey 3:
After round 8, the monkeys are holding items with these worry levels:
Monkey 0: 51, 126, 20, 26, 136
Monkey 1: 343, 26, 30, 1546, 36
Monkey 2:
Monkey 3:
After round 9, the monkeys are holding items with these worry levels:
Monkey 0: 116, 10, 12, 517, 14
Monkey 1: 108, 267, 43, 55, 288
Monkey 2:
Monkey 3:
After round 10, the monkeys are holding items with these worry levels:
Monkey 0: 91, 16, 20, 98
Monkey 1: 481, 245, 22, 26, 1092, 30
Monkey 2:
Monkey 3:
...
After round 15, the monkeys are holding items with these worry levels:
Monkey 0: 83, 44, 8, 184, 9, 20, 26, 102
Monkey 1: 110, 36
Monkey 2:
Monkey 3:
...
After round 20, the monkeys are holding items with these worry levels:
Monkey 0: 10, 12, 14, 26, 34
Monkey 1: 245, 93, 53, 199, 115
Monkey 2:
Monkey 3:
Chasing all of the monkeys at once is impossible; you're going to have to focus on the two most active monkeys if you want any hope of getting your stuff back. Count the total number of times each monkey inspects items over 20 rounds:
Monkey 0 inspected items 101 times.
Monkey 1 inspected items 95 times.
Monkey 2 inspected items 7 times.
Monkey 3 inspected items 105 times.
In this example, the two most active monkeys inspected items 101 and 105 times. The level of monkey business in this situation can be found by multiplying these together: 10605.
Figure out which monkeys to chase by counting how many items they inspect over 20 rounds. What is the level of monkey business after 20 rounds of stuff-slinging simian shenanigans?
# Python imports
from __future__ import annotations
from math import prod
from pathlib import Path
from tqdm.notebook import tqdm
test = Path("data/day11_test.txt") # test data
data = Path("data/day11_data.txt") # puzzle data
class MonkeyPool:
"""Represents a set of stealing monkeys"""
def __init__(self) -> None:
"""Initialise an empty pool of monkeys"""
self.monkeys = {}
def add_monkey(self, monkey: Monkey) -> None:
"""Add a monkey to the pool
:param monkey: the monkey to add
"""
monkey.pool = self # Register this pool with the monkey
self.monkeys[int(monkey.name)] = monkey # add monkey to the pool
def throw_to_monkey(self, item: int, monkey: Monkey) -> None:
"""Throw an item to the named monkey
:param item: the item to throw
:param monkey: the monkey the item is thrown to
"""
self.monkeys[monkey].add_item(item)
def play(self) -> None:
"""Play a single round of Keep Away"""
for name, monkey in self.monkeys.items():
# Each monkey exhausts its items on each turn
while len(monkey.items):
monkey.take_turn()
def set_nervous(self) -> None:
"""Implements the solution for Part 2
The function of the division by 3 in part 1 was to keep the
item values small, so that calculation is fast (for the small
number of rounds we work with).
However, for large numbers of rounds, the item values get very
large, which is unacceptably slow. We need a way to keep the
values small that still produces the same value for the division
test of which monkey receives the item when it's thrown.
The way we might do this is convert each item's value modulo the
least common multiple (LCM) of the divisors. To see this, suppose
there are two monkeys, and our divisors are 10 and 15 - our test
value is 145. The remainder of 145 on division by 10 is 5, and on
division by 15 is 10. We want a different value than 10 or 15 that
retains this property. The divisors of 10 are 1, 2, 5; those of 15
are 1, 2, 3, 5. If we multiply these together, we get:
1 * 2 * 5 * 1 * 2 * 3 * 5 = 300; we can divide this through by the
greatest common divisor (GCD), which is 5, to get 60.
Now, if we take 145 (mod 60) = 25, we can see that the remainder
of 25 / 10 is 5, and 25/15 is 10 - just as it was for 145
However, in our problem, all the divisors are prime, so there is
no GCD other than 1. We can shortcut by just calculating the
product of all the divisors, and taking the item values modulo
this number. We put this number into the lcm attribute of each
monkey
"""
for monkey in self.monkeys.values():
monkey.nervous = True # mark the monkey to reflect our nerves
monkey.lcm = prod([_.div for _ in self.monkeys.values()])
def set_verbose(self) -> None:
"""Set each monkey's output to be verbose
This prints each step of the game out.
"""
for monkey in self.monkeys.values():
monkey.verbose = True
@property
def inspection_counts(self) -> list[int]:
"""Return the number of times each monkey inspects an item"""
return [_.inspection_count for _ in self.monkeys.values()]
@property
def monkey_business(self) -> int:
"""Return the puzzle solution: product of two highest inspection counts"""
return prod(sorted(self.inspection_counts)[-2:])
def __str__(self) -> str:
"""Return pretty string of all monkey states"""
outstr = []
for monkey in self.monkeys.values():
outstr.append(str(monkey))
return "\n".join(outstr)
class Monkey:
"""Represents a stealing monkey"""
def __init__(self, name, start_items, opn, div, pass_monkey, fail_monkey) -> None:
"""Initialise a stealing monkey
:param name: monkey name
:param start_items: items initially carried by monkey
:param opn: inspection operation on item
:param div: divisor for test
:param pass_monkey: throws to this monkey if test passes
:param fail_monkey: throw to this monkey if test fails
"""
self.name = name
self.items = list(start_items)
self.opn = opn
self.div = int(div)
self.pass_monkey = pass_monkey
self.fail_monkey = fail_monkey
self.pool = None # the pool the monkey belongs to
self.inspection_count = 0 # the number of items inspected by this monkey
self.nervous = False # are we nervous (use modulo instead of // 3)
self.lcm = 1 # least common multiple for modulo operation
self.verbose = False # are we pretty-printing each step?
def add_item(self, item: int) -> None:
"""Add item to monkey
:param item: integer of item worry level
"""
self.items.append(item)
def inspect(self, old: int) -> int:
"""Monkey inspects item and returns changed worry level
:param old: item worry level
"""
new = eval(self.opn) # apply operation to item
if self.verbose:
print(f" Worry level is changed to {new}.")
self.inspection_count += 1 # increment inspection count
return new
def test_item(self, item: int) -> bool:
"""Returns true if worry value divisible by monkey's divisor
:param item: item's worry value
"""
return item % self.div == 0
def take_turn(self) -> None:
"""Play monkey's turn in a single round of Keep Away"""
if self.verbose:
print(f"Monkey {self.name}:")
# Inspect and test each carried item, and throw to appropriate monkey
while len(self.items):
item = self.items.pop(0) # get next item
if self.verbose:
print(f" Monkey inspects an item with a worry level of {item}.")
item = self.inspect(item) # inspect the item (changing worry value)
if not self.nervous: # Part 1 solution: integer division by 3
item = item // 3
if self.verbose:
print(f" Monkey gets bored with item. Worry level is divided by 3 to {item}.")
else: # Part 2 solution: item value modulo product of all monkey divisors
item = item % self.lcm
if self.test_item(item): # item passes division test
if self.verbose:
print(f" Current worry level is divisible by {self.div}.")
print(f" Item with worry level {item} is thrown to monkey {self.pass_monkey}.")
self.pool.throw_to_monkey(item, self.pass_monkey)
else: # item fails division test
if self.verbose:
print(f" Current worry level is not divisible by {self.div}.")
print(f" Item with worry level {item} is thrown to monkey {self.fail_monkey}.")
self.pool.throw_to_monkey(item, self.fail_monkey)
def __str__(self) -> str:
"""Pretty print monkey description"""
outstr = [f"Monkey {self.name}:",
f" Starting items: {self.items}",
f" Operation: {self.opn}",
f" Test: divisible by {self.div}",
f" If true: throw to monkey {self.pass_monkey}",
f" If false: throw to monkey {self.fail_monkey}"]
return "\n".join(outstr) + "\n"
def parse_input(fpath: Path) -> MonkeyPool:
"""Parse puzzle input into
:param fpath: path to puzzle input
"""
with fpath.open() as ifh:
monkeys = MonkeyPool()
for line in [_.strip() for _ in ifh.readlines()]:
if line.startswith("Monkey"): # start parsing monkey
name = line[:-1].split()[-1]
elif line.startswith("Starting"): # read in items
items = [int(_) for _ in line.split(": ")[-1].split(", ")]
elif line.startswith("Operation"):
opn = line.split(": ")[-1].split("= ")[-1]
elif line.startswith("Test"):
div = int(line.split()[-1])
elif line.startswith("If true"):
pass_monkey = int(line.split()[-1])
elif line.startswith("If false"):
fail_monkey = int(line.split()[-1])
monkeys.add_monkey(Monkey(name, items, opn, div, pass_monkey, fail_monkey))
return monkeys
def part1(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
monkeys = parse_input(fpath)
for round in range(20):
monkeys.play()
return monkeys.monkey_business
part1(test)
10605
part1(data)
62491
You're worried you might not ever get your items back. So worried, in fact, that your relief that a monkey's inspection didn't damage an item no longer causes your worry level to be divided by three.
Unfortunately, that relief was all that was keeping your worry levels from reaching ridiculous levels. You'll need to find another way to keep your worry levels manageable.
At this rate, you might be putting up with these monkeys for a very long time - possibly 10000 rounds!
With these new rules, you can still figure out the monkey business after 10000 rounds. Using the same example above:
== After round 1 ==
Monkey 0 inspected items 2 times.
Monkey 1 inspected items 4 times.
Monkey 2 inspected items 3 times.
Monkey 3 inspected items 6 times.
== After round 20 ==
Monkey 0 inspected items 99 times.
Monkey 1 inspected items 97 times.
Monkey 2 inspected items 8 times.
Monkey 3 inspected items 103 times.
== After round 1000 ==
Monkey 0 inspected items 5204 times.
Monkey 1 inspected items 4792 times.
Monkey 2 inspected items 199 times.
Monkey 3 inspected items 5192 times.
== After round 2000 ==
Monkey 0 inspected items 10419 times.
Monkey 1 inspected items 9577 times.
Monkey 2 inspected items 392 times.
Monkey 3 inspected items 10391 times.
== After round 3000 ==
Monkey 0 inspected items 15638 times.
Monkey 1 inspected items 14358 times.
Monkey 2 inspected items 587 times.
Monkey 3 inspected items 15593 times.
== After round 4000 ==
Monkey 0 inspected items 20858 times.
Monkey 1 inspected items 19138 times.
Monkey 2 inspected items 780 times.
Monkey 3 inspected items 20797 times.
== After round 5000 ==
Monkey 0 inspected items 26075 times.
Monkey 1 inspected items 23921 times.
Monkey 2 inspected items 974 times.
Monkey 3 inspected items 26000 times.
== After round 6000 ==
Monkey 0 inspected items 31294 times.
Monkey 1 inspected items 28702 times.
Monkey 2 inspected items 1165 times.
Monkey 3 inspected items 31204 times.
== After round 7000 ==
Monkey 0 inspected items 36508 times.
Monkey 1 inspected items 33488 times.
Monkey 2 inspected items 1360 times.
Monkey 3 inspected items 36400 times.
== After round 8000 ==
Monkey 0 inspected items 41728 times.
Monkey 1 inspected items 38268 times.
Monkey 2 inspected items 1553 times.
Monkey 3 inspected items 41606 times.
== After round 9000 ==
Monkey 0 inspected items 46945 times.
Monkey 1 inspected items 43051 times.
Monkey 2 inspected items 1746 times.
Monkey 3 inspected items 46807 times.
== After round 10000 ==
Monkey 0 inspected items 52166 times.
Monkey 1 inspected items 47830 times.
Monkey 2 inspected items 1938 times.
Monkey 3 inspected items 52013 times.
After 10000 rounds, the two most active monkeys inspected items 52166 and 52013 times. Multiplying these together, the level of monkey business in this situation is now 2713310158.
Worry levels are no longer divided by three after each item is inspected; you'll need to find another way to keep your worry levels manageable. Starting again from the initial state in your puzzle input, what is the level of monkey business after 10000 rounds?
def part2(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
monkeys = parse_input(fpath)
monkeys.set_nervous() # Use modulus instead of // 3
for round in tqdm(range(10000)):
monkeys.play()
return monkeys.monkey_business
part2(test)
0%| | 0/10000 [00:00<?, ?it/s]
2713310158
part2(data)
0%| | 0/10000 [00:00<?, ?it/s]
17408399184