"""Emptying the bag, exact: a 0-1 breadth-first search over (field, cleaned fields, bag load).

Moves cost 1 and 'C' costs 0. Only practical for tiny rooms (about 9 dirty fields).
"""
from collections import deque

from dirt_common import neighbours, parse


def solution(room, capacity, pick):
    dock, dirt = parse(room)
    fields = [f for f in sorted(dirt) if dirt[f] > 0]
    bit = {f: 1 << i for i, f in enumerate(fields)}
    full = (1 << len(fields)) - 1

    first = (dock, 0, 0)
    cost, parent = {first: 0}, {first: None}
    queue = deque([first])

    def relax(state, new_cost, command, now):
        if new_cost < cost.get(state, new_cost + 1):
            cost[state], parent[state] = new_cost, (current, command)
            queue.appendleft(state) if now else queue.append(state)

    while queue:
        current = queue.popleft()
        pos, mask, load = current
        if mask == full:
            return rebuild(parent, current)
        c = cost[current]
        if pick and pos in bit and not mask & bit[pos] and load + dirt[pos] <= capacity:
            relax((pos, mask | bit[pos], load + dirt[pos]), c, 'C', True)
        for n, go, _ in neighbours(pos, dirt):
            new_mask, new_load = mask, load
            if n == dock:
                new_load = 0
            elif not pick and not mask & bit[n]:
                if load + dirt[n] > capacity:
                    continue
                new_mask, new_load = mask | bit[n], load + dirt[n]
            relax((n, new_mask, new_load), c + 1, go, False)
    raise ValueError('no plan cleans every field')


def rebuild(parent, state):
    out = []
    while parent[state]:
        state, command = parent[state]
        out.append(command)
    return ''.join(reversed(out))