"""The original cleaning robot puzzle (Part 1 of the blog post).

Room strings use '#' for walls, '.' for floor and '*' for the start. Commands are
'^' up, 'v' down, '<' left and '>' right. The robot must clean every floor field.
"""
import sys

DIRS = [(-1, 0, '^', 'v'), (1, 0, 'v', '^'), (0, -1, '<', '>'), (0, 1, '>', '<')]


def solution(room):
    """Step into every unvisited floor field, and step back when stuck. 2 * (fields - 1) commands."""
    sys.setrecursionlimit(10000)
    R, C = len(room), len(room[0])
    start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')

    seen = {start}
    moves = []

    def dfs(r, c):
        for dr, dc, go, back in DIRS:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                dfs(nr, nc)
                moves.append(back)   # step back to where we came from

    dfs(*start)
    return ''.join(moves)


def solution_trimmed(room):
    """The same walk without the final walk home, which the rules don't require."""
    sys.setrecursionlimit(10000)
    R, C = len(room), len(room[0])
    start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')

    seen = {start}
    moves = []
    last = 0   # length of moves right after the robot last reached a new field

    def dfs(r, c):
        nonlocal last
        for dr, dc, go, back in DIRS:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                last = len(moves)
                dfs(nr, nc)
                moves.append(back)

    dfs(*start)
    return ''.join(moves[:last])


def solution_iterative(room):
    """The same commands as `solution`, with an explicit trail instead of recursion."""
    R, C = len(room), len(room[0])
    start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')

    seen = {start}
    moves = []
    trail = []   # (command that undoes the step, field we came from)
    r, c = start
    while True:
        for dr, dc, go, back in DIRS:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                trail.append((back, r, c))
                r, c = nr, nc
                break
        else:                 # no new neighbour: retrace one step
            if not trail:
                break
            back, r, c = trail.pop()
            moves.append(back)
    return ''.join(moves)