"""Part 4: a blind robot that can't tell whether its room wraps around.

Part 3's blind robot names each field by the position it works out from counting its own moves.
In a room that wraps around, one field has many such positions, one per way round, so a floor
with a loop that goes round the torus looks like an endless plane, and the robot never stops.
No robot can do better with only its bump sensor (the post proves it), so this one gets a second
sense: robot.on_dock() is True when it stands on its dock, the field it started on, and there is
only one dock.

Whenever the robot stands on the dock at a counted position other than (0, 0), it has walked a
loop round the room, and that position is a period. It adds the period to a lattice (Hermite
normal form, from periods.py) and from then on names every field by its position reduced modulo
the lattice, which folds its map up.

It explores the way many real robots do, frontier first: walk to the nearest known floor field
that still has an unprobed neighbour, and probe it. On its own that could chase an endless-looking
map for ever, so the robot only probes next to fields within `radius` steps of the dock, and
doubles the radius whenever that limit is what stopped it. With the radius doubling, a copy of the
dock at any finite distance is reached in finite time, and when nothing is left to probe at all,
the folded map is the whole room.
"""
from collections import deque

from periods import hermite, reduce

STEP = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}
ORDER = '^v<>'


def shift(p, d):
    return p[0] + STEP[d][0], p[1] + STEP[d][1]


class Lattice:
    """The periods found so far, as translations: a field's name is its position reduced
    modulo them."""

    def __init__(self):
        self.basis = ()

    def canon(self, p):
        return reduce(p, self.basis)

    def learn(self, p, reading=None):
        """The dock turned up at counted position p. Returns True if that is news."""
        if self.canon(p) == (0, 0):
            return False
        self.basis = hermite(self.basis + (p,))
        return True


def solution(robot, group=None, growth=2, radius=1):
    """Clean everything and stop. Returns (fields cleaned, statistics). `growth` is how much
    the radius grows each time it is what stopped the robot; radius=math.inf switches the limit
    off (and the robot can then run for ever)."""
    group = group if group is not None else Lattice()
    known = {group.canon((0, 0)): True}     # name of a field -> True floor, False furniture
    pos = (0, 0)
    stats = {'periods': 0, 'doublings': 0}
    while True:
        near = dock_distances(known, group)
        target = nearest_frontier(pos, known, group, near, radius)
        if target is None:
            if not any(near[name] >= radius for name in frontier(known, group, near)):
                stats['radius'] = radius
                return sum(known.values()), stats
            radius *= growth                # the limit stopped it: look further
            stats['doublings'] += 1
            continue
        path, d = target
        for step in path:                   # over known floor to the frontier field
            assert robot.move(step)
            pos = shift(pos, step)
        n = shift(pos, d)
        known[group.canon(n)] = robot.move(d)
        if not known[group.canon(n)]:
            continue                        # bumped into furniture
        pos = n
        reading = robot.on_dock()
        assert reading or group.canon(pos) != group.canon((0, 0)), 'map says dock, robot says not'
        if reading and group.learn(pos, reading):
            stats['periods'] += 1
            known = fold(known, group)


def fold(known, group):
    folded = {}
    for name, floor in known.items():
        key = group.canon(name)
        assert folded.get(key, floor) == floor, 'the room is not what the map says'
        folded[key] = floor
    return folded


def dock_distances(known, group):
    """Steps from the dock to every known floor field, over known floor."""
    home = group.canon((0, 0))
    dist, queue = {home: 0}, deque([(0, 0)])
    while queue:
        p = queue.popleft()
        k = dist[group.canon(p)]
        for d in ORDER:
            n = shift(p, d)
            name = group.canon(n)
            if known.get(name) and name not in dist:
                dist[name] = k + 1
                queue.append(n)
    return dist


def frontier(known, group, near):
    """Known floor fields with a neighbour nobody has probed yet."""
    out = []
    for name in near:
        if any(group.canon(shift(name, d)) not in known for d in ORDER):
            out.append(name)
    return out


def nearest_frontier(pos, known, group, near, radius):
    """Breadth-first search from the robot over known floor, in its own counted positions, for
    the nearest field within radius - 1 of the dock that has an unprobed neighbour. Returns
    (path there, direction to probe), or None."""
    start = group.canon(pos)
    parent = {start: None}
    queue = deque([pos])
    while queue:
        p = queue.popleft()
        name = group.canon(p)
        if near[name] < radius:
            for d in ORDER:
                if group.canon(shift(p, d)) not in known:
                    path = []
                    while parent[group.canon(p)] is not None:
                        p, step = parent[group.canon(p)]
                        path.append(step)
                    return path[::-1], d
        for d in ORDER:
            n = shift(p, d)
            key = group.canon(n)
            if known.get(key) and key not in parent:
                parent[key] = (p, d)
                queue.append(n)
    return None