import random

# Exercice 1

fichier = open("lorem_ipsum.txt", "r") # On suppose qu'on est dans le bon dossier !
contenu = fichier.read().lower()
contenu = contenu.replace(",", "")
contenu = contenu.replace(".", "")
contenu = contenu.replace(";", "")
contenu = contenu.replace("\n", " ") # Attention, sinon à une occasion deux mots ne sont pas séparés
mots = contenu.split(" ")
cles = []
for mot in mots:
    if mot not in cles and mot != "": # Pour les autres remplacements du saut de ligne
        cles.append(mot)

# Exercice 2

nb_essais = 0
liste0 = [] # Ici besoin de tests pour éviter les doublons
while len(liste0) < 1000:
    nombre = random.randint(0, 999999)
    if nombre not in liste0:
        liste0.append(nombre)
    nb_essais += 1
# print("Au passage, le nombre d'essais était de", nb_essais) # Souvent 1000, éventuellement 1001, la théorie est contente.

liste = random.sample(range(1000000), 1000) # La gestion est laissée à Python

liste1 = list(range(1000000)) # On va faire essentiellement la même chose à la main !
random.shuffle(liste1)
liste1 = liste1[:1000] # La complexité est linéaire en la taille de l'ensemble où on prend les valeurs, vu que c'est aussi le carré du nombre de valeurs à garder on ne perd presque rien.

# Exercice 3

listef = [int(random.random() * 1e12) / 1e6 for _ in range(1000)] # Qu'on ne commence pas à me parler de doublons…

# Exercice 4

# Exemple classique : assimiler les lettres à des nombres de 0 à 25 (par exemple la lettre a correspond à 0, et ainsi de suite), et calculer en base 26.

def deux_lettres_vers_un_nombre(s):
    """Fonction bijective de l'ensemble des mots de deux lettres
    en bas de casse vers l'ensemble des entiers de 0 à 275.
    On calcule vingt-six fois l'indice de la première lettre dans l'alphabet
    (a donnant 0) plus l'indice de la deuxième.
    """
    return 26 * (ord(s[0])-ord('a')) + ord(s[1])-ord('a')

# On va utiliser cette fonction sur les deux premières lettres des mots et les placer dans une table de hachage maison.

def cree_table(cles, taille, fonction):
    """Crée une table de hachage avec les clés fournies. Le type des clés
    peut être indifféremment chaînes de caractères ou entiers.
    On précise également la fonction de hachage.
    La gestion des conflits se fait par chaînage.
    On n'incorpore pas de valeurs ici.
    """
    tdh = [[] for _ in range(taille)] # Attention à ne pas faire [[]] * taille
    for cle in cles:
        indice = fonction(cle)
        if cle not in tbh[indice]:
            tdh[indice].append(cle)
    return tdh

# Voyons ce que cela donne sur un histogramme
def liste_occurrences(table):
    """Détermine le nombre de cellules contenant une liste de taille k
    pour toutes les valeurs de k.
    """
    occurrences = [] # on ajoutera des éléments en fonction des besoins
    for i in range(len(table)):
        k = len(table[i])
        while len(occurrences) < k+1: # c'est bon, ce sera rare, en fait calculer le maximum des tailles va plus vite
            occurrences.append(0)
        occurrences[k] += 1
    return occurrences

def hache_debut(s):
    if len(s) == 1: # Cela arrive une fois dans notre exemple, pour le mot a
        s = "a" + s # solution de fortune
    return deux_lettres_vers_un_nombre(s[:2])

# Autre test : deux dernières lettres
def hache_fin(s):
    if len(s) == 1: # Cela arrive une fois dans notre exemple, pour le mot a
        s = "a" + s # solution de fortune
    return deux_lettres_vers_un_nombre(s[-2:])

# Dernier test : deux lettres extrémales (pour le mot a, cela ne change rien par rapport aux autres fois…)
def hache_extreme(s):
    return deux_lettres_vers_un_nombre(s[0] + s[-1])

## Tests :

### tdh = cree_table(cles, 676, hache_debut)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # On observe une cellule avec 5 occurrences : celle des lettres co avec consectetur, congue, consequat, consectetuer et convallis

### tdh = cree_table(cles, 676, hache_fin)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # Une cellule avec 13 occurrences ! Évidemment, c'est -us…

### tdh = cree_table(cles, 676, hache_extreme)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # e & t, l & s et m & s sont les trois couples initiale & dernière lettre ayant quatre occurrences
# En pratique, un essai supplémentaire avec les deux lettres du milieu n'a rien donné de concluant, avec également quatre occurrences rencontrées trois fois.

# Exercice 5

# Si la fonction n'était pas injective, on aurait deux écritures différentes pour un même entier, en excluant des 0 non significatifs. Ceci est tout aussi impossible en base 26 qu'en base 10.
# Ici on a besoin d'un peu plus de rigueur, car ce n'est pas vraiment la base 26, les valeurs associées étant entre 1 et 26 au lieu de 0 à 25.
# Il convient de remarquer que néanmoins tout mot strictement plus court qu'un autre donne lieu à un encodage strictement moindre,
# car la somme des 26 à la puissance k de 1 à n est inférieure à 26 puissance n+1.
# Quand le nombre de lettres est identique, une propagation de retenue sur un Z ne peut pas créer d'ambiguïté, car rien n'est encodé par un 0.

def evaluation(mot):
    """Détermine l'entier représenté en "pseudo-base 26" par un mot
    en utilisant les lettres minuscules en guise de chiffres (a donnant 1).
    L'algorithme repose sur la méthode de Horner.
    """
    rep = 0
    for lettre in mot:
        rep = 26 * rep + ord(lettre) - ord('a') + 1
    return rep

def evaluation_mod(mot, n):
    """Détermine l'entier représenté en "pseudo-base 26" par un mot
    en utilisant la fonction evaluation qui n'était pas bornée
    et en prenant le résidu modulo n.
    """
    return evaluation(mot) % n

## Tests :

### tdh = cree_table(cles, 677, lambda s : evaluation_mod(s, 677)) # Parce que 676 ferait juste les deux dernières lettres en gros…
### occurrences = liste_occurrences(tdh)
### print(occurrences) # 120 cellules avec une seule valeur, 2 avec deux, 1 avec trois.

### tdh = cree_table(cles, 1009, lambda s : evaluation_mod(s, 1009)) # Premier nombre premier à 4 chiffres
### occurrences = liste_occurrences(tdh)
### print(occurrences) # 113 cellules avec une seule valeur, 7 avec deux.

### tdh = cree_table(cles, 16127, lambda s : evaluation_mod(s, 16127)) # Dernier nombre premier inférieur à 127 au carré
### occurrences = liste_occurrences(tdh)
### print(occurrences) # Pas de conflit.

# Exercice 6

### tdh = cree_table(liste, 1009, lambda s : s % 1009)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # Le nombre maximal d'occurrences est souvent 5, il y a eu un test donnant 7.

### tdh = cree_table(liste, 10007, lambda s : s % 10007)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # Il y a régulièrement une ou deux cellules avec 3 clés.

### tdh = cree_table(liste, 100003, lambda s : s % 100003)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # De rares tests donnent une cellule avec 3 clés, le nombre de conflits ne dépasse pas la dizaine.

# Exercice 7

def arrondi_fractionnaire(x):
    """Arrondit à l'entier le plus proche la partie fractionnaire d'un flottant
    multipliée par un million, sachant que le flottant a censément six chiffres
    après la virgule. En l'occurrence on passe par des chaînes cette fois.
    """
    s = str(x)
    virgule = s.index(".")
    return int(s[virgule+1:virgule+7])

### tdh = cree_table(listef, 1000000, arrondi_fractionnaire)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # La moitié du temps un conflit, l'autre moitié aucun.

### tdh = cree_table(listef, 1000000, int)
### occurrences = liste_occurrences(tdh)
### print(occurrences) # Sensiblement le même résultat. Par hasard un test a donné deux conflits.

# Exercice 8

# Il suffit de changer la fonction de création !
def cree_table_adressage_ouvert_decalage_un(cles, taille, fonction):
    """Crée une table de hachage avec les clés fournies. Le type des clés
    peut être indifféremment chaînes de caractères ou entiers.
    On précise également la fonction de hachage.
    La gestion des conflits se fait par adressage ouvert
    en décalant d'une unité à chaque fois.
    """
    if len(cles) > taille:
        raise ValueError("Il n'y aura pas assez de place !")
    tdh = [None for _ in range(taille)] # On est d'accord, None n'est jamais une clé
    for cle in cles:
        indice = fonction(cle)
        while tdh[indice] is not None:
            indice = (indice + 1) % taille
        tdh[indice] = cle
    return tdh

def ecarts(cles, taille, fonction):
    """Détermine la liste des écarts entre l'adresse théorique
    et l'adresse réelle dans une table de hachage.
    En fait il s'agit de créer virtuellement la table en étudiant les conflits.
    """
    if len(cles) > taille:
        raise ValueError("Il n'y aura pas assez de place !")
    tdh = [None for _ in range(taille)]
    occurrences = []
    for cle in cles:
        indice = fonction(cle)
        decalage = 0
        while tdh[indice] is not None:
            indice = (indice + 1) % taille
            decalage += 1
        tdh[indice] = cle
        while len(occurrences) < decalage+1:
            occurrences.append(0)
        occurrences[decalage] += 1
    return occurrences

## Tests :

### tdh = cree_table_adressage_ouvert_decalage_un(cles, 676, hache_extreme)
### print(tdh)
### occurrences = ecarts(cles, 676, hache_extreme)
### print(occurrences) # 80 bien placées, 25 décalées d'un cran, pour les crans suivants cela arrive respectivement 7, 10, 3, 1 et 1 fois.

### tdh = cree_table_adressage_ouvert_decalage_un(liste, 10007, lambda s : s % 10007)
### print(tdh)
### occurrences = ecarts(liste, 10007, lambda s : s % 10007)
### print(occurrences) # En général 50 décalées d'un cran et moins de 5 décalées de deux, rien d'autre. Un cas extrême : 954, 39, 6, 0, 1.

### tdh = cree_table_adressage_ouvert_decalage_un(listef, 1000000, arrondi_fractionnaire)
### # Éviter éventuellement print(tdh), ça spamme !
### occurrences = ecarts(listef, 1000000, arrondi_fractionnaire)
### print(occurrences) # Même constat que par chaînage, de temps en temps un élément décalé.

# Exercice 9

def collision(cles, taille, fonction): # à ce stade, on aurait pu faire une fonction rassemblant création, mesure des écarts et test de collisions, mais tant pis
    """Détermine s'il y aurait une collision en créant une table de hachage.
    Par principe on crée une liste de booléens pour ne pas stocker trop d'informations
    et avoir un temps de calcul raisonnable.
    """
    if len(cles) > taille:
        return True # trivial
    cle_prise = [False] * taille
    for cle in cles:
        indice = fonction(cle)
        if cle_prise[indice]:
            return True
        cle_prise[indice] = True
    return False

# On va faire le test pour des listes d'entiers comme liste, c'est plus pratique !
def taux_collisions(taille_liste, seuil_liste, taille_table, repetitions):
    """Détermine le taux de collisions lors de repetitions tentatives
    de création de tables de hachage de taille précisée, où l'on a mis
    des listes d'entiers de taille précisée et de valeurs comprises
    entre zéro inclus et un seuil exclu.
    La fonction de hachage est le résidu modulo la taille de la table.
    """
    nb_collisions = 0
    for _ in range(repetitions):
        liste = random.sample(range(seuil_liste), taille_liste)
        if collision(liste, taille_table, lambda x : x % taille_table):
            nb_collisions += 1
    return nb_collisions / repetitions

## Tests :

### print(taux_collisions(1000, 1000000, 10000, 10000)) # 100 %, réponse après quelques secondes
### print(taux_collisions(1000, 1000000, 100000, 10000)) # Environ 99 %
### print(taux_collisions(1000, 1000000, 500000, 10000)) # Environ 40 %
# On va faire moins de tests pour accélerer, quand même…
### print(taux_collisions(1000, 1000000, 250000, 1000)) # Environ 78 %
### print(taux_collisions(1000, 1000000, 400000, 1000)) # Environ 56 %

### print(taux_collisions(100, 1000000, 1000, 1000)) # Environ 99 %
### print(taux_collisions(100, 1000000, 4000, 1000)) # Environ 75 %
### print(taux_collisions(100, 1000000, 6000, 1000)) # Environ 58 %
### print(taux_collisions(100, 1000000, 7500, 1000)) # Environ 49 %

# Là, ça devient très long ! On diminue encore le nombre de tests.
### print(taux_collisions(10000, 1000000000, 10000000, 200)) # Environ 99 %
### print(taux_collisions(10000, 1000000000, 50000000, 200)) # Environ 64 %
### print(taux_collisions(10000, 1000000000, 70000000, 200)) # Environ 49 %

# Exercice 10

def FNV32(chaine_en_tuple):
    """Transforme un tuple d'entiers représentant une chaîne de caractères
    en son haché par l'algorithme FNV32 avec ou exclusif avant multiplication.
    """
    x = 2166136261
    p = 16777619
    dp32 = 2**32
    for c in chaine_en_tuple:
        x = x^c # Enfin on utilise ce symbole à raison !
        x = (x*p) % dp32
    return x

def cree_chaine_en_tuple_aleatoire():
    """Crée un n-uplet de taille entre deux et quinze (la taille est obtenue
    selon une loi normale de paramètres (9, 2) en ramenant au bon intervalle),
    dont les éléments sont des entiers aléatoires entre zéro inclus et
    deux puissance huit exclu.
    """
    taille = min(15, max(2, int(random.gauss(9, 2))))
    l = []
    for _ in range(taille):
        l.append(random.randint(0, 255))
    return tuple(l)

def cree_des_chaines_en_tuple_aleatoires(nombre_tuples):
    """Crée une liste de nombre_tuples n-uplets de taille entre deux et quinze
    par la fonction cree_chaine_en_tuple_aleatoire sans répétition.
    On crée en fait un peu plus de tuples que le nombre nécessaire,
    puis on trie et on élimine les doublons et on élimine au hasard l'excédent.
    """
    l = [cree_chaine_en_tuple_aleatoire() for _ in range(11*nombre_tuples//10)]
    l.sort()
    res = [l[0]]
    for i in range(1, 11*nombre_tuples//10):
        if l[i] != l[i-1]:
            res.append(l[i])
    for i in range(nombre_tuples - len(res)): # improbable qu'on entre là
        t = cree_chaine_en_tuple_aleatoire()
        while t in res: # À ce stade, plus besoin d'optimiser
            t = cree_chaine_en_tuple_aleatoire()
        res.append(t)
    return random.sample(res, nombre_tuples)

def taux_collisions_FNV32(nombre_tuples, repetitions):
    """Détermine le taux de collisions lors de repetitions tentatives
    de création de tables de hachage de taille deux à la puissance trente-deux,
    où l'on a mis des chaînes de caractères simulées par des n-uplets,
    au nombre de nombre_tuples, contenant entre deux et quinze entiers
    compris entre zéro inclus et deux puissance huit exclu.
    La fonction de hachage est FNV32 avec ou exclusif avant multiplication.
    """
    nb_collisions = 0
    for _ in range(repetitions):
        les_indices = set() # pas question de faire une liste d'un milliard de booléens !
        les_tuples = cree_des_chaines_en_tuple_aleatoires(nombre_tuples)
        for t in les_tuples:
            indice = FNV32(t)
            if indice in les_indices:
                nb_collisions += 1
                break
            les_indices.add(indice)
    return nb_collisions / repetitions

def evaluation_mod_bis(t):
    """Évalue un n-uplet d'entiers comme s'il s'agissait d'un nombre
    en base deux puissance huit. Le résultat du calcul est alors pris
    modulo deux puissance trente-deux, ce qui fait qu'en pratique
    le n-uplet est un peu géré en quatre paquets dépendants uniquement
    par d'éventuelles retenues…
    """
    res = 0
    for element in t:
        res = res * 256 + element
    return res % (2 ** 32)

def taux_collisions_temoin(nombre_tuples, repetitions):
    """Détermine le taux de collisions lors de repetitions tentatives
    de création de tables de hachage de taille deux à la puissance trente-deux,
    où l'on a mis des chaînes de caractères simulées par des n-uplets,
    au nombre de nombre_tuples, contenant entre deux et quinze entiers
    compris entre zéro inclus et deux puissance huit exclu.
    La fonction de hachage est une adaptation de l'évaluation de l'exercice 5.
    """
    nb_collisions = 0
    for _ in range(repetitions):
        les_indices = set()
        les_tuples = cree_des_chaines_en_tuple_aleatoires(nombre_tuples)
        for t in les_tuples:
            indice = evaluation_mod_bis(t)
            if indice in les_indices:
                nb_collisions += 1
                break
            les_indices.add(indice)
    return nb_collisions / repetitions

## Tests :

### print(taux_collisions_FNV32(70000, 100)) # Environ 40 %, calculé en deux minutes environ
### print(taux_collisions_temoin(70000, 100)) # Environ 45 %.

# Exercice 11

def mute_table_chainage(table, nouvelle_taille, nouvelle_fonction):
    """Mute une table de hachage en changeant la taille et en utilisant
    une nouvelle fonction de hachage.
    La gestion des collisions se faisait et se refait par chaînage.
    """
    liste_cles = []
    for cellule in table:
        liste_cles += cellule
    nouvelle_table = cree_table(liste_cles, nouvelle_taille, nouvelle_fonction)
    table[:] = nouvelle_table # astuce pour muter
 
def mute_table_adressage_ouvert(table, nouvelle_taille, nouvelle_fonction):
    """Mute une table de hachage en changeant la taille et en utilisant
    une nouvelle fonction de hachage.
    La gestion des collisions se faisait et se refait par adressage ouvert
    en décalant d'une unité à chaque fois.
    """
    liste_cles = []
    for cellule in table:
        if cellule is not None:
            liste_cles.append(cellule)
    ctaodu = cree_table_adressage_ouvert_decalage_un # j'aime pas déborder de 80 lignes sur le code
    nouvelle_table = ctaodu(liste_cles, nouvelle_taille, nouvelle_fonction)
    table[:] = nouvelle_table