#!/usr/bin/env python3

import sys
from copy import deepcopy


def find_track(track, p, c):
    path = deepcopy(track)
    directions = [[0,1], [1,0], [0,-1], [-1,0]]
    curx, cury = p['s']
    p[0] = p['s']
    for i in range(sum([t.count('.') for t in track])+1):
        for d in directions:
            nx, ny = curx + d[0], cury + d[1]
            if 0 <= nx < len(track[0]) and 0 <= ny < len(track):
                if path[ny][nx] == '.' or path[ny][nx] == 'E':
                    path[ny][nx] = str(i+1)
                    p[i+1] = (nx, ny)
                    curx, cury = nx, ny
                    break

    for i in range(sum([t.count('.') for t in track])+1):
        curx, cury = p[i]
        for d in directions:
            nx, ny = curx + d[0], cury + d[1]
            if 0 <= nx < len(track[0]) and 0 <= ny < len(track) and track[ny][nx] == '#':
                for d1 in directions:
                    tx, ty = nx + d1[0], ny + d1[1]
                    if 0 <= tx < len(track[0]) and 0 <= ty < len(track) and track[ty][tx] in ['.', 'E'] and int(path[ty][tx]) > i:
                        c[(i,path[ty][tx])] = int(path[ty][tx]) - i - 2
    return path


if __name__ == '__main__':
    track = [list(line.strip('\n')) for line in open(sys.argv[1])]
    positions = {}
    cheats ={}
    for j,t in enumerate(track):
        if 'S' in t: positions['s'] = (t.index('S'),j)
        if 'E' in t: positions['e'] = (t.index('E'),j)
    path = find_track(track, positions, cheats)

    # challenge 1
    res1 = 0
    for v in sorted(set(cheats.values())):
        if v >= 100:
            res1 += [x for x in cheats.values()].count(v)
    print(f"challenge 1:\n{res1}\n")

    # challenge 2 (replace 100 by 50 for example)
    res2 = 0
    for i in range(sum([t.count('.') for t in track])+2):
        x, y = positions[i]
        for j in range(i+100, sum([t.count('.') for t in track])+2):
            x1, y1 = positions[j]
            dist = abs(y1-y) + abs(x1-x)
            if dist <= 20 and j-i-dist>=100:
                res2 += 1
    print(f"challenge 2:\n{res2}")