import numpy as np
import sympy as sp
from sympy import symbols, Eq, solve, Matrix
from typing import Tuple, Dict, Any, Optional
import matplotlib.pyplot as plt
from fractions import Fraction

class SystemSolver:
    """
    A class to solve systems of linear equations using multiple methods
    for Algebra II level students.
    """
    
    def __init__(self):
        self.x, self.y, self.z = symbols('x y z')
    
    def solve_2x2_system(self, coefficients: list, constants: list, method: str = 'all') -> Dict[str, Any]:
        """
        Solve a 2x2 system of linear equations.
        
        Args:
            coefficients: [[a1, b1], [a2, b2]] for equations a1*x + b1*y = c1, a2*x + b2*y = c2
            constants: [c1, c2]
            method: 'graphical', 'substitution', 'elimination', 'matrix', or 'all'
        
        Returns:
            Dictionary containing solution and method details
        """
        a1, b1 = coefficients[0]
        a2, b2 = coefficients[1]
        c1, c2 = constants
        
        result = {
            'system_type': self._classify_2x2_system(coefficients, constants),
            'coefficients': coefficients,
            'constants': constants
        }
        
        if method == 'all' or method == 'matrix':
            result['matrix_solution'] = self._solve_2x2_matrix(coefficients, constants)
        
        if method == 'all' or method == 'elimination':
            result['elimination_solution'] = self._solve_2x2_elimination(coefficients, constants)
        
        if method == 'all' or method == 'substitution':
            result['substitution_solution'] = self._solve_2x2_substitution(coefficients, constants)
        
        if method == 'all' or method == 'graphical':
            result['graphical_solution'] = self._solve_2x2_graphical(coefficients, constants)
        
        return result
    
    def solve_3x3_system(self, coefficients: list, constants: list, method: str = 'all') -> Dict[str, Any]:
        """
        Solve a 3x3 system of linear equations.
        
        Args:
            coefficients: [[a1, b1, c1], [a2, b2, c2], [a3, b3, c3]]
            constants: [d1, d2, d3]
            method: 'elimination', 'matrix', or 'all'
        """
        result = {
            'system_type': self._classify_3x3_system(coefficients, constants),
            'coefficients': coefficients,
            'constants': constants
        }
        
        if method == 'all' or method == 'matrix':
            result['matrix_solution'] = self._solve_3x3_matrix(coefficients, constants)
        
        if method == 'all' or method == 'elimination':
            result['elimination_solution'] = self._solve_3x3_elimination(coefficients, constants)
        
        return result
    
    def _classify_2x2_system(self, coefficients: list, constants: list) -> str:
        """Classify the type of solution for a 2x2 system"""
        a1, b1 = coefficients[0]
        a2, b2 = coefficients[1]
        c1, c2 = constants
        
        # Calculate determinant
        det = a1 * b2 - a2 * b1
        
        if det != 0:
            return "unique_solution"  # Consistent independent
        elif det == 0:
            # Check if system is inconsistent or dependent
            if abs(a1 * c2 - a2 * c1) < 1e-10 and abs(b1 * c2 - b2 * c1) < 1e-10:
                return "infinite_solutions"  # Consistent dependent
            else:
                return "no_solution"  # Inconsistent
    
    def _classify_3x3_system(self, coefficients: list, constants: list) -> str:
        """Classify the type of solution for a 3x3 system"""
        A = np.array(coefficients, dtype=float)
        b = np.array(constants, dtype=float)
        
        det_A = np.linalg.det(A)
        
        if abs(det_A) > 1e-10:
            return "unique_solution"
        else:
            # Check rank to determine if no solution or infinite solutions
            rank_A = np.linalg.matrix_rank(A)
            rank_Ab = np.linalg.matrix_rank(np.column_stack([A, b]))
            
            if rank_A == rank_Ab:
                return "infinite_solutions"
            else:
                return "no_solution"
    
    def _solve_2x2_matrix(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Solve using matrix method (Cramer's rule or inverse)"""
        try:
            A = np.array(coefficients, dtype=float)
            b = np.array(constants, dtype=float)
            
            det_A = np.linalg.det(A)
            
            if abs(det_A) < 1e-10:
                return {
                    'method': 'Matrix (Determinant)',
                    'steps': [
                        f"Coefficient matrix A = {A.tolist()}",
                        f"Constants vector b = {b.tolist()}",
                        f"det(A) = {det_A:.6f} ≈ 0",
                        "System has no unique solution"
                    ],
                    'solution': None,
                    'determinant': det_A
                }
            
            # Use Cramer's rule
            det_x = np.linalg.det([[constants[0], coefficients[0][1]], 
                                  [constants[1], coefficients[1][1]]])
            det_y = np.linalg.det([[coefficients[0][0], constants[0]], 
                                  [coefficients[1][0], constants[1]]])
            
            x_val = det_x / det_A
            y_val = det_y / det_A
            
            return {
                'method': 'Matrix (Cramers Rule)',
                'steps': [
                    f"det(A) = {det_A}",
                    f"det(Ax) = {det_x} → x = {det_x}/{det_A} = {x_val}",
                    f"det(Ay) = {det_y} → y = {det_y}/{det_A} = {y_val}"
                ],
                'solution': {'x': x_val, 'y': y_val},
                'determinant': det_A
            }
            
        except Exception as e:
            return {'method': 'Matrix', 'error': str(e), 'solution': None}
    
    def _solve_2x2_elimination(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Solve using elimination method"""
        a1, b1 = coefficients[0]
        a2, b2 = coefficients[1]
        c1, c2 = constants
        
        steps = [
            f"Original system:",
            f"  {a1}x + {b1}y = {c1}  ... (1)",
            f"  {a2}x + {b2}y = {c2}  ... (2)"
        ]
        
        # Eliminate x by multiplying equations
        if a1 != 0 and a2 != 0:
            mult1 = a2
            mult2 = -a1
            
            new_a1, new_b1, new_c1 = mult1 * a1, mult1 * b1, mult1 * c1
            new_a2, new_b2, new_c2 = mult2 * a2, mult2 * b2, mult2 * c2
            
            steps.extend([
                f"Multiply equation (1) by {mult1}: {new_a1}x + {new_b1}y = {new_c1}",
                f"Multiply equation (2) by {mult2}: {new_a2}x + {new_b2}y = {new_c2}",
                "Add the equations:"
            ])
            
            final_b = new_b1 + new_b2
            final_c = new_c1 + new_c2
            
            if abs(final_b) < 1e-10:
                if abs(final_c) < 1e-10:
                    return {
                        'method': 'Elimination',
                        'steps': steps + ["0 = 0 (Infinite solutions)"],
                        'solution': 'infinite'
                    }
                else:
                    return {
                        'method': 'Elimination',
                        'steps': steps + [f"0 = {final_c} (No solution)"],
                        'solution': None
                    }
            
            y_val = final_c / final_b
            steps.append(f"{final_b}y = {final_c}")
            steps.append(f"y = {y_val}")
            
            # Back substitute
            x_val = (c1 - b1 * y_val) / a1
            steps.append(f"Substitute back: x = ({c1} - {b1}*{y_val})/{a1} = {x_val}")
            
            return {
                'method': 'Elimination',
                'steps': steps,
                'solution': {'x': x_val, 'y': y_val}
            }
        
        return {'method': 'Elimination', 'error': 'Cannot eliminate with zero coefficients'}
    
    def _solve_2x2_substitution(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Solve using substitution method"""
        a1, b1 = coefficients[0]
        a2, b2 = coefficients[1]
        c1, c2 = constants
        
        steps = [
            f"Original system:",
            f"  {a1}x + {b1}y = {c1}  ... (1)",
            f"  {a2}x + {b2}y = {c2}  ... (2)"
        ]
        
        # Solve equation 1 for x (if a1 != 0) or y (if b1 != 0)
        if abs(a1) >= abs(b1) and a1 != 0:
            # Solve for x from equation 1
            steps.append(f"Solve equation (1) for x:")
            steps.append(f"x = ({c1} - {b1}y)/{a1}")
            
            # Substitute into equation 2
            steps.append("Substitute into equation (2):")
            # a2*((c1 - b1*y)/a1) + b2*y = c2
            # a2*(c1 - b1*y)/a1 + b2*y = c2
            # a2*c1/a1 - a2*b1*y/a1 + b2*y = c2
            # y*(b2 - a2*b1/a1) = c2 - a2*c1/a1
            
            coeff_y = b2 - (a2 * b1) / a1
            const_term = c2 - (a2 * c1) / a1
            
            steps.append(f"{a2}*({c1} - {b1}y)/{a1} + {b2}y = {c2}")
            steps.append(f"({coeff_y})y = {const_term}")
            
            if abs(coeff_y) < 1e-10:
                if abs(const_term) < 1e-10:
                    return {'method': 'Substitution', 'steps': steps + ["0 = 0 (Infinite solutions)"], 'solution': 'infinite'}
                else:
                    return {'method': 'Substitution', 'steps': steps + [f"0 = {const_term} (No solution)"], 'solution': None}
            
            y_val = const_term / coeff_y
            x_val = (c1 - b1 * y_val) / a1
            
            steps.append(f"y = {y_val}")
            steps.append(f"x = ({c1} - {b1}*{y_val})/{a1} = {x_val}")
            
            return {
                'method': 'Substitution',
                'steps': steps,
                'solution': {'x': x_val, 'y': y_val}
            }
        
        elif b1 != 0:
            # Solve for y from equation 1
            steps.append(f"Solve equation (1) for y:")
            steps.append(f"y = ({c1} - {a1}x)/{b1}")
            
            # Substitute into equation 2
            coeff_x = a2 - (b2 * a1) / b1
            const_term = c2 - (b2 * c1) / b1
            
            steps.append("Substitute into equation (2):")
            steps.append(f"({coeff_x})x = {const_term}")
            
            if abs(coeff_x) < 1e-10:
                if abs(const_term) < 1e-10:
                    return {'method': 'Substitution', 'steps': steps + ["0 = 0 (Infinite solutions)"], 'solution': 'infinite'}
                else:
                    return {'method': 'Substitution', 'steps': steps + [f"0 = {const_term} (No solution)"], 'solution': None}
            
            x_val = const_term / coeff_x
            y_val = (c1 - a1 * x_val) / b1
            
            steps.append(f"x = {x_val}")
            steps.append(f"y = ({c1} - {a1}*{x_val})/{b1} = {y_val}")
            
            return {
                'method': 'Substitution',
                'steps': steps,
                'solution': {'x': x_val, 'y': y_val}
            }
        
        return {'method': 'Substitution', 'error': 'Cannot solve - both coefficients are zero'}
    
    def _solve_2x2_graphical(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Prepare data for graphical solution"""
        a1, b1 = coefficients[0]
        a2, b2 = coefficients[1]
        c1, c2 = constants
        
        # Convert to slope-intercept form y = mx + b
        lines = []
        
        if b1 != 0:
            slope1 = -a1 / b1
            intercept1 = c1 / b1
            lines.append({
                'slope': slope1,
                'y_intercept': intercept1,
                'equation': f"y = {slope1:.3f}x + {intercept1:.3f}",
                'original': f"{a1}x + {b1}y = {c1}"
            })
        else:
            # Vertical line x = c1/a1
            lines.append({
                'vertical': True,
                'x_value': c1 / a1 if a1 != 0 else None,
                'equation': f"x = {c1/a1:.3f}" if a1 != 0 else "undefined",
                'original': f"{a1}x + {b1}y = {c1}"
            })
        
        if b2 != 0:
            slope2 = -a2 / b2
            intercept2 = c2 / b2
            lines.append({
                'slope': slope2,
                'y_intercept': intercept2,
                'equation': f"y = {slope2:.3f}x + {intercept2:.3f}",
                'original': f"{a2}x + {b2}y = {c2}"
            })
        else:
            lines.append({
                'vertical': True,
                'x_value': c2 / a2 if a2 != 0 else None,
                'equation': f"x = {c2/a2:.3f}" if a2 != 0 else "undefined",
                'original': f"{a2}x + {b2}y = {c2}"
            })
        
        # Find intersection point
        try:
            A = np.array(coefficients, dtype=float)
            b = np.array(constants, dtype=float)
            solution = np.linalg.solve(A, b)
            intersection = {'x': solution[0], 'y': solution[1]}
        except:
            intersection = None
        
        return {
            'method': 'Graphical',
            'lines': lines,
            'intersection': intersection,
            'system_type': self._classify_2x2_system(coefficients, constants)
        }
    
    def _solve_3x3_matrix(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Solve 3x3 system using matrix methods"""
        try:
            A = np.array(coefficients, dtype=float)
            b = np.array(constants, dtype=float)
            
            det_A = np.linalg.det(A)
            
            if abs(det_A) < 1e-10:
                return {
                    'method': 'Matrix (3x3)',
                    'steps': [f"det(A) = {det_A:.6f} ≈ 0", "System has no unique solution"],
                    'solution': None,
                    'determinant': det_A
                }
            
            solution = np.linalg.solve(A, b)
            
            return {
                'method': 'Matrix (3x3)',
                'steps': [
                    f"Coefficient matrix A determinant = {det_A:.6f}",
                    f"Solution: x = {solution[0]:.6f}, y = {solution[1]:.6f}, z = {solution[2]:.6f}"
                ],
                'solution': {'x': solution[0], 'y': solution[1], 'z': solution[2]},
                'determinant': det_A
            }
            
        except Exception as e:
            return {'method': 'Matrix (3x3)', 'error': str(e), 'solution': None}
    
    def _solve_3x3_elimination(self, coefficients: list, constants: list) -> Dict[str, Any]:
        """Solve 3x3 system using Gaussian elimination"""
        # Create augmented matrix
        augmented = np.array([coefficients[i] + [constants[i]] for i in range(3)], dtype=float)
        
        steps = [
            "Augmented matrix:",
            f"{augmented.tolist()}"
        ]
        
        # Forward elimination
        for i in range(3):
            # Find pivot
            max_row = i + np.argmax(np.abs(augmented[i:, i]))
            if max_row != i:
                augmented[[i, max_row]] = augmented[[max_row, i]]
                steps.append(f"Swap rows {i+1} and {max_row+1}")
            
            # Check for zero pivot
            if abs(augmented[i, i]) < 1e-10:
                steps.append(f"Zero pivot encountered at position ({i+1}, {i+1})")
                return {
                    'method': 'Elimination (3x3)',
                    'steps': steps,
                    'solution': None
                }
            
            # Eliminate below pivot
            for j in range(i + 1, 3):
                if abs(augmented[j, i]) > 1e-10:
                    factor = augmented[j, i] / augmented[i, i]
                    augmented[j] = augmented[j] - factor * augmented[i]
                    steps.append(f"R{j+1} = R{j+1} - ({factor:.3f})R{i+1}")
        
        steps.append("After forward elimination:")
        steps.append(f"{augmented.tolist()}")
        
        # Back substitution
        solution = np.zeros(3)
        for i in range(2, -1, -1):
            solution[i] = augmented[i, 3]
            for j in range(i + 1, 3):
                solution[i] -= augmented[i, j] * solution[j]
            solution[i] /= augmented[i, i]
        
        steps.append("Back substitution:")
        steps.append(f"x = {solution[0]:.6f}, y = {solution[1]:.6f}, z = {solution[2]:.6f}")
        
        return {
            'method': 'Elimination (3x3)',
            'steps': steps,
            'solution': {'x': solution[0], 'y': solution[1], 'z': solution[2]}
        }

# Example usage and testing
if __name__ == "__main__":
    solver = SystemSolver()
    
    # Test 2x2 system
    print("=== 2x2 System Test ===")
    coeffs_2x2 = [[2, 1], [1, -1]]
    constants_2x2 = [7, 1]
    
    result_2x2 = solver.solve_2x2_system(coeffs_2x2, constants_2x2)
    print(f"System type: {result_2x2['system_type']}")
    
    if 'elimination_solution' in result_2x2:
        print("\nElimination method:")
        for step in result_2x2['elimination_solution']['steps']:
            print(f"  {step}")
        print(f"Solution: {result_2x2['elimination_solution']['solution']}")
    
    # Test 3x3 system
    print("\n=== 3x3 System Test ===")
    coeffs_3x3 = [[1, 2, -1], [2, 1, 1], [1, -1, 2]]
    constants_3x3 = [3, 7, 4]
    
    result_3x3 = solver.solve_3x3_system(coeffs_3x3, constants_3x3, method='matrix')
    print(f"System type: {result_3x3['system_type']}")
    
    if 'matrix_solution' in result_3x3:
        print("\nMatrix method:")
        for step in result_3x3['matrix_solution']['steps']:
            print(f"  {step}")
        print(f"Solution: {result_3x3['matrix_solution']['solution']}")