summaryrefslogtreecommitdiff
path: root/20_2023.py
blob: 6bb4596027259bef139e855725d8a8e2ea78b3c3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
import heapq
import math

D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])
TYP = {}
R = {}
FROM = {}
INV = defaultdict(list)
lo = 0
hi = 0
Q = deque()
ON = set()
PREV = {}
COUNT = defaultdict(int)
TO_LCM = []


def lcm(xs):
    ans = 1
    for x in xs:
        ans = (ans * x) // math.gcd(x, ans)
    return ans


for line in L:
    src, dest = line.split("->")
    src = src.strip()
    dest = dest.strip()
    dest = dest.split(", ")
    R[src] = dest
    TYP[src[1:]] = src[0]


def adjust(y):
    if y in TYP:
        return TYP[y] + y
    else:
        return y


for x, ys in R.items():
    R[x] = [adjust(y) for y in ys]
    for y in R[x]:
        if y[0] == "&":
            if y not in FROM:
                FROM[y] = {}
            FROM[y][x] = "lo"
        INV[y].append(x)
assert len(INV["rx"]) == 1
assert INV["rx"][0][0] == "&"
WATCH = INV[INV["rx"][0]]
for t in range(1, 10**8):
    Q.append(("broadcaster", "button", "lo"))
    while Q:
        x, from_, typ = Q.popleft()
        if typ == "lo":
            if x in PREV and COUNT[x] == 2 and x in WATCH:
                TO_LCM.append(t - PREV[x])
            PREV[x] = t
            COUNT[x] += 1
        if len(TO_LCM) == len(WATCH):
            print(lcm(TO_LCM))
            sys.exit(0)
        if x == "rx" and typ == "lo":
            print(t + 1)
        if typ == "lo":
            lo += 1
        else:
            hi += 1
        if x not in R:
            continue
        if x == "broadcaster":
            for y in R[x]:
                Q.append((y, x, typ))
        elif x[0] == "%":
            if typ == "hi":
                continue
            else:
                if x not in ON:
                    ON.add(x)
                    new_typ = "hi"
                else:
                    ON.discard(x)
                    new_typ = "lo"
                for y in R[x]:
                    Q.append((y, x, new_typ))
        elif x[0] == "&":
            FROM[x][from_] = typ
            new_typ = "lo" if all(y == "hi" for y in FROM[x].values()) else "hi"
            for y in R[x]:
                Q.append((y, x, new_typ))
        else:
            assert False, x
    if t == 1000:
        print(lo * hi)