day16

3 files changed, 241 insertions, 0 deletions

diff --git a/2022/day16.py b/2022/day16.py
new file mode 100755
index 0000000..15bac0a
--- /dev/null
+++ b/2022/day16.py
@@ -0,0 +1,174 @@
+#!/usr/bin/env python3
+
+# import numpy as np
+from functools import reduce
+from re import findall
+from copy import deepcopy
+import sys
+
+import traceback
+
+# filename = "in/day16.ref"
+filename = "in/day16.pzl"
+data = open(filename).read()
+lines = [line for line in data.rstrip('\n').split('\n')]
+
+
+N = dict()
+
+for line in lines:
+    a = line.split(' ')
+    name = a[1]
+    rate = int(a[4].split('=')[1][:-1])
+    to = a[9:]
+    to = [i.strip(',') for i in to]
+    N[name] = {'rate': rate, 'to': to}
+
+# print(N)
+
+res1 = 0
+res2 = 0
+
+NZR = set([i for i in N.keys() if N[i]['rate'] > 0])
+# print(NZR)
+
+def get_dist(cn, en, steps, S):
+    if cn == en:
+        return steps
+    elif S[cn] < steps:
+        return 999
+
+    S[cn] = steps
+    m = 999
+    for n in N[cn]['to']:
+        m = min(m, get_dist(n, en, steps+1,S))
+    return m
+
+D = dict()
+for i in N.keys():
+    D[i] = dict()
+    for j in N.keys():
+        D[i][j] = get_dist(i, j, 0, {i:999 for i in N.keys()} )
+# print(D)
+
+
+def best2_first(time, cn, rate, gas, opened):
+    if time == 29:
+        return gas
+    elif time == 28:
+        return gas + rate
+
+    if len(NZR) == len(opened):
+        gas += (30-time-1) * rate
+        return gas
+
+    best = list()
+    for n in NZR - opened:
+        d = get_dist(cn, n, 0, {i:999 for i in N.keys()} )
+        val = N[n]['rate'] * (30-time-d)
+        # print(n, d, val)
+        val = val/(d-0.5)
+        best.append((n, d, val))
+    best = sorted(best, key=lambda x: x[2], reverse=True)
+    # print(best)
+
+    m = 0
+    for (n, d, val) in best[:2]:
+        op = opened.copy()
+        op.add(n)
+        mm = best2_first(time + d + 1, n, rate + N[n]['rate'],
+                   gas + (d+1)*rate + N[n]['rate'], op)
+        m = max(m, mm)
+    return m
+
+
+def dual_best2_first(time, cn1, cn2, cn1_rem, cn2_rem, rate, gas, opened, p1, p2):
+
+
+    best1 = list()
+    if cn1_rem == 0:
+        rate += N[cn1]['rate']
+        for n1 in NZR - opened:
+            # d1 = get_dist(cn1, n1, 0, {i:999 for i in N.keys()} )
+            d1 = D[cn1][n1]
+            val1 = N[n1]['rate'] * (30-time-d1)
+            val1 = val1/(d1-0.5)
+            best1.append((n1, d1, val1))
+        best1 = sorted(best1, key=lambda x: x[2], reverse=True)
+
+    best2 = list()
+    if cn2_rem == 0:
+        rate += N[cn2]['rate']
+        for n2 in NZR - opened:
+            # d2 = get_dist(cn2, n2, 0, {i:999 for i in N.keys()} )
+            d2 = D[cn2][n2]
+            val2 = N[n2]['rate'] * (30-time-d2)
+            val2 = val2
+            best2.append((n2, d2, val2))
+        best2 = sorted(best2, key=lambda x: x[2], reverse=True)
+
+    gas += rate
+    # print(best1, best2, p1, p2)
+
+    if time == 29:
+        return gas
+
+    if len(best1) == 1 and len(best2) == 1:
+        if best1[0][0] == best2[0][0]:
+            if best1[0][1] < best2[0][1]:
+                best2 = list()
+            else:
+                best1 = list()
+            # print(best1, best2)
+            # sys.exit(1)
+
+
+    if len(best1) > 0 and len(best2) == 0:
+        m = 0
+        for (n1, d1, val1) in best1[:4]:
+            op = opened.copy()
+            op.add(n1)
+            mm =  dual_best2_first(time+1, n1, cn2,
+                       d1, cn2_rem - 1,
+                       rate, gas, op, p1 + [n1], p2)
+            m = max(m, mm)
+
+    elif len(best2) > 0 and len(best1) == 0:
+        m = 0
+        for (n2, d2, val2) in best2[:4]:
+            op = opened.copy()
+            op.add(n2)
+            mm =  dual_best2_first(time+1, cn1, n2,
+                       cn1_rem - 1 , d2,
+                       rate, gas, op, p1, p2 + [n2])
+            m = max(m, mm)
+
+    elif len(best1) > 0 and len(best2) > 0:
+        m = 0
+        for (n1, d1, val1) in best1[:6]:
+            for (n2, d2, val2) in best2[:6]:
+                if n1 == n2:
+                    continue
+                op = opened.copy()
+                op.add(n1)
+                op.add(n2)
+                mm = dual_best2_first(time+1, n1, n2,
+                           d1, d2,
+                           rate, gas, op, p1 + [n1], p2 + [n2])
+                m = max(m, mm)
+    else:
+        op = opened.copy()
+        m = dual_best2_first(time+1, cn1, cn2,
+                   cn1_rem - 1, cn2_rem - 1,
+                   rate, gas, op, p1, p2)
+    return m
+
+
+res1 = best2_first(0, 'AA', 0, 0, set())
+# res1 = dual_best2_first(0, 'AA', 'AA', 0, -1, 0, 0, set())
+res2 = dual_best2_first(4, 'AA', 'AA', 0, 0, 0, 0, set(), list(), list())
+
+
+print('res1:', res1)
+print('res2:', res2)
+
diff --git a/2022/in/day16.pzl b/2022/in/day16.pzl
new file mode 100644
index 0000000..ca73ce3
--- /dev/null
+++ b/2022/in/day16.pzl
@@ -0,0 +1,57 @@
+Valve ED has flow rate=0; tunnels lead to valves PS, AW
+Valve SI has flow rate=0; tunnels lead to valves AA, HX
+Valve LX has flow rate=22; tunnels lead to valves DY, YH
+Valve CR has flow rate=0; tunnels lead to valves BE, HX
+Valve BI has flow rate=0; tunnels lead to valves GC, AY
+Valve PB has flow rate=4; tunnels lead to valves IX, YG, RI, KR, BV
+Valve YY has flow rate=0; tunnels lead to valves PH, GJ
+Valve PH has flow rate=11; tunnels lead to valves YY, VE, ZG, MM
+Valve DY has flow rate=0; tunnels lead to valves LX, AW
+Valve SD has flow rate=0; tunnels lead to valves AY, EC
+Valve SV has flow rate=24; tunnels lead to valves CC, GF
+Valve RL has flow rate=0; tunnels lead to valves OW, IN
+Valve GF has flow rate=0; tunnels lead to valves RQ, SV
+Valve BE has flow rate=5; tunnels lead to valves CR, JC, MF, IT
+Valve PR has flow rate=0; tunnels lead to valves BV, GJ
+Valve AW has flow rate=21; tunnels lead to valves VE, DY, TR, ED
+Valve FY has flow rate=17; tunnels lead to valves GG, KJ
+Valve GC has flow rate=0; tunnels lead to valves BI, GJ
+Valve RI has flow rate=0; tunnels lead to valves PB, AY
+Valve RQ has flow rate=0; tunnels lead to valves HH, GF
+Valve IT has flow rate=0; tunnels lead to valves MZ, BE
+Valve XG has flow rate=0; tunnels lead to valves BL, AA
+Valve MK has flow rate=0; tunnels lead to valves HX, DV
+Valve IX has flow rate=0; tunnels lead to valves PB, JC
+Valve BV has flow rate=0; tunnels lead to valves PR, PB
+Valve TR has flow rate=0; tunnels lead to valves CD, AW
+Valve PS has flow rate=0; tunnels lead to valves ED, AY
+Valve HH has flow rate=12; tunnels lead to valves RQ, NL, ZQ
+Valve AA has flow rate=0; tunnels lead to valves KR, SI, XG, EC, ZG
+Valve FT has flow rate=0; tunnels lead to valves IN, YH
+Valve YG has flow rate=0; tunnels lead to valves PB, HX
+Valve HX has flow rate=14; tunnels lead to valves MK, ZQ, YG, SI, CR
+Valve DV has flow rate=0; tunnels lead to valves MK, QR
+Valve GJ has flow rate=3; tunnels lead to valves PR, CD, YY, GC, BL
+Valve BL has flow rate=0; tunnels lead to valves GJ, XG
+Valve CD has flow rate=0; tunnels lead to valves TR, GJ
+Valve GG has flow rate=0; tunnels lead to valves FY, NL
+Valve JC has flow rate=0; tunnels lead to valves IX, BE
+Valve JN has flow rate=0; tunnels lead to valves OW, QR
+Valve RM has flow rate=18; tunnel leads to valve KJ
+Valve NL has flow rate=0; tunnels lead to valves GG, HH
+Valve QR has flow rate=20; tunnels lead to valves CC, DV, PN, JN
+Valve ZG has flow rate=0; tunnels lead to valves AA, PH
+Valve AY has flow rate=6; tunnels lead to valves RI, PS, SD, BI, MM
+Valve VE has flow rate=0; tunnels lead to valves PH, AW
+Valve OW has flow rate=25; tunnels lead to valves MZ, RL, JN
+Valve MM has flow rate=0; tunnels lead to valves AY, PH
+Valve KJ has flow rate=0; tunnels lead to valves RM, FY
+Valve MF has flow rate=0; tunnels lead to valves BE, PN
+Valve YH has flow rate=0; tunnels lead to valves LX, FT
+Valve ZQ has flow rate=0; tunnels lead to valves HX, HH
+Valve KR has flow rate=0; tunnels lead to valves AA, PB
+Valve PN has flow rate=0; tunnels lead to valves MF, QR
+Valve CC has flow rate=0; tunnels lead to valves SV, QR
+Valve MZ has flow rate=0; tunnels lead to valves OW, IT
+Valve EC has flow rate=0; tunnels lead to valves SD, AA
+Valve IN has flow rate=16; tunnels lead to valves RL, FT
diff --git a/2022/in/day16.ref b/2022/in/day16.ref
new file mode 100644
index 0000000..9f30acc
--- /dev/null
+++ b/2022/in/day16.ref
@@ -0,0 +1,10 @@
+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II