<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">import sys
sys.setrecursionlimit(10000) # Pour l'exercice 3

# Exercice 1

def plus_frequent_liste_de_listes(l):
    """DÃ©termine l'Ã©lÃ©ment le plus frÃ©quent d'une liste de listes l
    contenant des nombres.
    """
    dico = {}
    for sousliste in l:
        for element in sousliste:
            if element in dico:
                dico[element] += 1
            else:
                dico[element] = 1
    if dico == {}:
        raise ValueError("Aucun Ã©lÃ©ment !")
    nocc = 0
    for element in dico:
        if dico[element] &gt; nocc:
            nocc = dico[element]
            maxi = element
    return maxi

# Exercice 2

def parcours_profondeur(graphe, depart, arrivee):
    """RÃ©alise le parcours en profondeur d'un graphe en premier argument
    entre les deux sommets en deuxiÃ¨me et troisiÃ¨me arguments.
    La reprÃ©sentation du graphe est par liste d'adjacence,
    en utilisant des dictionnaires.
    La liste des sommets rencontrÃ©s dans l'ordre est retournÃ©e.
    """
    chemin = [depart]
    dejavu = {depart : True} # Les ensembles ne sont pas au programme, on utilise un dictionnaire.
    def moulinage(chemin):
        if chemin[-1] == arrivee:
            return chemin
        sommet = chemin[-1]
        for successeur in graphe[sommet]:
            if successeur not in dejavu:
                dejavu[successeur] = True
                suite = moulinage(chemin + [successeur])
                if suite is not None:
                    return suite
        return None
    return moulinage(chemin)

# graphe = {"0" : ["1", "2", "3"], "1" : ["3", "5"], "2" : ["3"], "3": ["4", "5"], "4" : ["6"], "5" : [], "6" : ["5"]}
# print(parcours_profondeur(graphe, "0", "5"))

# Exercice 3

position_depart = (2, 1, 1, 3, 2, 1, 1, 3, 4, 5, 5, 6, 4, 7, 8, 6, 9, 0, 0, 10)
# Ligne par ligne, le 1 est pour le carrÃ© rouge, les autres dans l'ordre de dÃ©couverte Ã&nbsp; partir de 2

def arrivee_ane_rouge(position):
    """DÃ©termine si une position est finale pour le jeu de l'Ã¢ne rouge.
    """
    return position[-3] == position[-2] == 1

def voisins_ane_rouge(indice):
    """DÃ©termine les voisins d'un indice dans une position du jeu
    de l'Ã¢ne rouge.
    """
    rep = []
    if indice &gt; 3:
        rep.append(indice-4)
    if indice &lt; 16:
        rep.append(indice+4)
    if indice % 4 != 0:
        rep.append(indice-1)
    if indice % 4 != 3:
        rep.append(indice+1)
    return rep

def encodage(configuration):
    """Simplifie une configuration de l'Ã¢ne rouge pour Ã©liminer
    des configurations Ã©quivalentes.
    """
    les_codes = [0, 1, 2, 2, 2, 3, 2, 4, 4, 4, 4]
    return tuple([les_codes[code] for code in configuration])

def successeurs_ane_rouge(position):
    """DÃ©termine les successeurs d'une position pour le jeu de l'Ã¢ne rouge.
    """
    voisins_zero = [[] for _ in range(10)] # mouvements possibles des dix piÃ¨ces
    for i in range(20):
        for indice in voisins_ane_rouge(i):
            if position[indice] == 0 and position[i] != 0:
                voisins_zero[position[i]-1].append((i, indice))
    rep = []
    for i in range(6, 10):
        for (mettre0, mettreiplusun) in voisins_zero[i]:
            posbis = list(position) # plus simple de passer par une liste et muter
            posbis[mettre0] = 0
            posbis[mettreiplusun] = i+1
            rep.append(tuple(posbis))
    for (mettre0, mettre5) in voisins_zero[4]: # piÃ¨ce horizontale : dÃ©calage horizontal ou vertical avec test supplÃ©mentaire
        if mettre0 == mettre5-1:
            posbis = list(position)
            posbis[mettre5] = 5
            posbis[mettre0-1] = 0 # Attention, on dÃ©cale deux cases
            rep.append(tuple(posbis))
        elif mettre0 == mettre5+1:
            posbis = list(position)
            posbis[mettre5] = 5
            posbis[mettre0+1] = 0
            rep.append(tuple(posbis))
        elif (mettre0 == mettre5+4 or mettre0 == mettre5-4) and 0 &lt;= mettre0-1 &lt; 20 and 0 &lt;= mettre5-1 &lt; 20 and position[mettre0-1] == 5 and position[mettre5-1] == 0: # J'ai craquÃ©
            posbis = list(position)
            posbis[mettre5] = 5
            posbis[mettre0] = 0
            posbis[mettre5-1] = 5
            posbis[mettre0-1] = 0
            rep.append(tuple(posbis))
        # Ã€ noter : pas besoin de faire le cas avec mettre0+1 vs. mettre5+1 car on verrait un autre Ã©lÃ©ment de voisins_zero[4] qui gÃ¨re le cas prÃ©cÃ©dent ! (astuce pour sauver les meublesâ€¦)
    for i in [2, 3, 4, 6]:
        for (mettre0, mettrei) in voisins_zero[i-1]: # piÃ¨ce verticale : dÃ©calage vertical ou horizontal avec test supplÃ©mentaire
            if mettre0 == mettrei-4:
                posbis = list(position)
                posbis[mettrei] = i
                posbis[mettre0-4] = 0
                rep.append(tuple(posbis))
            elif mettre0 == mettrei+4:
                posbis = list(position)
                posbis[mettrei] = i
                posbis[mettre0+4] = 0
                rep.append(tuple(posbis))
            elif (mettre0 == mettrei+1 or mettre0 == mettrei-1) and 0 &lt;= mettre0-4 &lt; 20 and 0 &lt;= mettrei-4 &lt; 20 and position[mettre0-4] == i and position[mettrei-4] == 0:
                posbis = list(position)
                posbis[mettrei] = i
                posbis[mettre0] = 0
                posbis[mettrei-4] = i
                posbis[mettre0-4] = 0
                rep.append(tuple(posbis))
    for (mettre0, mettre1) in voisins_zero[0]: # piÃ¨ce rouge : test supplÃ©mentaire dans tous les cas
        if mettre0 == mettre1+1 and 0 &lt;= mettre0-4 &lt; 20 and 0 &lt;= mettre1-4 &lt; 20 and position[mettre0-4] == 1 and position[mettre1-4] == 0:
            posbis = list(position)
            posbis[mettre1] = 1
            posbis[mettre0+1] = 0
            posbis[mettre1-4] = 1
            posbis[mettre0-3] = 0
            rep.append(tuple(posbis))
        if mettre0 == mettre1-1 and 0 &lt;= mettre0-4 &lt; 20 and 0 &lt;= mettre1-4 &lt; 20 and position[mettre0-4] == 1 and position[mettre1-4] == 0:
            posbis = list(position)
            posbis[mettre1] = 1
            posbis[mettre0-1] = 0
            posbis[mettre1-4] = 1
            posbis[mettre0-5] = 0
            rep.append(tuple(posbis))
        if mettre0 == mettre1+4 and 0 &lt;= mettre0-1 &lt; 20 and 0 &lt;= mettre1-1 &lt; 20 and position[mettre0-1] == 1 and position[mettre1-1] == 0:
            posbis = list(position)
            posbis[mettre1] = 1
            posbis[mettre0+4] = 0
            posbis[mettre1-1] = 1
            posbis[mettre0+3] = 0
            rep.append(tuple(posbis))
        if mettre0 == mettre1-4 and 0 &lt;= mettre0-1 &lt; 20 and 0 &lt;= mettre1-1 &lt; 20 and position[mettre0-1] == 1 and position[mettre1-1] == 0:
            posbis = list(position)
            posbis[mettre1] = 1
            posbis[mettre0-4] = 0
            posbis[mettre1-1] = 1
            posbis[mettre0-5] = 0
            rep.append(tuple(posbis))
    return rep[::-1] # PrivilÃ©gier les dÃ©placements de grosses piÃ¨ces

def ane_rouge():
    """RÃ©sout le jeu de l'Ã¢ne rouge par un parcours en profondeur.
    """
    chemin = [position_depart]
    dejavu = {encodage(position_depart) : True}
    def moulinage(chemin):    
        if arrivee_ane_rouge(chemin[-1]):
            return chemin
        sommet = chemin[-1]
        for successeur in successeurs_ane_rouge(sommet):
            if encodage(successeur) not in dejavu:
                dejavu[encodage(successeur)] = True
                suite = moulinage(chemin + [successeur])
                if suite is not None:
                    return suite
        return None
    return moulinage(chemin)

def dessine_ane_rouge_une_config(configuration):
    """ReprÃ©sente une configuration du jeu de l'Ã¢ne rouge en ASCIIART.
    """
    symboles = " R*-./+o@$&amp;"
    for i in range(20):
        print(symboles[configuration[i]], end="")
        if i % 4 == 3:
            print()
    print()

def dessine_ane_rouge(chemin):
    """ReprÃ©sente une solution du jeu de l'Ã¢ne rouge en ASCIIART.
    """
    for configuration in chemin:
        dessine_ane_rouge_une_config(configuration)
        print("\n")
        import time
        time.sleep(.2)

### chemin = ane_rouge() # Solution avec un chemin de taille 1102 trouvÃ©e aprÃ¨s 1779 coupsâ€¦
### dessine_ane_rouge(chemin)

def raccourcit_chemin_ane_rouge(chemin, depart=0):
    """Raccourcit un chemin trouvÃ© par la fonction ane_rouge
    en cherchant des configurations non consÃ©cutives qui sont cependant
    atteignables en une Ã©tape.
    """
    for i in range(depart, len(chemin)-2):
        for j in range(len(chemin)-1, i+1, -1):
            for configuration in successeurs_ane_rouge(chemin[i]):
                if encodage(configuration) == encodage(chemin[j]):
                    chemin[i+1:j] = []
                    return raccourcit_chemin_ane_rouge(chemin, i)

### raccourcit_chemin_ane_rouge(chemin) # raccourci Ã&nbsp; une taille de 552
### dessine_ane_rouge(chemin)

# Exercice 4

voisins = {}
voisins['A'] = ['BC', 'DG', 'EI', 'F', 'H']
voisins['B'] = ['A', 'C', 'D', 'EH', 'F', 'G', 'I']
voisins['C'] = ['BA', 'D', 'EG', 'FI', 'H']
voisins['D'] = ['A', 'B', 'C', 'EF', 'G', 'H', 'I']
voisins['E'] = ['A', 'B', 'C', 'D', 'F', 'G', 'H', 'I']
voisins['F'] = ['A', 'B', 'C', 'ED', 'G', 'H', 'I']
voisins['G'] = ['DA', 'B', 'EC', 'F', 'HI']
voisins['H'] = ['A', 'EB', 'C', 'D', 'F', 'G', 'I']
voisins['I'] = ['EA', 'B', 'FC', 'D', 'HG']

def compte_schemas_deverouillage(depart, longueur):
    """Compte le nombre de schÃ©mas de dÃ©verouillage d'un tÃ©lÃ©phone
    en fonction du point de dÃ©part et de la longueur.
    Un schÃ©ma est une suite de lignes reliant un sous-ensemble
    des neuf points d'un quadrillage de taille 3 par 3.
    Il est interdit de passer par-dessus un point sans s'y arrÃªter
    pour la premiÃ¨re fois, ainsi que de s'y arrÃªter plus d'une fois. 
    """
    if longueur &lt; 1 or longueur &gt; 9:
        return 0
    chemins = {depart}
    for i in range(1, longueur):
        nouveaux_chemins = set()
        for chemin in chemins:
            dernier = chemin[-1]
            for directions in voisins[dernier]:
                j = None
                if directions[0] not in chemin:
                    j = directions[0]
                elif directions[-1] not in chemin:
                    j = directions[-1]
                if j:
                    nouveaux_chemins.add(chemin + j)
        chemins = nouveaux_chemins
    return len(chemins)

### print(compte_schemas_deverouillage("A", 5))
### print(compte_schemas_deverouillage("F", 7))
### print(compte_schemas_deverouillage("E", 9))

# Exercice 5

def vers_romain(n):
    """Transforme un entier entre 1 et 3999 en la chaÃ®ne de caractÃ¨res
    correspondant Ã&nbsp; l'Ã©criture de l'entier en chiffres romains.
    """
    assert 1 &lt;= n &lt; 4000  
    unites = "IXCM"
    cinquaines = "VLD"
    formats = ["", "u", "uu", "uuu", "uc", "c", "cu", "cuu", "cuuu", "uU"]
    fonctions = {}
    fonctions["u"] = lambda i : unites[i]
    fonctions["c"] = lambda i : cinquaines[i]
    fonctions["U"] = lambda i : unites[i+1]
    rep = ""
    for i in range(4):
        r = n % 10
        rep2 = ""
        for code in formats[r]:
            rep2 += fonctions[code](i)
        n //= 10
        rep = rep2 + rep
    return rep

### print(vers_romain(1912))
### print(vers_romain(42))
### print(vers_romain(2048))

def depuis_romain(ch):
    """Transforme une chaÃ®ne de caractÃ¨res correspondant Ã&nbsp; un nombre
    Ã©crit en chiffres romains en le nombre en question.
    On ne vÃ©rifiera pas la cohÃ©rence de la chaÃ®ne fournie, on la suppose bonne.
    """
    valeurs_speciales = {"CM" : 900, "CD" : 400, "XC" : 90, "XL" : 40, "IX" : 9, "IV" : 4}
    valeurs = {"M" : 1000, "D" : 500, "C" : 100, "L" : 50, "X" : 10, "V" : 5, "I" : 1}
    rep = 0
    i = 0
    while i &lt; len(ch):
        if ch[i:i+2] in valeurs_speciales: # Pas de risque de dÃ©bordement, merci Python !
            rep += valeurs_speciales[ch[i:i+2]]
            i += 2
        else:
            rep += valeurs[ch[i]]
            i += 1
    assert vers_romain(rep) == ch # On vÃ©rifie quand mÃªme
    return rep

### print(depuis_romain("MDXV"))
### print(depuis_romain("MCMLXXXVIII"))
### print(depuis_romain("CDXCIX"))

# Exercice 6

acides_amines = {
  'UCA':'S', # SÃ©rine
  'UCC':'S',
  'UCG':'S',
  'UCU':'S',
  'UUC':'F', # PhÃ©nylalanine
  'UUU':'F',
  'UUA':'L', # Leucine
  'UUG':'L',
  'UAC':'Y', # Tyrosine
  'UAU':'Y',
  'UAA':'STOP', # Codon Stop
  'UAG':'STOP',
  'UGC':'C', # CystÃ©ine
  'UGU':'C',
  'UGA':'STOP',
  'UGG':'W', # Tryptophane
  'CUA':'L',
  'CUC':'L',
  'CUG':'L',
  'CUU':'L',
  'CCA':'P', # Proline
  'CCC':'P',
  'CCG':'P',
  'CCU':'P',
  'CAC':'H', # Histidine
  'CAU':'H',
  'CAA':'Q', # Glutamine
  'CAG':'Q',
  'CGA':'R', # Arginine
  'CGC':'R',
  'CGG':'R',
  'CGU':'R',
  'AUA':'I', # Isoleucine
  'AUC':'I',
  'AUU':'I',
  'AUG':'M', # MÃ©thionine
  'ACA':'T', # ThrÃ©onine
  'ACC':'T',
  'ACG':'T',
  'ACU':'T',
  'AAC':'N', # Asparagine
  'AAU':'N',
  'AAA':'K', # Lysine
  'AAG':'K',
  'AGC':'S',
  'AGU':'S',
  'AGA':'R',
  'AGG':'R',
  'GUA':'V', # Valine
  'GUC':'V',
  'GUG':'V',
  'GUU':'V',
  'GCA':'A', # Alanine
  'GCC':'A',
  'GCG':'A',
  'GCU':'A',
  'GAC':'D', # Acide Aspartique
  'GAU':'D',
  'GAA':'E', # Acide Glutamique
  'GAG':'E',
  'GGA':'G', # Glycine
  'GGC':'G',
  'GGG':'G',
  'GGU':'G',  
  'start' : ['AUG'] # MÃ©thionine, on renverse exceptionnellement l'ordre ici
}

def construit_proteine(adn):
    """DÃ©termine la protÃ©ine codÃ©e par un brin d'ADN.
    Par principe, on passe d'abord par la transcription de l'ARN messager,
    mÃªme si on pouvait raccourcir la programmation.
    """
    adn_vers_arn = {"A" : "U", "C" : "G", "G" : "C", "T" : "A"}
    arn = ""
    for base in adn:
        arn += adn_vers_arn[base]
    proteine = []
    for i in range(len(arn)):
        if arn[i:i+3] in acides_amines["start"]:
            for j in range(i+3, len(arn), 3):
                codon = arn[j:j+3]
                if len(codon) &lt; 3:
                    raise ValueError("Dernier codon incomplet")
                if acides_amines[codon] == "STOP":
                    return proteine
                proteine.append(acides_amines[codon])
            raise ValueError("Pas de codon stop rencontrÃ© !")
    raise ValueError("Pas de codon initiateur rencontrÃ© !")

### print(construit_proteine("GCCTAAGACTACTACCGTTGTGCGTAAACACTCATTCAGTACTACGACTA")) # Improvisation totale de cet exemple !
</pre></body></html>