algorithms/ada.py

"""
USSU Algorithm Analyzer v4.0 - ADA Theory & Analysis Tools
Master Theorem, Recurrence Relations, Amortized Analysis, NP-Completeness.
"""
import math
import random
from typing import Dict, List, Tuple, Optional
from dataclasses import dataclass


@dataclass
class MasterTheoremResult:
    a: float
    b: float
    f_n: str
    log_b_a: float
    case: int
    solution: str
    explanation: str
    verified: bool


class ADATools:
    """Analysis and Design of Algorithms theoretical tools"""

    # ==================== ASYMPTOTIC NOTATION REFERENCE ====================
    @staticmethod
    def big_o_reference() -> List[Dict]:
        return [
            {"notation": "O(1)", "name": "Constant", "example": "Array access, hash lookup", "class": "P"},
            {"notation": "O(log n)", "name": "Logarithmic", "example": "Binary search, balanced BST", "class": "P"},
            {"notation": "O(√n)", "name": "Square Root", "example": "Prime checking, Grover's algorithm", "class": "P"},
            {"notation": "O(n)", "name": "Linear", "example": "Linear search, array traversal", "class": "P"},
            {"notation": "O(n log n)", "name": "Linearithmic", "example": "Merge sort, heap sort, Dijkstra", "class": "P"},
            {"notation": "O(n²)", "name": "Quadratic", "example": "Bubble sort, matrix multiplication", "class": "P"},
            {"notation": "O(n³)", "name": "Cubic", "example": "Floyd-Warshall, naive matrix mult", "class": "P"},
            {"notation": "O(2ⁿ)", "name": "Exponential", "example": "Recursive Fibonacci, subsets", "class": "NP"},
            {"notation": "O(n!)", "name": "Factorial", "example": "Traveling salesman brute force", "class": "NP"},
        ]

    @staticmethod
    def asymptotic_definitions() -> Dict[str, str]:
        return {
            "Big-O (O)": "f(n) = O(g(n)) if ∃ c > 0, n₀ > 0 such that 0 ≤ f(n) ≤ c·g(n) ∀ n ≥ n₀. Upper bound.",
            "Big-Omega (Ω)": "f(n) = Ω(g(n)) if ∃ c > 0, n₀ > 0 such that 0 ≤ c·g(n) ≤ f(n) ∀ n ≥ n₀. Lower bound.",
            "Big-Theta (Θ)": "f(n) = Θ(g(n)) if ∃ c₁, c₂ > 0, n₀ > 0 such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) ∀ n ≥ n₀. Tight bound.",
            "Little-o (o)": "f(n) = o(g(n)) if ∀ c > 0, ∃ n₀ > 0 such that 0 ≤ f(n) < c·g(n) ∀ n ≥ n₀. Strictly smaller.",
            "Little-omega (ω)": "f(n) = ω(g(n)) if ∀ c > 0, ∃ n₀ > 0 such that 0 ≤ c·g(n) < f(n) ∀ n ≥ n₀. Strictly larger.",
        }

    # ==================== MASTER THEOREM SOLVER ====================
    @staticmethod
    def master_theorem(a: float, b: float, f_n: str, n: int = 1000) -> MasterTheoremResult:
        """
        Solve T(n) = aT(n/b) + f(n)
        f_n should be in form like 'n', 'n^2', 'n*log(n)', '1', etc.
        """
        log_b_a = math.log(a) / math.log(b)

        # Parse f(n) to determine polynomial degree
        f_n_clean = f_n.replace(" ", "").lower()
        k = 0  # polynomial degree of f(n)

        if f_n_clean in ['1', 'c', 'constant']:
            k = 0
        elif 'n^' in f_n_clean or 'n**' in f_n_clean:
            # Extract exponent
            parts = f_n_clean.split('^') if '^' in f_n_clean else f_n_clean.split('**')
            if len(parts) > 1:
                try:
                    k = float(parts[1].split('*')[0].split('/')[0])
                except:
                    k = 1
        elif f_n_clean == 'n':
            k = 1
        elif 'n*log' in f_n_clean or 'nlog' in f_n_clean:
            k = 1  # n log n is n^1 * polylog, treated as n^1 for case 2 extended
        elif 'log' in f_n_clean and 'n' not in f_n_clean:
            k = 0  # log n is polylog

        epsilon = 1e-9
        diff = k - log_b_a

        if diff < -epsilon:
            case = 1
            solution = f"Θ(n^{log_b_a:.3f})"
            explanation = (f"f(n) = O(n^{k}) is polynomially smaller than n^{log_b_a:.3f}. "
                          f"Since k < log_b(a) = {log_b_a:.3f}, Case 1 applies.")
        elif abs(diff) < epsilon:
            case = 2
            if 'log' in f_n_clean:
                solution = f"Θ(n^{log_b_a:.3f} · log² n)" if 'log' in f_n_clean and k == log_b_a else f"Θ(n^{log_b_a:.3f} · log n)"
                explanation = (f"f(n) = Θ(n^{log_b_a:.3f} · log^k n). Case 2 (extended) applies. "
                              "Work is evenly distributed across levels.")
            else:
                solution = f"Θ(n^{log_b_a:.3f} · log n)"
                explanation = (f"f(n) = Θ(n^{log_b_a:.3f}). Case 2 applies. "
                              "Work at each level is roughly equal.")
        else:
            case = 3
            # Check regularity condition (simplified)
            solution = f"Θ({f_n})"
            explanation = (f"f(n) = Ω(n^{k}) is polynomially larger than n^{log_b_a:.3f}. "
                          f"Since k > log_b(a) = {log_b_a:.3f}, Case 3 applies. "
                          "Root dominates total cost.")

        return MasterTheoremResult(a, b, f_n, log_b_a, case, solution, explanation, True)

    # ==================== RECURSION TREE CALCULATOR ====================
    @staticmethod
    def recursion_tree_cost(a: float, b: float, f_n_func, n: float, levels: int = 6) -> Dict:
        """Calculate level-by-level cost for T(n) = aT(n/b) + f(n)"""
        tree = []
        total_cost = 0.0
        current_n = n
        current_nodes = 1

        for level in range(levels):
            if current_n < 1:
                break
            level_cost = current_nodes * f_n_func(current_n)
            tree.append({
                'level': level,
                'nodes': int(current_nodes),
                'subproblem_size': current_n,
                'cost': level_cost,
            })
            total_cost += level_cost
            current_nodes *= a
            current_n /= b

        return {
            'tree': tree,
            'total_cost_approx': total_cost,
            'levels_computed': len(tree),
        }

    # ==================== SUBSTITUTION METHOD DEMO ====================
    @staticmethod
    def substitution_guess(guess: str, recurrence: str, base_case: str) -> Dict:
        """Demonstrate substitution method with a guess"""
        return {
            'method': 'Substitution',
            'recurrence': recurrence,
            'guess': guess,
            'base_case': base_case,
            'steps': [
                f"1. Guess: T(n) = {guess}",
                f"2. Substitute into recurrence: {recurrence}",
                f"3. Verify base case: {base_case}",
                f"4. Use mathematical induction to prove bound.",
            ],
            'note': 'Substitution requires creativity to guess the correct bound. Often used after recursion tree intuition.'
        }

    # ==================== AMORTIZED ANALYSIS ====================
    @staticmethod
    def amortized_dynamic_array(n_operations: int = 20) -> Dict:
        """Aggregate analysis of dynamic array doubling"""
        costs = []
        size = 1
        count = 0

        for i in range(1, n_operations + 1):
            if count == size:
                # Double: copy all elements + insert new
                cost = size + 1  # size copies + 1 insert
                size *= 2
            else:
                cost = 1
            count += 1
            costs.append({'operation': i, 'actual_cost': cost, 'array_size': size, 'elements': count})

        total = sum(c['actual_cost'] for c in costs)
        amortized = total / n_operations

        return {
            'scenario': 'Dynamic Array (Aggregate Analysis)',
            'operations': costs,
            'total_cost': total,
            'amortized_cost': amortized,
            'theoretical': 2.0,  # O(1) amortized, actual approaches 2 per op
            'explanation': 'Expensive doubling operations are rare. Total cost ≤ 2n, so amortized cost is O(1).'
        }

    @staticmethod
    def amortized_binary_counter(n_bits: int = 8, increments: int = 20) -> Dict:
        """Amortized analysis of binary counter using accounting method"""
        counter = [0] * n_bits
        history = []
        total_flips = 0

        for inc in range(1, increments + 1):
            flips = 0
            i = 0
            while i < n_bits and counter[i] == 1:
                counter[i] = 0
                flips += 1
                i += 1
            if i < n_bits:
                counter[i] = 1
                flips += 1
            total_flips += flips
            history.append({
                'increment': inc,
                'flips': flips,
                'counter_state': ''.join(map(str, reversed(counter))),
                'total_flips': total_flips,
            })

        return {
            'scenario': 'Binary Counter (Accounting Method)',
            'history': history,
            'total_flips': total_flips,
            'amortized_per_increment': total_flips / increments,
            'theoretical': 2.0,
            'explanation': 'Each bit flips every 2^i increments. Total flips for n increments ≤ 2n. Amortized cost per increment: O(1).'
        }

    @staticmethod
    def amortized_stack_multipop(operations: List[str]) -> Dict:
        """Accounting method for stack with multipop"""
        stack = []
        history = []
        total_cost = 0

        for op in operations:
            if op.startswith('push'):
                stack.append(int(op.split()[1]))
                cost = 2  # 1 for push, 1 credit stored on item
                total_cost += cost
                history.append({'op': op, 'stack_size': len(stack), 'actual_cost': 1, 'charge': 2, 'credits': len(stack)})
            elif op.startswith('pop'):
                if stack:
                    stack.pop()
                    cost = 0  # Paid by credit
                    total_cost += 0
                    history.append({'op': op, 'stack_size': len(stack), 'actual_cost': 1, 'charge': 0, 'credits': len(stack)})
            elif op.startswith('multipop'):
                k = int(op.split()[1])
                actual = min(k, len(stack))
                for _ in range(actual):
                    stack.pop()
                cost = 0  # Paid by credits
                total_cost += 0
                history.append({'op': op, 'stack_size': len(stack), 'actual_cost': actual, 'charge': 0, 'credits': len(stack)})

        return {
            'scenario': 'Stack with Multipop (Accounting Method)',
            'history': history,
            'total_amortized_cost': total_cost,
            'explanation': 'Charge 2 per push: 1 for push, 1 credit stored. Pop/Multipop use stored credits. Amortized cost per operation: O(1).'
        }

    # ==================== PROBABILISTIC ANALYSIS ====================
    @staticmethod
    def hiring_problem(n_candidates: int) -> Dict:
        """Expected cost of hiring problem (order statistics)"""
        # Expected number of hires = H_n = ln(n) + gamma
        harmonic = sum(1/i for i in range(1, n_candidates + 1))
        return {
            'problem': 'Hiring Problem',
            'n_candidates': n_candidates,
            'expected_hires': harmonic,
            'approximation': math.log(n_candidates) + 0.5772,
            'explanation': 'With random order, expected hires = H_n ≈ ln(n) + γ. Each candidate has 1/i chance of being best so far.'
        }

    @staticmethod
    def randomized_quicksort_analysis(n: int) -> Dict:
        """Expected comparisons for randomized quicksort"""
        # E[comparisons] ≈ 2n ln n - 1.51n
        expected = 2 * n * math.log(n) - 1.51 * n if n > 1 else 0
        return {
            'algorithm': 'Randomized Quicksort',
            'input_size': n,
            'expected_comparisons': expected,
            'expected_time': f'O(n log n) ≈ {expected:.0f} comparisons',
            'explanation': 'Random pivot selection makes running time independent of input distribution. Expected comparisons ≈ 2n ln n.'
        }

    # ==================== NP-COMPLETENESS REFERENCE ====================
    @staticmethod
    def np_completeness_reference() -> Dict[str, List[Dict]]:
        return {
            'complexity_classes': [
                {'class': 'P', 'definition': 'Decision problems solvable in polynomial time by deterministic Turing machine.', 'examples': ['Sorting', 'Shortest Path', 'MST', 'Matching']},
                {'class': 'NP', 'definition': 'Decision problems where solutions can be verified in polynomial time.', 'examples': ['SAT', 'Clique', 'Hamiltonian Cycle', 'Subset Sum']},
                {'class': 'NP-Complete', 'definition': 'Problems in NP that are at least as hard as every problem in NP. If one is in P, all are.', 'examples': ['3-SAT', 'Vertex Cover', 'TSP (decision)', 'Graph Coloring']},
                {'class': 'NP-Hard', 'definition': 'Problems at least as hard as NP-Complete, but not necessarily in NP.', 'examples': ['TSP (optimization)', 'Halting Problem', 'Chess Generalization']},
                {'class': 'co-NP', 'definition': 'Complements of NP problems. Verifying NO answers in polynomial time.', 'examples': ['co-SAT', 'Primality (now in P)']},
            ],
            'reductions': [
                {'from': '3-SAT', 'to': 'Clique', 'type': '≤p'},
                {'from': 'Clique', 'to': 'Vertex Cover', 'type': '≤p'},
                {'from': 'Vertex Cover', 'to': 'Hamiltonian Cycle', 'type': '≤p'},
                {'from': 'Hamiltonian Cycle', 'to': 'TSP', 'type': '≤p'},
            ],
            'open_problems': [
                'P vs NP (Millennium Prize Problem, $1M)',
                'NP vs co-NP',
                'P = BPP? (Randomized algorithms)',
                'Quantum polynomial time (BQP) vs NP',
            ]
        }

    # ==================== PARADIGM COMPARISON ====================
    @staticmethod
    def paradigm_comparison() -> List[Dict]:
        return [
            {
                'paradigm': 'Divide & Conquer',
                'approach': 'Break into independent subproblems, solve recursively, combine.',
                'examples': ['Merge Sort', 'Quick Sort', 'Strassen Matrix', 'Closest Pair'],
                'key_property': 'Optimal substructure',
                'when_to_use': 'Subproblems are independent and non-overlapping.',
                'time_pattern': 'T(n) = aT(n/b) + f(n)',
            },
            {
                'paradigm': 'Dynamic Programming',
                'approach': 'Break into overlapping subproblems, memoize to avoid recomputation.',
                'examples': ['Knapsack', 'LCS', 'Edit Distance', 'Matrix Chain'],
                'key_property': 'Optimal substructure + Overlapping subproblems',
                'when_to_use': 'Subproblems overlap and optimal solution contains optimal subsolutions.',
                'time_pattern': 'Usually polynomial in states',
            },
            {
                'paradigm': 'Greedy',
                'approach': 'Make locally optimal choice at each step, never reconsider.',
                'examples': ['Dijkstra', 'Prim/Kruskal', 'Huffman', 'Activity Selection'],
                'key_property': 'Greedy choice property + Optimal substructure',
                'when_to_use': 'Local optimal leads to global optimal. Proof by exchange argument.',
                'time_pattern': 'Often O(n log n) due to sorting',
            },
            {
                'paradigm': 'Backtracking',
                'approach': 'DFS over state space, prune invalid branches.',
                'examples': ['N-Queens', 'Sudoku', 'Graph Coloring', 'Subset Sum'],
                'key_property': 'State space exploration with constraints',
                'when_to_use': 'Need all solutions or exact answer, exponential space acceptable.',
                'time_pattern': 'Exponential in worst case',
            },
            {
                'paradigm': 'Branch & Bound',
                'approach': 'BFS/DFS with bounds to prune suboptimal branches.',
                'examples': ['TSP', 'Job Assignment', 'Knapsack (0/1)'],
                'key_property': 'Bound function + Priority queue',
                'when_to_use': 'Optimization problems where bounds can prune effectively.',
                'time_pattern': 'Exponential worst, often better in practice',
            },
        ]