#*********
# Fait Par
# Maxime Carbonneau (16 209 657)
#
# Pour strassen, nous avons besoin de la library numpy
# Pour l'installer, éxécuter la ligne suivante dans un terminal en mode administrateur
# pip install numpy
#
#*********
from random import random
from math import floor
import heapq
import numpy as np
import time

TAILLE_MATRICE = 4 # NE PAS CHANGER

def naif(A,B, TAILLE):
    X = np.asarray(A)
    Y = np.asarray(B)

    result = ([[0 for i in range(TAILLE)] for j in range(TAILLE)])
    # iterate through rows of X
    for i in range(len(X)):
        # iterate through columns of Y
        for j in range(len(Y[0])):
            # iterate through rows of Y
            for k in range(len(Y)):
                result[i][j] += X[i][k] * Y[k][j]

    return result


# https://stackoverflow.com/questions/12867099/strassen-matrix-multiplication-close-but-still-with-bugs
def straight(a, b):
    if len(a[0]) != len(b): return "Matrices are not m*n and n*p"
    p_matrix = np.zeros((len(a), len(b[0])))
    p_matrix += [[np.sum([a[i][k] * b[k][j] for k in range(len(b))]) for j in range(len(b[0]))] for i in range(len(a))]
    return p_matrix

# split matrix into quarters
def split(matrix):
    row, col = matrix.shape
    return matrix[:row//2, :col//2], matrix[:row//2, col//2:], matrix[row//2:, :col//2], matrix[row//2:, col//2:]

def strassen(a, b):
    q = len(a)
    if q == 1:  # base case: 1x1 matrix
        return a * b
    a11, a12, a21, a22 = split(a)
    b11, b12, b21, b22 = split(b)
    p1 = strassen(a11 + a22, b11 + b22)  # p1 = (a11 + a22) * (b11 + b22)
    p2 = strassen(a21 + a22, b11)        # p2 = (a21 + a22) * b11
    p3 = strassen(a11, b12 - b22)        # p3 = a11 * (b12 - b22)
    p4 = strassen(a22, b21 - b11)        # p4 = a22 * (b21 - b11)
    p5 = strassen(a11 + a12, b22)        # p5 = (a11 + a12) * b22
    p6 = strassen(a21 - a11, b11 + b12)  # p6 = (a21 - a11) * (b11 + b12)
    p7 = strassen(a12 - a22, b21 + b22)  # p7 = (a12 - a22) * (b21 + b22)
    c11 = p1 + p4 - p5 + p7  # c11 = p1 + p4 - p5 + p7
    c12 = p3 + p5            # c12 = p3 + p5
    c21 = p2 + p4            # c21 = p2 + p4
    c22 = p1 + p3 - p2 + p6  # c22 = p1 + p3 - p2 + p6
    c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))
    return c








n = int(input("Entrez un n (Nombre d'élément à afficher) : "))

#Liste des évènements possible qui peuvent se produire lors d'un harcèlement
# Probabilités que l'évènement se produise
#e = ["Insulter", "Rabaisser", "Frapper", "Violer"]
e = np.matrix([[round(random(), 2)] for i in range(TAILLE_MATRICE)])

#Liste  des effets psychologiques et physiques définies par des évènements
# AUGMENTÉ d'un effet non identifié
f = ["Atteinte à la dignité", "Santé physique", "Peur", "Effet non identifié"]

# f = Re   où R est la matrice des probabilités
R = np.matrix([[round(random(), 2) for i in range(TAILLE_MATRICE)] for j in range(TAILLE_MATRICE)])

# Matrice des probabilités qu'un effet provoque un type d'harcèlement
Q = np.matrix([[round(random(), 2) for i in range(TAILLE_MATRICE)] for j in range(TAILLE_MATRICE)])

matrix_strassen = strassen(Q,R)
h = np.dot(matrix_strassen, e) # Q * R * e

# Afficher dans un ordre croissant les n éléments de h ayant les plus fortes valeurs
print("Numéro 1.1 et 1.2")
result_array = np.squeeze(np.asarray(h))
result_array.sort()
for i in range(n):
    print(i, ":", result_array[i])



# Comparer le temps d’exécution des deux algorithmes
print("Numéro 1.3")
print("SIZE", "NAIF", "------------", "STRASSEN")

for count in range(2,10):
    SIZE = 2**count
    Q = np.matrix([[round(random(), 2) for i in range(SIZE)] for j in range(SIZE)])
    R = np.matrix([[round(random(), 2) for i in range(SIZE)] for j in range(SIZE)])

    start = time.time()
    matrix_naif = naif(Q,R,SIZE) # Q * R
    end = time.time()
    temps_naif = end - start

    start = time.time()
    matrix_strassen = strassen(Q,R) # Q * R
    end = time.time()
    temps_strassen = end - start


    print(SIZE, round(temps_naif, 4), " ------------", round(temps_strassen, 4))