#!/usr/bin/env python3

# import numpy as np
from functools import reduce
from re import findall
from copy import deepcopy
import sys
import time

# filename = "in/day12.ref"
filename = "in/day12.pzl"
data = open(filename).read()
lines = [line for line in data.rstrip('\n').split('\n')]
# print(lines)

res1 = 0
res2 = 0

grid = list()

start_x = 0
start_y = 0
end_x = 0
end_y = 0
for y,line in enumerate(lines):
    l = list()
    for x,char in enumerate(line.strip()):
        if char == 'S':
            start_x = x
            start_y = y
            l.append(0)
        elif char == 'E':
            end_x = x
            end_y = y
            l.append(25)
        else:
            l.append(ord(char) - ord('a'))
    grid.append(l)

# print('grid', grid)
# print('end', end_y, end_x)

def print_visited(visited, steps):
    print('\x1b[2J')
    for y,l in enumerate(visited):
        for x,_ in enumerate(l):
            if visited[y][x] > steps:
                print('.', end='')
            else:
                print('#', end='')
        print()
    time.sleep(0.1)


# def traverse(grid, visited, steps, y, x):
#     # if visited[y][x] < steps:
#     # if visited[y][x] < 12345:
#         # print('syx', steps, y,x)
#         # print(steps, visited[y][x])
#         # return 420000, visited
#         # visited[y][x] = steps

#     # if steps % 100 == 0:
#         # print(steps)
#     print_visited(visited, steps)

#     if x==end_x and y==end_y:
#         print('steps', steps)
#         return steps, visited

#     lowest = list()
#     lowest.append(42000)
#     if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1:
#         low, visited = traverse(grid, visited, steps+1, y, x+1)
#         lowest.append(low)

#     if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1:
#         low, visited = traverse(grid, visited, steps+1, y+1, x)
#         lowest.append(low)

#     if y > 0 and grid[y-1][x] <= grid[y][x]+1:
#         low, visited = traverse(grid, visited, steps+1, y-1, x)
#         lowest.append(low)

#     if x > 0 and grid[y][x-1] <= grid[y][x]+1:
#         low, visited  = traverse(grid, visited, steps+1, y, x-1)
#         lowest.append(low)

#     return min(lowest), visited


# def traverse_same(s, y, x):
#     for t in tiles:
#         if (y,x) in t:
#             # print('already in tiles', y,x)
#             return s
#     if (y,x) in s:
#         # print('already in set', y,x)
#         return s

#     s.add((y,x))
#     # if steps % 100 == 0:
#         # print(steps)
#         # print_visited(visited, steps)

#     if x+1 < len(grid[0]) and grid[y][x+1] == grid[y][x]:
#         s.union(traverse_same(s, y, x+1))

#     if x > 0 and grid[y][x-1] == grid[y][x]:
#         s.union(traverse_same(s, y, x-1))

#     if y+1 < len(grid) and grid[y+1][x] == grid[y][x]:
#         s.union(traverse_same(s, y+1, x))

#     if y > 0 and grid[y-1][x] == grid[y][x]:
#         s.union(traverse_same(s, y-1, x))

#     # print(y, x, s)
#     return s

# sys.setrecursionlimit(10000)
# visited = [[9999999 for i in l] for l in grid]
# print(visited)
# res1, visited = traverse(grid, visited, 0, start_y, start_x)

# tiles = list()
# tiles_vals = list()
# yx_to_tile = [[None for i in l] for l in grid]

# for j,l in enumerate(grid):
#     for i,_ in enumerate(l):
#         s = traverse_same(set(), j, i)
#         if len(s) > 0:
#             for (y,x) in s:
#                 yx_to_tile[y][x] = len(tiles)
#             tiles.append(s)
#             tiles_vals.append(grid[y][x])
#         # print(y, x, s)
# for line in grid:
#     print(line)
# print(tiles)
# print(tiles_vals)
# for line in yx_to_tile:
#     print(line)


def bfs(grid, start_y, start_x, end_y, end_x):
    visited = set()
    visited.add((start_y,start_x))

    steps = 0
    while True:
        new_visited = set()
        # print(visited)
        for (y,x) in visited:
            if x == end_x and y == end_y:
                # print('steps', steps, y, x)
                return steps

            if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1:
                new_visited.add((y, x+1))

            if x > 0 and grid[y][x-1] <= grid[y][x]+1:
                new_visited.add((y, x-1))

            if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1:
                new_visited.add((y+1, x))

            if y > 0 and grid[y-1][x] <= grid[y][x]+1:
                new_visited.add((y-1, x))

        visited = visited.union(new_visited)
        steps += 1

res1 = bfs(grid, start_y, start_x, end_y, end_x)

def bfs2(grid, start_y, start_x, end):
    visited = set()
    visited.add((start_y,start_x))

    steps = 0
    while True:
        new_visited = set()
        # print(visited)
        for (y,x) in visited:
            if (y,x) in end:
                # print('steps', steps, y, x)
                return steps

            if x+1 < len(grid[0]) and grid[y][x+1]+1 >= grid[y][x]:
                new_visited.add((y, x+1))

            if x > 0 and grid[y][x-1]+1 >= grid[y][x]:
                new_visited.add((y, x-1))

            if y+1 < len(grid) and grid[y+1][x]+1 >= grid[y][x]:
                new_visited.add((y+1, x))

            if y > 0 and grid[y-1][x]+1 >= grid[y][x]:
                new_visited.add((y-1, x))

        visited = visited.union(new_visited)
        steps += 1

elea = set()
for y,l in enumerate(grid):
    for x,_ in enumerate(l):
        if grid[y][x] == 0:
            elea.add((y,x))
# print(elea)

res2 = bfs2(grid, end_y, end_x, elea)


print('res1:', res1)
print('res2:', res2)