diff options
author | Jack Sangdahl <[email protected]> | 2024-12-04 22:59:08 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-04 22:59:08 -0700 |
commit | a3c129a57340bda27240cef0b5d6228d425e9314 (patch) | |
tree | fccaa883b39b3b58517d3386f72f19553ae9027a /5_2024.py | |
parent | ac6785b735a8e34f71e17c3ec823a4fcd58fb728 (diff) | |
download | aoc-a3c129a57340bda27240cef0b5d6228d425e9314.tar.gz aoc-a3c129a57340bda27240cef0b5d6228d425e9314.zip |
Day 5 2024
Diffstat (limited to '5_2024.py')
-rw-r--r-- | 5_2024.py | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/5_2024.py b/5_2024.py new file mode 100644 index 0000000..61e8a06 --- /dev/null +++ b/5_2024.py @@ -0,0 +1,52 @@ +import sys +from pyperclip import copy +from collections import defaultdict, deque + +input = "data/5_2024.txt" +data = open(input).read().strip() +edges, queries = data.split("\n\n") +sys.setrecursionlimit(10**6) +p1, p2 = 0, 0 +prev = defaultdict(set) +past = defaultdict(set) + +for line in edges.split("\n"): + x, y = line.split("|") + x, y = int(x), int(y) + prev[y].add(x) + past[x].add(y) + +for query in queries.split("\n"): + vs = [int(x) for x in query.split(",")] + assert len(vs) % 2 == 1 + ok = True + for i, x in enumerate(vs): + for j, y in enumerate(vs): + if i < j and y in prev[x]: + ok = False + if ok: + p1 += vs[len(vs) // 2] + else: + good, q = [], deque([]) + data = {v: len(prev[v] & set(vs)) for v in vs} + for v in vs: + if data[v] == 0: + q.append(v) + while q: + x = q.popleft() + good.append(x) + for y in past[x]: + if y in data: + data[y] -= 1 + if data[y] == 0: + q.append(y) + p2 += good[len(good) // 2] + + +def solve(s): + print(s) + copy(s) + + +solve(p1) +solve(p2) |