"""Enumerate and count exact-duration workshop plans with topic separation."""
from functools import lru_cache


def _prepare(workshops, budget):
    # Workshop = (unique name, positive duration, available copies, topic).
    if not isinstance(budget, int) or not 0 <= budget <= 100:
        raise ValueError("budget must be an integer from 0 to 100")
    items = []
    names = set()
    for row in workshops:
        if len(row) != 4:
            raise ValueError("workshop requires name, duration, copies, topic")
        name, duration, copies, topic = row
        if (not isinstance(name, str) or not name or name in names
                or not isinstance(duration, int) or not 1 <= duration <= 100
                or not isinstance(copies, int) or copies < 0
                or not isinstance(topic, str) or not topic):
            raise ValueError("invalid or duplicate workshop")
        names.add(name)
        items.append(tuple(row))
    if len(items) > 6 or sum(item[2] for item in items) > 8:
        raise ValueError("at most 6 types and 8 total copies")
    return sorted(items)


def enumerate_plans(workshops, budget):
    items = _prepare(workshops, budget)
    counts = [item[2] for item in items]
    path, plans = [], []

    def search(remaining, previous_topic):
        if remaining == 0:
            plans.append(tuple(path))
            return
        if sum(counts[i] * item[1] for i, item in enumerate(items)) < remaining:
            return  # Even taking every remaining copy cannot fill the budget.
        for index, (name, duration, _, topic) in enumerate(items):
            if counts[index] == 0 or duration > remaining or topic == previous_topic:
                continue
            counts[index] -= 1
            path.append(name)
            search(remaining - duration, topic)
            path.pop()
            counts[index] += 1

    search(budget, None)
    return plans


def count_plans(workshops, budget):
    items = _prepare(workshops, budget)

    @lru_cache(maxsize=None)
    def count(remaining, counts, previous_topic):
        if remaining == 0:
            return 1
        if sum(counts[i] * item[1] for i, item in enumerate(items)) < remaining:
            return 0
        total = 0
        for index, (_, duration, _, topic) in enumerate(items):
            if counts[index] == 0 or duration > remaining or topic == previous_topic:
                continue
            following = list(counts)
            following[index] -= 1
            total += count(remaining - duration, tuple(following), topic)
        return total

    return count(budget, tuple(item[2] for item in items), None)


def plan_workshop(workshops, budget):
    # Materialize once so generator inputs work in both independent solvers.
    workshops = list(workshops)
    return {"count": count_plans(workshops, budget),
            "plans": enumerate_plans(workshops, budget)}