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))
|