################
##            ##
## Exercice 3 ##
##            ##
################
print("\nExercice 3\n")


TAILLE_PILE = -1
HAUT_PILE   = -2
DÉBUT_PILE  = -3


def incrémenter(pile, indice):
    pile[indice] = pile[indice] + 1

def décrémenter(pile, indice):
    pile[indice] = pile[indice] - 1

## Question 3.1

def nouvelle_pile(taille_tampon, taille_pile):
    pile =  [0] * taille_tampon
    pile[HAUT_PILE]   = 0
    pile[DÉBUT_PILE]  = 0  # Pour la question 3
    pile[TAILLE_PILE] = taille_pile
    return pile

def est_vide(pile):
    return pile[HAUT_PILE] == pile[DÉBUT_PILE]

def est_pleine(pile):
    return  pile[HAUT_PILE] == pile[TAILLE_PILE]

def push(pile, x):
    if est_pleine(pile):
        raise ValueError("Pile pleine")
    i = pile[HAUT_PILE]
    pile[i] = x
    incrémenter(pile, HAUT_PILE)

def pop(pile):
    if est_vide(pile):
        raise ValueError("Pile Vide")
    décrémenter(pile, HAUT_PILE)
    i = pile[HAUT_PILE]
    return pile[i]



def réduire_v1(pile):
    décrémenter(pile, HAUT_PILE)
    haut = pile[HAUT_PILE]
    for i in range(haut): # haut exclu
        pile[i] = pile[i+1]

def push(pile, x):
    if est_pleine(pile):
        réduire_v1(pile)
    i = pile[HAUT_PILE]
    pile[i] = x
    incrémenter(pile, HAUT_PILE)



def réduire(pile):
    if est_vide(pile):
        raise ValueError("On ne peut réduire une pile vide")
    incrémenter(pile, DÉBUT_PILE)

def est_pleine(pile):
    haut  = pile[HAUT_PILE]
    début = pile[DÉBUT_PILE]
    taille = pile[TAILLE_PILE]
    return  haut -  début == taille


# Il suffit de travailler modulo n avec n = taille + 1
def incrémenter(pile, indice):
    n = pile[TAILLE_PILE] + 1
    pile[indice] = (pile[indice] + 1)%n

def est_pleine(pile):
    haut  = pile[HAUT_PILE]
    début = pile[DÉBUT_PILE]
    n = pile[TAILLE_PILE] + 1
    return (1 + haut -  début) % n == 0 # car (1+taille)%n == 0







TAILLE_PILE = -1 # À supprimer
HAUT_PILE   = -2 # ou -1 si on supprime TAILLE_PILE
DÉBUT_PILE  = -3 # ou -2 si on supprime TAILLE_PILE

def nouvelle_pile(taille_pile):
    pile =  [0] * (taille_pile + 4) # ou [0] * (taille_pile + 3)
    pile[HAUT_PILE]   = 0
    pile[DÉBUT_PILE]  = 0
    pile[TAILLE_PILE] = taille_pile # À supprimer
    return pile

def incrémenter(pile, indice):
    n = pile[TAILLE_PILE] + 1 # ou n = len(pile) - 3 + 1 = len(pile)-2
    pile[indice] = (pile[indice] + 1)%n

def decrémenter(pile, indice):
    n = pile[TAILLE_PILE] - 1 # ou n = len(pile)-2
    pile[indice] = (pile[indice] - 1)%n

def est_vide(pile):
    return pile[HAUT_PILE] == pile[DÉBUT_PILE]

def est_pleine(pile):
    n = pile[TAILLE_PILE] + 1 # ou n = len(pile)-2
    return (1 + pile[HAUT_PILE] -  pile[DÉBUT_PILE]) % n == 0

def réduire(pile):
    if est_vide(pile):
        raise ValueError("On ne peut réduire une pile vide")
    incrémenter(pile, DÉBUT_PILE)

def push(pile, x):
    if est_pleine(pile):
        réduire(pile)
    i = pile[HAUT_PILE]
    pile[i] = x
    incrémenter(pile, HAUT_PILE)

def pop(pile):
    if est_vide(pile):
        raise ValueError("Pile vide")
    décrémenter(pile, HAUT_PILE)
    i = pile[HAUT_PILE]
    return pile[i]


# Pour tester le code


def test(liste):
    pile = nouvelle_pile(5)
    print(f"    ", end="")
    afficher_pile(pile)
    for action in liste:
        if action==p:
            r = pop(pile)
            r = f"<{r}> " if r is not None else "/!\\ "
            print(r, end="")
        else:
            print(f"    ", end="")
            push(pile, action)
        afficher_pile(pile)
    return pile


def afficher_pile(pile):
    haut  = pile[HAUT_PILE]
    début = pile[DÉBUT_PILE]
    n = pile[TAILLE_PILE] + 1
    r = "["
    i = début
    while i != haut:
        r = r+str(pile[i]) + " ["
        i = (i+1)%n
    print(f"{r:40} {pile}")


def pop(pile):
    if est_vide(pile):
        return None # Pour le test
    décrémenter(pile, HAUT_PILE)
    i = pile[HAUT_PILE]
    return pile[i]

p="pop"
test([2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,p,p,p,p,p,p,1,5,4,4,p,p,p,1,1,p])



################
##            ##
## Exercice 4 ##
##            ##
################
print("\nExercice 4\n")


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)) # Vous savez écrire la fonction sum !
    # 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