# -*- coding: utf-8 -*-
# Correction du TP 1

# Exercice 1

def miroir(l):
    l2 = []   # L'énoncé demande de faire un nouvelle liste !
    n = len(l)    
    for i in range(0,n):
        l2.append(l[n-1-i])
    return l2

#print(miroir([1,2,7,5]))

# Autre solution
def miroir2(l):
    l2 = []   # L'énoncé demande de faire un nouvelle liste !
    n = len(l)    
    for i in range(n-1,-1,-1):
        l2.append(l[i])
    return l2

#print(miroir2([1,2,7,5]))



# Exercice 2

def testTri(l):
    for i in range(1,len(l)): # Attention aux bornes de la boucle à cause de l[i-1]
        if l[i-1] > l[i]:
            return False
    return True

# un bon test cherche à piéger la fonction :
#print(testTri([1,2,5,4,6])) # tableau presque trié mais pas tout à fait


# Exercice 3

def incremente(l):
    for i in range(0,len(l)):
        for j in range(0,len(l[i])):
            l[i][j] = l[i][j] + 1
    return l

#incremente([[3,6,5],[-2,-4,-1,-8],[7,9]])


# Exercice 4
    
def table(n,m):
    # Ne pas confondre nombre de lignes (nombre de sous-listes) et nombre de colonnes (taille des sous-listes)
    l = [ [0]*m for i in range(n) ]
    for i in range(len(l)):
        for j in range(len(l[i])):
            l[i][j] = i*j
    return l

#print(table(3,5))


# Exercice 5

def recherche(l,x):
    for i in range(0,len(l)):
        for j in range(0,len(l[i])):
            if l[i][j] == x:
                return True
    return False   # Attention à ne pas mettre return False dans l'une des boucles !

#print(recherche([[3,6,5],[-2,-4,-1,-8],[7,9]],-8))


# Exercice 6

#1
def carre(l):
    for i in range(0,len(l)):
        if len(l[i]) != len(l):
            return False
    return True

#print(carre([[0,0,0],[0,0],[0,0,0]]))

#2
def sommeLigne(l,i):
    s = 0
    for k in range(0,len(l[i])): # Attention, len(l[i]) et pas len(l)
        s = s + l[i][k]
    return s
    
#print(sommeLigne([[3,6,5],[-2,-4,-1,-8],[7,9]],0))

def sommeColonne(l,i):
    s = 0
    for k in range(0,len(l)): # Ici c'est bien len(l) et pas len(l[i])
        s = s + l[k][i]
    return s
    
#print(sommeColonne([[3,6,5],[-2,-4,-1,-8],[7,9]],1))

#3
def sommeDiagonaleMajeure(l):
    s = 0
    for i in range(0,len(l)): # Une seule boucle suffit
        s = s + l[i][i]
    return s
    
#print(sommeDiagonaleMajeure([[3,6,5],[-2,-4,-1],[-8,7,9]]))

def sommeDiagonaleMineure(l):
    s = 0
    for i in range(0,len(l)): # Une seule boucle suffit
        s = s + l[i][len(l)-1-i]
    return s
    
#print(sommeDiagonaleMineure([[3,6,5],[-2,-4,-1],[-8,7,9]]))

#4
def carreMagique(l):
    if not carre(l):
        return False
    s = sommeDiagonaleMajeure(l) # On enregistre la valeur pour ne faire qu'un appel à la fonction
    if sommeDiagonaleMineure(l) != s:
        return False
    for i in range(0,len(l)):
        if sommeLigne(l,i) != s:
            return False
        if sommeColonne(l,i) != s:
            return False
    return True

#print(carreMagique([[0,0,0],[0,0,0],[0,0,0]]))
#print(carreMagique([[0,0,0],[0,0,1],[0,0,0]]))

#5
def histogramme(t):
    h = []
    # On initialise toutes les cases de h à 0:
    for i in range(0,len(t)**2+1):
        h.append(0)
    # On parcourt tout le tableau t, et à chaque valeur t[i][j] qu'on voit, on augmente de 1 la valeur de la case de h correspondante
    for i in range(0,len(t)):
        for j in range(0,len(t[i])):
            h[t[i][j]] = h[t[i][j]] + 1
    return h

#print(histogramme([[1,2,1],[9,6,2],[1,1,7]]))

#6
def carreMagiqueNormal(l):
    if not carreMagique(l):
        return False
    h = histogramme(l)
    for i in range(1,len(h)):
        if h[i] != 1:
            return False
    return True
    
#print(carreMagiqueNormal([[0,0,0],[0,0,0],[0,0,0]]))
#print(carreMagiqueNormal([[6,7,2],[1,5,9],[8,3,4]]))



# Exercice 7

def dichotomie(t,v):
    p = 0        # p est le plus petit indice de la zone du tableau dans laquelle on cherche
    g = len(t)-1 # g est le plus grand indice de la zone du tableau dans laquelle on cherche
    while p <= g: # quand p = g il y a une case et il faut continuer pour regarder ce qu'il y a dans la case
        m = (p+g) // 2  # m est un indice environ au milieu. C'est un quotient car il doit être entier
        if t[m] == v:  # dans ce cas on a trouvé
            return m
        elif t[m] < v: # dans ce cas on ne regarde plus que la partie droite de la liste
            p = m+1    # ne pas oublier le +1
        else:  # dans ce cas on sait que t[m] > v et on ne regarde plus que la partie gauche
            g = m-1    # ne pas oublier le -1
    return False  # quand on sort de la boucle, la partie de liste qu'il reste à regarder est vide donc ne contient pas v

#print(dichotomie([1,3,5,6,9,12,14],9))
#print(dichotomie([1,3,5,6,9,12,14],10))