"""Take all, exact: searches every connected set that could beat the fast answer.

Guaranteed best, but the search can take exponential time when the fast answer isn't proven.
"""
import sys

from dirt_common import neighbours, parse, take_all_route
from take_all_fast import best_connected_set


def best_connected_set_exact(start, dirt, capacity):
    best, best_cells, upper = best_connected_set(start, dirt, capacity)
    if best == upper:
        return best, best_cells
    sys.setrecursionlimit(max(sys.getrecursionlimit(), 3 * len(dirt) + 100))

    # 'in' = in the set, 'edge' = next to the set and undecided, 'out' = never take; absent = untouched
    status = {cell: 'out' for cell, d in dirt.items() if d > capacity}
    status[start] = 'in'
    taken = [start]
    first_edge = []
    for n, _, _ in neighbours(start, dirt):
        if n not in status:
            status[n] = 'edge'
            first_edge.append(n)
    available = sum(d for cell, d in dirt.items() if status.get(cell) != 'out')

    def search(edge, total, available):
        """Each connected set is reached exactly once: pick an edge cell, then take it or ban it."""
        nonlocal best, best_cells
        if total > best:
            best, best_cells = total, set(taken)
        if best == upper or not edge or total + available <= best:
            return
        v, rest = edge[-1], edge[:-1]
        if total + dirt[v] <= capacity:         # branch 1: take v
            status[v] = 'in'
            taken.append(v)
            added = [n for n, _, _ in neighbours(v, dirt) if n not in status]
            for n in added:
                status[n] = 'edge'
            search(rest + added, total + dirt[v], available - dirt[v])
            for n in added:
                del status[n]
            taken.pop()
        status[v] = 'out'                       # branch 2: never take v
        search(rest, total, available - dirt[v])
        status[v] = 'edge'

    search(first_edge, 0, available)
    return best, best_cells


def solution(room, capacity):
    start, dirt = parse(room)
    _, cells = best_connected_set_exact(start, dirt, capacity)
    return take_all_route(start, cells)