"""Part 6: the cleaning robot on the walls of a box.

A pool robot cleans the floor and then drives up the walls; a window robot crosses from one pane
to the next round the corner of a building. Here the room is the surface of a box, cut into
square fields, and the robot drives over the edges from one face to the next as if they weren't
there. Every field still has four neighbours, and at almost every corner four fields meet, as on
a flat floor. Only at the box's own eight corners do three meet, and that is enough to change
what the robot's directions mean.

The robot's commands are its own directions, as in Part 5, and it carries them over the edges
without turning. Near a corner of the box that has a surprising effect: "forward k fields, turn
left" closes a loop after three turns instead of four.
"""
from group_dsu import TURNS, GroupDSU, turn_across
from surface import DIRS, box, depth_first, frames_reachable, move


def solution(a, b, c, open_top=False, blocked=()):
    """Part 1's walk on the walls of the box: 2(N - 1) commands."""
    s = box(a, b, c, open_top, blocked)
    return depth_first(s, s.floor[0])


LEFT_OF = {'^': '<', '<': 'v', 'v': '>', '>': '^'}


def square_loop(surface, start, k, heading='^', frame=(0, False), most=8):
    """Drive k fields, turn left, and repeat. The robot has no turn command, so 'turn left' is
    'use the next direction anticlockwise'. Returns the number of straight stretches driven
    when it is first back on its starting field, and its frame then, or None after `most`."""
    field = start
    for stretch in range(1, most + 1):
        for _ in range(k):
            step = move(surface, field, frame, heading)
            if step is None:
                return None
            field, frame = step
        if field == start:
            return stretch, frame
        heading = LEFT_OF[heading]
    return None


def turns_on_loops(surface, start):
    """The quarter turns the robot can come home with, found with union-find: join every pair of
    neighbouring fields, labelled with the turn the frame makes crossing between them. A loop's
    leftover is its turn. Returns the set of turns the loops produce, closed under adding."""
    dsu = GroupDSU(*TURNS)
    floor = sorted({f for f, _ in frames_reachable(surface, start)})
    for f in floor:
        dsu.add(f)
    found = {0}
    for f in floor:
        for side in range(4):
            g = surface.glue[f][side]
            if g is not None and f < g[0]:
                kind, left = dsu.union(f, g[0], turn_across(surface, f, side))
                if kind == 'loop':
                    found.add(left)
    closed = set(found)
    while True:
        more = {(x + y) % 4 for x in closed for y in closed} - closed
        if not more:
            return closed
        closed |= more


def corner_fields(surface, corner):
    """The fields that have `corner` (a 3D point) as one of their corners."""
    return [f for f in surface.floor if corner in surface.corners[f]]


def direction_from(surface, f, g, frame):
    """The robot's command that takes it from f to neighbour g, in the given frame."""
    for d in DIRS:
        step = move(surface, f, frame, d)
        if step is not None and step[0] == g:
            return d
    return None