"""
Python basics and search algorithms
===================================

This single file is a small, beginner-friendly reference for:
1. Basic Python, NumPy, and pandas
2. UCS, BFS, and DFS search
3. Greedy Best-First Search and A*

Run this file with:
    python python_and_search_algorithms.py

The examples use fixed values so the file can run without waiting for input.
An input() example is included in basic_python_demo().
"""

from __future__ import annotations

from collections import deque
import heapq
from statistics import mean, median


def basic_python_demo() -> None:
    """Show common Python ideas with simple examples."""
    print("\n" + "=" * 60)
    print("1. BASIC PYTHON")
    print("=" * 60)

    # -------------------- Data types --------------------
    age = 20                       # int: a whole number
    height = 1.75                   # float: a decimal number
    name = "Amina"                 # str: text
    is_student = True              # bool: True or False
    nothing = None                 # None: no value

    print("\nData types:")
    print(age, type(age))
    print(height, type(height))
    print(name, type(name))
    print(is_student, type(is_student))
    print(nothing, type(nothing))

    # Collections: list, tuple, set, and dictionary
    scores = [80, 95, 72, 88]                  # mutable ordered collection
    coordinates = (10, 20)                    # immutable ordered collection
    unique_numbers = {1, 2, 2, 3}             # duplicate values disappear
    student = {"name": name, "age": age}      # key-value pairs

    print("\nCollections:")
    print("List:", scores)
    print("Tuple:", coordinates)
    print("Set:", unique_numbers)
    print("Dictionary:", student)

    # -------------------- Output and input --------------------
    print("\nOutput:")
    print(f"{name} has an average score of {mean(scores):.2f}.")

    # This is the normal way to read text from a user:
    # user_name = input("What is your name? ")
    # print("Hello,", user_name)
    #
    # The line is commented out so this teaching file can run automatically.
    sample_input = "  python  "
    print("Input example after strip and upper:", sample_input.strip().upper())

    # -------------------- Conditions --------------------
    print("\nConditional statements:")
    if mean(scores) >= 80:
        print("The student is doing very well.")
    elif mean(scores) >= 50:
        print("The student passed.")
    else:
        print("The student needs more practice.")

    # -------------------- Loops and filtering --------------------
    print("\nLoops and filtering:")
    for score in scores:
        print("Score:", score)

    # A list comprehension creates a new list in one readable line.
    passed_scores = [score for score in scores if score >= 80]
    print("Scores >= 80:", passed_scores)

    # -------------------- Functions --------------------
    def square(number: float) -> float:
        """Return the square of a number."""
        return number * number

    def average(values: list[float]) -> float:
        """Return the arithmetic mean of a non-empty list."""
        if not values:
            raise ValueError("average() needs at least one value")
        return sum(values) / len(values)

    print("\nFunctions:")
    print("square(5) =", square(5))
    print("average(scores) =", average(scores))
    print("statistics.mean(scores) =", mean(scores))
    print("statistics.median(scores) =", median(scores))

    # -------------------- Class, methods, and objects --------------------
    class Student:
        """A simple class that stores a student's data."""

        def __init__(self, student_name: str, student_scores: list[float]) -> None:
            self.name = student_name       # attribute
            self.scores = student_scores   # attribute

        def get_average(self) -> float:
            """A method that calculates this student's average."""
            return average(self.scores)

        def describe(self) -> str:
            """A method that returns a sentence about the object."""
            return f"{self.name} has an average of {self.get_average():.2f}."

    # student_one is an object created from the Student class.
    student_one = Student("Amina", [80, 95, 72, 88])
    print("\nClass and object:")
    print("Object attribute name:", student_one.name)
    print("Object attribute scores:", student_one.scores)
    print("Calling a method:", student_one.describe())

    # -------------------- NumPy and pandas --------------------
    print("\nNumPy and pandas:")
    try:
        import numpy as np
        import pandas as pd
    except ImportError:
        print("NumPy/pandas are not installed in this Python environment.")
        print("Install them with: python -m pip install numpy pandas")
        return

    # NumPy arrays are useful for fast numerical operations.
    numbers = np.array([10, 20, 30, 40])
    print("NumPy array:", numbers)
    print("Array multiplied by 2:", numbers * 2)
    print("NumPy mean:", numbers.mean())
    print("NumPy median:", np.median(numbers))

    # A DataFrame is a table with rows and named columns.
    data = {
        "name": ["Amina", "Bilal", "Chloe", "David"],
        "age": [20, 22, 19, 21],
        "score": [88, 75, 95, 60],
    }
    frame = pd.DataFrame(data)
    print("\nComplete DataFrame:")
    print(frame)

    # Select one column, one row, and one specific cell.
    print("\nOnly the score column:")
    print(frame["score"])
    print("\nFirst row with iloc:")
    print(frame.iloc[0])
    print("\nSpecific value (row 1, score column):")
    print(frame.loc[1, "score"])

    # Conditions in a DataFrame return only matching rows.
    high_scores = frame[frame["score"] >= 80]
    adults_with_high_scores = frame[(frame["age"] >= 20) & (frame["score"] >= 80)]
    print("\nStudents with score >= 80:")
    print(high_scores)
    print("\nStudents age >= 20 and score >= 80:")
    print(adults_with_high_scores)


# A graph is represented as: node -> [(neighbor, cost), ...].
WeightedGraph = dict[str, list[tuple[str, float]]]


def ucs(graph: WeightedGraph, start: str, goal: str) -> tuple[list[str], float]:
    """Uniform Cost Search: find the least-cost path in a weighted graph."""
    queue: list[tuple[float, str, list[str]]] = [(0, start, [start])]
    best_cost: dict[str, float] = {start: 0}

    while queue:
        cost, node, path = heapq.heappop(queue)
        if node == goal:
            return path, cost
        if cost > best_cost.get(node, float("inf")):
            continue

        for neighbor, edge_cost in graph.get(node, []):
            new_cost = cost + edge_cost
            if new_cost < best_cost.get(neighbor, float("inf")):
                best_cost[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor, path + [neighbor]))

    return [], float("inf")


def bfs(graph: WeightedGraph, start: str, goal: str) -> list[str]:
    """Breadth-First Search: find a path with the fewest edges."""
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path

        for neighbor, _ in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return []


def dfs(graph: WeightedGraph, start: str, goal: str) -> list[str]:
    """Depth-First Search: explore one branch deeply before another."""
    stack = [(start, [start])]
    visited: set[str] = set()

    while stack:
        node, path = stack.pop()
        if node in visited:
            continue
        visited.add(node)

        if node == goal:
            return path

        # Reverse keeps the example's left-to-right order predictable.
        for neighbor, _ in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append((neighbor, path + [neighbor]))

    return []


def heuristic(node: str, goal: str) -> float:
    """An example heuristic: estimated remaining cost.

    A real heuristic uses problem knowledge, such as straight-line distance.
    Here, the values are hand-written only to keep the example easy to read.
    """
    estimates = {
        "A": 7,
        "B": 6,
        "C": 2,
        "D": 3,
        "E": 1,
        "F": 0,
    }
    return estimates.get(node, 0) if node != goal else 0


def greedy_best_first(
    graph: WeightedGraph, start: str, goal: str
) -> tuple[list[str], float]:
    """Greedy Best-First Search: choose the smallest h(n) first."""
    queue: list[tuple[float, float, str, list[str]]] = [
        (heuristic(start, goal), 0, start, [start])
    ]
    visited: set[str] = set()

    while queue:
        _, cost, node, path = heapq.heappop(queue)
        if node in visited:
            continue
        visited.add(node)
        if node == goal:
            return path, cost

        for neighbor, edge_cost in graph.get(node, []):
            if neighbor not in visited:
                heapq.heappush(
                    queue,
                    (
                        heuristic(neighbor, goal),
                        cost + edge_cost,
                        neighbor,
                        path + [neighbor],
                    ),
                )

    return [], float("inf")


def a_star(graph: WeightedGraph, start: str, goal: str) -> tuple[list[str], float]:
    """A*: choose the smallest f(n) = g(n) + h(n)."""
    queue: list[tuple[float, float, str, list[str]]] = [
        (heuristic(start, goal), 0, start, [start])
    ]
    best_cost: dict[str, float] = {start: 0}

    while queue:
        _, cost, node, path = heapq.heappop(queue)
        if node == goal:
            return path, cost
        if cost > best_cost.get(node, float("inf")):
            continue

        for neighbor, edge_cost in graph.get(node, []):
            new_cost = cost + edge_cost
            if new_cost < best_cost.get(neighbor, float("inf")):
                best_cost[neighbor] = new_cost
                estimated_total = new_cost + heuristic(neighbor, goal)
                heapq.heappush(
                    queue,
                    (estimated_total, new_cost, neighbor, path + [neighbor]),
                )

    return [], float("inf")


def search_algorithms_demo() -> None:
    """Run all search algorithms on the same small graph."""
    print("\n" + "=" * 60)
    print("2. UCS, BFS, DFS, GREEDY BEST-FIRST, AND A*")
    print("=" * 60)

    graph: WeightedGraph = {
        "A": [("B", 2), ("C", 5)],
        "B": [("D", 4), ("E", 10)],
        "C": [("E", 1)],
        "D": [("F", 3)],
        "E": [("F", 2)],
        "F": [],
    }

    print("\nGraph edges:")
    for node, edges in graph.items():
        print(f"{node} -> {edges}")

    path, cost = ucs(graph, "A", "F")
    print("\nUCS:", path, "cost =", cost)
    print("BFS:", bfs(graph, "A", "F"), "(fewest edges, ignores costs)")
    print("DFS:", dfs(graph, "A", "F"), "(first deep path found)")

    greedy_path, greedy_cost = greedy_best_first(graph, "A", "F")
    a_star_path, a_star_cost = a_star(graph, "A", "F")
    print("Greedy Best-First:", greedy_path, "cost =", greedy_cost)
    print("A*:", a_star_path, "cost =", a_star_cost)

    print("\nComparison:")
    print("- UCS uses g(n), the cost already travelled. It finds an optimal path.")
    print("- BFS uses depth. It is optimal only when every edge has equal cost.")
    print("- DFS uses depth-first exploration. It may find a non-optimal path.")
    print("- Greedy uses h(n), the estimated distance to the goal. It can be fast")
    print("  but is not always optimal.")
    print("- A* uses g(n) + h(n). With a good admissible heuristic, it is both")
    print("  efficient and optimal.")


def main() -> None:
    basic_python_demo()
    search_algorithms_demo()


if __name__ == "__main__":
    main()