import random as rd

# caractères de chr = 32 à 122 (compris)

def genere_chromosome(len_chromosome):
    ch = ""
    for k in range(len_chromosome):
        ch += chr(rd.randint(33,122))
    return ch

def genere_population0(taille_pop,len_chromosome):
    return [genere_chromosome(len_chromosome) for x in range(taille_pop)]

def crossover(ch1,ch2):
    n = len(ch1)
    i = rd.randint(1,n-1)
    return ch1[:i]+ch2[i:], ch2[:i]+ch1[i:]

def mutation(ch,proba_mutation):
    if rd.random() < proba_mutation:
        n = len(ch)
        i = rd.randint(0,n-1)
        car = chr(rd.randint(32,122))
        return ch[:i] + car + ch[i+1:]
    else:
        return ch

def score(chromosome,solution):
    s = 0
    n = len(solution)
    for k in range(n):
        if chromosome[k] == solution[k]:
            s += 1
    return s

def partition(population,solution):
    chromosome0 = population[0]
    inf, sup = [], []
    for chromosome in population[1:]:
        if score(chromosome,solution) > score(chromosome0,solution):
            sup.append(chromosome)
        else:
            inf.append(chromosome)
    return inf, chromosome0, sup

def tri_rapide(population,solution):
    N = len(population)
    if N<=1:
        return population
    else:
        inf, chromosome0, sup = partition(population,solution)
        return tri_rapide(sup,solution) + [chromosome0] + tri_rapide(inf,solution)

def selection(population,solution):
    N = len(population)
    sorted_population = tri_rapide(population,solution)
    best = sorted_population[:N//3]
    rest = sorted_population[N//3:]
    survivors = rd.sample(rest,N//5)
    return best + survivors

def generation(population,solution,proba_mutation):
    taille_pop = len(population)
    enfants = []
    population_select = selection(population,solution)
    while len(enfants) < taille_pop:
        parent1, parent2 = rd.sample(population_select,2)
        enfant1, enfant2 = crossover(parent1,parent2)
        enfants.append(mutation(enfant1,proba_mutation))
        enfants.append(mutation(enfant2,proba_mutation))
    return enfants

def trouve_solution(population,solution):
    for chromosome in population:
        if score(chromosome,solution) == len(solution):
            return True, chromosome
    return False, population[0]

def resolution(solution,proba_mutation=0.1):
    taille_pop = 100
    len_chromosome = len(solution)
    population = genere_population0(taille_pop,len_chromosome)
    nb_generations = 1
    obtenu, chromosome_solution = trouve_solution(population,solution)
    while not obtenu:
        population = generation(population,solution,proba_mutation)
        obtenu, chromosome_solution = trouve_solution(population,solution)
        nb_generations += 1
        print(max([score(chromosome,solution) for chromosome in population]))
        #print(population)
    return chromosome_solution, nb_generations

print(resolution("Vive, !!!!la BCPST !"))