def find_landmark(map, landmark):
    for y in range(len(map)):
        x = map[y].find(landmark)
        if x >= 0: return (x, y)
    return None

def print_map_compact(map, path):
    for y, row in enumerate(map):
        for x, char in enumerate(row):
            if (x, y) in path:
                print("@", end="")
            else:
                print(char, end="")
    print()
    if len(path) == 0: print("    ###  NO PATH  ###\n\n")

# I'm also defining an html output for debugging
def print_map_html(map, explored, path):
    light_left = {}
    max_light = 1
    for location, dt_list in explored.items():
        for (distance, light, *_) in dt_list:
            light_left[location] = max(light, light_left.get(location, 0))
            max_light = max(max_light, light)

    print('<pre style="letter-spacing:3px;font-size:12px;line-height:15px">')
    for y, row in enumerate(map):
        for x, char in enumerate(row):
            if char == '\n':
                print()
            else:
                style = []
                title = []
                if WALL_CHARS.find(char) >= 0:
                    style.append("background:#999;color:#999")
                if (x, y) in path:
                    style.append("color:green")
                    for i, loc in enumerate(path):
                        if loc == (x, y): title.append("@step {}".format(i))
                    if char == ' ':
                        count = path.count((x, y))
                        if count == 1: char = '&#x2022;'
                        elif count == 2: char = '&#x25cf;'
                        else: char = '&#x25c9;'
                    if char == 't':
                        char = 'T'
                if (x, y) in light_left:
                    if char == 't' or char == 'T':
                        style.append("background:yellow")
                    else:
                        style.append("background:hsl(60,50%,{:.0%})".format(
                            0.5 * (1 + light_left[(x, y)] / max_light)))
                if not style:
                    style.append("background:hsl(240,20%,70%)")
                if char == ' ': 
                    char = "&#160;" # ugh, not sure why this is needed
                print("<span style='{}' title='{}'>{}</span>".format(
                    ";".join(style), "; ".join(title), char), end="")
    print('</pre>')

import time, collections
DIRS = [(1, 0), (0, -1), (-1, 0), (0, 1)]
WALL_CHARS = "x-|"

def search(map, start, goal):
    start_time, COUNT, HIT_WALL, PRUNED, OUT_OF_LIGHT = time.time(), 0, 0, 0, 0
    open = collections.deque() # state
    open.append((start, 0, set(), None))
    seen = {} # {loc: set of (distance, light)}
    seen[start] = set([(0, 15)])

    while open:
        state = open.popleft()
        loc, distance, torches, _ = state
        if loc == goal: break

        COUNT += 1
        if 15 + 15 * len(torches) - distance <= 0:
            OUT_OF_LIGHT += 1
            continue # can't take any distance because we're out of light

        (x, y) = loc
        for (dx, dy) in DIRS:
            x2 = x + dx
            y2 = y + dy
            loc2 = (x2, y2)
            distance2 = distance + 1
            torches2 = torches

            if WALL_CHARS.find(map[y2][x2]) >= 0:
                # can't walk into a wall
                HIT_WALL += 1
                continue

            if map[y2][x2] == 't' and (x2, y2) not in torches:
                # pick up the torch if it's still there
                torches2 = torches.copy()
                torches2.add(loc2)
                
            seen.setdefault(loc2, set())
            light2 = 15 + 15 * len(torches2) - distance2
            for (d, l) in seen[loc2]:
                if d <= distance2 and l >= light2:
                    # we've been here before with better conditions
                    PRUNED += 1
                    break
            else:
                open.append((loc2, distance2, torches2, state))
                seen[loc2].add((distance2, light2))

    # reconstruct the path
    path = []
    light_levels = []
    if state[0] == goal:
        current = state
        while current != None:
            loc, distance, torches, parent = current
            path.append(loc)
            light_levels.append(15 + 15 * len(torches) - distance)
            current = parent
    light_levels.reverse()
    path.reverse()

    # some stats
    print("processed:", COUNT, "; hit wall:", HIT_WALL, "; out of light:", OUT_OF_LIGHT, "; pruned:", PRUNED, "; path length:", len(path)-1, "; time: %dms" % (1000*(time.time()-start_time)))
    print("light along the path:", light_levels)
    return seen, path

def run(filename):
    print("_"*20, filename, "_"*40)
    map = open(filename).readlines()
    start = find_landmark(map, 'H')
    goal = find_landmark(map, 'T')
    results, path = search(map, start, goal)
    print_map_compact(map, path)
    print("\n\n\n")