diff options
| author | Marvin Borner | 2023-12-21 19:49:03 +0100 |
|---|---|---|
| committer | Marvin Borner | 2023-12-21 19:49:03 +0100 |
| commit | afbe42e5eb0bd682a1a1e9004f14f85404322601 (patch) | |
| tree | 080cb889770d38088a07c035bccbfe98fbc0ad6a /2023/21 | |
| parent | 0e937ae7fe7cbd4b9b491421705d556f38a00114 (diff) | |
i have no idea
Diffstat (limited to '2023/21')
| -rw-r--r-- | 2023/21/solve.py | 102 |
1 files changed, 57 insertions, 45 deletions
diff --git a/2023/21/solve.py b/2023/21/solve.py index 9aca201..a10340e 100644 --- a/2023/21/solve.py +++ b/2023/21/solve.py @@ -4,56 +4,68 @@ L = { for (j, c) in enumerate(l.strip()) } -W = max(j for (i, j) in L.keys()) -H = max(i for (i, j) in L.keys()) +W = max(j for (i, j) in L.keys()) + 1 +C = W // 2 -def solve1(): - LIM = 64 +# from day 9 +def predict(s): + f = [] + while s: + f.append(s[-1]) + s = [s[i] - s[i - 1] for i in range(1, len(s))] + return sum(f) - res = 0 - s = [(i, j) for (i, j) in L if L[(i, j)] == "S"][0] - q = [(s, 0)] - v = set() - while q: - p, n = q.pop(0) - if n == LIM + 1: - continue - for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]: - np = (p[0] + move[0], p[1] + move[1]) - if np not in L or np in v or L[np] == "#": - continue - q.append((np, n + 1)) - v.add(np) - if n % 2: - res += 1 - print(res) - - -def solve2(): - LIM = 26501365 - - res = 0 - s = [(i, j) for (i, j) in L if L[(i, j)] == "S"][0] - q = [(s, 0)] - v = set() - while q: - p, n = q.pop(0) - if n == LIM + 1: +# more efficient than predict +from numpy.polynomial import Polynomial + + +FIN = 26501365 +PREHEAT = 5 +LIM1 = 64 +LIM2 = C + PREHEAT * W + +pre = {-1: 0} +s = [(i, j) for (i, j) in L if L[(i, j)] == "S"][0] +q = [(s, 0)] +v = set() + +part1 = 0 + +while q: + p, n = q.pop(0) + if n == LIM1 and not part1: + part1 = pre[LIM1 - 1] + if n == LIM2: + break + + for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]: + np = (p[0] + move[0], p[1] + move[1]) + _np = (np[0] % W, np[1] % W) + if _np not in L or np in v or L[_np] == "#": continue + q.append((np, n + 1)) + v.add(np) + if n % 2: + if n not in pre: + pre[n] = pre[n - 2] + pre[n] += 1 + +print(part1) +print(pre) - for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]: - np = (p[0] + move[0], p[1] + move[1]) - _np = (np[0] % (H + 1), np[1] % (W + 1)) - if _np not in L or np in v or L[_np] == "#": - continue - q.append((np, n + 1)) - v.add(np) - if n % 2: - res += 1 - print(res) +poly = {} +for i in range(PREHEAT): + j = C + i * W + if j % 2: + poly[i] = pre[j] +print(poly) +f = Polynomial.fit(list(poly.keys()), list(poly.values()), 2) +x = (FIN - C) / W +res = f(x) +print(f, x, round(res)) -solve1() -solve2() +# for i in range(PREHEAT, (FIN - C) / W + 1): +# poly.append(predict(poly)) |