import heapq
import time

t0 = time.time()


class DiscoveryNode(tuple):
    def __new__(cls, x, y, cost=0, ancestors=None, matches=None):
        n = tuple.__new__(cls, (x, y))
        n.cost = cost
        n.ancestors = ancestors if ancestors is not None else []
        n.matches = matches if matches is not None else []
        return n

    def __repr__(self):
        return f"<{self[0]}, {self[1]}>"


class Queue:
    def __init__(self):
        self.items = []

    def __bool__(self):
        return bool(self.items)

    def __repr__(self):
        return str(self.items)

    def values(self):
        return (v for _, v in self.items)

    def put(self, priority, item):
        while priority in [p for p, _ in self.items]:
            priority += 1
        heapq.heappush(self.items, (priority, item))

    def get(self):
        return heapq.heappop(self.items)[1]

    def get_items(self):
        return heapq.heappop(self.items)


def log(*msg):
    print("{} - ".format(str(time.time() - t0)[:5]), *msg)


start = (0, 3)
obstacles = [(0, 0), (1, 0), (3, 0), (9, 0), (11, 0), (12, 0), (0, 1), (1, 1), (5, 1), (7, 1), (11, 1), (12, 1), (3, 3), (9, 3)]
neutrals = [(1, 4), (2, 3), (1, 5), (3, 5), (2, 6), (4, 1), (11, 4), (10, 3), (11, 5), (9, 5), (10, 6), (8, 1)]

width = 13
height = 7


def get_neighbors(x, y):
    return [(xn, yn) for xn, yn in [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if
                                       0 <= xn < width and 0 <= yn < height]


def can_move_on(pos):
    return pos not in obstacles and pos not in neutrals


def discover_multiple(start, key, limit=5):
    nodes = Queue()
    its, break_on = 0, 20000
    origin = DiscoveryNode(*start)

    nodes.put(0, origin)

    while nodes:
        current = nodes.get()

        neighbors = get_neighbors(*current)

        for pos in neighbors:
            its += 1
            if its > break_on:
                log(f"<!> discovery broke")
                break

            if not can_move_on(pos):
                continue

            moving_cost = 1

            matches = []
            for n in get_neighbors(*pos):
                if n not in current.matches and key(n):
                    matches.append(n)

            cost = current.cost + moving_cost
            priority = 100 * cost - (200 * (len(current.matches) + len(matches)))
            priority += 10 * len([a for a in current.ancestors if a == pos])  # décourage de revenir à une case visitée

            node = DiscoveryNode(
                pos[0],
                pos[1],
                cost,
                current.ancestors + [current],
                current.matches + matches
            )

            nodes.put(priority, node)

        if len(current.matches) >= limit or its > break_on:
            break

    best_node = nodes.get()
    path = best_node.ancestors[1:] + [best_node]
    return path, best_node.matches


log("start")

res = discover_multiple(start, key=lambda x: x in neutrals, limit=6)

log(res)