Skip to content

Latest commit

 

History

History
67 lines (50 loc) · 2.21 KB

8.md

File metadata and controls

67 lines (50 loc) · 2.21 KB
Raw

Day 8

This one was pretty neat!

Part 1 Part 2 Total
Time 5:35 12:35 18:10

Part 1

I totally didn't waste time trying to eval() the tuple of left and right nodes. Nothing much of note here.

from helpers.datagetter import aocd_data_in
from collections import defaultdict

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

maps = defaultdict(list)

instr = din[0]

for line in din[2:]:
    maps[line.split(" ")[0]] = [line.split("(")[1].split(",")[0], line.split(", ")[1].split(")")[0]]

at = "AAA"
i = 0
while at != "ZZZ":
    at = maps[at][0] if instr[i % len(instr)] == "L" else maps[at][1]
    i += 1

aocd_submit(i)

Part 2

As soon as I ran it and it did not respond within 5 seconds, I knew there was more. I first checked if the numbers were coprime, for Chinese remainder theorem. Nope. Then I tried GCD and the answer was too small. What left? LCM! Oh, I thought, and that makes sense. My answer was entered from an online calculator, and then I did the Python after for completeness.

The reason this uses the LCM is because the first time multiple closed loops will sync up is at their least common multiple. I suppose this assumes they are all closed loops of always the same lengths, interesting. I never tested that. Anyway, I check from each starting point the step when they first reach their ends, and compute the LCM of the stop step.

from helpers.datagetter import aocd_data_in
from collections import defaultdict
import math

din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0

maps = defaultdict(list)

instr = din[0]

for line in din[2:]:
    maps[line.split(" ")[0]] = [line.split("(")[1].split(",")[0], line.split(", ")[1].split(")")[0]]

at = [x for x in maps.keys() if x.endswith("A")]
i = 0
finished_by = [0 for _ in range(len(maps.keys()))]
while any([not x.endswith("Z") for x in at]):
    for j in range(len(at)):
        if finished_by[j] != 0:
            continue
        at[j] = maps[at[j]][0] if instr[i % len(instr)] == "L" else maps[at[j]][1]
        if at[j].endswith("Z"):
            finished_by[j] = i + 1
    i += 1

ans = math.lcm(*[x for x in finished_by if x != 0])

aocd_submit(ans)