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] > 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 à 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 > 3:
        rep.append(indice-4)
    if indice < 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 <= mettre0-1 < 20 and 0 <= mettre5-1 < 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 <= mettre0-4 < 20 and 0 <= mettrei-4 < 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 <= mettre0-4 < 20 and 0 <= mettre1-4 < 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 <= mettre0-4 < 20 and 0 <= mettre1-4 < 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 <= mettre0-1 < 20 and 0 <= mettre1-1 < 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 <= mettre0-1 < 20 and 0 <= mettre1-1 < 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@$&"
    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 à 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 < 1 or longueur > 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 à l'écriture de l'entier en chiffres romains.
    """
    assert 1 <= n < 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 à 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 < 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) < 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 !