# TP 06 correction : Algorithmes sur les listes
# BCPST1B 2025-2026
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% importation des fonctions utiles
# exécuter une fois pour toute au début du TP

from random import randint, gauss

#%% partie I
# programme d'exemple : exécuter toute la cellule et observer

def compte_positifs(L):
    c = 0
    for i in range(len(L)):
        if L[i] >= 0:
            c = c + 1
    return c

# test avec une vraie liste
L = [8, -2, 3, -7, 2]
print("L =", L)
print(compte_positifs(L))
# avec une autre
L = [9, 3, 0, 2, 0]
print("L =", L)
print(compte_positifs(L))
# encore
L = [-2, -4, -4, -6, -1]
print("L =", L)
print(compte_positifs(L))
# test avec une liste aléatoire de 10 nombres
L = [randint(-5, 9) for _ in range(10)]
print("(liste aléatoire) L =", L)
print(compte_positifs(L))

#%% exercice 1

def compte(L, x):
    c = 0
    for i in range(len(L)):
        if L[i] == x:
            c = c + 1
    return c

# test
L = [2, 0, 1, 3, 8, 1, 8, 9, 7, 6]
x = 8
print("L =", L, "x =", x)
print(compte(L, x))
x = 5
print("L =", L, "x =", x)
print(compte(L, x))
# test avec une liste aléatoire
L = [randint(0, 5) for _ in range(10)]
x = 0
print("(liste aléatoire) L =", L, "x =", x)
print(compte(L, x))

#%% exercice 2

def différences(L, M):
    assert len(L) == len(M), "Les deux listes doivent être de même longueur."
    c = 0
    for i in range(len(L)):
        if L[i] != M[i]:
            c = c + 1
    return c

# test
L = [3, 7, 6, 5, 3]
M = [3, 8, 6, 5, 4]
print("L =", L, "M =", M)
print(différences(L, M))

#%% exercice 3

def compte_voyelles(s):
    c = 0
    for i in range(len(s)):
        if s[i] == "a" or s[i] == "e" or s[i] == "i" or s[i] == "o" or s[i] == "u" or s[i] == "y":
            c = c + 1
    return c

# test
# se limiter à des caractères minuscules, sans accents
s = "versailles"
print("s =", s)
print(compte_voyelles(s))
s = "portez ce vieux whisky au juge blond qui fume"
print("s =", s)
print(compte_voyelles(s))
s = "tartelette framboises" # à vous de jouer !
print("s =", s)
print(compte_voyelles(s))

#%% exercice 4

def somme(L):
    S = 0
    for i in range(len(L)):
        S = S + L[i]
    return S

# test avec une toute petite liste aléatoire
L = [randint(0, 9) for _ in range(3)]
print("(liste aléatoire) L =", L)
print(somme(L))

#%% exercice 5
# réfléchir, tester, observer

def tous_positifs_1(L):
    for i in range(len(L)):
        if L[i] >= 0:
            return True
        else:
            return False

def tous_positifs_2(L):
    for i in range(len(L)):
        if L[i] >= 0:
            return True
    return False

def tous_positifs_3(L):
    for i in range(len(L)):
        if L[i] < 0:
            return False
        else:
            return True

def tous_positifs_4(L):
    for i in range(len(L)):
        if L[i] < 0:
            return False
    return True

# test
L = [1, 3, 5, 7]
print("L =", L)
print(tous_positifs_1(L))
print(tous_positifs_2(L))
print(tous_positifs_3(L))
print(tous_positifs_4(L))
L = [-2, 4, 6, 8]
print("L =", L)
print(tous_positifs_1(L))
print(tous_positifs_2(L))
print(tous_positifs_3(L))
print(tous_positifs_4(L))
L = [10, 11, -12, 13]
print("L =", L)
print(tous_positifs_1(L))
print(tous_positifs_2(L))
print(tous_positifs_3(L))
print(tous_positifs_4(L))

#%% exercice 6

def binaire(m):
    for i in range(len(m)):
        if m[i] != "0" and m[i] != "1":
            return False
    return True

# test
m = "11111"
print("m =", m)
print(binaire(m))
m = "001101101"
print("m =", m)
print(binaire(m))
m = "00103010"
print("m =", m)
print(binaire(m))

#%% exercice 7

def est_croissante(L):
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            return False
    return True

# test
L = [1, 3, 5, 7]
print("L =", L)
print(est_croissante(L))
L = [4, 3, 2, 1]
print("L =", L)
print(est_croissante(L))
L = [1, 5, 3, 7]
print("L =", L)
print(est_croissante(L))

#%% exercice 8

def cherche(L, x):
    for i in range(len(L)):
        if L[i] == x:
            return i
    return None

# test
L = [8, 7, 5, 0, 2, 5, 2, 5, 6, 3]
x = 5
print("L =", L, "x =", x)
print(cherche(L, x))
x = 8
print("L =", L, "x =", x)
print(cherche(L, x))
x = 3
print("L =", L, "x =", x)
print(cherche(L, x))
x = 1
print("L =", L, "x =", x)
print(cherche(L, x))

#%% exercice 9

def premier_negatif(L):
    for i in range(len(L)):
        if L[i] <= 0:
            return L[i]
    return None

# test
L = [3, 5, -2, 8, -3]
print("L =", L)
print(premier_negatif(L))
L = [-3, 5, -1, 8, 7]
print("L =", L)
print(premier_negatif(L))
L = [3, 4, 2, 6]
print("L =", L)
print(premier_negatif(L))
# test avec une liste aléatoire
L = [randint(-3, 9) for _ in range(10)]
print("(liste aléatoire) L =", L)
print(premier_negatif(L))

#%% exercice 10

def indice_différents(s, t):
    assert len(s) == len(t), "Les deux chaines doivent être de même longueur."
    for i in range(len(s)):
        if s[i] != t[i]:
            return i
    return None

# test
s = "ACGTGATAA"
t = "ACGTCATTA"
print("s =", s, "t =", t)
print(indice_différents(s, t))
s = "ACGTGATAA"
t = "ACGTGATAA"
print("s =", s, "t =", t)
print(indice_différents(s, t))

#%% exercice 11

def compte_tout(L):
    assert all(0 <= x and x <= 9 for x in L), "La liste ne doit contenir que des nombres entre 0 et 9 (inclus)."
    C = [0] * 10
    for i in range(len(L)):
        # augmenter C de 1 à l'indice L[i]
        C[L[i]] += 1
    return C

# test
L = [3, 7, 5, 3, 2, 3, 0, 4, 7, 9, 3, 4, 3, 0, 4]
print("L =", L)
print(compte_tout(L))
# test avec une liste aléatoire
L = [randint(0, 9) for _ in range(30)]
print("(liste aléatoire) L =", L)
print(compte_tout(L))
# test avec une liste aléatoire biaisée
L = [min(max(int(gauss(3, 3)), 0), 9) for _ in range(30)]
print("(liste aléatoire) L =", L)
print(compte_tout(L))

#%% exercice 12.1

def caractère_valide(x):
    A = "abcdefghijklmnopqrstuvwxyz0123456789"
    for i in range(len(A)):
        if A[i] == x:
            return True
    return False

# test
print(caractere_valide("c"))
print(caractere_valide("7"))
print(caractere_valide("A"))
print(caractere_valide("?"))

#%% exercice 12.2

def motdepasse_valide(m):
    for i in range(len(m)):
        if not caractère_valide(m[i]):
            return False
    return True

# test
print(motdepasse_valide("hoche2024"))
print(motdepasse_valide("Hoche2024"))
print(motdepasse_valide("hoche2024bioB"))

#%% exercice 12.3

# *une possibilité* avec cette fonction annexe
# 0 pour un caractère invalide, 1 pour une lettre et 2 pour un chiffre
def classe_caractère(x):
    B = "abcdefghijklmnopqrstuvwxyz"
    C = "0123456789"
    for i in range(len(B)):
        if B[i] == x:
            return 1
    for i in range(len(C)):
        if C[i] == x:
            return 2
    return 0

# utilisation
def motdepasse_fort(m):
    contient_au_moins_une_lettre = False
    contient_au_moins_un_chiffre = False
    for i in range(len(m)):
        t = classe_caractère(m[i])
        if t == 0:
            return False
        elif t == 1:
            contient_au_moins_une_lettre = True
        elif t == 2:
            contient_au_moins_un_chiffre = True
    return (contient_au_moins_une_lettre and contient_au_moins_un_chiffre)

# variante possible : compter les lettres et les chiffres

# test
print(motdepasse_fort("hoche"))
print(motdepasse_fort("2024"))
print(motdepasse_fort("hoche2024bioB"))
print(motdepasse_fort("hoche2024"))
print(motdepasse_fort("2024hoche"))

#%% exercice 13

def est_monotone(L):
    n = len(L)
    # cas à traiter à part
    if n == 0 or n == 1:
        return True
    # ici la liste a au moins 2 éléments, ceci ne provoquera pas d'erreur
    if L[0] <= L[1]:
        # dans ce cas, la liste *doit* être croissante (à partir de 1)
        for i in range(1, n-1):
            if L[i] > L[i+1]:
                return False
    else:
        # sinon, la liste *doit* être décroissante
        for i in range(1, n-1):
            if L[i] < L[i+1]:
                return False
    # cas final, rien n'a renvoyé False
    return True

# test
print(est_monotone([1, 3, 5, 7]))
print(est_monotone([7, 5, 3, 1]))
print(est_monotone([1, 3, 7, 5]))
print(est_monotone([7, 5, 1, 3]))

#%% exercice 14

def compte_blocs(L):
    c = 0
    # nécessaire pour avoir le bon résultat même si le bloc est au début de la liste
    debut_de_bloc = True
    for i in range(len(L)):
        if L[i] == 0:
            debut_de_bloc = True
        else:
            if debut_de_bloc:
                c = c + 1
                debut_de_bloc= False
    return c

# test
print(compte_blocs([0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1]))
print(compte_blocs([1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1]))
print(compte_blocs([0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0]))

#%% exercice 15

# standard
def appartient(L, x):
    for i in range(len(L)):
        if L[i] == x:
            return True
    return False

# standard
def est_permutation(L):
    n = len(L)
    for i in range(n):
        if not appartient(L, i):
            return False
    return True

# mieux
def est_permutation_2(L):
    n = len(L)
    # départ : aucun nombre n'est coché
    M = [False] * n
    for i in range(n):
        x = L[i]
        # x n'est pas dans le bon intervalle
        if x < 0 or x >= n:
            return False
        # la valeur de x a déjà été cochée
        elif M[x] == True:
            return False
        # sinon : cocher x
        else:
            M[x] = True
    return True

# test
L = [3, 1, 0, 2]
print("L =", L)
print(est_permutation(L))
print(est_permutation_2(L))
L = [3, 1, 0, 1]
print("L =", L)
print(est_permutation(L))
print(est_permutation_2(L))
L = [3, 1, 0, 4]
print("L =", L)
print(est_permutation(L))
print(est_permutation_2(L))

#%% exercice 15.5

# très difficile ! attendre le cours sur le dénombrement
def permutations(n):
    # liste de listes
    L = [[]]
    for i in range(n):
        # permutations obtenues en rajoutant i
        T = []
        for P in L:
            for j in range(i+1):
                # rajouter i, à toutes les permutations sans i, à tous les indices possibles
                T.append(P[:j] + [i] + P[j:])
        L = T
    return L

print(permutations(4))