Last active
December 21, 2024 20:47
-
-
Save expectancyViolation/94af576f9035e52a731d729c02715edc to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import re | |
| from collections import defaultdict | |
| from itertools import product | |
| import numpy as np | |
| def mat_prod(arr1, arr2): | |
| L = len(arr1) | |
| res = [[sum(arr1[i][k] * arr2[k][j] for k in range(L)) for j in range(L)] | |
| for i in range(L)] | |
| return res | |
| # file with lines "these moves are optimal to get from X to Y in depth i" | |
| # generated by my previous solver | |
| #e.g. optimal {"<vA", "v<A"} ('A' to 'v') 1 | |
| #e.g. optimal {"<A"} ('v' to '<') 1 | |
| #e.g. optimal {"A"} ('<' to '<') 1 | |
| with open("day21.txt", "r") as f: | |
| lines = f.readlines() | |
| reg = r'optimal (.*) \(\'(.)\' to \'(.)\'\) (.)' | |
| sols = defaultdict(list) | |
| for line in lines: | |
| m = re.match(reg, line) | |
| sol, a, b, d = m.groups() | |
| sol = eval(sol) | |
| sols[(a, b)].append((sol, d)) | |
| lut = {} | |
| for state, sols_ in sols.items(): | |
| moves = [x for x, _ in sols_] | |
| m = moves[0] | |
| # intersect the solution sets across all depths | |
| for m2 in moves[1:]: | |
| m = m.intersection(m2) | |
| # if len(m)==1: | |
| # print("----") | |
| # print(state, m) | |
| # print(state,sols_) | |
| # funnily there is a solution for every move that works across all depths | |
| always_sol = m.pop() | |
| lut[state] = always_sol | |
| # for s, t in lut.items(): | |
| # print(f"{s} replace with {t}") | |
| # print([*lut.items()]) | |
| rows = [] | |
| encoding = {} | |
| index = 1 | |
| N_CHARS = 16 | |
| LUT = [""] * N_CHARS * N_CHARS | |
| seen = set() | |
| for t, tar in lut.items(): | |
| for x in t: | |
| if x not in encoding: | |
| encoding[x] = index | |
| index += 1 | |
| # initial character encoding | |
| s = encoding[t[0]] * N_CHARS + encoding[t[1]] | |
| assert s not in seen | |
| seen.add(s) | |
| LUT[s] = tar | |
| rows += [f'({s},"{tar}")'] | |
| # print("[" + "\n,".join(rows) + "]") | |
| #print(LUT) | |
| # first version of LUT | |
| # i-th entry is the list of neighbors of state i | |
| double_LUT = [] | |
| for i, x in enumerate(LUT): | |
| et = [] | |
| x = "A" + x | |
| for a, b in zip(x, x[1:]): | |
| et.append(encoding[a] * N_CHARS + encoding[b]) | |
| et += [0] * (6 - len(et)) | |
| double_LUT.append(et) | |
| print(double_LUT) | |
| # fill a matrix with these transitions | |
| M = [[0 for _ in range(256)] for _ in range(256)] | |
| for i, l in enumerate(double_LUT): | |
| for j in l: | |
| if j > 0: | |
| M[i][j] += 1 | |
| def mpow(m, n): | |
| res = m | |
| for i in range(n - 1): | |
| res = mat_prod(res, m) | |
| return res | |
| # calculate matrix powers | |
| res1, res2 = mpow(M, 3), mpow(M, 26) | |
| print(np.array(res1).shape) | |
| v = [sum(a[1:]) for a in res1] | |
| w = [sum(b[1:]) for b in res2] | |
| # v is LUT for part1 | |
| print(v) | |
| # w is LUT for part2 | |
| print(w) | |
| # this is the encoding of a single "0..9A<>^v" | |
| print(encoding) | |
| # encoding[from_] * N_CHARS + encoding[to_] is the formula to get the full index | |
| # from here on is just an additional compression | |
| # where we remove all the steps that cannot be part of the inital vector | |
| # (any transition with a "<^>v" in it | |
| # => 11*11=121 entries instead of 256 | |
| def ind(x): | |
| x = ord(x) | |
| return x % 16 + (x // 64) * 9 | |
| compressed = {} | |
| for x, y in product(encoding, repeat=2): | |
| e1, e2 = encoding[x], encoding[y] | |
| i1, i2 = ind(x), ind(y) | |
| if i1 >= 11 or i2 >= 11: | |
| continue | |
| compressed[e1 * N_CHARS + e2] = i1 * 11 + i2 | |
| print(compressed) | |
| cv = [0] * 11 * 11 | |
| cw = [0] * 11 * 11 | |
| for x, c in compressed.items(): | |
| cv[c] = v[x] | |
| cw[c] = w[x] | |
| print(cv) | |
| print(cw) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment