import numpy as np
np.set_printoptions(suppress=True)


def sparse_gauss(arr, n):
    h, k = 0, 0
    while h < n and k < n + 1:
        idx, pivot = None, 0
        for i in range(h, n):
            if abs(arr[i].get(k, 0)) > pivot:
                pivot = abs(arr[i].get(k, 0))
                idx = i
        if idx is None:
            k += 1
        else:
            cpy = dict(arr[idx])
            arr[idx] = arr[h]
            arr[h] = dict(cpy)
            for i in range(h + 1, n):  
                f = arr[i].get(k, 0) / arr[h][k]
                arr[i][k] = 0
                for j in range(k + 1, n + 1):
                    if j in arr[h]:
                        arr[i][j] = arr[i].get(j, 0) - arr[h][j] * f
            h += 1
            k += 1
    return None

def from_dense(arr):
    n, m = len(arr), len(arr[0])
    return {i: {j: arr[i][j] for j in range(m) if arr[i][j] != 0} for i in range(n)}
    
def to_dense(dct, n, m):
    return [[dct[i].get(j, 0) if i in dct else 0 for j in range(m)] for i in range(n)]
        
arr = [[1, 2, 3],
      [3, -4, 5],
      [-5, 6, 7]]
b = [8, 9, 10]

n = len(arr)
arr_sp = from_dense(arr)

for k in range(n):
    arr_sp[k][n] = b[k]
    
sparse_gauss(arr_sp, n)   
print(to_dense(arr_sp, n, n + 1))    


sol = [None] * n
sol[n - 1] = arr_sp[n - 1][n] / arr_sp[n - 1][n - 1]
for i in range(n - 2, -1, -1):
    cols = [j for j in arr_sp[i] if arr_sp[i][j] != 0 and n > j >= i + 1]
    sol[i] = (arr_sp[i][n] - sum(arr_sp[i][j] * sol[j] for j in cols)) / arr_sp[i][i]
print(sol)


cpy = [arr[i][:] + [b[i]] for i in range(n)]


ref_sol = np.linalg.solve(arr, b)
print(ref_sol)



# def solve(a):
#     n, m = len(a), len(a[0])
#     arr = gauss(a)  
#     print(arr)
#     sol = [None] * n
#     sol[-1] = arr[-1][-1] / arr[-1][-2]
#     for i in range(n - 2, -1, -1):
#         sol[i] = (arr[i][-1] - sum(arr[i][j] * sol[j] for j in range(i + 1, n))) / arr[i][i]
#     return sol

# def gauss_solve(a, b):
#     arr = [r[:] for r in a]
#     for i in range(len(arr)):
#         arr[i].append(b[i])
#     sol = solve(arr)
#     return sol