# -*- coding: utf-8 -*-
# Correction du TP 2

# Exercice 1

def creation(n):
    d ={}
    for i in range(1,n+1):
        d[i] = -i
    return d

#print(creation(3))

# Autre solution
def creation2(n):
    d ={ i:-i for i in range(1,n+1)}
    return d

#print(creation2(3))


# Exercice 2

def min_max(L):
    M = L[0]
    m = L[0]
    for x in L:
        if x > M:
            M = x
        elif x < m:
            m = x
    return {"min":m, "max":M}

#print(min_max([8,45,-32,135,5]))


# Exercice 3

#1.
def occurrence(L,x):
    nb = 0
    for element in L:
        if element == x:
            nb += 1
    return nb

L = [3,2,3,3,5,3]
#print(occurrence(L,3))
#print(occurrence(L,4))

#2.
def Occurrences(L):
    d = {}
    for x in L:
        d[x] = occurrence(L,x)
    return d

#print(Occurrences([5, 42, -3, 5, 5, -3]))


#3. La version précédente a une complexité O(len(L)^2),
# car appel à une fonction en O(len(L)) dans une boucle faite len(L) fois. 
# Ci-dessous une version en O(len(L)), donc bien meilleure:
def occurrences(L):
    d = {}
    for x in L:
        if x not in d:
            d[x] = 1
        else:
            d[x] += 1
    return d

d0 = occurrences([5, 42, -3, 5, 5, -3])
#print(d0)

#4.
def taille(d):
    t = 0
    for c in d:
        t += d[c]
    return t

#print(taille(d0))

#5.
# Version1:
def compare(l1,l2):
    d1 = occurrences(l1)
    d2 = occurrences(l2)
    if taille(d1) != taille(d2):
        return False
    for c in d1:
        if c not in d2:
            return False
        if d1[c] != d2[c]:
            return False
    return True

#print(compare([42, -3, 5, 5, -3],[7, 42, -3, 5, 5, -3]))

# Version2:
def compare2(l1,l2):
    return occurrences(l1) == occurrences(l2)

# Remarque: La 2e version n'est pas plus efficace que la première, les 2 versions font exactement le même nombre d'opérations !
# En effet le test d'égalité entre dictionnaires fait les mêmes opérations que celles qui sont effectuée dans la version 1.

#6. Dans les deux cas on a une complexité linéaire en la somme des tailles des 2 listes l1 et l2.


# Exercice 4

#1.
# Pour l'accès ou la modification de la température d'une ville,
# il faut parcourir la liste pour rechercher la ville,
# donc complexité O(n) où n est le nombre de villes.
# Pour l'ajout d'une ville, complexité O(1) amortie:
# on l'ajoute à la fin avec append -> complexité de l'ajout à la fin dans les listes Python.

#2.
# Tri de la liste O(n.log(n)), recherche dichotomique O(log(n)). Au total O(n.log(n))
# Si on a besoin d'accéder à des températures de villes plus de log(n) fois,
# ça vaut le coup de trier une fois pour avoir ensuite une recherche plus rapide (log(n) au lieu de n). Mais ça reste pas très efficace. 
# Remarque: attention de ne pas confondre O(n.log(n)) et O(log(n)), ce n'est pas du tout la même chose !
# O(log(n)) est une complexité meilleure que linéaire, tandis que O(n.log(n)) est une complexité pire que linéaire !


#3.
def dico(L):
    d = {}
    for i in range(len(L)):
        d[L[i][0]] = L[i][1]
    return d

dt = dico([["Paris",12],["Lyon",14],["Marseille",19]]) 
#print(dt)    

# Autre solution:
def dico2(L):
    d = {}
    for l in L:
        d[l[0]] = l[1]
    return d
        
#print(dico2([["Paris",12],["Lyon",14],["Marseille",19]]))    

#4. Complexité de dico : O(n) où n est le nombre de villes
#   Les opérations de la question 1 sont maintenant toutes en O(1) car on a accès direct aux villes par les clés du dictionnaire.
#   C'est beaucoup plus efficace qu'avec la liste de départ, même si on la trie (cf question 2).

#5.
def temperature(d,ville):
    return d[ville]

#print(temperature(dt,"Lyon"))


# Exercice 5

f=open("ListeMotsFrancais.txt", "r")
Liste=f.readlines()
f.close()

# Question 1
print("Il y a ", len(Liste),"mots dans la liste.")

# Question 2
mot=Liste[49]
print("Le cinquantième mot de la liste est:",mot)

# Question 3
for i in range(len(Liste)):
    Liste[i]=Liste[i][:-1]

# Question 4
print(sorted(mot)) # on obtient une liste triée des caractères du mot
print("".join(sorted(mot))) # on obtient une chaîne triée des caractères du mot

#%%

# Question 5
D={}
for mot in Liste:
    s="".join(sorted(mot))
    if s not in D:
        D[s]=1
    else:
        D[s]=D[s]+1

# Question 6
Max=0
for mot in D:
    if D[mot]>Max:
        Max=D[mot]
        motmax=mot

print("La valeur maximale d’anagramme est",Max,"atteint pour",motmax)

# Question 7
print("Les mots suivant sont ceux qui ont le nombre maximum d’anagrame")
for mot in Liste:
    s="".join(sorted(mot))
    if D[s]==Max:
        print(mot)


#%%
# EXERCICE 6

# Question 1

def f(mot):
    S=0
    for i in range(len(mot)):
        S=S+(ord(mot[i])-97)*(26**i)
    return S

print(f("cpge"))
print(f("anticonstitutionnellement"))


# Si la fonction était une fonction de hachage,
# il faudrait que la table de hachage ait plus d’éléments que
# f("anticonstitutionnellement") ce qui prendrait beaucoup trop de mémoire.

# Question 2
n=10**6

def h1(mot):
    return f(mot)%n

print(h1("anticonstitutionnellement"))

# Question 3
# h1 prend des valeurs entre 0 et 10**6-1, il faudrait
# donc une table de hachage de 10**6, or il y a 330 000 mots dans
# ce dictionnaire, il est donc possible qu’il y ait des collisions
print("En moyenne, il y aura", len(Liste)/10**6, "mots dans chaque alévole")

# Question 4
def Bilan():
    L=[0 for i in range(n)]
    for mot in Liste:
        s=h1(mot)
        L[s]=L[s]+1
    return L

L=Bilan()

# Question 5
def Moyenne(L):
    m=0
    for i in L:
        m=m+i
    return m/len(L)

def EcartType(L):
    m=Moyenne(L)
    S=0
    for i in L:
        S=S+(i-m)**2
    return (S/len(L))**0.5

def Maximum(L):
    m=0
    for i in L:
        if i>m:
            m=i
    return m

def ProportionOccupation(L):
    M=[i for i in L if i!=0]
    return len(M)/len(L)

m=Maximum(L)
if m==1:
    print("Il n’y a pas eu de collision")
else:
    print("Il y a eu des collisions")

print("Le nombre maximum de clés dans la même alvéole est:",m)
print("Le nombre moyen de clés dans une alvéole est:",Moyenne(L))
print("L’écart-type du nombre de clés dans une alvéole est:",EcartType(L))
print("Le pourcentage d’alvéoles occupés est",ProportionOccupation(L))
        
# Question 6

def Prob(n,k):
    p=1
    for i in range(k):
        p=p*(n-i)/n
    return 1-p
k=len(Liste)
Dico={}

afficher=True
while n<=10**12:
    Dico[n]=Prob(n,k)
    if afficher and Dico[n]<0.5:
        print("première valeur trouvée pour avoir une proba plus petite que 1/2:",n)
        afficher=False
    n=int(n*1.15) 
  
import matplotlib.pyplot as plt
    
plt.figure()    
plt.plot(list(Dico.keys()),list(Dico.values()),"o")
plt.xlabel("n: taille de la table de hachage")
plt.ylabel("probabilité d’avoir une collision")
plt.title("Probabilité d’avoir une collision avec "+str(k)+"clés\n en fonction de la taille de hachage")
plt.show()

def Inverse(mot):
    inverse=""
    for k in range(len(mot)):
        inverse=inverse+mot[len(mot)-k-1]
    return inverse

Palindrome=[]
for mot in Liste:
    if Inverse(mot)==mot:
        Palindrome.append(mot)