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 = (1, 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), (1, 4), (2, 3)]
neutrals = [(1, 5), (3, 4), (2, 6), (4, 2), (10, 2), (12, 5), (9, 5), (10, 6), (8, 2)]
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


class ConversionStep:
    def __init__(self):
        self.pos = None
        self.candidates = []

    def __repr__(self):
        return f"<{self.pos}, c:{self.candidates}>"


class ConversionPath:
    def __init__(self):
        self.steps = []

    def __repr__(self):
        return f"<{self.steps}>"

    @classmethod
    def make_from_discovery_node(cls, node):
        nodes = node.ancestors + [node]
        path = cls()
        found = []

        for node in nodes:
            step = ConversionStep()
            step.pos = tuple(node)
            for m in node.matches:
                if m in found:
                    continue
                step.candidates.append(m)
                found.append(m)
            path.steps.append(step)
        return path

    def path_to_next_candidate(self):
        path = []
        for step in self.steps:
            path.append(step)
            if step.candidates:
                return path
        return None


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

    abandon_at = 200  # number of paths explored

    nodes.put(0, origin)

    for n in get_neighbors(*start):
        if key(n):
            origin.matches.append(n)

    while nodes:
        its += 1
        if its > break_on:
            log(f"<!> discovery broke")
            break

        if len(nodes.items) > abandon_at:
            log("<!> get_conversion_path abandoned")
            break

        current = nodes.get()

        neighbors = get_neighbors(*current)

        for pos in neighbors:
            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 = 1000 * cost - (2000 * (len(current.matches) + len(matches)))
            priority += 100 * 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
            )

            if matches:
                winners.put(40 * node.cost - 100 * len(node.matches), node)

            nodes.put(priority, node)

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

    # for p, w in winners.items:
    #     log(f'* {p} - {w.ancestors + [w]} - {w.matches}')

    best_node = winners.get()
    path = ConversionPath.make_from_discovery_node(best_node)
    log(its)
    return path


log("start")

res = discover_multiple(start, key=lambda x: x in neutrals, limit=min(4, len(neutrals)))

log(res)