import sys
import heapq
sys.setrecursionlimit(int(1e6))
data = sys.argv[1] if len(sys.argv) > 1 else "day15data.txt"
G = []
for line in open(data):
G.append([int(x) for x in line.strip()])
R = len(G)
C = len(G[0])
DR = [-1, 0, 1, 0]
DC = [0, 1, 0, -1]
def solve(nTiles):
D = [[None for _ in range(nTiles * C)] for _ in range(nTiles * R)]
Q = [(0, 0, 0)]
while Q:
(dist, r, c) = heapq.heappop(Q)
if r < 0 or r >= nTiles * R or c < 0 or c >= nTiles * C:
continue
val = G[r % R][c % C] + (r // R) + (c // C)
while val > 9:
val -= 9
rcCost = dist + val
if D[r][c] is None or rcCost < D[r][c]:
D[r][c] = rcCost
else:
continue
if r == nTiles * R - 1 and c == nTiles * C - 1:
break
for d in range(4):
rr = r + DR[d]
cc = c + DC[d]
heapq.heappush(Q, (D[r][c], rr, cc))
return D[nTiles * R - 1][nTiles * C - 1] - G[0][0]
print(solve(1))
print(solve(5))
