import time


def add_matrix(A, B):
    return [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]


def sub_matrix(A, B):
    return [[A[i][j] - B[i][j] for j in range(len(A[0]))] for i in range(len(A))]


def standard_matrix_multiply(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C


def strassen_matrix_multiply(A, B, leaf_size=2):
    n = len(A)

    if n <= leaf_size:
        return standard_matrix_multiply(A, B)

    mid = n // 2
    A11 = [row[:mid] for row in A[:mid]]
    A12 = [row[mid:] for row in A[:mid]]
    A21 = [row[:mid] for row in A[mid:]]
    A22 = [row[mid:] for row in A[mid:]]

    B11 = [row[:mid] for row in B[:mid]]
    B12 = [row[mid:] for row in B[:mid]]
    B21 = [row[:mid] for row in B[mid:]]
    B22 = [row[mid:] for row in B[mid:]]

    M1 = strassen_matrix_multiply(add_matrix(A11, A22), add_matrix(B11, B22), leaf_size)
    M2 = strassen_matrix_multiply(add_matrix(A21, A22), B11, leaf_size)
    M3 = strassen_matrix_multiply(A11, sub_matrix(B12, B22), leaf_size)
    M4 = strassen_matrix_multiply(A22, sub_matrix(B21, B11), leaf_size)
    M5 = strassen_matrix_multiply(add_matrix(A11, A12), B22, leaf_size)
    M6 = strassen_matrix_multiply(sub_matrix(A21, A11), add_matrix(B11, B12), leaf_size)
    M7 = strassen_matrix_multiply(sub_matrix(A12, A22), add_matrix(B21, B22), leaf_size)

    C11 = add_matrix(sub_matrix(add_matrix(M1, M4), M5), M7)
    C12 = add_matrix(M3, M5)
    C21 = add_matrix(M2, M4)
    C22 = add_matrix(add_matrix(sub_matrix(M1, M2), M3), M6)

    C = [[0] * n for _ in range(n)]
    for i in range(mid):
        for j in range(mid):
            C[i][j] = C11[i][j]
            C[i][j + mid] = C12[i][j]
            C[i + mid][j] = C21[i][j]
            C[i + mid][j + mid] = C22[i][j]

    return C


def get_matrix_input(name, n):
    print(f"\nEnter the elements for Matrix {name} ({n}x{n}):")
    matrix = []
    for i in range(n):
        row = list(map(int, input(f"Row {i + 1} (space-separated {n} values): ").split()))
        while len(row) != n:
            print(f"Invalid input! Please enter exactly {n} numbers.")
            row = list(map(int, input(f"Row {i + 1} (space-separated {n} values): ").split()))
        matrix.append(row)
    return matrix


def print_matrix(matrix):
    for row in matrix:
        print("  ".join(f"{val:>5}" for val in row))


if __name__ == "__main__":
    print("=== Strassen vs Standard Matrix Multiplication ===")
    
    # Input matrix dimension (must be a power of 2 for basic Strassen)
    n = int(input("Enter matrix dimension N (must be a power of 2, e.g., 2, 4, 8): "))
    
    # Input Matrices A and B
    A = get_matrix_input("A", n)
    B = get_matrix_input("B", n)

    # Standard Multiplication Execution
    start_std = time.perf_counter()
    result_std = standard_matrix_multiply(A, B)
    time_std = time.perf_counter() - start_std

    # Strassen Multiplication Execution
    start_strassen = time.perf_counter()
    result_strassen = strassen_matrix_multiply(A, B, leaf_size=1)
    time_strassen = time.perf_counter() - start_strassen

    # Display Results
    print("\n" + "=" * 45)
    print("Result Matrix (Standard Multiplication):")
    print_matrix(result_std)

    print("\nResult Matrix (Strassen Multiplication):")
    print_matrix(result_strassen)

    print("\n" + "=" * 45)
    print(f"Standard Time : {time_std * 1000:.4f} ms")
    print(f"Strassen Time : {time_strassen * 1000:.4f} ms")