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