def adjacents(point):
    x, y = point
    return sorted([(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)], key=lambda x: (x[1], x[0]))


def targets(attacker, units):
    faction = units[attacker][0]
    targets = dict()
    for unit in units:
        if faction != units[unit][0]:
            targets[unit] = units[unit]
    return targets


def in_range(targets, area, units):
    in_range = list()
    for target in targets:
        for adjacent in adjacents(target):
            if adjacent not in units and area[adjacent] != "#":
                in_range.append(adjacent)
    return in_range


def reachable(attacker, in_range, area, units):
    reachable = list()
    for point in in_range:
        if pathsearch(attacker, point, area, units):
            reachable.append(point)
    return reachable


def nearest(attacker, reachable, area, units):
    nearest = list()
    distances = []
    for point in reachable:
        distance = len(pathsearch(attacker, point, area, units))
        if distance:
            distances.append(distance)
    for point in reachable:
        if len(pathsearch(attacker, point, area, units)) == min(distances):
            nearest.append(point)
    return nearest


def chosen(nearest):
    return sorted(nearest, key=lambda x: (x[1], x[0]))[0]


def pathsearch(origin, destination, area, units):
    unvisited = dict()
    visited = dict()
    current = origin
    current_distance = 0
    unvisited[origin] = current_distance

    for point in area:
        if area[point] != "#" and point not in units:
            unvisited[point] = None

    while True:
        for adjacent in adjacents(current):
            if adjacent not in unvisited:
                continue
            distance = current_distance + 1
            if unvisited[adjacent] is None or unvisited[adjacent] > distance:
                unvisited[adjacent] = distance
        visited[current] = current_distance
        del unvisited[current]
        candidates = [point for point in unvisited.items() if point[1]]
        if destination in visited:
            break
        elif not candidates:
            return False
        else:
            current, current_distance = sorted(candidates, key=lambda x: x[1])[0]

    path = [destination]

    while True:
        next_step = []
        for adjacent in adjacents(destination):
            if adjacent in visited:
                next_step.append((adjacent[0], adjacent[1], visited[adjacent]))

        next_step = min(next_step, key=lambda x: (x[2], x[1], x[0]))
        destination = (next_step[0], next_step[1])
        if destination == origin:
            break
        path.append((next_step[0], next_step[1]))

    path.reverse()
    return path


def move(unit, area, units):
    t = targets(unit, units)
    # no targets remaining
    if not t:
        return False
    for target in t:
        # target adjacent so return without moving
        if target in adjacents(unit):
            return unit
    ir = in_range(t, area, units)
    r = reachable(unit, ir, area, units)
    # no reachable point so return without moving
    if not r:
        return unit
    n = nearest(unit, r, area, units)
    c = chosen(n)
    m = pathsearch(unit, c, area, units)[0]
    units[m] = units[unit]
    del units[unit]
    area[unit] = "."
    return m


def main():
    elves_attack_power = 2

    while True:
        has_dead_elf = False
        elves_attack_power += 1
        if elves_attack_power > 3:
            print(f"Trying ap {elves_attack_power}")

        data = [line for line in open('input', 'rt').readlines()]
        area = dict()
        units = dict()

        for y, datum in enumerate(data):
            for x, char in enumerate(datum):
                if char == "#":
                    area[(x, y)] = char
                elif char == ".":
                    area[(x, y)] = char
                elif char == "E":
                    units[(x, y)] = ("E", 200, elves_attack_power)
                elif char == "G":
                    units[(x, y)] = ("G", 200, 3)

        round = 0
        has_target = True

        while True:
            for unit in sorted(units, key=lambda x: (x[1], x[0])):
                if unit not in units:
                    continue

                has_target = move(unit, area, units)
                if not has_target:
                    break
                unit = has_target

                targets = list()
                for adjacent in adjacents(unit):
                    if adjacent in units and unit in units and units[adjacent][0] != units[unit][0]:
                        targets.append((adjacent, units[adjacent][1]))

                if targets:
                    target = sorted(targets, key=lambda x: (x[1], x[0][1], x[0][0]))[0]
                    target = target[0]
                    units[target] = (units[target][0], units[target][1] - units[unit][2], units[target][2])
                    if units[target][1] <= 0:

                        if units[target][0] == "E" and elves_attack_power != 3:
                            has_dead_elf = True
                            break

                        del units[target]
                        area[target] = "."

            if not has_target or has_dead_elf:
                break

            round += 1

        if has_dead_elf:
            continue

        total_hit_points = 0
        for faction, hit_points, _ in units.values():
            total_hit_points += hit_points

        if elves_attack_power == 3:
            print(f"Part 1:")
            print(f"Ended with {round} rounds and {total_hit_points} total hp")
            print(f"Puzzle part 1 answer is {round * total_hit_points}")
            print(f"Part 2:")
        else:
            print(f"Ended with {round} rounds and {total_hit_points} total hp")
            print(f"Puzzle part 2 answer is {round * total_hit_points}")
            return 0


exit(main())