"""Part 4: the cleaning robot in a room that wraps around.

The room is given as strings, as in Part 1, but there is no wall round the edge: walking off the
right edge brings the robot back on the left, and off the bottom back on the top. '#' is
furniture, '.' floor and '*' the start. The commands are still '^ v < >', and on a torus they
mean the same thing everywhere, so Part 1's walk works unchanged once its neighbours wrap.
"""
from surface import depth_first, torus

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


def solution(room):
    """Part 1's walk with wrapped neighbours: 2 * (fields - 1) commands."""
    s, start = torus(room)
    return depth_first(s, start)


def wrapped(cell, d, R, C):
    return (cell[0] + STEP[d][0]) % R, (cell[1] + STEP[d][1]) % C


def random_room(rng, R, C, furniture):
    """Random furniture on an R x C torus, with every floor field reachable from the start."""
    grid = [['#' if rng.random() < furniture else '.' for _ in range(C)] for _ in range(R)]
    cells = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == '.']
    if not cells:
        grid[0][0] = '.'
        cells = [(0, 0)]
    start = rng.choice(cells)
    reach, todo = {start}, [start]
    while todo:
        cell = todo.pop()
        for d in STEP:
            n = wrapped(cell, d, R, C)
            if grid[n[0]][n[1]] == '.' and n not in reach:
                reach.add(n)
                todo.append(n)
    for r, c in cells:
        if (r, c) not in reach:
            grid[r][c] = '#'
    grid[start[0]][start[1]] = '*'
    return [''.join(row) for row in grid]


class Robot:
    """A robot on a real torus. The solutions only get its move and on_dock methods.

    move(d) steps one field and returns True, or bumps into furniture, stays put and returns
    False. on_dock() says whether the robot stands on the field it started on. Past `limit`
    calls to move it raises, so a robot that would walk forever is caught.
    """

    def __init__(self, room, limit=50_000):
        self._room = room
        self._R, self._C = len(room), len(room[0])
        self._dock = next((r, c) for r, row in enumerate(room) for c, ch in enumerate(row) if ch == '*')
        self._pos = self._dock
        self._limit = limit
        self.moves = self.bumps = 0
        self.cleaned = {self._pos}
        self.log = []

    def move(self, d):
        if self.moves + self.bumps >= self._limit:
            raise RuntimeError(f'more than {self._limit:,} move calls')
        n = wrapped(self._pos, d, self._R, self._C)
        ok = self._room[n[0]][n[1]] != '#'
        self.log.append((d, ok))
        if not ok:
            self.bumps += 1
            return False
        self._pos = n
        self.moves += 1
        self.cleaned.add(n)
        return True

    def on_dock(self):
        return self._pos == self._dock


def floor(room):
    return {(r, c) for r, row in enumerate(room) for c, ch in enumerate(row) if ch != '#'}