from fractions import Fraction
import sympy 

def isZero(x):
    if x == 0:
        return True

def isZeroVector(v):
    return all(isZero(vi) for vi in v)

def addVector(v, w):
    return [vi + wi for vi, wi in zip(v, w)]

def subVector(v, w):
    return [vi - wi for vi, wi in zip(v, w)]

def mulScalarVector(alpha, v):
    return [alpha*vi for vi in v]

def equalVector(v, w):
    return isZeroVector(subVector(v, w))

def switchRow(A, i, k):    
    A[i], A[k] = A[k], A[i] #"di <-> dk"
    
def mulRow(A, i, num):  
    A[i] = mulScalarVector(num, A[i]) #"di = num*di"

def addRow(A, i, k, num):  
    A[i] = addVector(A[i], mulScalarVector(num, A[k])) #"di = di + num*dk"

def convertToFraction(A):
    if isinstance(A, list):
        return [convertToFraction(i) for i in A]
    else:
        return Fraction(A)
def printMatrix(A, sep=" "):
    if isinstance(A, list) and A:
        if isinstance(A[0], list):                  #list of list
            m, n = len(A), len(A[0])                #size of matrix
            widths = [max(len(str(di[j])) for di in A) for j in range(n)]
            rows = [sep.join(format(str(di[j]),  f">{widths[j]}") for j in range(n)) for di in A]
            print("[" + "\n".join((" [" if i > 0 else "[") + rows[i] + "]" for i in range(m)) + "]")
        else: # list
            print("[" + sep.join(str(q) for q in A) + "]")
    else:
        print(A)   

def Gauss_elimination(A):
    R = A.copy()             #Result
    m, n = len(R), len(R[0]) #Size of matrix
    row = col = 0

    while row < m:
        #Step 1: Determines the leftmost column that does not contain all zeroes
        while col < n and all(isZero(R[i][col]) for i in range(row, m)):
            col += 1

        if col == n: #Echelon matrix
            break
        
        #Step 2: Select the first line with a non-zero term. Switch two rows
        pivot_row = row + [not isZero(R[i][col]) for i in range(row, m)].index(True)
        switchRow(R, row, pivot_row)
        
        #Step 3: With the leading term from Step 2 being a≠0 , multiply the row containing it by 1/a
        mulRow(R, row, 1/R[row][col])
            
        #Step 4: Add an appropriate multiple of the top line to each bottom line to turn the terms below the leading number into 0
        for i in range(row + 1, m):
            multiplier = R[i][col] / R[row][col]
            addRow(R, i, row, -multiplier)
    
        #Step 5: Repeat the steps until you get the echolon matrix.
        row += 1

    printMatrix(R)
    print("\n")

    return R