"""Two robots, sharing allowed: split the work so the floor is clean as soon as possible.

Robot A starts on '*' and robot B on '@'. Both move at the same time, one command per step, and
the floor is clean once every field has been visited by one of them. The time is the length of
the longer command string. (Collisions are handled on top of this in two_robots_no_collide.py.)
"""
import time
from collections import deque

from shortest_route_fast import DIRS, best_route, shortest_path, steps

BACK = {'^': 'v', 'v': '^', '<': '>', '>': '<'}
MOVE = {go: (dr, dc) for dr, dc, go in DIRS}


def parse_two(room):
    a = b = None
    floor = set()
    for r, row in enumerate(room):
        for c, ch in enumerate(row):
            if ch != '#':
                floor.add((r, c))
                if ch == '*':
                    a = (r, c)
                elif ch == '@':
                    b = (r, c)
    return a, b, floor


def distances(start, cells):
    dist, queue = {start: 0}, deque([start])
    while queue:
        cell = queue.popleft()
        for n, _ in steps(cell, cells):
            if n not in dist:
                dist[n] = dist[cell] + 1
                queue.append(n)
    return dist


def lower_bound(room):
    """Each step cleans at most two new fields, and some field is this far from both robots."""
    a, b, floor = parse_two(room)
    da, db = distances(a, floor), distances(b, floor)
    return max(-(-(len(floor) - 2) // 2), max(min(da[f], db[f]) for f in floor))


def positions(start, commands):
    cells = [start]
    for go in commands:
        if go != '.':
            cells.append((cells[-1][0] + MOVE[go][0], cells[-1][1] + MOVE[go][1]))
        else:
            cells.append(cells[-1])
    return cells


def finish_time(plan):
    return max(len(plan[0]), len(plan[1])), len(plan[0]) + len(plan[1])


def solution(room, seconds=1.0):
    a, b, floor = parse_two(room)
    b_part, a_part = shared_walk(b, a, floor)
    plans = [split_by_regions(a, b, floor, seconds),
             shared_walk(a, b, floor),
             (a_part, b_part),
             (best_route(a, floor - {b}, floor), ''),
             ('', best_route(b, floor - {a}, floor))]
    return min(plans, key=finish_time)


def split_by_regions(a, b, floor, seconds):
    """Give each field to the robot that reaches it first when B starts `delay` steps late, pick
    the delay where the two routes balance, then move border fields from the longer region."""
    da, db = distances(a, floor), distances(b, floor)

    def routes(region_a, region_b, runs=3):
        return best_route(a, region_a, floor, runs), best_route(b, region_b, floor, runs)

    best = None
    lo, hi = -max(db.values()), max(da.values())
    while lo <= hi:
        delay = (lo + hi) // 2
        region_a = {f for f in floor if da[f] <= db[f] + delay and f != b} | {a}
        region_b = (floor - region_a) | {b}
        plan = routes(region_a, region_b)
        if best is None or finish_time(plan) < finish_time(best[0]):
            best = (plan, region_a, region_b)
        if len(plan[0]) < len(plan[1]):
            lo = delay + 1
        else:
            hi = delay - 1

    plan, region_a, region_b = best
    deadline = time.perf_counter() + seconds
    improved = True
    while improved and time.perf_counter() < deadline:
        improved = False
        a_is_longer = len(plan[0]) >= len(plan[1])
        give, take, start = (region_a, region_b, a) if a_is_longer else (region_b, region_a, b)
        border = sorted(f for f in give if f != start and any(n in take for n, _ in steps(f, floor)))
        for cell in border:
            smaller = give - {cell}
            if not connected(smaller, start):
                continue
            new_a, new_b = (smaller, take | {cell}) if a_is_longer else (take | {cell}, smaller)
            candidate = routes(new_a, new_b)
            if finish_time(candidate) < finish_time(plan):
                plan, region_a, region_b, improved = candidate, new_a, new_b, True
                break
            if time.perf_counter() >= deadline:
                break
    return routes(region_a, region_b, runs=10)


def connected(region, start):
    seen, queue = {start}, deque([start])
    while queue:
        cell = queue.popleft()
        for n, _ in steps(cell, region):
            if n not in seen:
                seen.add(n)
                queue.append(n)
    return len(seen) == len(region)


def shared_walk(a, b, floor):
    """One route from a over the whole floor, extended to end on b. A walks its front part and B
    walks its back part in reverse, cut where the longer of the two parts is shortest."""
    commands = best_route(a, floor - {b}, floor)
    end = positions(a, commands)[-1]
    if end != b:
        commands += ''.join(go for go, _ in shortest_path(end, b, floor))
    cells = positions(a, commands)
    n = len(commands)
    first, last = {}, {}
    for k, cell in enumerate(cells):
        first.setdefault(cell, k)
        last[cell] = k
    starts_at = [[] for _ in range(n + 1)]
    for cell, k in first.items():
        starts_at[k].append(cell)
    # need[i]: the latest index where B's part may begin if A's part ends at index i
    need, latest = [0] * (n + 1), n
    for i in range(n, -1, -1):
        need[i] = latest
        latest = min([latest] + [last[cell] for cell in starts_at[i]])
    i = min(range(n + 1), key=lambda i: (max(i, n - need[i]), i + n - need[i]))
    j = need[i]
    return commands[:i], ''.join(BACK[go] for go in reversed(commands[j:]))