import heapq
from dataclasses import dataclass, field
from typing import Callable, Dict, List, Tuple, Optional

State = Tuple[int, int]  # (row, col) for a grid; generalize as needed

@dataclass(order=True)
class _Entry:
    priority: float
    counter: int
    state: State = field(compare=False)


def astar(
    start: State,
    goal: State,
    neighbors_fn: Callable[[State], List[Tuple[State, float]]],
    heuristic_fn: Callable[[State, State], float],
) -> Optional[Tuple[List[State], float]]:
    """Generic A* search.

    neighbors_fn(state) -> list of (next_state, step_cost)
    heuristic_fn(state, goal) -> admissible estimate of remaining cost

    Returns (path, total_cost) or None if no path exists.
    """
    counter = 0
    open_set: List[_Entry] = []
    start_h = heuristic_fn(start, goal)
    heapq.heappush(open_set, _Entry(start_h, counter, start))

    g_score: Dict[State, float] = {start: 0.0}
    came_from: Dict[State, State] = {}
    closed: set = set()

    while open_set:
        entry = heapq.heappop(open_set)
        current = entry.state

        if current in closed:
            continue
        if current == goal:
            path = _reconstruct_path(came_from, current)
            return path, g_score[current]

        closed.add(current)

        for neighbor, step_cost in neighbors_fn(current):
            tentative_g = g_score[current] + step_cost
            if tentative_g < g_score.get(neighbor, float("inf")):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + heuristic_fn(neighbor, goal)
                counter += 1
                heapq.heappush(open_set, _Entry(f, counter, neighbor))

    return None


def _reconstruct_path(
    came_from: Dict[State, State], current: State
) -> List[State]:
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path
