# -*- coding: utf-8 -*-

# Correction du TP 3


# Exercice 1

#1.
def sommeCarre(n):
    if n <= 0:
        return(0)
    else:
        return n**2 + sommeCarre(n-1)
#print(sommeCarre(4))

#2.        
def compter(n):
    if n >= 1:
        compter(n-1)
        print(n)
#compter(4)

#3.
def rebours(n):
    if n >= 0:
        print(n)
        rebours(n-1)
#rebours(4)


# Exercice 2

# Question 1

def F(n):
    if n<=1:
        return 1
    return F(n-1)+F(n-2)

# Une version qui compte le nombre d'appels à la fonction F:
compt=[0]
def F(n):
    compt[0]+=1
    if n<=1:
        return 1
    return F(n-1)+F(n-2)

compt=[0]
print("La valeur de F_20 sans mémoïsation:",F(20))
print("Cela a nécessité",compt[0],"appels.")

compt=[0]
print("La valeur de F_30 sans mémoïsation:",F(30))
print("Cela a nécessité",compt[0],"appels.")

compt=[0]
print("La valeur de F_32 sans mémoïsation:",F(32))
print("Cela a nécessité",compt[0],"appels.")


# Question 2

D={} #Dictionnaire de mémoïsation
def Fb(n):
    if n not in D:
        if n==0 or n==1:
            D[n] = 1 # On rentre la valeur dans le dico.
        else:
            D[n] = Fb(n-1)+Fb(n-2) # On rentre la valeur dans le dico.
    return D[n] # On renvoie la valeur

print("La valeur de F_100 avec mémoïsation:",Fb(100)) #calcul bien plus rapide


#%%%
#EXERCICE 3

T=[[3],
   [7,4],
   [2,4,6],
   [8,5,9,3]]

# Question 1
# a)
T=[[3],
   [10,7],
   [12,14,13],
   [20,19,23,16]]

# b)
# T[i][0]=T[i-1][0]+T[i][0]
# T[i][i]=T[i-1][i-1]+T[i][i]

# c)
# T[i][j]=max(T[i-1][j]+T[i][j],T[i-1][j-1]+T[i][j])

# Question 2

T=[[3],
   [7,4],
   [2,4,6],
   [8,5,9,3]]

def Chemin_max(T):
    for i in range(1,len(T)):
        T[i][0]=T[i-1][0]+T[i][0]
        T[i][i]=T[i-1][i-1]+T[i][i]
        for j in range(1,len(T[i])-1):
            T[i][j]=T[i][j]+max(T[i-1][j],T[i-1][j-1])
    return max(T[-1])

print("Le total maximum des chemins possibles est :",Chemin_max(T))


#%%%
#EXERCICE 4

#QUESTION 1
#a) Si s ou t est de longueur nulle alors longueur(s,t) = 0

#b) longueur(s,t) = longueur(s[:-1],t[:-1])+1

#c) longueur(s,t) = max(longueur(s[:-1],t),longueur(s,t[:-1]))

D={}

def longueur(s,t):
    if (s,t) not in D:
        if s=="" or t=="":
            D[(s,t)]=0
        elif s[-1]==t[-1]:
            D[(s,t)]=longueur(s[:-1],t[:-1])+1
        else:
            D[(s,t)]=max(longueur(s[:-1],t),longueur(s,t[:-1]))
    return D[(s,t)]
    
print("La plus longue sous-séquence commune entre circonstance et importance\
      a pour longueur",longueur("circonstance","importance"))

#%%%

#QUESTION 2

def PLSC(s,t):
    if s=="" or t=="":
        return ""
    if s[-1]==t[-1]:
        return PLSC(s[:-1],t[:-1]) + s[-1]
    if longueur(s[:-1],t)>longueur(s,t[:-1]):
        return PLSC(s[:-1],t)
    else:
        return PLSC(s,t[:-1])

D={}

print("Une plus longue sous-séquence commune entre circonstance et importance\
      est :",PLSC("circonstance","importance"))  

#%%%

#QUESTION 3

fichier=open("ListeMots.txt", "r")
Liste=fichier.readlines()
fichier.close()

m=0
for i in range(len(Liste)):    
    for j in range(i+1,len(Liste)):
        mota,motb=Liste[i][:-1],Liste[j][:-1] # On enlève le \n à la fin
        l=longueur(mota,motb)
        if l>m:
            m,i0,j0=l,mota,motb

print("Les mots du dictionnaire qui ont la plus longue sous séquence commune sont:",i0,j0)
print("La longueur de la sous-séquence commune est",m)
print("Cette sous-séquence commune est",PLSC(i0,j0))

#%%%
#EXERCICE 5

T=[[3],
   [7,4],
   [2,4,6],
   [8,5,9,3]]


def Chemin_max(T):
    for i in range(1,len(T)):
        T[i][0]=T[i-1][0]+T[i][0]
        T[i][i]=T[i-1][i-1]+T[i][i]
        for j in range(1,len(T[i])-1):
            T[i][j]=max(T[i-1][j]+T[i][j],T[i-1][j-1]+T[i][j])
    return max(T[-1])

print(Chemin_max(T))

chemin=[]
M=max(T[len(T)-1])
for j in range(len(T)-1):
    if T[len(T)-1][j]==M:
        chemin.append((len(T)-1,j))
        j0=j

print("M=",M)
print("j0 =",j0)

for i in range(2,len(T)+1):
    if j0==0:
        chemin.append((len(T)-i,j0))
    elif j0==len(T)-i+1:
        chemin.append((len(T)-i,j0-1))
        j0=j0-1
    elif T[len(T)-i][j0]>T[len(T)-i][j0-1]:
        chemin.append((len(T)-i,j0))
    else:
        chemin.append((len(T)-i,j0-1))
        j0=j0-1

print(chemin[::-1])

#%%%
#EXERCICE 6

T=[[3],
   [7,4],
   [2,4,6],
   [8,5,9,3]]

D={}

def Valeur(T,i,j):
    if (i,j) not in D:
        if (i,j)==(0,0):
            return T[0][0]
        else:
            if j==0:
                D[(i,0)]=Valeur(T,i-1,0)+T[i][0]
            elif j==i:
                D[(i,i)]=Valeur(T,i-1,i-1)+T[i][i]
            else:
                D[(i,j)]=max(Valeur(T,i-1,j-1)+T[i][j],Valeur(T,i-1,j)+T[i][j])
    return D[(i,j)]

print("Le poids total max d'un chemin vaut :",max([Valeur(T,len(T)-1,j) for j in range(len(T)-1)]))