from collections import deque
from dataclasses import dataclass, field
from typing import Any, Callable, List, Optional
import heapq


@dataclass
class Node:
    state: Any
    parent: Optional["Node"] = None
    action: Any = None
    path_cost: float = 0.0
    depth: int = 0


def build_path(node: Node) -> List[Any]:
    actions = []
    while node.parent is not None:
        actions.append(node.action)
        node = node.parent
    actions.reverse()
    return actions


def bfs(problem) -> Optional[List[Any]]:
    start = Node(problem.initial_state)
    if problem.goal_test(start.state):
        return build_path(start)
    frontier = deque([start])
    visited = {start.state}
    while frontier:
        node = frontier.popleft()
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            if child_state in visited:
                continue
            step_cost = problem.cost(node.state, action, child_state)
            child = Node(
                child_state, node, action,
                node.path_cost + step_cost, node.depth + 1,
            )
            if problem.goal_test(child_state):
                return build_path(child)
            visited.add(child_state)
            frontier.append(child)
    return None


def dfs_limited(problem, limit: int) -> Optional[List[Any]]:
    def recurse(node, depth_remaining, visited):
        if problem.goal_test(node.state):
            return build_path(node)
        if depth_remaining == 0:
            return None
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            if child_state in visited:
                continue
            step_cost = problem.cost(node.state, action, child_state)
            child = Node(
                child_state, node, action,
                node.path_cost + step_cost, node.depth + 1,
            )
            result = recurse(
                child, depth_remaining - 1, visited | {child_state}
            )
            if result is not None:
                return result
        return None

    start = Node(problem.initial_state)
    return recurse(start, limit, {start.state})


def iterative_deepening(problem, max_depth: int = 1000):
    for limit in range(max_depth + 1):
        result = dfs_limited(problem, limit)
        if result is not None:
            return result
    return None


def uniform_cost_search(problem) -> Optional[List[Any]]:
    counter = 0
    start = Node(problem.initial_state)
    frontier = [(0.0, counter, start)]
    best_cost = {start.state: 0.0}
    while frontier:
        cost, _, node = heapq.heappop(frontier)
        if cost > best_cost.get(node.state, float("inf")):
            continue
        if problem.goal_test(node.state):
            return build_path(node)
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            step_cost = problem.cost(node.state, action, child_state)
            new_cost = node.path_cost + step_cost
            if new_cost < best_cost.get(child_state, float("inf")):
                best_cost[child_state] = new_cost
                child = Node(
                    child_state, node, action, new_cost, node.depth + 1
                )
                counter += 1
                heapq.heappush(frontier, (new_cost, counter, child))
    return None
