def readfile(path):
    with open(path) as input_file: 
        return input_file.read().strip()

memo3 = {}

def find_nearest(grid, current):
    gridkey = "".join(grid.values())
    if (memoized := memo3.get((gridkey, current))):
        return memoized

    q = [(current, 0)]
    keys = {}
    doors = {}
    visited = set()
    while q:
        cur, d = q.pop(0)
        for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            x, y = cur[0] + i, cur[1] + j
            if (x, y) in visited:
                continue
            visited.add((x, y))

            ch = grid.get((x, y))
            if ch == '.' or ch == '@' or (ch >= '0' and ch <= '3'):
                q.append(((x, y), d + 1))
            elif ch >= 'a' and ch <= 'z':
                keys[ch] = ((x, y), d + 1)
                q.append(((x, y), d + 1))
            elif ch >= 'A' and ch <= 'Z':
                doors[ch] = ((x, y), d + 1)

    result = keys, doors
    memo3[(gridkey, current)] = result
    return result

def gridmaker(inp):
    grid = {}
    points = {}

    x, y = 0, 0
    bot = 0
    for c in inp:
        if c != '#' and c != '.' and c != '\n':
            if c == '@':
                c = str(bot)
                bot += 1
            points[c] = (x, y)

        if c == '\n':
            y += 1
            x = 0
        else:
            grid[(x, y)] = c
            x += 1
    return grid, points

def printgrid(grid):
    minx = min(x for (x, _) in grid.keys())
    maxx = max(x for (x, _) in grid.keys())
    miny = min(y for (_, y) in grid.keys())
    maxy = max(y for (_, y) in grid.keys())

    for y in range(miny, maxy + 1):
        for x in range(minx, maxx + 1):
            print(grid.get((x, y)), end='')
        print()
    
# memo = {}

def keyfinder(grid, points, point, opened=""):
    # if (point, opened) in memo:
    #     return memo[(point, opened)]

    keys, doors = find_nearest(grid, point)
    min_distance = None
    min_opened = ""
    min_pos = point

    for label, (pos, dist) in keys.items():
        if min_distance is not None and dist > min_distance: 
            continue

        nextgrid = grid.copy()
        if (door := label.upper()) in points:
            nextgrid[points[door]] = '.' # Open door
        nextgrid[pos] = '.'

        distance, new_opened, last_pos = keyfinder(nextgrid, points, pos, "".join(sorted(opened + label))) 
        distance += dist

        if not min_distance or distance < min_distance:
            min_distance = distance
            min_opened = new_opened
            min_pos = last_pos

    # memo[(point, opened)] = (min_distance or 0, "".join(sorted(opened + min_opened)), min_pos)
    return (min_distance or 0, "".join(sorted(opened + min_opened)), min_pos)
    # return memo[(point, opened)]

memo2 = {}

def botfinder2(grid, points):
    gridkey = "".join(grid.values())
    pointskey = "-".join([f"{l}.{x}.{y}" for l, (x, y) in points.items()])
    if (memoized := memo2.get((gridkey, pointskey))):
        return memoized

    accessible_keys = []
    for point in range(4):
        keys, doors = find_nearest(grid, points[str(point)])
        accessible_keys.extend((str(point), x[0], x[1]) for x in keys.items())

    min_distance = None

    for pt, label, (pos, dist) in accessible_keys:
        if min_distance is not None and dist > min_distance: 
            continue

        nextgrid = grid.copy()
        nextpoints = points.copy()

        if (door := label.upper()) in points:
            nextgrid[points[door]] = '.' # Open door
        nextgrid[pos] = '.'
        nextpoints[pt] = pos

        distance = botfinder2(nextgrid, nextpoints) + dist

        if not min_distance or distance < min_distance:
            min_distance = distance

    result = min_distance or 0
    memo2[(gridkey, pointskey)] = result
    return result
    

memo2, memo3 = {}, {}
botfinder2(*gridmaker("""#######
#a.#Cd#
##@#@##
#######
##@#@##
#cB#.b#
#######"""))

8

memo2 = {}
botfinder2(*gridmaker("""###############
#d.ABC.#.....a#
######@#@######
###############
######@#@######
#b.....#.....c#
###############"""))

24

memo2 = {}
botfinder2(*gridmaker("""#############
#DcBa.#.GhKl#
#.###@#@#I###
#e#d#####j#k#
###C#@#@###J#
#fEbA.#.FgHi#
#############"""))

32

memo2, memo3 = {}, {}
botfinder2(*gridmaker("""#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba@#@BcIJ#
#############
#nK.L@#@G...#
#M###N#H###.#
#o#m..#i#jk.#
#############"""))

72

memo2, memo3 = {}, {}
botfinder2(*gridmaker(readfile("AoC/input18_2.txt").strip()))

1988