"""Blind robot: there is no map. robot.move(d) moves one field and returns True, or returns
False and stays put when a wall is in the way. The robot must clean every field it can reach.

The robot builds its own map in local coordinates that start at (0, 0).
"""
from collections import deque

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


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


def map_order(heading):
    """Always try up, down, left, right: the order Part 1 uses."""
    return '^v<>'


def left_hand_order(heading):
    """Left, straight, right, back, relative to the robot's last move (up at the start)."""
    h = heading or '^'
    return LEFT[h], h, BACK[LEFT[h]], BACK[h]


def solution(robot):
    """Depth-first exploration that walks all the way home. Returns the number of fields cleaned."""
    return explore(robot, map_order, trim=False, shortcuts=False)


def solution_trimmed(robot, order=map_order, shortcuts=False):
    """Stops the moment nothing is left to probe; can also take shortcuts when walking back."""
    return explore(robot, order, trim=True, shortcuts=shortcuts)


def explore(robot, order, trim, shortcuts):
    pos, heading = (0, 0), None
    known = {pos: True}                     # True: floor the robot has stood on, False: wall
    trail = []                              # fields the robot came from, newest last
    unknown = {shift(pos, d) for d in STEP}  # unprobed cells next to visited floor
    while True:
        for d in order(heading):
            n = shift(pos, d)
            if n in known:                  # never probe a known wall or a visited field
                continue
            unknown.discard(n)
            if robot.move(d):
                known[n] = True
                trail.append(pos)
                pos, heading = n, d
                unknown.update(m for m in (shift(n, e) for e in STEP) if m not in known)
                break
            known[n] = False
        else:                               # everything around this field is known
            if not trail or (trim and not unknown):
                return sum(known.values())
            last = walk_shortcut(robot, pos, trail, known) if shortcuts else None
            if last:
                pos, heading = trail.pop(), last
                continue
            back = trail.pop()
            heading = next(d for d in STEP if shift(pos, d) == back)
            robot.move(heading)
            pos = back


def walk_shortcut(robot, pos, trail, known):
    """Skip trail fields with nothing left to probe and walk straight to the newest one that has
    something, if the known floor offers a shorter way than retracing the trail.

    On success the robot stands on trail[-1] (the caller pops it) and the last direction moved is
    returned; otherwise None."""
    k = len(trail) - 1
    while k > 0 and all(shift(trail[k], d) in known for d in STEP):
        k -= 1
    if len(trail) - k < 3:                  # a shortcut must save at least 2 steps
        return None
    path = known_path(pos, trail[k], known)
    if len(path) >= len(trail) - k:
        return None
    for d in path:
        robot.move(d)
    del trail[k + 1:]
    return path[-1]


def known_path(a, b, known):
    """Directions along a shortest path from a to b over floor the robot has already visited."""
    parent, queue = {a: None}, deque([a])
    while b not in parent:
        cell = queue.popleft()
        for d in STEP:
            n = shift(cell, d)
            if known.get(n) and n not in parent:
                parent[n] = (cell, d)
                queue.append(n)
    path = []
    while b != a:
        b, d = parent[b]
        path.append(d)
    return path[::-1]