#!/usr/bin/python3 -B

################ 
##            ## 
## Exercice 3 ## 
##            ## 
################ 

M = [ [1,2,3], [4,5,6] ]

## Question 3.1

M[0][2] = 0


## Question 3.2


M+M
2*M

## Question 3.3

# Cette fonction est dans le cours
def dimensions(M):
    return (len(M),len(M[0]))

def doubler(M):
    (n, m) = dimensions(M)
    for i in range(n):
        for j in range(m):
            M[i][j] = 2 * M[i][j]

## Question 3.4

# Cette fonction aussi est dans le cours !
def matrice_nulle(n,m):
    A=[]
    for ligne in range(n):
        L=[]
        for colonne in range(m):
            L.append(0)
        A.append(L)

def double(M):
    (n, m) = dimensions(M)
    D = matrice_nulle(n,m)
    for i in range(n):
        for j in range(m):
            D[i][j] = 2 * M[i][j]
    return D





################ 
##            ## 
## Exercice 4 ## 
##            ## 
################ 

M = [ [2,7,6] , [9,5,1] , [4,3,8] ]
## Question 4.1

def est_carré(M):
    if M==[]:
        return False
    n = len(M)
    for ligne in M:
        if len(ligne) != n:
            return False
    return True

        

## Question 4.2


def ligne(M,i):
    return M[i]

def colonne(M, j):
    (n,m) = dimensions(M)
    return [ M[i][j] for i in range(m)]

# Renvoie la diagonale de la matrice M. k=0 ou 1 suivant si on veut la
# diagonale de gauche à droite ou de droite à gauche

def diagonale(M,k):
    (n,m) = dimensions(M)
    if k==0:
        return [ M[i][i] for i in range(n)]
    else:
        return [ M[n-1-i][i] for i in range(n)]

def est_magique(M):
    if not est_carré(M):
        return False
    (n,m) = dimensions(M) # Forcément n=m
    S = sum(ligne(M,0))
    # vérification des lignes
    for i in range(n):
        if sum(ligne(M,i)) != S:
            return False        
    # vérification des colonnes
    for j in range(n):
        if sum(colonne(M,j)) != S:
            return False
    # vérification des diagonales
    for k in range(2): # k=0 ou 1
        if sum(diagonale(M,k)) != S:
            return False
    # Si tous les tests ont été passé avec succés
    return True


def est_magique(M):
    if not est_carré(M):
        return False
    (n,m) = dimensions(M) # Forcément n=m
    El = { sum(ligne(M,i)) for i in range(n) }
    Ec = { sum(colonne(M,j)) for j in range(m) }
    Ed = { sum(diagonale(M,k)) for k in range(2) }
    return len( El | Ec | Ed ) == 1





################ 
##            ## 
## Exercice 5 ## 
##            ## 
################ 
            

## Question 5.1

def inverse_liste_contacts(contacts) :
    res = dict()
    for nom in contacts :
        tél = contacts[nom] # ici nom est la clé et tel la valeur
        res[tél] = nom      # ici tél est la clé et nom la valeur
    return res


## Question 5.2

def affiche_liste_appels(L , contacts) :
    contacts_inv = inverse_liste_contacts2(contacts)
    for e in L :
        (heure,tel)=e
        if tel in contacts_inv :
            nom = contacts_inv[tel]
            print(heure, nom)
        else :
            print(heure ,tel)




################ 
##            ## 
## Exercice 6 ## 
##            ## 
################ 


## Question 6.1

def trouve_numéro(contacts,nom) :
    for e in contacts :
        (nom2,tel) = e
        if nom == nom2 :
            return tel
    return -1

## Question 6.2

memo = dict()

def trouve_numéro_mémo(contacts,nom) :
    if not nom in memo : # Si ce n'est pas dans le cache, on le cherche et on l'ajoute
        for e in contacts :   
            (nom2,tel) = e
            if nom == nom2 :
                memo[nom] = tel
                break # on a trouvé, inutile de continuer la recherche
    return memo[nom]

## Question 6.3







################ 
##            ## 
## Exercice 7 ## 
##            ## 
################ 


def fibo(n) :
    print('début calcul de fibo({})'.format(n))
    if n < 2 :
        res = 1
    else :
        res = fibo(n-1) + fibo(n-2)
    print('fin calcul de fibo({})'.format(n))
    return res


## Question 7.1



fibo(5)



## Question 7.2



mem = dict()
def fib_memo(n):
    print('début calcul de fibo_memo({})'.format(n))
    if n==0 or n==1:
        mem[n] = 1
    elif n not in mem:
        mem[n] = fib_memo(n-1)+fib_memo(n-2)
    print('fin calcul de fibo_memo({})'.format(n))
    return mem[n]

print('Exécution de fibo_memo(5)')
fib_memo(5)


fib_memo(5)




## Question 7.3




from time import time

def chronomètre(f,n) :
    t1 = time()
    f(n)
    t2 = time()
    return t2-t1


mem = dict()
def fibo_memo(n):
    if n==0 or n==1:
        mem[n] = 1
    elif n not in mem:
        mem[n] = fibo_memo(n-1)+fibo_memo(n-2)
    return mem[n]

def fibo(n) :
    if n < 2 :
        res = 1
    else :
        res = fibo(n-1) + fibo(n-2)
    return res







d1 = chronomètre(fibo,30)
d2 = chronomètre(fibo_memo,30)
d1/d2





################ 
##            ## 
## Exercice 8 ## 
##            ## 
################ 


## Question 8.1

contacts2 = {'Maison Chloé': '0901020304', 'Maison Lyes': '0901020304','Alex': '0412345678'}



inverse_liste_contacts(contacts2) # On a perdu Chloé !


## Question 8.2

def inverse_liste_contacts2(contacts) :
    res = dict()
    for nom in contacts :
        tél = contacts[nom]
        if res.get(tél,None)==None:
            res[tél] = [nom]
        else:
            res[tél].append(nom)
    return res



################ 
##            ## 
## Exercice 9 ## 
##            ## 
################ 


## Question 9.1

def nim_gagnant(n):
    if n<=0:
        return True
    for i in [1,2,3]:
        if not nim_gagnant(n-i):
            return True

    return False

## Question 9.2

mem=dict()

def nim_memo(n):
    if n<=0:
        return True
    if n in mem:
        return mem[n]
    for i in [1,2,3]:
        if not nim_memo(n-i):
            mem[n]=True
            return True
    mem[n]=False   
    return False

## Question 9.3







d1 = chronomètre(nim_gagnant,33)
d2 = chronomètre(nim_memo,33)
d1/d2 # La différence est impressionnante (un facteur d’environ 200 000)