"""Two robots, no collisions: they may never stand on the same field or swap places in one step.
A robot may follow into the field the other one just left, and '.' makes a robot wait.

Start from the sharing plan. One robot keeps its route; the other visits its fields in the same
order but plans every step in space and time around the first. A simple plan that always works is
kept as a fallback.
"""
from collections import deque

import two_robots
from dirt_common import walk
from shortest_route_fast import DIRS
from two_robots import finish_time, parse_two, positions


def solution(room, seconds=1.0):
    a, b, floor = parse_two(room)
    plan = two_robots.solution(room, seconds)
    if collision_free(a, b, *plan):
        return plan
    candidates = [last_resort(a, b, floor)]
    for keep_a in (True, False):
        replanned = replan(a, b, floor, plan, keep_a)
        if replanned and collision_free(a, b, *replanned):
            candidates.append(replanned)
    return min(candidates, key=finish_time)


def collision_free(a, b, a_moves, b_moves):
    pa, pb = positions(a, a_moves), positions(b, b_moves)
    for t in range(1, max(len(pa), len(pb))):
        a0, a1 = pa[min(t - 1, len(pa) - 1)], pa[min(t, len(pa) - 1)]
        b0, b1 = pb[min(t - 1, len(pb) - 1)], pb[min(t, len(pb) - 1)]
        if a1 == b1 or (a1 == b0 and b1 == a0):
            return False
    return True


def replan(a, b, floor, plan, keep_a):
    """The kept robot follows its route; the other visits its remaining fields around it."""
    keep_start, move_start = (a, b) if keep_a else (b, a)
    keep_moves, move_moves = plan if keep_a else plan[::-1]
    keep_path = positions(keep_start, keep_moves)
    end = len(keep_path) - 1
    last_seen = {cell: t for t, cell in enumerate(keep_path)}
    last_seen[keep_path[-1]] = float('inf')             # it stays on its final field for good

    def kept_at(t):
        return keep_path[min(t, end)]

    pos, t, moves, cleaned = move_start, 0, [], set(keep_path) | {move_start}
    targets = [cell for cell in dict.fromkeys(positions(move_start, move_moves)) if cell not in cleaned]
    goals = [lambda cell, time, target=target: cell == target for target in targets]
    goals.append(lambda cell, time: last_seen.get(cell, -1) < time)     # park out of the way
    for goal, target in zip(goals, targets + [None]):
        if target in cleaned:
            continue
        path = timed_path(pos, t, goal, kept_at, end, floor)
        if path is None:
            return None
        for go, cell in path:
            moves.append(go)
            pos, t = cell, t + 1
            cleaned.add(cell)
    moved = ''.join(moves).rstrip('.')
    return (keep_moves, moved) if keep_a else (moved, keep_moves)


def timed_path(pos, t, goal, kept_at, end, floor):
    """Earliest sequence of moves or waits from (pos, t) to a (field, time) that meets goal, never
    sharing a field with the kept robot and never swapping with it. None if impossible."""
    if goal(pos, t):
        return []
    options = [(0, 0, '.')] + DIRS
    first = (pos, min(t, end))
    parent = {first: None}
    queue = deque([(pos, t)])
    while queue:
        cell, time = queue.popleft()
        here = kept_at(time)
        there = kept_at(time + 1)
        for dr, dc, go in options:
            n = (cell[0] + dr, cell[1] + dc)
            if n not in floor or n == there or (n == here and there == cell):
                continue
            state = (n, min(time + 1, end))
            if state in parent:
                continue
            parent[state] = ((cell, min(time, end)), go, time)
            if goal(n, time + 1):
                path = []
                while parent[state]:
                    prev, go, _ = parent[state]
                    path.append((go, state[0]))
                    state = prev
                return path[::-1]
            queue.append((n, time + 1))
    return None


def last_resort(a, b, floor):
    """A cleans everything it can reach without passing B and comes home while B waits; then B
    cleans everything it can reach without passing A. Any field's shortest path from A either
    avoids B or continues past B without coming back, so together they clean every field."""
    a_moves, _ = walk(a, floor - {b})
    b_moves, order = walk(b, floor - {a})
    b_part = ''.join(b_moves[:order[-1][1]])
    return ''.join(a_moves), ('.' * len(a_moves) + b_part).rstrip('.')