#### TP n°7: Algorithmes à boucles imbriquées ####
#################


### SOMMES ET PRODUITS DOUBLES, TRIPLES, … ###
## Question 1 
import math
n=50
somme=0
for i in range(4,n+1):
    for j in range(2,n+4):
        somme=somme+math.sqrt(i+j)
print("La valeur numérique de la somme est : "+str(somme))
## Question 2 
somme=0
for i in range(4,11):
    for j in range(9,16):
        for k in range(5,29):
            somme=somme+1/(i+j+k)
print("La valeur numérique de la somme est : "+str(somme))
## Question 3 
import math
produit=1
for i in range(3,12):
    for j in range(4,13):
        produit=produit*math.tan(i+j)
print("La valeur numérique du produit est : "+str(produit))
### EXEMPLE DE SOMMES DOUBLES: LA TRANSFORMÉE DE FOURIER DISCRÈTE ###


## Question 4 
import cmath # librairie de manipulation des nombres complexes

def DFT(temps,signal):
    N=len(signal)
    Deltat=temps[-1]-temps[0] # durée du signal
    liste_freq=[] # liste contenant les fréquences fk
    liste_amp=[] # liste contenant les amplitudes |ŝ|
    # boucle calculant pour chaque valeur de k la fréquence fk et l'amplitude |ŝ(fk)|
    for k in range(N//2):
        f=k/Deltat
        liste_freq.append(f)
        s=0
        for n in range(N):
            s=s+signal[n]*cmath.exp(-1j*2*cmath.pi*k*n/N)
        liste_amp.append(abs(s))
    return liste_freq,liste_amp
lf,la=DFT(tab_t,tab_s)
plt.figure()
plt.plot(lf,la)
plt.show()
### COEFFICIENTS BINOMIAUX ###

## Question 5 
N=10
Lcb=[ [1] ]
for n in range(N):
    liste=[1]
    for p in range(1,n+1):
        liste.append(Lcb[n][p-1]+Lcb[n][p])
    liste.append(1)
    Lcb.append(liste)
for n in range(N+1):
    print(Lcb[n])
### CHEMINS AUTO-ÉVITANT ###


## Question 6 
def est_cae(chemin):
    """ teste si un chemin est auto-évitant """
    for i in range(len(chemin)):
        for j in range(i+1,len(chemin)):
            if chemin[i]==chemin[j]:
                return False
    return True
print(est_cae(chemin1))
print(est_cae(chemin2))
print(est_cae(chemin3))
print(est_cae(chemin4))
## Question 7 
def compte_intersections(chemin):
    """ compte le nombre d'auto-intersections d'un chemin """
    compteur=0
    for i in range(len(chemin)):
        for j in range(i+1,len(chemin)):
            if chemin[i]==chemin[j]:
                compteur=compteur+1
    return compteur
print(compte_intersections(chemin1))
print(compte_intersections(chemin2))
print(compte_intersections(chemin3))
print(compte_intersections(chemin4))
### RECHERCHE DES VALEURS LES PLUS PROCHES D'UNE LISTE ###

## Question 8 
def ecart_min(L):
    """ Cette fonction prend comme argument une liste numérique à plus de 2 éléments
        et recherche le couple de valeurs les plus proches dans cette liste
        renvoie: le couple d'indices de ces valeurs """
    i_proche,j_proche=0,1
    for i in range(len(L)):
        for j in range(len(L)):
            if j!=i and abs(L[i]-L[j])< abs(L[i_proche]-L[j_proche]):
                i_proche=i
                j_proche=j
    return (i_proche,j_proche)
## Test de la fonction `ecart_min`; **à exécuter sans éditer**
ok=True
if not(sorted(ecart_min([1,2,4,5,-2,0,0.1]))==[5,6]): ok=False
if not(sorted(ecart_min([-100000,100000]))==[0,1]): ok=False
if ok:
    print("Fonction ecart_min: test réussi!")
else:
    print("Fonction ecart_min: test échoué!")
## Question 9 : Recherche des deux points les plus proches

def distance(x1,y1,x2,y2):
    """ calcule la distance entre deux points
    arguments: x1,y1: les coordonnées du premier point
               x2,y2: les coordonnées du second point
    renvoie: la distance entre les deux points """
    return np.sqrt((x1-x2)**2+(y1-y2)**2)
def plus_proches_points(lx,ly):
    """ recherche dans une liste de coordonnées les deux points les plus proches
    arguments: lx,ly: la liste des coordonnées des points
    renvoie: les indices des deux points les plus proches """
    i_proche,j_proche=0,1
    for i in range(len(lx)):
        for j in range(len(lx)):
            if j!=i and distance(lx[i],ly[i],lx[j],ly[j])<distance(lx[i_proche],ly[i_proche],lx[j_proche],ly[j_proche]):
                i_proche=i
                j_proche=j
    return i_proche,j_proche
ip,jp=plus_proches_points(listex,listey)
print("Les deux points les plus proches sont ("+str(listex[ip])+","+str(listey[ip])+") et ("+str(listex[jp])+","+str(listey[jp])+") à une distance "+str(distance(listex[ip],listey[ip],listex[jp],listey[jp])))
### RECHERCHE D'UN MOTIF ###

## Question 10 
def motif_present(texte,i,motif):
    """ Renvoie si le motif se trouve dans le texte à la position i """
    pareil=True
    for j in range(len(motif)):
        if texte[i+j]!=motif[j]:
            pareil=False
    return pareil
## Question 11 
def position_motif(texte,motif):
    """ recherche si la chaîne de caractères motif se trouve dans la chaîne texte
    si oui, la fonction renvoie l'indice de la position de la première occurrence trouvée
    sinon, elle renvoie -1 """
    l_texte=len(texte)
    l_motif=len(motif)
    for i in range(l_texte-l_motif+1):
        if motif_present(texte,i,motif):
            return i
    return -1
print(position_motif("abracadabra","brac"))
## Test de la fonction `position_motif`; **à exécuter sans éditer**
ok=True
if not(position_motif("Ceci est une phrase de test","un")==9): ok=False
if not(position_motif("Ceci est une phrase de test","tz")==-1): ok=False
if not(position_motif("Ceci est une phrase de test","test")==23): ok=False
if not(position_motif("Ceci est une phrase de test","nnnn")==-1): ok=False
if ok:
    print("Fonction position_motif: test réussi!")
else:
    print("Fonction position_motif: test échoué!")
## Question 12 
def nombre_motif(texte,motif):
    """ recherche si la chaîne de caractères motif se trouve dans la chaîne texte
    elle renvoie le nombre de fois que le motif a été trouvé """
    l_texte=len(texte)
    l_motif=len(motif)
    nb=0
    for i in range(l_texte-l_motif+1):
        if motif_present(texte,i,motif):
            nb=nb+1
    return nb
print(nombre_motif("abracadabra","bra"))
## Test de la fonction `nombre_motif`; **à exécuter sans éditer**
ok=True
if not(nombre_motif("Ceci est une phrase de test","un")==1): ok=False
if not(nombre_motif("Ceci est une phrase de test","est")==2): ok=False
if not(nombre_motif("Ceci est une phrase de test","nnnn")==0): ok=False
if ok:
    print("Fonction nombre_motif: test réussi!")
else:
    print("Fonction nombre_motif: test échoué!")
## Question 13 
def positions_motif(texte,motif):
    """ recherche si la chaîne de caractères motif se trouve dans la chaîne texte
    elle renvoie la liste des indices où le motif a été trouvé """
    rep=[]
    l_texte=len(texte)
    l_motif=len(motif)
    for i in range(l_texte-l_motif+1):
        if motif_present(texte,i,motif):
            rep.append(i)
    return rep
print(positions_motif("abracadabra","bra"))


## Question 14 
def dico_distances(motif):
    """ pré-traitement du motif """""
    dico={}
    n=len(motif)
    for j in range(n-1):
        dico[motif[j]]=n-1-j
    return dico
print(dico_distances("carapace"))
## Question 15 
def positions_motif2(texte,motif):
    """ recherche si la chaîne de caractères motif se trouve dans la chaîne texte
    elle renvoie la liste des indices où le motif a été trouvé """
    rep=[]
    l_texte=len(texte)
    l_motif=len(motif)
    dico=dico_distances(motif)
    i=0
    while i<l_texte-l_motif+1:
        if motif_present(texte,i,motif):
            rep.append(i)
        lettre=texte[i+l_motif-1]
        if lettre in dico:
            i=i+dico[lettre]
        else:
            i=i+len(motif)
    return rep
print(positions_motif2("abracadabra","bra"))

import time
debut=time.time()
l=positions_motif2(texte,"canon")
fin=time.time()
print("La recherche des positions du mot canon a pris "+str(fin-debut)+"s")
print(str(len(l))+" occurences trouvées")
### PLUS LONGUE SOUS-LISTE CROISSANTE ###
## Question 16 
def extrait_ssc(liste,i):
    """ renvoie la plus longue sous-suite croissante de liste à partir de la position i """
    ssc=[]
    ssc.append(liste[i])
    j=1
    while i+j<len(liste) and liste[i+j]>=liste[i+j-1]:
        ssc.append(liste[i+j])
        j=j+1
    return ssc

def plssc(liste):
    """ extrait la plus longue sous suite croissante d'une liste """
    best=[]
    for i in range(len(liste)):
        ssc=extrait_ssc(liste,i)
        if len(ssc)>len(best):
            best=ssc
    return best
print(plssc([1,4,3,5,6,7,5,3,-1,3,-2,3,4,2,3,5,2,3,6,8,9,7,6,2]))
### COMPRESSIONS ###

## Question 17 
def encode(liste):
    code=[]
    i=0 
    while i<len(liste):
        v=liste[i]
        n=1
        while i+n<len(liste) and liste[i+n]==liste[i]:
            n=n+1
        code.append([v,n])
        i=i+n
    return code 

l=[0,0,0,1,1,0,0,0,0,0,0,0,2,0,0,1,1,1,1,1]
print(encode(l))
## Question 18 
def decode(code):
    liste=[]
    for i in range(len(code)):
        v=code[i][0]
        n=code[i][1]
        for j in range(n):
            liste.append(v)
    return liste
print(decode([[0, 3], [1, 2], [0, 7], [2, 1], [0, 2], [1, 5]]))

## Question 19 
texte1="Abracadabra la mare a plein de tétards, ha ha"
texte2="Portez ce vieux whisky au juge blond qui fume"
def dico_comptage(texte):
    """ crée un dictionnaire de comptage des lettres """
    dico={}
    for i in range(len(texte)):
        lettre=texte[i]
        if lettre in dico:
            dico[lettre]+=1
        else:
            dico[lettre]=1
    return dico
print(dico_comptage(texte1))
print(dico_comptage(texte2))
## Question 20 
def cle_min(dico):
    """ cherche dans un dictionnaire d'occurences la lettre qui apparaît le moins souvent """
    min=float("inf")
    kmin=None
    for k in dico.keys():
        if dico[k]<min:
            min=dico[k]
            kmin=k
    return kmin
print(cle_min(dico_comptage(texte1)))
## Question 21 
def codage_huffman(texte):
    """ crée le codage de Huffman d'un texte """
    comptage=dico_comptage(texte)
    codage={}
    for k in comptage.keys():
        codage[k]=""
    while len(comptage)>1:
        kmin1=cle_min(comptage)
        v1=comptage[kmin1]
        del comptage[kmin1]
        kmin2=cle_min(comptage)
        v2=comptage[kmin2]
        del comptage[kmin2]
        for l in kmin1:
            codage[l]="0"+codage[l]
        for l in kmin2:
            codage[l]="1"+codage[l]
        comptage[kmin1+kmin2]=v1+v2
    return codage
print(codage_huffman(texte1))
print(codage_huffman(texte2))
## Question 22 
def encode_huffman(texte):
    """ encode un texte par codage de Huffman """
    codage=codage_huffman(texte)
    code=""
    for i in range(len(texte)):
        lettre=texte[i]
        c=codage[lettre]
        code=code+c
    return code
print(len(encode_huffman(texte1)))
print(len(encode_huffman(texte2)))
### RECHERCHE DE RÉPÉTITIONS ###
## Question 23 : recherche de répétitions
def index_repetitions(chaine,periode,longueur):
    """ recherche un motif qui est répété dans une chaine
    arguments: chaine: la chaine de caractères où on cherche
               periode: la période de répétition du motif
               longueur: la longueur du motif
    renvoie: l'index du premier motif trouvé """
    for i in range(len(chaine)-longueur-periode):
        idem=True
        for j in range(longueur):
            if chaine[i+j]!=chaine[i+j+periode]:
                idem=False
        if idem:
            return i
    return -1
st,per,l="ucabcucbabcbbcabcuabc",12,4
i=index_repetitions(st,per,l)
print(st[i:i+l])
## Question 24 
def cherche_repetitions(chaine,longueur):
    """ cherche dans une chaine des motifs de longueur fixés répétés au bout d'une période multiple de 3
    arguments: chaine: la chaine de caractères où on cherche
               longueur: la longueur du motif recherché
    renvoie: l'index de début du motif, et la période trouvée; renvoie (-1,-1) si rien n'est trouvé """
    for p in range(3,(len(chaine)-longueur),3):
        i=index_repetitions(chaine,p,longueur)
        if i>=0:
            return (i,p)
    return (-1,-1)
st,l="ucabcucbabcbbcabcuabc",3
i,p=cherche_repetitions("ucabcucbabcbbcabcuabc",3)
print("Le motif "+st[i:i+l]+" se répète avec une période de "+str(p))