| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 15:54 | 29:13 | 45:07 |
I felt like I did Part 1 pretty fast. A lot of it was spent reading. I finished 220th worldwide for Part 1, so I guess it was fast! I don't like how I stored the information for each monkey. I'd like to have done it with a class. After I finished writing my code, it worked first try on the example case, so that's a win in my book!
from helpers.datagetter import data_in, submit
import re
import math
ans = 0
din = data_in(split=True, numbers=False)
monkeys = []
starting_items = []
operation = ""
test = 0
t_cond, f_cond = 0, 0
for line in din:
if line.startswith(" Starting items:"):
starting_items = list(map(int, re.findall(r'\d+(?:\.\d+)?', line)))
if line.startswith(" Operation: "):
operation = line.split(" Operation: new = ")[1]
if line.startswith(" Test: "):
test = int(line.split(" ")[-1])
if line.startswith(" If true: "):
t_cond = int(line.split(" ")[-1])
if line.startswith(" If false: "):
f_cond = int(line.split(" ")[-1])
monkeys.append([starting_items, operation, test, t_cond, f_cond, 0])
print(monkeys)
for round in range(20):
for monkey in monkeys:
for i, item in enumerate(monkey[0]):
old = item
worry = math.floor(eval(monkey[1]) / 3)
if worry % monkey[2] == 0:
monkeys[monkey[3]][0].append(worry)
else:
monkeys[monkey[4]][0].append(worry)
monkey[5] += 1
monkey[0] = []
inspections = []
for monkey in monkeys:
inspections.append(monkey[5])
inspections.sort()
ans = inspections[-1] * inspections[-2]
print(ans)
submit(ans)This is what makes Advent of Code so good as a learning experience: it forces you to do unbruteforceable problems. I couldn't just run the code for 10,000 rounds after removing the worry level divider. The numbers got thousands of digits long after only a couple of dozen rounds. I knew what I needed to do, just not how to do it. I needed to somehow preserve the properties of modulus without letting the numbers get absolutely gigantic.
I found it hard to search for something like this online, but I found some helpful articles. I found this and this, but honestly now looking at them closer, neither of them mention using the LCM of all the moduli to preserve residuals for all of them. Regardless, I got the idea somehow and decided to try it. Below is the result, which I was overjoyed to find working after messing around aimlessly with GCD, LCM, and Modulus operations for almost 30 minutes.
Hmm, I'm back now 5 minutes later. A friend of mine told me how they did it and it seems I did some extra work. All the divisors are prime! The LCM of a list of primes is just all of them multiplied together. This now makes so much more sense in my head why performing modulus with the multiplication of all the divisors works. I don't know where I got LCM from, but hey, it accidentally worked! Scratch that again... I just tried 50 round bruteforce and with the LCM solution and it gave the same answer. Maybe my LCM wasn't so crazy after all. And... I just tried it when multiplying them all together, which also worked. I'd love to see the math on this, but apparently I can't even tell the difference between LCM and product of a list.
from helpers.datagetter import data_in, submit
import re
import math
from tqdm import tqdm
ans = 0
din = data_in(split=True, numbers=False)
monkeys = []
starting_items = []
operation = ""
test = 0
t_cond, f_cond = 0, 0
mods = []
for line in din:
if line.startswith(" Starting items:"):
starting_items = list(map(int, re.findall(r'\d+(?:\.\d+)?', line)))
if line.startswith(" Operation: "):
operation = line.split(" Operation: new = ")[1]
if line.startswith(" Test: "):
test = int(line.split(" ")[-1])
mods.append(test)
if line.startswith(" If true: "):
t_cond = int(line.split(" ")[-1])
if line.startswith(" If false: "):
f_cond = int(line.split(" ")[-1])
monkeys.append([starting_items, operation, test, t_cond, f_cond, 0])
# Computing the LCM of all the moduli
lcm = 1
for mod in mods:
lcm = math.lcm(lcm, mod)
for round in tqdm(range(10000)):
for monkey in monkeys:
for i, item in enumerate(monkey[0]):
old = item
worry = eval(monkey[1])
if worry % monkey[2] == 0:
monkeys[monkey[3]][0].append(worry % lcm) # <- Here is the critical part
else:
monkeys[monkey[4]][0].append(worry % lcm) # <- Here too
monkey[5] += 1
monkey[0] = []
inspections = []
for monkey in monkeys:
inspections.append(monkey[5])
inspections.sort()
ans = inspections[-1] * inspections[-2]
print(ans)
submit(ans)