"""Part 7: search from both ends.

Breadth-first search from the start to a goal d steps away looks at every field closer than d
before it finds the goal: a disc of radius d. Searching from both ends at once, one ring at a
time from whichever side has the smaller ring, and stopping when the two meet, looks at two discs
of radius about d / 2 instead.

On a flat floor a disc of radius d has about 2d^2 fields and two discs of radius d / 2 about d^2,
so searching from both ends saves about half. On the hyperbolic floor a disc of radius d has
about 2.3^d fields, and two discs of radius d / 2 about 2 x 2.3^(d/2): the saving grows without
limit. The same algorithm, a different floor, a different answer to "is it worth it?".
"""
from collections import deque


def one_sided(neighbours, s, t):
    """Plain breadth-first search. Returns (distance, fields taken off the queue)."""
    dist, queue, expanded = {s: 0}, deque([s]), 0
    while queue:
        x = queue.popleft()
        expanded += 1
        if x == t:
            return dist[x], expanded
        for y in neighbours(x):
            if y not in dist:
                dist[y] = dist[x] + 1
                queue.append(y)
    return None, expanded


def two_sided(neighbours, s, t):
    """Breadth-first search from both ends, a whole ring at a time from the side whose ring is
    smaller. Returns (distance, fields expanded)."""
    if s == t:
        return 0, 1
    dist = [{s: 0}, {t: 0}]
    rings = [[s], [t]]
    expanded = 0
    while rings[0] and rings[1]:
        side = 0 if len(rings[0]) <= len(rings[1]) else 1
        here, there = dist[side], dist[1 - side]
        best, nxt = None, []
        for x in rings[side]:
            expanded += 1
            for y in neighbours(x):
                if y in there:                      # the searches meet
                    total = here[x] + 1 + there[y]
                    best = total if best is None else min(best, total)
                if y not in here:
                    here[y] = here[x] + 1
                    nxt.append(y)
        if best is not None:
            return best, expanded
        rings[side] = nxt
    return None, expanded


def grid_neighbours(cell):
    r, c = cell
    return ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1))


def tile_neighbours(tiles):
    """Neighbour lists for the fields of hyperbolic.rings: fields sharing an edge."""
    owner, nbrs = {}, [[] for _ in tiles]
    for t, c in enumerate(tiles):
        for k in range(4):
            e = frozenset((c[k], c[(k + 1) % 4]))
            if e in owner:
                nbrs[t].append(owner[e])
                nbrs[owner[e]].append(t)
            else:
                owner[e] = t
    return nbrs