algorithms/dp.py

"""
USSU Algorithm Analyzer v4.0 - Dynamic Programming Suite
Classic DP problems with table reconstruction and complexity analysis.
"""
import math
from typing import List, Dict, Tuple, Any
from utils.core import profile_algorithm, OperationCounter


class DynamicProgramming(OperationCounter):
    """Dynamic Programming algorithm collection for ADA"""

    def __init__(self):
        super().__init__()
        self.dp_table = []
        self.traceback = []

    def reset(self):
        self.reset_counters()
        self.dp_table = []
        self.traceback = []

    # ==================== 0/1 KNAPSACK ====================
    @profile_algorithm
    def knapsack_01(self, weights: List[int], values: List[int], capacity: int) -> Dict:
        self.reset()
        n = len(weights)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for w in range(capacity + 1):
                self.iterations += 1
                self.comparisons += 1
                if weights[i-1] <= w:
                    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
                else:
                    dp[i][w] = dp[i-1][w]

        # Traceback
        w = capacity
        selected = []
        for i in range(n, 0, -1):
            self.accesses += 1
            if dp[i][w] != dp[i-1][w]:
                selected.append(i-1)
                w -= weights[i-1]

        self.dp_table = dp
        return {
            'algorithm': '0/1 Knapsack (DP)',
            'max_value': dp[n][capacity],
            'selected_items': list(reversed(selected)),
            'time_complexity': 'O(n × W)',
            'space_complexity': 'O(n × W)',
            'dp_table': dp,
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== UNBOUNDED KNAPSACK ====================
    @profile_algorithm
    def knapsack_unbounded(self, weights: List[int], values: List[int], capacity: int) -> Dict:
        self.reset()
        n = len(weights)
        dp = [0] * (capacity + 1)
        choice = [-1] * (capacity + 1)

        for w in range(1, capacity + 1):
            for i in range(n):
                self.iterations += 1
                self.comparisons += 1
                if weights[i] <= w and dp[w - weights[i]] + values[i] > dp[w]:
                    dp[w] = dp[w - weights[i]] + values[i]
                    choice[w] = i

        # Traceback
        w = capacity
        items_used = []
        while w > 0 and choice[w] != -1:
            items_used.append(choice[w])
            w -= weights[choice[w]]

        self.dp_table = [dp]
        return {
            'algorithm': 'Unbounded Knapsack (DP)',
            'max_value': dp[capacity],
            'items_used': items_used,
            'time_complexity': 'O(n × W)',
            'space_complexity': 'O(W)',
            'dp_table': [dp],
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== LONGEST COMMON SUBSEQUENCE ====================
    @profile_algorithm
    def lcs(self, s1: str, s2: str) -> Dict:
        self.reset()
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.iterations += 1
                self.comparisons += 1
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        # Reconstruct LCS
        i, j = m, n
        lcs_str = []
        while i > 0 and j > 0:
            self.accesses += 1
            if s1[i-1] == s2[j-1]:
                lcs_str.append(s1[i-1])
                i -= 1
                j -= 1
            elif dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1

        self.dp_table = dp
        return {
            'algorithm': 'Longest Common Subsequence',
            'length': dp[m][n],
            'subsequence': ''.join(reversed(lcs_str)),
            'time_complexity': 'O(m × n)',
            'space_complexity': 'O(m × n)',
            'dp_table': dp,
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== COIN CHANGE (Min Coins) ====================
    @profile_algorithm
    def coin_change_min(self, coins: List[int], amount: int) -> Dict:
        self.reset()
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        parent = [-1] * (amount + 1)

        for i in range(1, amount + 1):
            for coin in coins:
                self.iterations += 1
                self.comparisons += 1
                if coin <= i and dp[i - coin] + 1 < dp[i]:
                    dp[i] = dp[i - coin] + 1
                    parent[i] = coin

        if dp[amount] == float('inf'):
            return {
                'algorithm': 'Coin Change (Min Coins)',
                'min_coins': -1,
                'time_complexity': 'O(amount × |coins|)',
                'space_complexity': 'O(amount)',
            }

        # Traceback
        coins_used = []
        cur = amount
        while cur > 0:
            coins_used.append(parent[cur])
            cur -= parent[cur]

        self.dp_table = [dp]
        return {
            'algorithm': 'Coin Change (Min Coins)',
            'min_coins': dp[amount],
            'coins_used': coins_used,
            'time_complexity': 'O(amount × |coins|)',
            'space_complexity': 'O(amount)',
            'dp_table': [dp],
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== COIN CHANGE (Ways) ====================
    @profile_algorithm
    def coin_change_ways(self, coins: List[int], amount: int) -> Dict:
        self.reset()
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount + 1):
                self.iterations += 1
                dp[i] += dp[i - coin]

        self.dp_table = [dp]
        return {
            'algorithm': 'Coin Change (Ways)',
            'ways': dp[amount],
            'time_complexity': 'O(amount × |coins|)',
            'space_complexity': 'O(amount)',
            'dp_table': [dp],
            'iterations': self.iterations,
        }

    # ==================== MATRIX CHAIN MULTIPLICATION ====================
    @profile_algorithm
    def matrix_chain_order(self, dims: List[int]) -> Dict:
        self.reset()
        n = len(dims) - 1
        dp = [[0] * n for _ in range(n)]
        split = [[0] * n for _ in range(n)]

        for chain_len in range(2, n + 1):
            for i in range(n - chain_len + 1):
                j = i + chain_len - 1
                dp[i][j] = float('inf')
                for k in range(i, j):
                    self.iterations += 1
                    self.comparisons += 1
                    cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                    if cost < dp[i][j]:
                        dp[i][j] = cost
                        split[i][j] = k

        def print_optimal(i, j):
            if i == j:
                return f"A{i+1}"
            k = split[i][j]
            return f"({print_optimal(i, k)} × {print_optimal(k+1, j)})"

        self.dp_table = dp
        return {
            'algorithm': 'Matrix Chain Multiplication',
            'min_multiplications': dp[0][n-1],
            'optimal_parenthesization': print_optimal(0, n-1),
            'time_complexity': 'O(n³)',
            'space_complexity': 'O(n²)',
            'dp_table': dp,
            'split_table': split,
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== EDIT DISTANCE ====================
    @profile_algorithm
    def edit_distance(self, s1: str, s2: str) -> Dict:
        self.reset()
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.iterations += 1
                self.comparisons += 1
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

        # Traceback operations
        i, j = m, n
        operations = []
        while i > 0 or j > 0:
            self.accesses += 1
            if i > 0 and j > 0 and s1[i-1] == s2[j-1]:
                operations.append(('match', s1[i-1]))
                i -= 1
                j -= 1
            elif j > 0 and (i == 0 or dp[i][j] == dp[i][j-1] + 1):
                operations.append(('insert', s2[j-1]))
                j -= 1
            elif i > 0 and (j == 0 or dp[i][j] == dp[i-1][j] + 1):
                operations.append(('delete', s1[i-1]))
                i -= 1
            else:
                operations.append(('replace', s1[i-1], s2[j-1]))
                i -= 1
                j -= 1

        self.dp_table = dp
        return {
            'algorithm': 'Edit Distance (Levenshtein)',
            'distance': dp[m][n],
            'operations': list(reversed(operations)),
            'time_complexity': 'O(m × n)',
            'space_complexity': 'O(m × n)',
            'dp_table': dp,
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== LONGEST INCREASING SUBSEQUENCE ====================
    @profile_algorithm
    def lis(self, arr: List[int]) -> Dict:
        self.reset()
        n = len(arr)
        if n == 0:
            return {'algorithm': 'LIS', 'length': 0, 'subsequence': [], 'time_complexity': 'O(n²)', 'space_complexity': 'O(n)'}

        dp = [1] * n
        parent = [-1] * n

        for i in range(1, n):
            for j in range(i):
                self.iterations += 1
                self.comparisons += 1
                if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j

        max_len = max(dp)
        idx = dp.index(max_len)
        seq = []
        while idx != -1:
            seq.append(arr[idx])
            idx = parent[idx]

        self.dp_table = [dp]
        return {
            'algorithm': 'Longest Increasing Subsequence',
            'length': max_len,
            'subsequence': list(reversed(seq)),
            'time_complexity': 'O(n²)',
            'space_complexity': 'O(n)',
            'dp_table': [dp],
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }