from dataclasses import dataclass
from typing import FrozenSet, Set, Tuple, List, Optional
from collections import deque


@dataclass(frozen=True)
class Action:
    name: str
    preconditions: FrozenSet[str]
    add_list: FrozenSet[str]
    delete_list: FrozenSet[str]

    def is_applicable(self, state: FrozenSet[str]) -> bool:
        return self.preconditions.issubset(state)

    def apply(self, state: FrozenSet[str]) -> FrozenSet[str]:
        return (state - self.delete_list) | self.add_list


def strips_plan(
    initial_state: FrozenSet[str],
    goal: FrozenSet[str],
    actions: List[Action],
) -> Optional[List[str]]:
    """Breadth-first forward planning: shortest plan in action count."""
    if goal.issubset(initial_state):
        return []

    frontier = deque([(initial_state, [])])
    visited = {initial_state}
    while frontier:
        state, plan = frontier.popleft()
        for action in actions:
            if not action.is_applicable(state):
                continue
            next_state = action.apply(state)
            if next_state in visited:
                continue
            next_plan = plan + [action.name]
            if goal.issubset(next_state):
                return next_plan
            visited.add(next_state)
            frontier.append((next_state, next_plan))
    return None
