aoc 2023 day 20 part 2.py

aoc 2023 day 20 part 2.py

from util import ints
from collections import defaultdict
from functools import cmp_to_key
from copy import deepcopy, copy

prob = "20"
f = open(prob, "r")

lines = []

types = {}
g = defaultdict(set)
for line in f.readlines():
    line = line.strip()
    src, dst = line.split("->")
    src = src.strip()
    if src[0] == '%':
        types[src[1:]] = '%'
        src=src[1:]
    elif src[0] == '&':
        types[src[1:]] = '&'
        src=src[1:]
    dst = dst.strip()
    dst = dst.split(",")
    for d in dst:
        g[src].add(d.strip())

    print(src,dst)

print(types)

conj = defaultdict(dict)
for t in types:
    if types[t] == '&':
        dst = t
        # find all edges to t
        for k in g:
            if dst in g[k]:
                conj[dst][k] = 0

# pulse at broadcast, press button
# send low pulse to broadcaster
# broadcaster just forwards pulse
# 0 for low, 1 for high

visited = set()
on = defaultdict(bool)
low=0
high=0
K = 0
T = defaultdict(list)
found = False
while not found:
    Q = [('broadcaster',0, 'button')] # node, pulse, src
    while len(Q) > 0:
        v, pulse, src = Q[0]
        if v == 'rx' and pulse == 0:
            print(K)
        if pulse == 0:
            low+=1
        else:
            high+=1
        del Q[0]
        if v in types and types[v] == '%' and pulse == 1: # flip flop, skip pulse
            continue
        else:
            if v in types and types[v] == '&':
                conj[v][src] = pulse
                if all([conj[v][k] == 1 for k in conj[v]]): # remembers high
                    pulse = 0
                else:
                    pulse = 1

                # collect cycles, for investigation
                if v in ['ll']: # incoming edge to rx
                    for k in conj[v]:
                        # record when an incoming bit to ll is 1
                        if conj[v][k] == 1 and len(T[k]) == 0:
                            T[k].append(K)
                if len(T) == 4:
                    import math
                    print(T)
                    lcm = math.lcm(*[int(T[k][0])+1 for k in list(T.keys())])
                    print("Answer for part 2", lcm)
                    found = True
                    break
                    # hardcoded the incoming edge to rx and recorded when
                    # all of its incoming bits are 1 at timesteps K respectively
                    # since the incoming edge to rx requires all bits to be 1
                    # then you just do cycle detection
                    # drawing this out as a picture helps
                    # top 350 for pt1/pt2
                    # the bug was that K is the button press - 1 so you have to add 1

            if v in types and types[v] == '%' and pulse == 0:
                on[v] = not on[v]
                if on[v]:
                    pulse = 1
                else:
                    pulse = 0
            for n in g[v]:
                Q.append((n,pulse,v))
    K += 1
        
#print(on)
#print(low*high)

# % is flip flop
# & is inverter
# broadcaster just broadcasts