Capstone Project: Route Planner

class Graph:
    """An undirected, weighted map: towns connected by roads (weight = minutes)."""

    def __init__(self) -> None:
        self._adj: dict[str, list[tuple[str, int]]] = {}

    def add_town(self, name: str) -> None:
        self._adj.setdefault(name, [])

    def add_road(self, a: str, b: str, minutes: int) -> None:
        self.add_town(a)
        self.add_town(b)
        self._adj[a].append((b, minutes))   # roads run both ways
        self._adj[b].append((a, minutes))

    def towns(self) -> list[str]:
        return list(self._adj)

    def neighbors(self, town: str) -> list[tuple[str, int]]:
        return self._adj[town]

import heapq
from collections import deque

from graph import Graph


class RoutePlanner:
    """Answers routing questions about a Graph, each with the right algorithm."""

    def __init__(self, graph: Graph) -> None:
        self.graph = graph

    def reachable_from(self, start: str) -> set[str]:
        # BFS flood fill (Lesson 13): every town you can get to from "start"
        seen = {start}
        queue = deque([start])
        while queue:
            town = queue.popleft()
            for neighbor, _ in self.graph.neighbors(town):
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
        return seen

    def is_connected(self) -> bool:
        towns = self.graph.towns()
        return len(self.reachable_from(towns[0])) == len(towns)

    def fewest_stops(self, start: str, goal: str) -> list[str] | None:
        # BFS shortest path (Lesson 13): fewest legs, ignoring travel time
        parent = {start: None}
        queue = deque([start])
        while queue:
            town = queue.popleft()
            if town == goal:
                break
            for neighbor, _ in self.graph.neighbors(town):
                if neighbor not in parent:
                    parent[neighbor] = town
                    queue.append(neighbor)
        return self._rebuild_path(parent, goal)

    def fastest_route(self, start: str, goal: str) -> tuple[list[str] | None, float]:
        # Dijkstra (Lesson 20) with a min-heap (Lesson 9): fewest minutes
        distance = {town: float("inf") for town in self.graph.towns()}
        distance[start] = 0
        parent = {start: None}
        visited: set[str] = set()
        heap = [(0, start)]
        while heap:
            dist, town = heapq.heappop(heap)
            if town in visited:
                continue
            visited.add(town)
            for neighbor, minutes in self.graph.neighbors(town):
                if dist + minutes < distance[neighbor]:
                    distance[neighbor] = dist + minutes
                    parent[neighbor] = town
                    heapq.heappush(heap, (distance[neighbor], neighbor))
        return self._rebuild_path(parent, goal), distance[goal]

    def cheapest_network(self) -> tuple[list[tuple[str, str, int]], int]:
        # Kruskal's MST + union-find (Lesson 20): min roads to connect every town
        root = {town: town for town in self.graph.towns()}

        def find(x: str) -> str:
            while root[x] != x:
                root[x] = root[root[x]]   # path compression
                x = root[x]
            return x

        def union(a: str, b: str) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False              # already connected: this edge would form a cycle
            root[rb] = ra
            return True

        edges = set()
        for town in self.graph.towns():
            for neighbor, minutes in self.graph.neighbors(town):
                a, b = sorted((town, neighbor))
                edges.add((minutes, a, b))

        chosen: list[tuple[str, str, int]] = []
        total = 0
        for minutes, a, b in sorted(edges):   # cheapest road first
            if union(a, b):
                chosen.append((a, b, minutes))
                total += minutes
        return chosen, total

    @staticmethod
    def _rebuild_path(parent: dict[str, str | None], goal: str) -> list[str] | None:
        if goal not in parent:
            return None                   # goal was never reached
        path = []
        current = goal
        while current is not None:
            path.append(current)
            current = parent[current]
        return path[::-1]

from graph import Graph
from planner import RoutePlanner


def build_map() -> Graph:
    graph = Graph()
    roads = [
        ("A", "B", 7), ("A", "C", 9), ("A", "F", 14), ("B", "C", 10),
        ("B", "D", 15), ("C", "D", 11), ("C", "F", 2), ("D", "E", 6), ("E", "F", 9),
    ]
    for a, b, minutes in roads:
        graph.add_road(a, b, minutes)
    return graph


def main() -> None:
    planner = RoutePlanner(build_map())

    print("== ByteCode Route Planner ==")
    print("Towns:", ", ".join(sorted(planner.graph.towns())))
    print()

    reachable = planner.reachable_from("A")
    print("Reachable from A:", ", ".join(sorted(reachable)))
    print("Network connected:", planner.is_connected())
    print()

    stops = planner.fewest_stops("A", "F")
    legs = len(stops) - 1
    print(f"Fewest stops A -> F: {' -> '.join(stops)}  ({legs} leg{'s' if legs != 1 else ''})")

    route, minutes = planner.fastest_route("A", "F")
    print(f"Fastest route A -> F: {' -> '.join(route)}  ({minutes} min)")
    print("   the 2-leg detour beats the direct 14-min road!")
    print()

    network, cost = planner.cheapest_network()
    print("Cheapest network to connect every town:")
    for a, b, m in network:
        print(f"  {a} - {b}   {m} min")
    print(f"  total track: {cost} min")


if __name__ == "__main__":
    main()