"""Helpers shared by the dirty-room robot solutions.

Room strings use '#' for walls, '*' for the start (no dirt) and '1'..'5' for dirt.
"""

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


def parse(room):
    """Return (start, dirt) where dirt maps every floor cell to its dirt (0 for the start)."""
    start, dirt = None, {}
    for r, row in enumerate(room):
        for c, ch in enumerate(row):
            if ch == '#':
                continue
            if ch == '*':
                start = (r, c)
            dirt[(r, c)] = int(ch) if ch.isdigit() else 0
    return start, dirt


def neighbours(cell, allowed):
    """Yield (neighbour, command to go there, command to come back) for neighbours in allowed."""
    r, c = cell
    for dr, dc, go, back in MOVES:
        n = (r + dr, c + dc)
        if n in allowed:
            yield n, go, back


def walk(start, allowed):
    """Depth-first walk over the cells of `allowed` connected to start, without recursion.

    Returns (moves, order). `order` lists (cell, i) in first-visit order, where i is the
    number of moves made when the robot first stands on the cell.
    """
    seen = {start}
    moves, order, trail = [], [(start, 0)], []
    cell = start
    while True:
        for n, go, back in neighbours(cell, allowed):
            if n not in seen:
                seen.add(n)
                moves.append(go)
                trail.append((back, cell))
                cell = n
                order.append((cell, len(moves)))
                break
        else:                                   # no new neighbour: retrace one step
            if not trail:
                return moves, order
            back, cell = trail.pop()
            moves.append(back)


def take_all_route(start, cells):
    """Route that enters every cell of the connected set `cells`, ending at the last new cell."""
    moves, order = walk(start, cells)
    return ''.join(moves[:order[-1][1]])


def route_with_cleaning(moves, order, chosen):
    """Add 'C' when the robot first stands on a chosen cell; drop the moves after the last 'C'."""
    clean_at = {i for cell, i in order if cell in chosen}
    out, end = [], 0
    for i in range(len(moves) + 1):
        if i in clean_at:
            out.append('C')
            end = len(out)
        if i < len(moves):
            out.append(moves[i])
    return ''.join(out[:end])


def best_subset(weights, capacity):
    """Choose weights with the largest sum that fits capacity. Returns (sum, chosen indices).

    Bit s of reach[i] is set when some of the first i weights add up to exactly s.
    """
    limit = min(capacity, sum(weights))
    mask = (1 << (limit + 1)) - 1
    reach = [1]
    for w in weights:
        reach.append(reach[-1] | ((reach[-1] << w) & mask))
    best = reach[-1].bit_length() - 1
    chosen, s = [], best
    for i in range(len(weights), 0, -1):
        if not (reach[i - 1] >> s) & 1:         # s can't be made without weight i-1
            chosen.append(i - 1)
            s -= weights[i - 1]
    return best, chosen