import time
from enum import Enum
from dataclasses import dataclass
from functools import cache
from typing import Any


class Signal(Enum):
    LOW = "LOW"
    HIGH = "HIGH"

    def __repr__(self):
        return self.value.lower()

    def __str__(self):
        return self.value.lower()


class Component:
    def apply(self, signal: Signal, index: int) -> Signal | None:
        raise NotImplementedError()

    def state(self) -> Any:
        raise NotImplementedError()

    def set_state(self, state: Any):
        raise NotImplementedError()


@dataclass
class FlipFlop(Component):
    name: str
    active: bool = False

    def apply(self, signal: Signal, index: int) -> Signal | None:
        if index != 0:
            raise Exception(f"FlipFlop can only receive one signal, not {index}")

        match signal:
            case Signal.LOW:
                self.active = not self.active
                if self.active:
                    return Signal.HIGH
                else:
                    return Signal.LOW
            case _:
                return None

    def __hash__(self):
        return hash(self.name)

    def state(self):
        return self.active

    def set_state(self, state: Any):
        self.active = state

    def __repr__(self):
        return f"FlipFlop({self.name})"


@dataclass
class TestComponent(Component):
    name: str

    def apply(self, signal: Signal, index: int) -> Signal | None:
        return None

    def state(self):
        return None

    def set_state(self, state: Any):
        pass

    def __hash__(self):
        return hash(self.name)


@dataclass
class Conjunction(Component):
    name: str
    memory: list[Signal]

    def apply(self, signal: Signal, index: int) -> Signal:
        print(index)
        self.memory[index] = signal
        if all([signal == Signal.HIGH for signal in self.memory]):
            return Signal.LOW
        else:
            return Signal.HIGH

    def __hash__(self):
        return hash(self.name)

    def state(self):
        return tuple(self.memory)

    def set_state(self, state: Any):
        self.memory = list(state)

    def __repr__(self):
        return f"Conjunction({self.name}: {self.memory})"


@dataclass
class Broadcaster(Component):
    name: str = "broadcaster"

    def apply(self, signal: Signal, index: int) -> Signal:
        if index != 0:
            raise Exception("Broadcaster can only receive one signal")

        return signal

    def __hash__(self):
        return hash("constant")

    def state(self):
        return None

    def set_state(self, state: Any):
        pass

    def __repr__(self):
        return f"Broadcaster()"


text = """
%jr -> mq, xn
%zl -> tz, cm
&lh -> nr
%hx -> jx, tz
%cm -> tz, ls
&fk -> nr
broadcaster -> sj, pf, kh, cn
%gz -> mq, lq
%gb -> xf, kr
%zc -> rq
%ln -> qj, xf
%gq -> pp
%fb -> xf
%pf -> tg, nv
%bc -> cf
&tz -> cn, fk, ls
%cq -> fb, xf
%rq -> tg, dx
%km -> gq
&mq -> gq, xn, fv, km, lh, xv, sj
%zp -> mq, xv
%jx -> tz, np
&tg -> mm, rp, zc, pf, bc
%cv -> sq, xf
%nv -> ht, tg
%sq -> gb
%kr -> ln
%dk -> cv
%xn -> zp
%sx -> xf, cq
%zt -> tz, fq
%dx -> tg, qn
&ff -> nr
%bn -> hx, tz
%fj -> zt, tz
%ht -> rr, tg
%fq -> tz, bn
%kh -> dk, xf
%sj -> mq, fv
%vm -> zl, tz
&mm -> nr
%rp -> bc
%fh -> sx
%ls -> fj
%xz -> mq, gz
%fv -> km
&nr -> rx
%lq -> mq
%xv -> xz
%cn -> tz, vm
%pp -> jr, mq
%hn -> tg
%qn -> hn, tg
%rr -> rp, tg
%cf -> tg, zc
%qj -> fh, xf
&xf -> sq, dk, fh, ff, kh, kr
%np -> tz
"""


def parse_elem(elem: str):
    if elem == "broadcaster":
        return Broadcaster()
    if elem.startswith("%"):
        return FlipFlop(name=elem.strip("%"))
    if elem.startswith("&"):
        return Conjunction(name=elem.strip("&"), memory=[])
    return TestComponent(name=elem)


game = text.strip().split("\n")

topology = {}
name_to_component = {}

for line in game:
    source_, destinations_raw = line.split("->")
    father = parse_elem(source_.strip())
    children = [child.strip() for child in destinations_raw.split(",")]
    topology[father.name] = children
    name_to_component[father.name] = father

for children in topology.values():
    for child in children:
        if child not in name_to_component:
            name_to_component[child] = parse_elem(child)

reversed_topology = {}
for father, children in topology.items():
    for child in children:
        reversed_topology.setdefault(child, []).append(father)

for component_name, component in name_to_component.items():
    if isinstance(component, Conjunction):
        component.memory = list(Signal.LOW for child in reversed_topology[component_name])

from collections import deque


class HDict(dict):
    def __hash__(self):
        return hash(frozenset(self.items()))


@cache
def compute_high_and_low_signals(
        topology: HDict[str, list[str]],
        name_to_component: HDict[str, Component],
        components_state: HDict[str, Any],
        next_signal: Signal,
) -> tuple[HDict[str, Any], tuple[int, int]]:
    """
    Given a signal, the topology and the current state of the components, compute the next state of the components, the unprocessed signals
    and returns the number of low and high signals.
    """

    #for component_name, component_state in components_state.items():
    #    name_to_component[component_name].state = component_state

    to_forward = topology["broadcaster"]
    print("computing new state")

    signal_queue = deque()

    high_signals = 0 if next_signal == Signal.LOW else 1
    low_signals = 0 if next_signal == Signal.HIGH else 1

    for component_name in to_forward:
        signal_queue.append((("broadcaster", component_name), next_signal))

    while signal_queue:
        (source, destination), signal = signal_queue.popleft()


        match signal:
            case Signal.HIGH:
                high_signals += 1
            case Signal.LOW:
                low_signals += 1
            case _:
                pass

        print(f"{source} -{signal}-> {destination}")
        component_state = name_to_component[destination]
        index = reversed_topology[destination].index(source) if isinstance(component_state, Conjunction) else 0
        emitted_signal = component_state.apply(signal, index)

        if emitted_signal is None:
            continue

        for component_child in topology[destination]:
            signal_queue.append(((destination, component_child), emitted_signal))

    return (
        HDict(
            dict((component, name_to_component[component].state()) for component in sorted(name_to_component.keys()))),
        (high_signals, low_signals),
    )


def click_button(times: int = 1000):
    frozen_topology = HDict((k, tuple(v)) for k, v in topology.items())
    frozen_name_to_component = HDict(name_to_component)

    def compute_frozen_components_state():
        return HDict(
            (component, name_to_component[component].state()) for component in sorted(name_to_component.keys()))

    total_high_signals = 0
    total_low_signals = 0
    component_state_map = None
    for i in range(times):
        component_state_map, (high, low) = compute_high_and_low_signals(
            frozen_topology,
            frozen_name_to_component,
            compute_frozen_components_state() if component_state_map is None else component_state_map,
            Signal.LOW
        )
        total_high_signals += high
        total_low_signals += low

    return total_high_signals, total_low_signals


print(f"source to destination: {topology}")
print(f"destination to source: {reversed_topology}")

high, low = click_button()
print(high*low)