"""
Cours Programmation dynamique (chapitre 3)
Mercredis 9 & 16 octobre 2024
"""

from time import *


## k parmi n
def cb_rec(k,n):
    """
    k, n : entiers
    fonction récursive
    """
    if k==n or k==0:
        return 1
    elif k==1:
        return n
    else: # appels récursifs, utilisation de la relation de récurrence
        return cb_rec(k-1,n-1)+cb_rec(k,n-1)


t0=time()
a=cb_rec(15,30)
tf=time()
print("Durée d'exécution en naïf : ",tf-t0)
# pour 13 parmi 26 : 2.06 seconde (ça dépend bien sûr de ce qui tourne par ailleurs !) ;  32.71 s pour 15 parmi 30

## Par mémoïsation : de haut en bas

def cb_mem(k,n,dico={}):
    """
    k, n : entiers
    dico : dictionnaire qui contient les valeurs déjà calculées
    c : valeur de k parmi n
    """
    if (k,n) in dico: # il a déjà été calculé, on renvoie la valeur
        return dico[(k,n)]
    # on traite les cas où la valeur n'a pas déjà été calculées
    elif k==n or k==0:
        c=1
    elif k==1:
        c=n
    else:
        c=cb_mem(k-1,n-1)+cb_mem(k,n-1) # appels récursifs
    dico[(k,n)]=c # on ajoute  la valeur au dictionnaire
    return c



def cb_mem2(k,n):
    dico={}
    def cb(i,j):
        if (i,j) in dico: # il a déjà été calculé, on renvoie la valeur
           return dico[(i,j)]
    # on traite les cas où la valeur n'a pas déjà été calculées
        elif i==j or i==0:
            c=1
        elif i==1:
            c=j
        else:
            c=cb_mem(i-1,j-1)+cb_mem(i,j-1) # appels récursifs
        dico[(i,j)]=c # on ajoute  la valeur au dictionnaire
        return c
    return cb(k,n)



t0=time()
a=cb_mem2(15,30)
tf=time()
print("Durée d'exécution de haut en bas : ",tf-t0) # 0.0

##  de bas en haut
def cb_asc(k,n):
    tab=[[0 for j in range(k+1)] for i in range(n+1)]
    for i in range(0,n+1):
        for j in range(0,k+1):
            if j==0 or j==i:
                tab[i][j]=1
            else:
                tab[i][j]=tab[i-1][j-1]+tab[i-1][j]
    return tab[n][k]


t0=time()
a=cb_asc(15,30)
tf=time()
print("Durée d'exécution de bas en haut : ",tf-t0) # 0.0


## Levenhstein


## De haut en bas

def de_mem(ch1,ch2,dico={}):
    """
    dico : dictionnaire qui stocke pour chaque couple de chaines pouvant être testée la distance {(a,b):de(a,b),...}
    """
    n1,n2=len(ch1),len(ch2)
    if (ch1,ch2) in dico: # la distance a déjà été calculée
        return dico[(ch1,ch2)] # on renvoie la valeur déjà calculée
    else :
        if n1==0 or n2==0:
            d=max(n1,n2) # si l'une des deux est vide, la distance d'édition est la longueur de l'autre chaine
        elif ch1[0]==ch2[0]:
            d=de_mem(ch1[1:],ch2[1:],dico) # deux caractères identiques, la de est la distance entre les deux chaines privées de leur premier élément
        else: # on cherche la distance minimale entre les trois possibilités :
            a=de_mem(ch1[1:],ch2,dico) # supprime ch1[0]
            b=de_mem(ch1,ch2[1:],dico) #  insertion de ch2[1:]
            c=de_mem(ch1[1:],ch2[1:],dico) # substitution de ch1[0] et ch2[0]
            d=1+min(a,b,c)
        dico[(ch1,ch2)]=d # on ajoute l'élément constitué de la clé (ch1,ch2) et de valeur, la distance calculée entre ch1 et ch2
        return dico[(ch1,ch2)]


## De bas en haut

def de_bas_haut(ch1,ch2):
    n1,n2=len(ch1),len(ch2)
    T=[[0 for j in range(n2+1)] for i in range(n1+1)] # tableau que l'on va compléter
    for i in range(n1+1):
        T[i][0]=i # si ch2 vide : distance d'édition = lg de ch1[0:i]
    for j in range(n2+1):
        T[0][j]=j # si ch1 vide : distance d'édition = lg de ch2[0:j]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            if ch1[i-1]==ch2[j-1]: # caractère identique
            # attention décalage entre le rang dans la chaine de caractère et le rang dans le tableau
                T[i][j]=T[i-1][j-1] # la distance d'édition est celle qui sépare les deux chaînes de caractères jusqu'à i-1, et j-1
            else: # on cherche la distance minimale entre
                a=T[i-1][j] # suppression
                b=T[i][j-1] # insertion
                c=T[i-1][j-1] # substitution
                T[i][j]=1+min(a,b,c)
    return T[n1][n2]


##  Reconstitution de la solution

def de_tab(ch1,ch2):
    n1,n2=len(ch1),len(ch2)
    T=[[0 for j in range(n2+1)] for i in range(n1+1)] # tableau que l'on va compléter
    for i in range(n1+1):
        T[i][0]=i # si ch2 vide : distance d'édition = lg de ch1[0:i]
    for j in range(n2+1):
        T[0][j]=j # si ch1 vide : distance d'édition = lg de ch2[0:j]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            if ch1[i-1]==ch2[j-1]: # caractère identique
            # attention décalage entre le rang dans la chaine de caractère et le rang dans le tableau
                T[i][j]=T[i-1][j-1] # la distance d'édition est celle qui sépare les deux chaînes de caractères jusqu'à i-1, et j-1
            else: # on cherche la distance minimale entre
                a=T[i-1][j] # suppression
                b=T[i][j-1] # insertion
                c=T[i-1][j-1] # substitution
                T[i][j]=1+min(a,b,c)
    return T


def de_sol(ch1,ch2):
    n1,n2=len(ch1),len(ch2)
    # 1ère étape : construire le tableau
    T=[[0 for j in range(n2+1)] for i in range(n1+1)] # tableau que l'on va compléter
    for i in range(n1+1):
        T[i][0]=i # si ch2 vide : distance d'édition = lg de ch1[0:i]
    for j in range(n2+1):
        T[0][j]=j # si ch1 vide : distance d'édition = lg de ch2[0:j]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            if ch1[i-1]==ch2[j-1]: # caractère identique
            # attention décalage entre le rang dans la chaine de caractère et le rang dans le tableau
                T[i][j]=T[i-1][j-1] # la distance d'édition est celle qui sépare les deux chaînes de caractères jusqu'à i-1, et j-1
            else: # on cherche la distance minimale entre
                a=T[i-1][j] # suppression
                b=T[i][j-1] # insertion
                c=T[i-1][j-1] # substitution
                T[i][j]=1+min(a,b,c)
    # 2è étape : remonter
    # sol=[]
    dep=[]
    i,j=n1,n2
    while i>0 and j>0:
        if T[i-1][j-1]==T[i][j]-1:
                # op=f"substitution de {ch1[i-1]} par {ch2[j-1]}"
                # ch=ch1[:i-1]+ch2[j-1]+ch1[i:]
                # sol.append((op,ch))
                i=i-1
                j=j-1
                dep.append("subs")
        elif T[i-1][j]==T[i][j]-1:
                # op=f"suppression de {ch1[i-1]}"
                # ch=ch1[:i-1]+ch1[i:]
                # sol.append((op,ch))
                i=i-1 # vers le haut
                dep.append("sup")
        elif T[i][j-1]==T[i][j]-1:
                # op=f"insertion de {ch2[j-1]}"
                # ch=ch1[:i-1]+ch2[j-1]+ch1[i-1:]
                # sol.append((op,ch))
                j=j-1 # vers la gauche
                dep.append("i")
        elif T[i-1][j-1]==T[i][j]: # il faut effectuer un changement !
            i=i-1
            j=j-1
            dep.append("r")
    if i==0:
        while j!=0:
            j=j-1 # vers la gauche
            dep.append("i")
    if j==0:
        while i!=0:
            i=i-1 # vers le haut
            dep.append("sup")
    print(dep)
    # 3è étape : solution
    dep=dep[::-1]
    sol=[]
    i,j=0,0
    for k in range(len(dep)):
        if dep[k]=="subs":
            i+=1
            j+=1
            op=f"substitution de {ch1[i-1]} par {ch2[j-1]}"
            ch=ch1[:i-1]+ch2[j-1]+ch1[i:]
            sol.append((op,ch))
        elif dep[k]=="sup":
            i+=1
            op=f"suppression de {ch1[i-1]}"
            if j>0:
                ch=ch1[:i-1]+ch1[i:]
            else:
                ch=ch1[1:]
            sol.append((op,ch))
        elif dep[k]=="i":
            j=j+1
            op=f"insertion de {ch2[j-1]}"
            if i>0:
                ch=ch1[:i-1]+ch2[j-1]+ch1[i-1:]
            else:
                ch=ch2[j-1]+ch1
            sol.append((op,ch))
        else:
            i+=1
            j+=1
            op=f"rien"
            c=ch1[:i-1]+ch2[j-1]
            sol.append((op,ch))
        print(k,op)
    return dep,sol






def de_sol2(ch1,ch2):
    n1,n2=len(ch1),len(ch2)
    T=de_tab(ch1,ch2)
    dep=[]
    i,j=n1,n2
    while i>0 and j>0:
        if T[i-1][j-1]==T[i][j]-1:
                op=f"substitution de {ch1[i-1]} par {ch2[j-1]}"
                i=i-1
                j=j-1
                dep.append((1,1,op))
        elif T[i-1][j]==T[i][j]-1:
                op=f"suppression de {ch1[i-1]}"
                i=i-1 # vers le haut
                dep.append((1,0,op))
        elif T[i][j-1]==T[i][j]-1:
                op=f"insertion de {ch2[j-1]}"
                j=j-1 # vers la gauche
                dep.append((0,1,op))
        elif T[i-1][j-1]==T[i][j]: # il faut effectuer un changement !
            op=f"{ch1[i-1]} inchangé"
            i=i-1
            j=j-1
            dep.append((1,1,op))
    while j!=0:
            op=f"insertion de {ch2[j-1]}"
            j=j-1 # vers la gauche
            dep.append((0,1,op))
    while i!=0:
            op=f"suppression de {ch1[i-1]}"
            i=i-1 # vers le haut
            dep.append((1,0,op))
    # 3è étape : solution
    dep=dep[::-1]
    sol=[]
    i,j=0,0
    for k in range(len(dep)):
        di,dj,op=dep[k]
        i=i+di
        j=j+dj
        sol.append(op)
    return 'la liste des opérations est :' ,sol, '; il y a ' , T[n1][n2], 'opérations à effectuer'





def de_sol3(ch1,ch2):
    n1,n2=len(ch1),len(ch2)
    T=de_tab(ch1,ch2)
    dep=[]
    i,j=n1,n2
    while i>0 and j>0:
        if ch1[i-1]==ch2[j-1] and T[i-1][j-1]==T[i][j]: # pas de changement
            op=f"{ch1[i-1]} inchangé"
            i=i-1
            j=j-1
            dep.append((1,1,op))
        # il y a des changements nécessaires, on cherche lequel
        elif T[i-1][j-1]==T[i][j]-1:
                op=f"substitution de {ch1[i-1]} par {ch2[j-1]}"
                i=i-1
                j=j-1
                dep.append((1,1,op))
        elif T[i-1][j]==T[i][j]-1:
                op=f"suppression de {ch1[i-1]}"
                i=i-1 # vers le haut
                dep.append((1,0,op))
        elif T[i][j-1]==T[i][j]-1:
                op=f"insertion de {ch2[j-1]}"
                j=j-1 # vers la gauche
                dep.append((0,1,op))
    while j!=0:
            op=f"insertion de {ch2[j-1]}"
            j=j-1 # vers la gauche
            dep.append((0,1,op))
    while i!=0:
            op=f"suppression de {ch1[i-1]}"
            i=i-1 # vers le haut
            dep.append((1,0,op))
    # 3è étape : solution
    dep=dep[::-1]
    sol=[]
    i,j=0,0
    for k in range(len(dep)):
        di,dj,op=dep[k]
        i=i+di
        j=j+dj
        sol.append(op)
    return sol




## Rendu de monnaie


# prog dynamique de haut en bas (récursif avec mémoïsation)

def rendu_mem(p:list,s:int,i:int,d={}):
    """
    p : liste des pièces du système de monnaie
    s : somme à rendre (entier)
    i : on utilise les i premières pièces pour rendre s
    d : dictionnaire qui sert à la mémoïsation
    """
    if (i,s) not in d: # solution non encore calculée
        if s==0: # la somme à rendre est nulle
            c=0
        elif i==1: # on n'utilise que la 1ère pièce
            c=s
        elif p[i-1]<=s: # la pièce p_{i-1} peut être rendue
            a=rendu_mem(p,s,i-1,d) # on rend la somme s sans utiliser la pièece p_{i-1}
            b=rendu_mem(p,s-p[i-1],i,d)+1 # on rend la somme s en utilisant une pièce p_{i-1}
            c=min(a,b)
        else: # la pièce p_{i-1} ne peut pas être rendue
            c=rendu_mem(p,s,i-1,d)
        d[(i,s)]= c              # on garde en mémoire la  solution déterminée ici
    return d[(i,s)]




pieces=[1,2,5,10,20,50,100,200]





def rendu_asc(p,S):
    """
    p : liste des pièces du système de monnaie
    S : somme à rendre
    """
    n=len(p) # nombre de pièces à rendre
    tab=[ [0 for s in range(S+1) ] for i in range(n)] # tableau de n lignes et de S+1 colonnes
    for s in range(1,S+1): # on ne rend que la première pièce
        tab[0][s]= s
    for i in range(1,n): # remplissage des lignes
        for s in range(1,S+1): # remplissage des colonnes
            if p[i]<=s:
                a= tab[i][s-p[i]]+1 # on rend une pièce p[i]
                b= tab[i-1][s]        # on rend la somme s sans utiliser p[i]
                tab[i][s]=min(a,b) # on choisit la meilleure solution
            else: # on ne peut pas rendre la pièce p[i]
                tab[i][s]= tab[i-1][s]  # on rend la somme s avec les pièces jusqu'à i-1
    return tab[n-1][S]    # la solution du problème




def rendu_asc_tab(p,S):
    """
    p : liste des pièces du système de monnaie
    S : somme à rendre
    """
    n=len(p) # nombre de types de pièces dans le syst de monnaie
    tab=[ [0 for s in range(S+1) ] for i in range(n)] # tableau de n lignes et de S+1 colonnes
    for s in range(1,S+1): # on n'utilise que la première pièce
        tab[0][s]= s
    for i in range(1,n): # remplissage des lignes
        for s in range(1,S+1): # remplissage des colonnes
            if p[i]<=s:
                a= tab[i][s-p[i]]+1 # on rend une pièce p[i]
                b= tab[i-1][s]        # on rend la somme s sans utiliser p[i]
                tab[i][s]=min(a,b) # on choisit la meilleure solution
            else: # on ne peut pas rendre la pièce p[i]
                tab[i][s]= tab[i-1][s]  # on rend la somme s avec les pièces jusqu'à i-1
    return tab  # la solution du problème

## Solution optimale
pieces=[1,3,4]
arendre={pi:0 for pi in pieces }
somme=6
i=len(pieces)-1
s=somme
tab=rendu_asc_tab(pieces,somme)
while s>0:
    pi=pieces[i]
    if tab[i][s-pi]+1<tab[i-1][s]:
        arendre[pi]=arendre[pi]+1
        s=s-pi
    else:
        i=i-1
print(arendre)