#!/usr/bin/env python3
"""A* path validation and comparison utility.

This script is a practical companion to articles about A* search in weighted graphs.
It:
  - validates graph and heuristic assumptions
  - computes an A* shortest path
  - optionally compares the result to Dijkstra's algorithm
  - supports simple JSON input for operational testing

Supported graph format
----------------------
Use a JSON object with these keys:

{
  "start": "A",
  "goal": "G",
  "edges": {
    "A": {"B": 2, "C": 4},
    "B": {"D": 7},
    "C": {"D": 1},
    "D": {"G": 3},
    "G": {}
  },
  "heuristic": {
    "A": 6,
    "B": 5,
    "C": 2,
    "D": 3,
    "G": 0
  }
}

Notes
-----
- Edge weights must be non-negative for A* optimality guarantees.
- The heuristic should be admissible: it must not overestimate the true remaining cost.
- If a heuristic is missing for a node, the script treats it as 0 by default.

Example usage
-------------
  python a_star_path_validation.py --input graph.json
  python a_star_path_validation.py --input graph.json --show-expanded
  python a_star_path_validation.py --input graph.json --skip-dijkstra-check
"""

from __future__ import annotations

import argparse
import json
import math
import heapq
from dataclasses import dataclass
from typing import Any, Dict, List, Optional, Tuple


Graph = Dict[str, Dict[str, float]]
Heuristic = Dict[str, float]


@dataclass
class PathResult:
    path: List[str]
    cost: float
    expanded_nodes: int


def load_problem(path: str) -> Tuple[str, str, Graph, Heuristic]:
    with open(path, "r", encoding="utf-8") as f:
        data = json.load(f)

    if not isinstance(data, dict):
        raise ValueError("Input JSON must be an object.")

    try:
        start = data["start"]
        goal = data["goal"]
        edges = data["edges"]
    except KeyError as exc:
        raise ValueError(f"Missing required key: {exc.args[0]}") from exc

    if not isinstance(start, str) or not start:
        raise ValueError("'start' must be a non-empty string.")
    if not isinstance(goal, str) or not goal:
        raise ValueError("'goal' must be a non-empty string.")
    if not isinstance(edges, dict):
        raise ValueError("'edges' must be an object mapping nodes to neighbors.")

    heuristic = data.get("heuristic", {})
    if heuristic is None:
        heuristic = {}
    if not isinstance(heuristic, dict):
        raise ValueError("'heuristic' must be an object mapping nodes to numeric values.")

    normalized_edges: Graph = {}
    for node, neighbors in edges.items():
        if not isinstance(node, str) or not node:
            raise ValueError("All node names in 'edges' must be non-empty strings.")
        if not isinstance(neighbors, dict):
            raise ValueError(f"Neighbors for node '{node}' must be an object.")

        normalized_edges[node] = {}
        for nbr, weight in neighbors.items():
            if not isinstance(nbr, str) or not nbr:
                raise ValueError(f"Neighbor names for node '{node}' must be non-empty strings.")
            if not isinstance(weight, (int, float)):
                raise ValueError(f"Edge weight {node} -> {nbr} must be numeric.")
            if math.isnan(weight) or math.isinf(weight):
                raise ValueError(f"Edge weight {node} -> {nbr} must be finite.")
            if weight < 0:
                raise ValueError(f"Negative edge weight detected: {node} -> {nbr} = {weight}")
            normalized_edges[node][nbr] = float(weight)

    normalized_heuristic: Heuristic = {}
    for node, value in heuristic.items():
        if not isinstance(node, str) or not node:
            raise ValueError("All node names in 'heuristic' must be non-empty strings.")
        if not isinstance(value, (int, float)):
            raise ValueError(f"Heuristic for node '{node}' must be numeric.")
        if math.isnan(value) or math.isinf(value):
            raise ValueError(f"Heuristic for node '{node}' must be finite.")
        normalized_heuristic[node] = float(value)

    if start not in normalized_edges:
        normalized_edges.setdefault(start, {})
    if goal not in normalized_edges:
        normalized_edges.setdefault(goal, {})

    return start, goal, normalized_edges, normalized_heuristic


def reconstruct_path(came_from: Dict[str, Optional[str]], current: str) -> List[str]:
    path = [current]
    while came_from[current] is not None:
        current = came_from[current]  # type: ignore[assignment]
        path.append(current)
    path.reverse()
    return path


def dijkstra(start: str, goal: str, graph: Graph) -> PathResult:
    frontier: List[Tuple[float, str]] = [(0.0, start)]
    best_g: Dict[str, float] = {start: 0.0}
    came_from: Dict[str, Optional[str]] = {start: None}
    expanded = 0

    while frontier:
        current_cost, current = heapq.heappop(frontier)
        if current_cost > best_g.get(current, math.inf):
            continue
        expanded += 1
        if current == goal:
            return PathResult(reconstruct_path(came_from, current), current_cost, expanded)

        for neighbor, weight in graph.get(current, {}).items():
            tentative = current_cost + weight
            if tentative < best_g.get(neighbor, math.inf):
                best_g[neighbor] = tentative
                came_from[neighbor] = current
                heapq.heappush(frontier, (tentative, neighbor))

    return PathResult([], math.inf, expanded)


def a_star(start: str, goal: str, graph: Graph, heuristic: Heuristic) -> PathResult:
    def h(node: str) -> float:
        return heuristic.get(node, 0.0)

    frontier: List[Tuple[float, float, str]] = [(h(start), 0.0, start)]
    best_g: Dict[str, float] = {start: 0.0}
    came_from: Dict[str, Optional[str]] = {start: None}
    expanded = 0

    while frontier:
        f_score, current_g, current = heapq.heappop(frontier)
        if current_g > best_g.get(current, math.inf):
            continue
        expanded += 1

        if current == goal:
            return PathResult(reconstruct_path(came_from, current), current_g, expanded)

        for neighbor, weight in graph.get(current, {}).items():
            tentative_g = current_g + weight
            if tentative_g < best_g.get(neighbor, math.inf):
                best_g[neighbor] = tentative_g
                came_from[neighbor] = current
                tentative_f = tentative_g + h(neighbor)
                heapq.heappush(frontier, (tentative_f, tentative_g, neighbor))

    return PathResult([], math.inf, expanded)


def validate_admissibility(graph: Graph, heuristic: Heuristic, goal: str) -> List[str]:
    """Check heuristic values against true shortest-path costs to the goal.

    This is a verification helper, not a runtime requirement for A*.
    It uses Dijkstra from each node to the goal in the reversed graph by
    simply computing all-pairs from node to goal via forward edges on a
    generated reverse graph.
    """
    reverse_graph: Graph = {}
    for src, neighbors in graph.items():
        reverse_graph.setdefault(src, {})
        for dst, weight in neighbors.items():
            reverse_graph.setdefault(dst, {})
            reverse_graph[dst][src] = weight

    violations: List[str] = []

    # Run Dijkstra on the reverse graph from the goal to obtain true costs to goal.
    true_costs: Dict[str, float] = {goal: 0.0}
    frontier: List[Tuple[float, str]] = [(0.0, goal)]
    while frontier:
        cost, node = heapq.heappop(frontier)
        if cost > true_costs.get(node, math.inf):
            continue
        for prev, weight in reverse_graph.get(node, {}).items():
            tentative = cost + weight
            if tentative < true_costs.get(prev, math.inf):
                true_costs[prev] = tentative
                heapq.heappush(frontier, (tentative, prev))

    for node, h_value in heuristic.items():
        true_cost = true_costs.get(node, math.inf)
        if h_value > true_cost:
            violations.append(
                f"Heuristic overestimates at node '{node}': h={h_value} > true_cost_to_goal={true_cost}"
            )

    return violations


def format_path(path: List[str]) -> str:
    return " -> ".join(path) if path else "<no path found>"


def main() -> int:
    parser = argparse.ArgumentParser(
        description="Validate and compare A* pathfinding on a weighted graph."
    )
    parser.add_argument("--input", required=True, help="Path to a JSON graph description.")
    parser.add_argument(
        "--show-expanded",
        action="store_true",
        help="Print how many nodes each algorithm expanded.",
    )
    parser.add_argument(
        "--skip-dijkstra-check",
        action="store_true",
        help="Skip the baseline Dijkstra comparison.",
    )
    parser.add_argument(
        "--skip-admissibility-check",
        action="store_true",
        help="Skip heuristic admissibility verification.",
    )
    args = parser.parse_args()

    start, goal, graph, heuristic = load_problem(args.input)

    astar_result = a_star(start, goal, graph, heuristic)
    print("A* result:")
    print(f"  path: {format_path(astar_result.path)}")
    print(f"  cost: {astar_result.cost}")
    if args.show_expanded:
        print(f"  expanded_nodes: {astar_result.expanded_nodes}")

    if not args.skip_admissibility_check:
        violations = validate_admissibility(graph, heuristic, goal)
        if violations:
            print("\nHeuristic admissibility check: FAILED")
            for item in violations:
                print(f"  - {item}")
        else:
            print("\nHeuristic admissibility check: PASSED")

    if not args.skip_dijkstra_check:
        dijkstra_result = dijkstra(start, goal, graph)
        print("\nDijkstra baseline:")
        print(f"  path: {format_path(dijkstra_result.path)}")
        print(f"  cost: {dijkstra_result.cost}")
        if args.show_expanded:
            print(f"  expanded_nodes: {dijkstra_result.expanded_nodes}")

        if math.isfinite(astar_result.cost) and math.isfinite(dijkstra_result.cost):
            if abs(astar_result.cost - dijkstra_result.cost) < 1e-9:
                print("\nComparison: A* matches Dijkstra on path cost.")
            else:
                print("\nComparison: A* DOES NOT match Dijkstra on path cost.")
        elif astar_result.cost == dijkstra_result.cost:
            print("\nComparison: both algorithms found no path.")
        else:
            print("\nComparison: results differ in reachability.")

    return 0


if __name__ == "__main__":
    raise SystemExit(main())