# Librairie du projet en version impératif

import random
import Levenshtein

def min_i(array: list[int]) -> int:
    """
    Fonction renvoyant l'indexe du minimum d'une liste d'entiers
    """
    min_val = array[0]
    min_i = 0
    for i in range(len(array)):
        if array[i] < min_val:
            min_val = array[i]
            min_i = i 
    return min_i

def max_i(array: list[int]) -> int:
    """
    Fonction renvoyant l'indexe du maximum d'une liste d'entiers
    """
    max_val = array[0]
    max_i = 0
    for i in range(len(array)):
        if array[i] > max_val:
            max_val = array[i]
            max_i = i 
    return max_i

def new_population(pm, ng, n, ts, tm, alpha, fm):
    """
    fonction qui renvoie une nouvelle population
    """
    population = {
        "individuals": [new_individual() for i in range(n)],
        "pm": pm,
        "ng": ng,
        "l": len(pm),
        "n": n,
        "ts": ts,
        "tm": tm,
        "alpha": alpha,
        "fm": fm
    }

    # On rend aléatoire les chromozomes des individus
    for individual in population["individuals"]:
        randomize(individual, 4, 30)

    return population

def new_individual():
    """
    fonction qui renvoie un nouvel individu
    """
    return {
        "chromozome": ""
    }

def randomize(individual, min_l, max_l) -> str:
    """
    Methode qui change la valeur d'un chromozome pour une valeur aléatoire
    """
    new = ""
    for i in range(random.randint(min_l, max_l)):
        new += chr(random.randint(0, 255))
    individual["chromozome"] = new

def fitness1(individual, pm) -> int:
    """
    Première methode de fitness, fait la somme des différences entre les codages des caractères des deux chaînes.
    """
    sum = 0
    for i in range(len(individual["chromozome"])):
        if i < len(pm) and i < len(individual["chromozome"]):
            sum += abs(ord(individual["chromozome"][i]) - ord(pm[i]))
    return -sum

def fitness2(individual, pm, alpha) -> int:
    """
    Deuxième methode de fitness qui compte les caractères bien placés et mal placés et qui renvoie un int pondéré par alpha
    """
    match = 0
    missed_placed = 0
    for i in range(len(individual["chromozome"])):
        # Si la chaîne est plus grande que la phrase alors on rajoute des caractères mal placés
        if i >= len(pm):
            missed_placed += len(individual["chromozome"]) - len(pm)
            break
        elif individual["chromozome"][i] == pm[i]:
            match += 1
        else:
            missed_placed += 1
    # Si la phrase est trop longue on rajoute autant de caractères mal placés que de caractères en trop
    if len(pm) > len(individual["chromozome"]):
        missed_placed += len(pm) - len(individual["chromozome"])
    return match + alpha * missed_placed

def fitness3(individual, pm) -> int:
    """
    Troisième methode de fitness qui utilise la distance de Levenshtein
    """
    return -Levenshtein.distance(individual["chromozome"], pm)

def get_fitness(population, individual) -> int:
    """
    Fonction qui renvoie la fitness d'un individu en utilisant la fonction choisie en paramètre de la population
    """
    match population["fm"]:
        case 1:
            return fitness1(individual, population["pm"])
        case 2:
            return fitness2(individual, population["pm"], population["alpha"])
        case 3:
            return fitness3(individual, population["pm"])
        case _:
            return fitness1(individual, population["pm"])

def get_fitness_list(population):
    """
    Fonction renvoyant une liste des fitness de touts les individus d'une population
    """
    fitness_list = []
    for individual in population["individuals"]:
        fitness_list.append(get_fitness(population, individual))
    return fitness_list

def get_best(population):
    """
    Methode qui renvoie le meilleur individu de la population
    """
    fitness_list = get_fitness_list(population)
    return population["individuals"][max_i(fitness_list)]

def print_best(population) -> None:
    """
    Methode qui affiche le meilleur individu de la population
    """
    print(get_best(population)["chromozome"])

def select(population) -> None:
    """
    Methode qui sélectionne les meilleurs individus
    """
    fitness_list = get_fitness_list(population)
    for i in range(int((1 - population["ts"]) * population["n"])):
        # On détermine quel est le moins bon individu
        least = min_i(fitness_list)
        # On le supprime des deux listes
        fitness_list.pop(least)
        population["individuals"].pop(least)

def get_two_random_individuals(population):
    """
    Fonction renvoyant deux individus choisis aléatoirement
    """
    i = random.randint(0, len(population["individuals"]) - 1)
    j = random.randint(0, len(population["individuals"]) - 1)
    while i == j:
        j = random.randint(0, len(population["individuals"]) - 1)
    return (population["individuals"][i], population['individuals'][j])

def reproduct(population) -> None:
    """
    Methode qui reproduit les individus entre eux jusqu'à obtenir une population de taille N
    """
    new = []
    # On créé de nouveaux individus jusqu'à avoir atteint la taille de population demandée
    while len(population["individuals"]) + len(new) != population["n"]:
        # On prend deux individus aléatoires
        indivi_1, indivi_2 = get_two_random_individuals(population)

        # On calcule le cut en fonction de la moyenne des tailles des deux individus
        avg = (len(indivi_1) + len(indivi_2)) // 2
        cut = random.randint(avg // 3, 2 * avg // 3)
        # On fait en sorte que le cut reste dans les valeurs possibles
        while cut > len(indivi_1) or cut > len(indivi_2): 
            cut = random.randint(avg // 3, 2 * avg // 3)

        # On créé le nouvel individu et on l'ajoute à la population
        new_chromozome = indivi_1["chromozome"][:cut] + indivi_2["chromozome"][cut:]
        child = new_individual()
        child["chromozome"] = new_chromozome
        new.append(child)

    population["individuals"] += new

def mutate(individual) -> None:
    """
    Methode qui change un des caractères du chromozome
    """
    new = list(individual["chromozome"])
    # On jette un dé 6 pour déterminer l'effet qu'aura la mutation
    dice = random.randint(1, 6)
    # Sur un 1 on ajoute un caractère aléatoire
    if dice == 1 and len(new) < 30:
        new.insert(random.randint(0, len(new) - 1), chr(random.randint(0, 255)))
    # Sur un 2 on retire un caractère aléatoire
    elif dice == 2 and len(new) > 4:
        new.pop(random.randint(0, len(new) - 1))
    # Sinon on modifie un caractère déjà existant
    else :
        new[random.randint(0, len(new) - 1)] = chr(random.randint(0, 255))
    individual["chromozome"] = "".join(new)

def mutate_pop(population) -> None:
    """
    Methode qui mute une partie de la population selon le taut de mutation
    """
    mutated = []
    for i in range(int(population["tm"] * population["n"])):
        # Sélectionne un individu aléatoire qui n'a pas encore été muté à cette génération
        to_mutate = random.randint(0, population["n"] - 1)
        while to_mutate in mutated:
            to_mutate = random.randint(0, population["n"] - 1)
        # Mutation de l'individu choisi
        mutate(population["individuals"][to_mutate])
        mutated.append(to_mutate)

def run(population) -> int:
    """
    Boucle principale
    """
    # On fait autant de générations que demandé
    for i in range(population["ng"]):
        # On arrête le programme une fois la phrase retrouvée et on renvoie le nombre de générations utilisées
        if get_best(population)["chromozome"] == population["pm"]:
            return i
        select(population)
        reproduct(population)
        mutate_pop(population)
    return population["ng"]