algorithms/math_tools.py

"""
USSU Algorithm Analyzer v4.0 - Mathematical Tools Suite
Number theory, matrix ops, combinatorics, and complexity utilities.
"""
import math
import random
from typing import List, Tuple, Dict, Any
from utils.core import profile_algorithm, OperationCounter


class MathTools(OperationCounter):
    """Advanced mathematical calculations for algorithm analysis"""

    def __init__(self):
        super().__init__()

    def reset(self):
        self.reset_counters()

    @profile_algorithm
    def factorial(self, n: int) -> Dict:
        self.reset()
        if n < 0:
            return {'algorithm': 'Factorial', 'result': None, 'error': 'Negative input'}
        result = 1
        for i in range(2, n + 1):
            self.iterations += 1
            result *= i
        return {
            'algorithm': 'Factorial',
            'n': n,
            'result': result,
            'time_complexity': 'O(n)',
            'space_complexity': 'O(1)',
            'iterations': self.iterations,
        }

    @profile_algorithm
    def fibonacci(self, n: int, method: str = "iterative") -> Dict:
        self.reset()
        if method == "recursive":
            def fib(k):
                self.recursions += 1
                if k <= 1:
                    return k
                return fib(k-1) + fib(k-2)
            result = [fib(i) for i in range(n)]
            return {
                'algorithm': 'Fibonacci (Recursive)',
                'sequence': result,
                'time_complexity': 'O(2ⁿ)',
                'space_complexity': 'O(n)',
                'recursions': self.recursions,
            }
        elif method == "memoization":
            memo = {}
            def fib(k):
                self.recursions += 1
                if k in memo:
                    return memo[k]
                if k <= 1:
                    return k
                memo[k] = fib(k-1) + fib(k-2)
                return memo[k]
            result = [fib(i) for i in range(n)]
            return {
                'algorithm': 'Fibonacci (Memoization)',
                'sequence': result,
                'time_complexity': 'O(n)',
                'space_complexity': 'O(n)',
                'recursions': self.recursions,
            }
        else:
            if n <= 0:
                return {'algorithm': 'Fibonacci (Iterative)', 'sequence': [], 'time_complexity': 'O(n)', 'space_complexity': 'O(1)'}
            fibs = [0, 1]
            for i in range(2, n):
                self.iterations += 1
                fibs.append(fibs[-1] + fibs[-2])
            return {
                'algorithm': 'Fibonacci (Iterative)',
                'sequence': fibs[:n],
                'time_complexity': 'O(n)',
                'space_complexity': 'O(1)',
                'iterations': self.iterations,
            }

    @profile_algorithm
    def gcd(self, a: int, b: int) -> Dict:
        self.reset()
        steps = 0
        x, y = a, b
        while y:
            self.iterations += 1
            x, y = y, x % y
            steps += 1
        return {
            'algorithm': 'Euclidean GCD',
            'gcd': x,
            'steps': steps,
            'time_complexity': 'O(log min(a,b))',
            'space_complexity': 'O(1)',
            'iterations': self.iterations,
        }

    @profile_algorithm
    def extended_gcd(self, a: int, b: int) -> Dict:
        self.reset()
        if b == 0:
            return {'algorithm': 'Extended GCD', 'gcd': a, 'x': 1, 'y': 0, 'time_complexity': 'O(log n)', 'space_complexity': 'O(log n)'}
        x0, x1, y0, y1 = 1, 0, 0, 1
        while b:
            self.iterations += 1
            q = a // b
            a, b = b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1
        return {
            'algorithm': 'Extended GCD',
            'gcd': a,
            'x': x0,
            'y': y0,
            'time_complexity': 'O(log n)',
            'space_complexity': 'O(log n)',
            'iterations': self.iterations,
        }

    @profile_algorithm
    def fast_exponentiation(self, base: float, exp: int) -> Dict:
        self.reset()
        result = 1
        b = base
        e = exp
        while e > 0:
            self.iterations += 1
            if e % 2 == 1:
                result *= b
            b *= b
            e //= 2
        return {
            'algorithm': 'Fast Exponentiation',
            'result': result,
            'time_complexity': 'O(log n)',
            'space_complexity': 'O(1)',
            'iterations': self.iterations,
        }

    @profile_algorithm
    def is_prime(self, n: int) -> Dict:
        self.reset()
        if n < 2:
            return {'algorithm': 'Primality Test', 'is_prime': False, 'checks': 0, 'time_complexity': 'O(√n)', 'space_complexity': 'O(1)'}
        if n == 2:
            return {'algorithm': 'Primality Test', 'is_prime': True, 'checks': 1, 'time_complexity': 'O(√n)', 'space_complexity': 'O(1)'}
        if n % 2 == 0:
            return {'algorithm': 'Primality Test', 'is_prime': False, 'checks': 1, 'time_complexity': 'O(√n)', 'space_complexity': 'O(1)'}
        checks = 0
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            self.iterations += 1
            self.comparisons += 1
            checks += 1
            if n % i == 0:
                return {'algorithm': 'Primality Test', 'is_prime': False, 'checks': checks, 'time_complexity': 'O(√n)', 'space_complexity': 'O(1)', 'iterations': self.iterations}
        return {'algorithm': 'Primality Test', 'is_prime': True, 'checks': checks, 'time_complexity': 'O(√n)', 'space_complexity': 'O(1)', 'iterations': self.iterations, 'comparisons': self.comparisons}

    @profile_algorithm
    def sieve_eratosthenes(self, n: int) -> Dict:
        self.reset()
        if n < 2:
            return {'algorithm': 'Sieve of Eratosthenes', 'primes': [], 'count': 0, 'time_complexity': 'O(n log log n)', 'space_complexity': 'O(n)'}
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(math.sqrt(n)) + 1):
            self.iterations += 1
            if is_prime[i]:
                for j in range(i*i, n + 1, i):
                    self.comparisons += 1
                    is_prime[j] = False
        primes = [i for i in range(2, n + 1) if is_prime[i]]
        return {
            'algorithm': 'Sieve of Eratosthenes',
            'primes': primes,
            'count': len(primes),
            'time_complexity': 'O(n log log n)',
            'space_complexity': 'O(n)',
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    @profile_algorithm
    def matrix_multiply(self, A: List[List[float]], B: List[List[float]]) -> Dict:
        self.reset()
        n = len(A)
        m = len(B[0])
        p = len(B)
        result = [[0.0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                for k in range(p):
                    self.iterations += 1
                    self.accesses += 2
                    result[i][j] += A[i][k] * B[k][j]
        return {
            'algorithm': 'Matrix Multiplication (Naive)',
            'result': result,
            'time_complexity': 'O(n³)',
            'space_complexity': 'O(n²)',
            'iterations': self.iterations,
            'accesses': self.accesses,
        }

    @profile_algorithm
    def modular_exponentiation(self, base: int, exp: int, mod: int) -> Dict:
        self.reset()
        result = 1
        b = base % mod
        e = exp
        while e > 0:
            self.iterations += 1
            if e % 2 == 1:
                result = (result * b) % mod
            b = (b * b) % mod
            e //= 2
        return {
            'algorithm': 'Modular Exponentiation',
            'result': result,
            'time_complexity': 'O(log exp)',
            'space_complexity': 'O(1)',
            'iterations': self.iterations,
        }

    @profile_algorithm
    def tower_of_hanoi(self, n: int) -> Dict:
        self.reset()
        moves = []
        def hanoi(disk, source, aux, target):
            self.recursions += 1
            if disk == 1:
                moves.append(f"Move disk 1 from {source} to {target}")
                return
            hanoi(disk - 1, source, target, aux)
            moves.append(f"Move disk {disk} from {source} to {target}")
            hanoi(disk - 1, aux, source, target)
        hanoi(n, 'A', 'B', 'C')
        return {
            'algorithm': 'Tower of Hanoi',
            'moves': moves,
            'total_moves': len(moves),
            'time_complexity': 'O(2ⁿ)',
            'space_complexity': 'O(n)',
            'recursions': self.recursions,
        }

    @profile_algorithm
    def generate_permutations(self, arr: List[Any]) -> Dict:
        self.reset()
        result = []
        def permute(a, l, r):
            self.recursions += 1
            if l == r:
                result.append(a[:])
            else:
                for i in range(l, r + 1):
                    self.iterations += 1
                    a[l], a[i] = a[i], a[l]
                    permute(a, l + 1, r)
                    a[l], a[i] = a[i], a[l]
        permute(arr[:], 0, len(arr) - 1)
        return {
            'algorithm': 'Permutations (Backtracking)',
            'permutations': result,
            'count': len(result),
            'time_complexity': 'O(n!)',
            'space_complexity': 'O(n)',
            'recursions': self.recursions,
            'iterations': self.iterations,
        }