16 p1

1 files changed, 75 insertions, 0 deletions

diff --git a/16.py b/16.py
new file mode 100644
index 0000000..5ea6748
--- /dev/null
+++ b/16.py
@@ -0,0 +1,75 @@
+from utils import open_day
+from functools import cache
+from dataclasses import dataclass
+from itertools import count
+import re
+
+@dataclass
+class Node:
+    flow: int
+    neighbours: list[tuple[str, int]]
+
+regex = re.compile(r'^Valve (..) has flow rate=([0-9]+); tunnels? leads? to valves? (.*)$')
+inp = {}
+with open_day(16) as f:
+    for line in f:
+        m = regex.match(line)
+        assert(m)
+        valve, flow, neighbours = m.group(1, 2, 3)
+        inp[valve] = (int(flow), neighbours.split(', '))
+
+nodes = {}
+for valve, (flow, neighbours) in inp.items():
+    if valve != 'AA' and flow == 0: continue
+    actual_neighbours = []
+    for n in neighbours:
+        prev = valve
+        for cost in count(1):
+            if n == 'AA' or inp[n][0] != 0:
+                break
+            l, r = inp[n][1]
+            if l == prev:
+                prev = n
+                n = r
+            else:
+                prev = n
+                n = l
+        actual_neighbours.append((n, cost))
+    nodes[valve] = Node(flow, actual_neighbours)
+
+@cache
+def sum_flow(open_valves):
+    return sum(nodes[n].flow for n in open_valves)
+
+@cache
+def recurse(open_valves, current, flow, time_left):
+    cflow = sum_flow(open_valves)
+    cnode = nodes[current]
+    best = 0
+    for neighbour, cost in cnode.neighbours:
+        if cost >= time_left:
+            best = max(best, flow + cflow * time_left)
+        else:
+            best = max(
+                best,
+                recurse(open_valves, neighbour,
+                        flow + cflow * cost, time_left - cost)
+            )
+    if current not in open_valves and time_left > 0 and cnode.flow > 0:
+        flow += cflow
+        open_valves |= {current}
+        cflow = sum_flow(open_valves)
+        best = max(best, flow)
+        time_left -= 1
+        for neighbour, cost in cnode.neighbours:
+            if cost >= time_left:
+                best = max(best, flow + cflow * time_left)
+            else:
+                best = max(
+                    best,
+                    recurse(open_valves, neighbour,
+                            flow + cflow * cost, time_left - cost)
+                )
+    return best
+
+print(recurse(frozenset(), 'AA', 0, 30))