generated from public/aoc_template
85 lines
2.5 KiB
Python
85 lines
2.5 KiB
Python
from collections import deque
|
|
|
|
from tools.aoc import AOCDay
|
|
from typing import Any
|
|
|
|
class Device:
|
|
def __init__(self, name: str):
|
|
self.name: str = name
|
|
self.outputs: list[Device] = []
|
|
self.inputs: list[Device] = []
|
|
|
|
|
|
class Day(AOCDay):
|
|
inputs = [
|
|
[
|
|
(5, "input11_test"),
|
|
(674, "input11_dennis"),
|
|
(634, "input11"),
|
|
],
|
|
[
|
|
(2, "input11_test2"),
|
|
(438314708837664, "input11_dennis"),
|
|
(377452269415704, "input11"),
|
|
]
|
|
]
|
|
|
|
def parse_input(self) -> dict[str, Device]:
|
|
devices: dict[str, Device] = {x.split(":")[0]: Device(x.split(":")[0]) for x in self.getInput()}
|
|
devices["out"] = Device("out")
|
|
for line in self.getInput():
|
|
device, outputs = line.split(": ")
|
|
for output in outputs.split():
|
|
devices[device].outputs.append(devices[output])
|
|
devices[output].inputs.append(devices[device])
|
|
|
|
return devices
|
|
|
|
def get_paths(self, start: str, target: str, devices: dict[str, Device]) -> int:
|
|
if start == target:
|
|
return 1
|
|
|
|
if target not in self.DP:
|
|
self.DP[target] = {}
|
|
|
|
if start in self.DP[target]:
|
|
return self.DP[target][start]
|
|
|
|
self.DP[target][start] = sum(self.get_paths(x.name, target, devices) for x in devices[start].outputs)
|
|
return self.DP[target][start]
|
|
|
|
def fill_cache(self, target: str, devices: dict[str, Device]) -> None:
|
|
self.seen_reset()
|
|
|
|
Q = deque([devices[target]])
|
|
while Q:
|
|
device = Q.popleft()
|
|
if self.seen(device.name):
|
|
continue
|
|
|
|
self.get_paths(device.name, target, devices)
|
|
|
|
for source in device.inputs:
|
|
Q.append(source)
|
|
|
|
def part1(self) -> Any:
|
|
return self.get_paths("you", "out", self.parse_input())
|
|
|
|
def part2(self) -> Any:
|
|
devices = self.parse_input()
|
|
self.fill_cache("out", devices)
|
|
if self.DP["out"]["fft"] < self.DP["out"]["dac"]:
|
|
self.fill_cache("fft", devices)
|
|
self.fill_cache("dac", devices)
|
|
return self.DP["dac"]["svr"] * self.DP["fft"]["dac"] * self.DP["out"]["fft"]
|
|
else:
|
|
self.fill_cache("dac", devices)
|
|
self.fill_cache("fft", devices)
|
|
return self.DP["fft"]["svr"] * self.DP["dac"]["fft"] * self.DP["out"]["dac"]
|
|
|
|
|
|
|
|
if __name__ == '__main__':
|
|
day = Day(2025, 11)
|
|
day.run(verbose=True)
|