summaryrefslogtreecommitdiff
path: root/21_2023.py
blob: 698b2a77b9f12022da0319f578129b74db19383a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
import heapq
import math

D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])

for r in range(R):
    for c in range(C):
        if G[r][c] == "S":
            sr, sc = r, c


def findD(r, c):
    D = {}
    Q = deque([(0, 0, sr, sc, 0)])
    while Q:
        tr, tc, r, c, d = Q.popleft()
        if r < 0:
            tr -= 1
            r += R
        if r >= R:
            tr += 1
            r -= R
        if c < 0:
            tc -= 1
            c += C
        if c >= C:
            tc += 1
            c -= C
        if not (0 <= r < R and 0 <= c < C and G[r][c] != "#"):
            continue
        if (tr, tc, r, c) in D:
            continue
        if abs(tr) > 4 or abs(tc) > 4:
            continue
        D[(tr, tc, r, c)] = d
        for dr, dc in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
            Q.append((tr, tc, r + dr, c + dc, d + 1))
    return D


D = findD(sr, sc)

SOLVE = {}


def solve(d, v, L):
    amt = (L - d) // R
    if (d, v, L) in SOLVE:
        return SOLVE[(d, v, L)]
    ret = 0
    for x in range(1, amt + 1):
        if d + R * x <= L and (d + R * x) % 2 == (L % 2):
            ret += (x + 1) if v == 2 else 1
    SOLVE[(d, v, L)] = ret
    return ret


def solve21(part1):
    L = 64 if part1 else 26501365
    ans = 0
    for r in range(R):
        for c in range(C):
            if (0, 0, r, c) in D:

                def fast(tr, tc):
                    ans = 0
                    B = 3
                    if tr > B:
                        ans += R * (abs(tr) - B)
                        tr = B
                    if tr < -B:
                        ans += R * (abs(tr) - B)
                        tr = -B
                    if tc > B:
                        ans += C * (abs(tc) - B)
                        tc = B
                    if tc < -B:
                        ans += C * (abs(tc) - B)
                        tc = -B
                    ans += D[(tr, tc, r, c)]
                    return ans

                # for tr in range(-8,8):
                #  msg = []
                #  for tc in range(-8,8):
                #    msg.append(str(D[(tr,tc,r,c)]))
                #  #print(' '.join(msg))
                # for tr in range(-8,8):
                #  for tc in range(-8,8):
                #    assert D[(tr,tc,r,c)]==fast(tr,tc), f'{tr} {tc} {D[(tr,tc,r,c)]} {fast(tr,tc)}'

                # How many ways are there to get a copy of (r,c) in L steps?
                # interior point: just check that point
                # edge: represents everything in that direction. can add arbitrarily many R to distance
                # corner: represents everything in that quadrant. can add arbitrarily many R or C to that distance

                # CEEEC
                # E...E
                # E...E
                # E...E
                # CEEEC
                assert R == C
                OPT = [-3, -2, -1, 0, 1, 2, 3]
                for tr in OPT:
                    for tc in OPT:
                        if part1 and (tr != 0 or tc != 0):
                            continue
                        d = D[(tr, tc, r, c)]
                        if d % 2 == L % 2 and d <= L:
                            ans += 1
                        if tr in [min(OPT), max(OPT)] and tc in [min(OPT), max(OPT)]:
                            ans += solve(d, 2, L)
                        elif tr in [min(OPT), max(OPT)] or tc in [min(OPT), max(OPT)]:
                            ans += solve(d, 1, L)
    return ans


print(solve21(True))
print(solve21(False))