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

TAILLE_PILE   = -1
DÉBUT_PILE    = -2
CAPACITÉ_PILE = -3

def indice_haut_pile(pile):
    return pile[DÉBUT_PILE] + pile[TAILLE_PILE]

## Question 3.1

def nouvelle_pile(taille_tab, capacité):
    pile =  [0] * taille_tab
    pile[TAILLE_PILE]   = 0
    pile[DÉBUT_PILE]    = 0
    pile[CAPACITÉ_PILE] = capacité
    return pile

def est_vide(pile):
    return pile[TAILLE_PILE] == 0

def est_pleine(pile):
    return  pile[TAILLE_PILE] == pile[CAPACITÉ_PILE]

def push(pile, x):
    if est_pleine(pile):
        raise ValueError("Pile pleine")
    i = indice_haut_pile(pile)
    pile[i] = x
    pile[TAILLE_PILE] = pile[TAILLE_PILE] + 1


def pop(pile):
    if est_vide(pile):
        raise ValueError("Pile Vide")
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    i = indice_haut_pile(pile)
    return pile[i]


def réduire_naïf(pile):
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    haut = indice_haut_pile(pile)
    for i in range(haut): # haut exclu
        pile[i] = pile[i+1]

def push(pile, x):
    if est_pleine(pile):
        réduire_naïf(pile)
    i = indice_haut_pile(pile)
    pile[i] = x
    pile[TAILLE_PILE] = pile[TAILLE_PILE] + 1




def réduire(pile):
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    pile[DÉBUT_PILE]  = pile[DÉBUT_PILE]  + 1


def push(pile, x):
    if est_pleine(pile):
        réduire(pile) # c’est le seul changement
    i = indice_haut_pile(pile)
    pile[i] = x
    pile[TAILLE_PILE] = pile[TAILLE_PILE] + 1

p = nouvelle_pile(12, 3)
push(p,11) ; p
push(p,22) ; p
push(p,33) ; p
push(p,44) ; p
push(p,55) ; p
push(p,66) ; p
push(p,77) ; p


# Il suffit de travailler pour l’indice de début modulo n avec n = capacité
def réduire(pile):
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    n = pile[CAPACITÉ_PILE]
    pile[DÉBUT_PILE]  = (pile[DÉBUT_PILE]  + 1)%n

def indice_haut_pile(pile):
    n = pile[CAPACITÉ_PILE]
    return (pile[DÉBUT_PILE] + pile[TAILLE_PILE])%n




## Question 3.1

def nouvelle_pile(capacité):
    pile =  [0] * (capacité+2)
    pile[TAILLE_PILE]   = 0
    pile[DÉBUT_PILE]    = 0
    return pile





TAILLE_PILE   = -1
DÉBUT_PILE    = -2

def nouvelle_pile(capacité):
    pile =  [0] * (capacité+2)
    pile[TAILLE_PILE]   = 0
    pile[DÉBUT_PILE]    = 0
    return pile

def est_vide(pile):
    return pile[TAILLE_PILE] == 0

def est_pleine(pile):
    return  pile[TAILLE_PILE] == len(pile) - 2

def réduire(pile):
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    n = len(pile) - 2
    pile[DÉBUT_PILE]  = (pile[DÉBUT_PILE]  + 1)%n

def indice_haut_pile(pile):
    n = len(pile) - 2
    return (pile[DÉBUT_PILE] + pile[TAILLE_PILE])%n

def pop(pile):
    if est_vide(pile):
        raise ValueError("Pile Vide")
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    i = indice_haut_pile(pile)
    return pile[i]

def push(pile, x):
    if est_pleine(pile):
        réduire(pile)
    i = indice_haut_pile(pile)
    pile[i] = x
    pile[TAILLE_PILE] = pile[TAILLE_PILE] + 1


# Pour tester le code


def test(taille,liste):
    pile = nouvelle_pile(taille)
    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):
    taille = pile[TAILLE_PILE]
    début = pile[DÉBUT_PILE]
    n = len(pile) - 2
    r = "["
    i = début
    for k in range(taille):
        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
    pile[TAILLE_PILE] = pile[TAILLE_PILE] - 1
    i = indice_haut_pile(pile)
    return pile[i]




p="pop"
test(4,[9,8,7,6,5,4])
test(5,[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