# Exercice 1
     
def maj_multiplication_matrices(tailles, valeurs, debut, separation, fin):
    """Manipule les données pour calculer le nombre optimal de multiplications
    scalaires pour faire un produit matriciel en considérant deux produits :
    l'un entre l'indice debut inclus et l'indice separation inclus,
    l'autre entre l'indice separation exclu et l'indice fin inclus.
    """
    nb_mult = tailles[debut] * tailles[separation+1] * tailles[fin+1]
    total = valeurs[debut][separation] + nb_mult + valeurs[separation+1][fin]
    if valeurs[debut][fin] == -1 or valeurs[debut][fin] > total:
        valeurs[debut][fin] = total

def nombre_multiplications(tailles):
    """Détermine le nombre optimal de multiplications scalaires pour faire
    un produit matriciel enchaîné. Les dimensions successives des matrices
    sont données dans la liste des tailles, en ne rappelant pas les valeurs
    redondantes, de sorte que le nombre de lignes de la matrice d'indice i
    soit dans tailles[i] et son nombre de colonnes dans tailles[i+1],
    puisqu'il doit aussi s'agir du nombre de lignes de la matrice d'indice i+1.
    L'algorithme est bottom-up en fonction des nombres de matrices consécutives
    multipliées, de deux à toutes.
    """
    n = len(tailles)-1
    valeurs = [[-1 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        valeurs[i][i] = 0
    for taille in range(1, n): # produits de matrices de plus en plus grands
        for i in range(n - taille): # départs possibles
            for j in range(i, i + taille): # séparations possibles
                maj_multiplication_matrices(tailles, valeurs, i, j, i + taille)
    return valeurs[0][-1]

## Test de l'énoncé :

### print(nombre_multiplications([4, 6, 2, 10, 3]))

# Exercice 2

def rendu_monnaie(s, systeme):
    """Détermine le nombre minimal de pièces et billets nécessaires
    pour obtenir une somme donnée dans un système monétaire précisé.
    On considère des valeurs entières pour s et le système, quitte à compter
    en fractions de l'unité monétaire.
    L'algorithme est bottom-up en fonction des valeurs inférieures
    à la somme.
    """
    toutes_valeurs = [s+1] * (s+1) # plus que le maximum possible, pour ne pas avoir besoin de faire de comparaisons à -1 ou None par exemple
    toutes_valeurs[0] = 0
    for somme in range(s):
        for valeur in systeme:
            if somme + valeur <= s:
                if toutes_valeurs[somme + valeur] > toutes_valeurs[somme] + 1:
                     toutes_valeurs[somme + valeur] = toutes_valeurs[somme] + 1
    if toutes_valeurs[s] != s+1:
        return toutes_valeurs[s]
    raise ValueError("Somme impossible à obtenir")

## Tests :

### print(rendu_monnaie(191288, [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000])) # Cas standard en centimes
### print(rendu_monnaie(84, [1, 42, 73])) # Cas d'échec du glouton
### print(rendu_monnaie(27, [5, 8])) # Cas d'impossibilité

# Exercice 3

def tri_taches(taches):
    """Tri de tâches pondérées de la forme ((debut, fin), valeur)
    selon les critères par ordre de priorité : fin croissante,
    valeur décroissante et début croissant.
    """
    taches.sort(key=lambda x : (x[0][1], -x[1], x[0][0]))

def weighted_interval_scheduling(taches):
    """Résout le problème de weighted interval scheduling, c'est-à-dire
    détermine une sous-liste de la liste des tâches donnée de somme
    de valeurs maximales parmi les sous-listes de tâches sans recoupement
    des intervalles associés.
    L'algorithme est bottom-up en fonction du sous-ensemble des premières
    tâches selon un ordre privilégiant la fin (le plus tôt possible), puis
    la valeur (la plus grande possible) puis le début (le plus tôt possible).
    On notera qu'avec des poids tous égaux l'algorithme glouton est optimal
    en utilisant précisément le tri qui a été fait.
    """
    tri_taches(taches)
    n = len(taches)
    reponses = [0] * n
    reponses[0] = taches[0][1]
    for i in range(1, n):
        j = i
        stop = False
        while j > -1 and not stop: # Recherche de la dernière tâche pouvant être faite avant i
            if taches[j][0][1] > taches[i][0][0]:
                j -= 1
            else:
                stop = True
        if j > -1:
            reponses[i] = max(reponses[i-1], reponses[j] + taches[i][1]) # Ce n'est pas forcément la tâche j qui est considérée, mais la meilleure valeur possible avant j
        else:
            reponses[i] = max(reponses[i-1], taches[i][1]) # Sinon, on prend soit l'optimum sans i, soit seulement i.
    return reponses[n-1]

## Tests :

### print(weighted_interval_scheduling([((1,2),50),((3,5),20),((6,19),100),((2,100),200)]))

# Exercice 4

def distance_edition(s, t, cr=1, ca=1, cs=1):
    """Détermine la distance d'édition entre deux chaînes s et t,
    en tant que coût à payer pour passer de l'une à l'autre,
    en additionnant cr fois le nombre de lettres à retirer,
    ca fois le nombre de lettres à ajouter et cs fois le nombre de lettres
    à modifier, sachant que cs doit être inférieur à cr + ca
    pour qu'une substitution soit pertinente.
    La valeur de retour est un couple avec la distance recherchée ainsi qu'une
    matrice des directions permettant de reconstituer un alignement optimal.
    L'algorithme est bottom-up en fonction des préfixes des mots.
    """
    ns = len(s)
    nt = len(t)
    distances = [[None for j in range(nt+1)] for i in range(ns+1)]
    directions = [[None for j in range(nt+1)] for i in range(ns+1)]
    for i in range(ns+1):
        distances[i][0] = i * cr
        directions[i][0] = (-1, 0)
    for j in range(nt+1):
        distances[0][j] = j * ca
        directions[0][j] = (0, -1)
    for i in range(1, ns+1):
        for j in range(1, nt+1):
            distances[i][j] = distances[i-1][j] + cr # Par défaut, on table sur un retrait
            directions[i][j] = (-1, 0)
            if distances[i][j] > distances[i][j-1] + ca: # Si un ajout est meilleur
                distances[i][j] = distances[i][j-1] + ca
                directions[i][j] = (0, -1)
            if distances[i][j] > distances[i-1][j-1] + cs * (s[i-1] != t[j-1]): # Test d'une substitution, gratuite si les lettres coïncident en assimilant un booléen à 1 ou 0
                distances[i][j] = distances[i-1][j-1] + cs * (s[i-1] != t[j-1])
                directions[i][j] = (-1, -1)
    return distances[-1][-1], directions

def levenshtein(s, t, cr=1, ca=1, cs=1):
    """Imprime l'alignement entre deux chaînes s et t selon le calcul
    de la distance d'édition, grâce aux directions obtenues.
    """
    distance, directions = distance_edition(s, t, cr, ca, cs)
    i = len(s)
    j = len(t)
    sf = "" # s formaté et à l'envers
    tf = "" # t formaté et à l'envers
    while i != 0 or j != 0:
        if directions[i][j] == (-1, 0):
            sf += s[i-1]
            tf += "-"
            i -= 1
        elif directions[i][j] == (0, -1):
            sf += "-"
            tf += t[j-1]
            j -= 1
        else:
            sf += s[i-1]
            tf += t[j-1]
            i -= 1
            j -= 1
    print(sf[::-1])
    print(tf[::-1])
    print("Distance :", distance)

## Tests :

### levenshtein("JOURNAL", "CHAT", 1, 1, 1)
### levenshtein("Distance", "Levenshtein", 4, 6, 8)

# Exercice 5

def sac_a_dos(objets, capacite):
    """Calcule une la solution au problème du sac à dos
    pour la liste des objets fournie en argument.
    La valeur de retour est la liste des indices des objets sélectionnés.
    Les objets sont donnés en tant que couples (valeur, poids).
    Il s'agit d'un algorithme naïf testant les 2^n sous-ensembles possibles,
    où n est la taille de la liste en argument."""
    n = len(objets)
    maximum_valeur = 0
    optimum = []
    liste_bool = [0] * n
    liste_bool[-1] = 1 # préparer le premier test
    while True: # arrêté par un return protégé par un test une fois tous les tests effectués, remplaçable par une boucle de taille 2**n - 1
        valeur = 0
        poids = 0
        for i in range(n):
            if liste_bool[i]:
                valeur += objets[i][0]
                poids += objets[i][1]
        if poids <= capacite and valeur > maximum_valeur:
            optimum = [i for i in range(n) if liste_bool[i]]
            maximum_valeur = valeur
        indice = n-1
        liste_bool[indice] += 1
        while indice >= 0 and liste_bool[indice] == 2:
            liste_bool[indice] = 0
            indice -= 1
            liste_bool[indice] += 1
        if indice == -1:
            return optimum

def sac_a_dos(objets, capacite):
    """Calcule la solution au problème du sac à dos pour la liste des objets
    fournie en argument et le poids maximal précisé.
    La valeur de retour est la liste des indices des objets sélectionnés.
    Les objets sont donnés en tant que couples (valeur, poids).
    L'algorithme est bottom-up en fonction des capacités inférieures au poids
    maximum et d'un sous-ensemble des premiers objets (l'ordre n'importe pas).
    """
    n = len(objets)
    toutes_valeurs = [[0 for j in range(capacite+1)] for i in range(n+1)]
    les_objets = [[[] for j in range(capacite+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, capacite+1):
            toutes_valeurs[i][j] = toutes_valeurs[i-1][j] # On ignore l'objet i dans un premier temps
            les_objets[i][j] = les_objets[i-1][j]
            if objets[i-1][1] <= j: # L'objet i-1 n'est pas trop lourd
                test = toutes_valeurs[i-1][j-objets[i-1][1]] + objets[i-1][0] # En incorporant l'objet i-1…
                if toutes_valeurs[i][j] < test: # … c'est mieux !
                    toutes_valeurs[i][j] = test
                    les_objets[i][j] = les_objets[i-1][j-objets[i-1][1]] + [i-1]
    return les_objets[-1][-1]
               
def sac_a_dos_glouton(objets, capacite):
    """Calcule une approximation de la solution au problème du sac à dos
    pour la liste des objets fournie en argument et le poids maximal précisé.
    La valeur de retour est la liste des indices des objets sélectionnés.
    Les objets sont donnés en tant que couples (valeur, poids)."""
    n = len(objets)
    liste_a_trier = [(-valeur / poids, valeur, poids) for (valeur, poids) in objets] # Autre façon de faire le tri
    liste_a_trier.sort()
    liste_triee = [(valeur, poids) for (_, valeur, poids) in liste_a_trier]
    correspondances = []
    for i in range(n):
        correspondances.append(objets.index(liste_triee[i]))
    rep = []
    for i in range(n):
        valeur, poids = liste_triee[i]
        if poids <= capacite:
            rep.append(correspondances[i])
            capacite -= poids
    return rep

## Tests :

### objets = [(4, 3), (9, 6), (11, 5), (12, 9), (11, 7)]
### print(sac_a_dos_glouton(objets, 14))
### print(sac_a_dos(objets, 14))

# Exercice 6

def pgcd(a, b):
    """Calcule le plus grand commun diviseur de deux entiers.
    """
    a, b = max(abs(a), abs(b)), min(abs(a), abs(b))
    if a == 0:
        raise ValueError("a et b sont nuls")
    while b != 0:
        a, b = b, a%b
    return a

def simplifie(couple):
    """Simplifie un couple représentant un rationnel. Il faut avoir
    un dénominateur strictement positif et premier avec le numérateur.
    """
    a, b = couple
    if b == 0:
        raise ValueError("Division par 0")
    if b < 0:
        a, b = -a, -b
    d = pgcd(a, b)
    return (a//d, b//d)

def add(p, q):
    """Addition de deux fractions représentées par des couples d'entiers.
    Le résultat est simplifié.
    """
    a, b = p
    c, d = q
    return simplifie((a*d+b*c, b*d))

def sub(p,q):
    """Soustraction de deux fractions représentées par des couples d'entiers.
    Le résultat est simplifié.
    """
    c, d = q
    return add(p, (-c, d))

def mul(p, q):
    """Multiplication de deux fractions représentées par des couples d'entiers.
    Le résultat est simplifié.
    """
    a, b = p
    c, d = q
    return simplifie((a*c, b*d))
    
def div(p,q):
    """Division de deux fractions représentées par des couples d'entiers.
    Le résultat est simplifié.
    """
    c, d = q
    return mul(p, (d, c)) # la vérification que c != 0 est faite par simplifie

def toutes_operations(p, q):
    """Détermine l'ensemble des valeurs qu'on peut obtenir avec les fractions
    p et q, en incluant d'éventuels doublons et des valeurs nulles.
    Note : on ne conservera jamais de valeur nulle, car c'est inutile
    dans l'optique de la fonction finale.
    """
    return [add(p, q), sub(p, q), sub(q, p), mul(p, q), div(p, q), div(q, p)]

def toutes_chaines(ch1, ch2):
    """Détermine l'ensemble des chaînes de caractères précisant les opérations
    qu'on peut effectuer à partir de deux chaînes, dans le même ordre
    que celui de la fonction toutes_operations.
    """
    ops = "+--*//"
    ch = [ch1, ch2]
    rep = []
    for i in range(6):
        if i % 3 == 2:
            chg, chd = ch2, ch1
        else:
            chg, chd = ch1, ch2
        rep.append("(%s%s%s)"%(chg, ops[i], chd))
    return rep

def initialise_dictionnaire():
    """Initialise un dictionnaire dont les clés sont tous les 1-uplets,
    couples, triplets et quadruplets croissants d'entiers de 1 à 10.
    Les valeurs seront des dictionnaires vides sauf pour les 1-uplets
    où l'on mettra le nombre i représenté par le couple (i, 1) comme clé,
    associé à la chaîne de caractères contenant juste i, et ce pour tout i.
    En pratique, pour les quadruplets, on met une chaîne de caractères
    signalant l'absence de solution par défaut.
    """
    d = {}
    for i in range(1, 11):
        d[(i, )] = { (i, 1) : str(i)}
        for j in range(i, 11):
            d[(i, j)] = {}
            for k in range(j, 11):
                d[(i, j, k)] = {}
                for l in range(k, 11):
                    d[(i, j, k, l)] = "Pas de solution" # Pour quatre, cela va encore, pas besoin d'optimiser l'écriture du programme…
    return d

def initialise_dictionnaire2(d):
    """Met à jour les entrées du dictionnaire d associées à des couples.
    Le dictionnaire d a été obtenu par initialise_dictionnaire()
    et on considère toutes les opérations possibles entre les deux éléments
    des couples.
    """
    for i in range(1, 11):
        for j in range(i, 11):
            to = toutes_operations((i, 1), (j, 1))
            tc = toutes_chaines(str(i), str(j))
            for ind in range(len(to)):
                if to[ind][0] != 0: # on retire les éventuels zéros
                    d[(i, j)][to[ind]] = tc[ind]

def initialise_dictionnaire3(d):
    """Met à jour les entrées du dictionnaire d associées à des triplets.
    Le dictionnaire d a été obtenu par initialise_dictionnaire()
    et mis à jour par initialise_dictionnaire2(d),
    et on considère toutes les opérations possibles entre un résultat
    d'opération entre deux éléments des triplets et le troisième élément.
    Note : on ne créera jamais la valeur 0, car elle est inutile dans l'optique
    de la fonction finale.
    """
    for i in range(1, 11):
        for j in range(i, 11):
            for k in range(1, 11): # tant pis pour les redondances, on évite le copier-coller (ou une boucle de taille 3 sur l'indice de l'élément isolé)
                cle = tuple(sorted([i, j, k]))
                for (num, den) in d[(i, j)]:
                    to = toutes_operations((num, den), (k, 1))
                    tc = toutes_chaines(d[(i, j)][(num, den)], str(k))
                    for ind in range(len(to)):
                        if to[ind][0] != 0:
                            d[cle][to[ind]] = tc[ind]
                    
def vingt_quatre():
    """Construit le dictionnaire résolvant le jeu vingt-quatre.
    Pour tous les quadruplets d'entiers croissants, une opération possible
    est fournie si elle existe (sinon l'entrée du dictionnaire le signale).
    """
    d = initialise_dictionnaire()
    initialise_dictionnaire2(d)
    initialise_dictionnaire3(d)
    for i in range(1, 11):
        for j in range(i, 11):
            for k in range(j, 11):
                for l in range(1, 11): # triplet vs. quatrième
                    cle = tuple(sorted([i, j, k, l]))
                    for (num, den) in d[(i, j, k)]:
                        to = toutes_operations((num, den), (l, 1))
                        tc = toutes_chaines(d[(i, j, k)][(num, den)], str(l))
                        for ind in range(len(to)):
                            if to[ind] == (24, 1):
                                d[cle] = tc[ind]
    for i in range(1, 11):
        for j in range(i, 11):
            for k in range(1, 11):
                for l in range(k, 11): # deux couples
                    cle = tuple(sorted([i, j, k, l]))
                    for (num, den) in d[(i, j)]:
                        for (num2, den2) in d[(k, l)]:
                            to = toutes_operations((num, den), (num2, den2))
                            tc = toutes_chaines(d[(i, j)][(num, den)], d[(k, l)][(num2, den2)])
                            for ind in range(len(to)):
                                if to[ind] == (24, 1):
                                    d[cle] = tc[ind]
    return d

## Tests :

### d = vingt_quatre() # Au passage, 598 des 715 instances seulement ont une solution
### print(d[(3, 3, 8, 8)]) # Attention, spoiler, c'est un cas difficile !