# Partie I

# Question 1
def liste_vers_dico(L):
    D = {}
    for e in L:
        if e in D:
            D[e] += 1
        else:
            D[e] = 1
    return D

L1 = ['Camion de pompiers','poupée Parpie','Jeu de construction Lebo','poupée Parpie','poupée Parpie','Manga Houane Pice','Écharpe bleue','Jeu de société SkyDassin','puzzle Kopémon','Jeu de société SkyDassin','figurine heroman','Jeu vidéo Delza','puzzle Kopémon','écharpe verte','Jeu de construction Lebo','Camion de pompiers','puzzle Kopémon']

D1 = liste_vers_dico(L1)

# Question 2
def compterJouets(D):
    s = 0
    for e in D:
        s += D[e]
    return s

#print(compterJouets(D1))

# Question 3 avec choix quelconque en cas d'égalité
def maxJouets(D):
    M = 0
    for e in D:
        if D[e] > M:
            jeuM = e
            M = D[e]
    return jeuM

#print(maxJouets(D1))

# Question 3 avec mémoire des ex-aequo
def maxJouets2(D):
    M = 0
    for e in D:
        if D[e] > M:
            jeuM = [e]
            M = D[e]
        elif D[e] == M:
            jeuM.append(e)
    return jeuM

#print(maxJouets2(D1))

# Question 4
def copieDico(D):
    D2 = {}
    for e in D:
        D2[e] = D[e]
    return D2

# Attention on ne peut pas simplement écrire le code suivant :
# D2 = D1
# En effet, cette instruction ne crée pas une copie. Elle dit simplement "D2 et D1" désigne le même dictionnaire en mémoire.
# Si on dispose d'un dictionnaire D1 et qu'on exécute les instructions suivantes
# D2 = D1
# D2['test copie'] = 2
# on constate que D1 a été modifié et contient maintenant la clé "test copie" associée à la valeur 2 !

# Question 5
def ajoutProd(D,listeLutins):
    D2 = copieDico(D)
    for d in listeLutins:
        for e in d:
            if e in D:
                D2[e] += d[e]
            else:
                D2[e] = d[e]
    return D2

listeLutins1 = [{'Jeu de construction Lebo': 150,'Livre Henry Botteur': 200},{'Manga Houane Pice': 500},{'Camion de pompiers': 100,'poupée Parpie': 100,'Jeu de construction Lebo': 100}]

#print(ajoutProd(D1,listeLutins1))



# Partie 2

# Question 6
def dico_vers_noms(D):
    return [e for e in D]

M1 = dico_vers_noms(D1)
#print(M1)


# Question 7
def standardisation(noms):
    nomsS = []
    for e in noms:
        if ord(e[0])>96 and ord(e[0])<123:
            nomsS.append(chr(ord(e[0])-32) + e[1:])
        else:
            nomsS.append(e)
    return nomsS

M2 = standardisation(M1)
#print(standardisation(M1))

# Question 8
def repartition(M):
    R = [[] for _ in range(27)]
    for e in M:
        if ord(e[0])>64 and ord(e[0])<91:
            R[ord(e[0])-65].append(e)
        else:
            R[26].append(e)
    return R

R1 = repartition(M2)
#print(R1)

# Question 9
def comp(s1,s2):
    n1 = len(s1)
    n2 = len(s2)
    i = 0
    while i < n1 and i < n2:
        if s1[i] < s2[i]:
            return -1
        elif s1[i] > s2[i]:
            return 1
        i += 1
    if n1 == n2:
        return 0
    elif n1 < n2:
        return -1
    else:
        return 1
    
# Remarque : on aurait pu aussi comparer directement s1 et s2 grâce aux opérateurs <,<=,... mais ce n'était pas l'esprit de la question.
    
#print(comp("abc","abcd"))

# Question 10
def indiceInsertion(T,e):
    for i in range(len(T)):
        if comp(T[i],e) == 1:
            return i
    return len(T)

#print(indiceInsertion(["Abb","Abc","Az"],"Abcd"))

# Question 11
def insertion(T,e,i):
    return T[:i] + [e] + T[i:]

# Question 12
def triInsertion(M):
    T = []
    for e in M:
        i = indiceInsertion(T,e)
        T = insertion(T,e,i)
    return T

#print(triInsertion(["Abc","Az","Abb","Abcd","Abd"]))

# Question 13
def indiceInsertionDicho(T,e):
    i = 0
    j = len(T)-1
    while i <= j:
        m = (i+j)//2
        if comp(T[m],e) == 1:
            j = m-1
        else:
            i = m+1
    return i

#print(indiceInsertionDicho(["Abb","Abc","Az"],"Abcd"))

# Question 14

def combiner(J, n):
    l = len(J)
    # R contiendra la liste finale de toutes les combinaisons
    R = []

    # combi contient les indices de la première combinaison [0, 1, 2, ..., n-1]
    combi = [i for i in range(n)]

    # Boucle principale : on génère chaque combinaison jusqu'à épuisement
    while True:
        # On ajoute à R la combinaison actuelle (conversion des indices en valeurs)
        R.append([J[k] for k in combi])

        # On cherche à quel indice modifier pour obtenir la prochaine combinaison
        i = n - 1
        # On remonte tant que l’indice atteint son maximum possible
        # L'indice i ne doit pas dépasser l - (n-i)
        while i >= 0 and combi[i] == l - (n - i):
            i -= 1

        # Si i < 0, cela signifie qu'on a parcouru toutes les combinaisons
        if i < 0:
            return R

        # On incrémente l'indice trouvé
        combi[i] += 1

        # On réinitialise les indices suivants
        for j in range(i + 1, n):
            combi[j] = combi[j - 1] + 1


J1 = ['Camion de pompiers', 'poupée Parpie', 'Jeu de construction Lebo', 'Manga Houane Pice', 'Jeu de société SkyDassin']

#print(combiner(J1,3))

# Autre proposition :

# On construit les combinaisons possibles jouet après jouet : on manipule au cours de l'algorithme une liste L de deux quantités : la combinaison que nous sommes en train de construire, ainsi que la liste des mots qu'il est encore possible d'utiliser

def combiner2(J,n):
    # Initialement, on n'a pas encore choisi de premier jouets et tous les jouets de J sont disponibles
    L = [([],J)]

    # On va construire des combinaisons de n jouets
    for i in range(n):
        # à l'étape i, L contient des tuples de la forme (combi-de-taille-i, liste-jouets-dispo).
        L2 = []
        for combi,dispo in L:
            for j in range(len(dispo)):
                #On ajoute à chacune des combinaisons de taille i l'un des jouets disponibles, et on met à jour la liste des jouets disponibles. Afin d'éviter les combinaisons identiques, la liste des jouets disponibles ne peut pas contenir des jouets déjà présents dans les combinaisons précédentes
                L2.append((combi+[dispo[j]],dispo[j+1:]))
        L = L2
    # on renvoie les combinaisons
    return [combi for (combi,_) in L]