diff options
Diffstat (limited to '2022/day16.py')
| -rwxr-xr-x | 2022/day16.py | 174 |
1 files changed, 174 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) + |