# https://adventofcode.com/2021/day/15

import heapq
import timeit

test = "2021-15_example.txt"
run = "2021-15_input.txt"

def get_risk(board):
    r = c = 0
    max_r = len(board) - 1
    max_c = len(board[0]) - 1
    pq = []
    heapq.heappush(pq, (0, (r,c))) #storing entire path made long run times with personal input
    visited = set([(r,c)])
    while r < max_r or c < max_c:
        total, (r,c) = heapq.heappop(pq)
        for dr,dc in [(-1,0), (0,-1), (1,0), (0,1)]:
            new_r = r + dr
            new_c = c + dc
            if 0 <= new_r <= max_r and 0 <= new_c <= max_c and (new_r, new_c) not in visited:
                heapq.heappush(pq, (total + int(board[new_r][new_c]), (new_r, new_c)))
                visited.add((new_r, new_c))
    return total

def part1(fname):
    board = open(fname).read().splitlines()
    return get_risk(board)

def part2(fname):
    tile = [list(map(int, line)) for line in open(fname).read().splitlines()]
    board = []
    for i in range(5):
        for r,row in enumerate(tile):
            line = []
            for j in range(5):
                for val in row:
                    v = val+i+j if val+i+j < 10 else val+i+j-9
                    line.append(v)
            board.append(line)
    #for line in board:
    #    print(''.join(map(str, line)))
    return get_risk(board)

assert part1(test) == 40
print(f'part1: {part1(run)}')

assert part2(test) == 315
print(f'part2: {part2(run)}')

def t1():
    board = open(test).read().splitlines()
    r = c = 0
    max_r = len(board) - 1
    max_c = len(board[0]) - 1
    pq = []
    heapq.heappush(pq, (0, [(r,c)]))
    visited = set([(r,c)])
    while r < max_r or c < max_c:
        total, path = heapq.heappop(pq)
        r,c = path[-1]
        for dr,dc in [(-1,0), (0,-1), (1,0), (0,1)]:
            new_r = r + dr
            new_c = c + dc
            if 0 <= new_r <= max_r and 0 <= new_c <= max_c and (new_r, new_c) not in visited:
                heapq.heappush(pq, (total + int(board[new_r][new_c]), path + [(new_r, new_c)]))
                visited.add((new_r, new_c))
    #print(f't1: {total}\n{path}')

def t2():
    board = open(test).read().splitlines()
    r = c = 0
    max_r = len(board) - 1
    max_c = len(board[0]) - 1
    pq = []
    pq.append((0, [(r,c)]))
    visited = set([(r,c)])
    while r < max_r or c < max_c:
        total, path = pq.pop()
        r,c = path[-1]
        for dr,dc in [(-1,0), (0,-1), (1,0), (0,1)]:
            new_r = r + dr
            new_c = c + dc
            if 0 <= new_r <= max_r and 0 <= new_c <= max_c and (new_r, new_c) not in visited:
                pq.append((total + int(board[new_r][new_c]), path + [(new_r, new_c)]))
                pq.sort(key=lambda x:x[0], reverse=True)
                visited.add((new_r, new_c))
    #print(f't2: {total}\n{path}')

#print(timeit.timeit('t1()', globals=globals(), number=1000))
# 1.5710312000010163
#print(timeit.timeit('t2()', globals=globals(), number=1000))
# 2.699324599998363
