def fib_recursive(n):
    """
    Computes F(n) by direct recursion.
    Time: O(phi^n) where phi ≈ 1.618  (exponential)
    Space: O(n) call stack depth
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib_recursive(n - 1) + fib_recursive(n - 2)

def fib_memo(n, memo=None):
    """
    Computes F(n) with memoisation — each subproblem solved once.
    Time: O(n)
    Space: O(n)
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

def fib_iterative(n):
    """
    Computes F(n) iteratively — best in practice.
    Time: O(n)
    Space: O(1)
    """
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

import time

def time_fib():
    n = 35
    
    # Iterative (fast)
    t0 = time.time()
    result = fib_iterative(n)
    t1 = time.time()
    print(f"Iterative  : F({n}) = {result}  |  time = {(t1-t0)*1000:.4f} ms")
    
    # Memoised (fast)
    t0 = time.time()
    result = fib_memo(n)
    t1 = time.time()
    print(f"Memoised   : F({n}) = {result}  |  time = {(t1-t0)*1000:.4f} ms")
    
    # Recursive (slow — try n=35 but NOT larger)
    t0 = time.time()
    result = fib_recursive(n)
    t1 = time.time()
    print(f"Recursive  : F({n}) = {result}  |  time = {(t1-t0)*1000:.4f} ms")

if __name__ == "__main__":
    print("First 10 Fibonacci numbers (iterative):")
    print([fib_iterative(i) for i in range(10)])
    print()
    time_fib()

def gcd(a, b):
    """
    Computes gcd(a, b) using Euclid's algorithm.
    Based on: gcd(a, b) = gcd(b, a mod b)
    Time: O(log(min(a, b))) divisions
    """
    while b != 0:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    """
    Returns (gcd, x, y) such that a*x + b*y = gcd(a, b).
    Useful for finding modular inverses.
    """
    if b == 0:
        return a, 1, 0
    d, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return d, x, y

def modular_inverse(a, N):
    """
    Returns x such that a*x ≡ 1 (mod N).
    Raises ValueError if inverse doesn't exist (gcd(a,N) != 1).
    """
    d, x, _ = extended_gcd(a, N)
    if d != 1:
        raise ValueError(f"Inverse of {a} mod {N} does not exist (gcd={d})")
    return x % N

if __name__ == "__main__":
    pairs = [(1071, 462), (840, 252), (17, 13), (100, 75)]
    
    for a, b in pairs:
        g = gcd(a, b)
        print(f"gcd({a}, {b}) = {g}")
    
    print()
    
    # Extended GCD
    a, b = 35, 15
    d, x, y = extended_gcd(a, b)
    print(f"Extended GCD: {a}*({x}) + {b}*({y}) = {d}")
    print(f"Verification: {a*x + b*y}")
    
    print()
    
    # Modular inverse
    a, N = 3, 7
    inv = modular_inverse(a, N)
    print(f"Inverse of {a} mod {N} = {inv}  (check: {a}*{inv} mod {N} = {(a*inv) % N})")

def mod_exp(base, exp, mod):
    """
    Computes base^exp mod mod using repeated squaring.
    Time: O(log exp) multiplications
    """
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:          # if exp is odd, multiply in current base
            result = (result * base) % mod
        exp //= 2                 # halve the exponent
        base = (base * base) % mod  # square the base
    return result

def is_prime_trial(n):
    """
    Tests primality by trial division up to sqrt(n).
    Time: O(sqrt(n)) = O(2^(n_bits/2)) — exponential in number of bits.
    Only practical for small n.
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

import random

def fermat_test(n, k=10):
    """
    Tests if n is probably prime using Fermat's Little Theorem.
    Performs k random tests. If any fails, n is definitely composite.
    If all pass, n is probably prime (may give false positives for Carmichael numbers).
    
    Time: O(k * log^2(n))
    """
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for _ in range(k):
        a = random.randint(2, n - 2)
        if mod_exp(a, n - 1, n) != 1:
            return False     # Definitely composite
    return True              # Probably prime

if __name__ == "__main__":
    # Test some small numbers
    test_numbers = [2, 3, 4, 5, 10, 13, 91, 97, 341, 561, 1009]
    
    print(f"{'n':>6}  {'Trial':>7}  {'Fermat':>7}")
    print("-" * 26)
    for n in test_numbers:
        trial = is_prime_trial(n)
        fermat = fermat_test(n, k=20)
        print(f"{n:>6}  {str(trial):>7}  {str(fermat):>7}")
    
    print()
    print("Note: 341 = 11 × 31 and 561 = 3 × 11 × 17 are Carmichael numbers.")
    print("The Fermat test may incorrectly classify them as prime.")
    
    print()
    # Modular exponentiation demo
    print("3^100 mod 17 =", mod_exp(3, 100, 17))
    print("7^(11-1) mod 11 =", mod_exp(7, 10, 11), " (should be 1 by Fermat's theorem)")

def dfs(graph, start):
    """
    Performs DFS on a graph given as adjacency list.
    Records pre-visit and post-visit times for each vertex.
    
    Args:
        graph: dict mapping vertex -> list of neighbours
        start: starting vertex (if None, runs from all unvisited vertices)
    
    Returns:
        (pre, post, visited) dicts
    """
    visited = {}
    pre = {}
    post = {}
    clock = [1]  # use list for mutability inside nested function
    
    def explore(v):
        visited[v] = True
        pre[v] = clock[0]; clock[0] += 1
        for u in graph.get(v, []):
            if u not in visited:
                explore(u)
        post[v] = clock[0]; clock[0] += 1
    
    # Run from all unvisited vertices (handles disconnected graphs)
    for v in graph:
        if v not in visited:
            explore(v)
    
    return pre, post, visited


def is_connected(graph):
    """
    Returns True if the undirected graph is connected.
    """
    if not graph:
        return True
    _, _, visited = dfs(graph, None)
    return len(visited) == len(graph)


def find_components(graph):
    """
    Returns a list of connected components (each component is a set of vertices).
    """
    visited = set()
    components = []
    
    def explore_component(v, component):
        visited.add(v)
        component.add(v)
        for u in graph.get(v, []):
            if u not in visited:
                explore_component(u, component)
    
    for v in graph:
        if v not in visited:
            comp = set()
            explore_component(v, comp)
            components.append(comp)
    
    return components

if __name__ == "__main__":
    # Undirected graph as adjacency list
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'D'],
        'D': ['B', 'C', 'E'],
        'E': ['D']
    }
    
    print("Graph:", {v: graph[v] for v in sorted(graph)})
    pre, post, visited = dfs(graph, None)
    
    print("\nDFS results:")
    print(f"{'Vertex':>8}  {'pre':>5}  {'post':>5}")
    for v in sorted(pre):
        print(f"{v:>8}  {pre[v]:>5}  {post[v]:>5}")
    
    print("\nConnected?", is_connected(graph))
    
    # Disconnected graph
    graph2 = {
        'A': ['B'], 'B': ['A'],
        'C': ['D'], 'D': ['C'],
        'E': []
    }
    print("\nDisconnected graph components:", find_components(graph2))

from collections import deque

def bfs(graph, source):
    """
    BFS from source vertex. Computes shortest hop-count distances.
    
    Args:
        graph: dict mapping vertex -> list of neighbours
        source: starting vertex
    
    Returns:
        dist: dict mapping vertex -> shortest distance from source
        parent: dict for reconstructing shortest paths
    """
    dist = {source: 0}
    parent = {source: None}
    queue = deque([source])
    
    while queue:
        v = queue.popleft()
        for u in graph.get(v, []):
            if u not in dist:
                dist[u] = dist[v] + 1
                parent[u] = v
                queue.append(u)
    
    return dist, parent


def shortest_path(parent, source, target):
    """
    Reconstructs shortest path from source to target using parent dict.
    Returns list of vertices on the path, or None if unreachable.
    """
    if target not in parent:
        return None
    path = []
    v = target
    while v is not None:
        path.append(v)
        v = parent[v]
    return list(reversed(path))

if __name__ == "__main__":
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    source = 'A'
    dist, parent = bfs(graph, source)
    
    print(f"BFS from {source}:")
    for v in sorted(dist):
        path = shortest_path(parent, source, v)
        print(f"  {source} → {v}: distance = {dist[v]}, path = {' → '.join(path)}")

import heapq

def dijkstra(graph, source):
    """
    Dijkstra's shortest path algorithm for weighted graphs with non-negative weights.
    
    Args:
        graph: dict mapping vertex -> list of (neighbour, weight) tuples
        source: starting vertex
    
    Returns:
        dist: dict mapping vertex -> shortest distance from source
        prev: dict for path reconstruction
    
    Time: O((V + E) log V) using a binary heap
    """
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    prev = {v: None for v in graph}
    
    # Priority queue: (distance, vertex)
    pq = [(0, source)]
    visited = set()
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if u in visited:
            continue   # already finalised
        visited.add(u)
        
        for v, weight in graph.get(u, []):
            if v not in visited:
                new_dist = dist[u] + weight
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    prev[v] = u
                    heapq.heappush(pq, (new_dist, v))
    
    return dist, prev


def get_path(prev, source, target):
    """Reconstruct the shortest path from source to target."""
    path = []
    v = target
    while v is not None:
        path.append(v)
        v = prev[v]
    path.reverse()
    if path[0] == source:
        return path
    return None   # target unreachable

if __name__ == "__main__":
    # Weighted graph as adjacency list: vertex -> [(neighbour, weight), ...]
    graph = {
        'A': [('B', 4), ('C', 2)],
        'B': [('C', 1), ('D', 5)],
        'C': [('B', 1), ('D', 8), ('E', 10)],
        'D': [('E', 2)],
        'E': []
    }
    
    source = 'A'
    dist, prev = dijkstra(graph, source)
    
    print(f"Dijkstra's shortest paths from {source}:")
    print(f"{'Vertex':>8}  {'Distance':>10}  {'Path'}")
    for v in sorted(dist):
        path = get_path(prev, source, v)
        path_str = ' → '.join(path) if path else 'unreachable'
        print(f"{v:>8}  {dist[v]:>10}  {path_str}")

# From the project root:
python DSA/notes/code/fibonacci.py
python DSA/notes/code/euclid_gcd.py
python DSA/notes/code/primality.py
python DSA/notes/code/dfs.py
python DSA/notes/code/bfs.py
python DSA/notes/code/dijkstra.py