# Cherche la meilleure grille de Ruzzle avec un algorithme génétique

from trie_fr import Trie
from ruzzlefr import *
from random import *


# ****************************** partie calcul ******************************

def lettre():
    x=10000*random()
    if x<1489: return "e"
    elif x<2510: return "s"
    elif x<3481: return "a"
    elif x<4421: return "i"
    elif x<5288: return "r"
    elif x<6022: return "n"
    elif x<6704: return "t"
    elif x<7286: return "o"
    elif x<7687: return "l"
    elif x<8047: return "u"
    elif x<8387: return "c"
    elif x<8641: return "m"
    elif x<8877: return "d"
    elif x<9112: return "p"
    elif x<9272: return "g"
    elif x<9412: return "b"
    elif x<9548: return "f"
    elif x<9664: return "h"
    elif x<9771: return "z"
    elif x<9867: return "v"
    elif x<9917: return "q"
    elif x<9951: return "y"
    elif x<9976: return "x"
    elif x<9994: return "j"
    elif x<9999: return "k"
    else: return "w"
    
def grille_aleatoire():
    grille=""
    for i in range(16):
        grille+=lettre()
    return grille

def mutation(n,grille):
    # changement d'une valeur au hasard
    if random()< 0.1:               # 10% de mutations
        p=randint(0,n-1)            # position de la mutation
        grille = grille[:p] + lettre() + grille[p+1:]
    return grille
    
def crossover(n,grille1,grille2):
    # croisement simple
    p=randint(1,n-2)              # position du croisement
    grille12 = grille1[:p]+ grille2[p:]
    grille21 = grille2[:p]+ grille1[p:]
    grille1 = grille12
    grille2 = grille21
    return grille1, grille2

def population_initiale(pop):
    for i in range(pop):
        grilles[i] = grille_aleatoire()
        print(grilles[i])
    print()

def calculer_scores(pop):
    for i in range(pop):
        donnees = grilles[i]
        grille = [Case(lettre) for lettre in donnees]  # la grille est une liste de 16 cases
        creer_connexions(grille)
        resultats = []
        for case in grille: # première lettre du mot à chercher (16 possibilités)
            noeud = trie    # on se place au début du Trie
            mots_trouves = chercher(noeud[case.getValue()], case)
            if len(mots_trouves) > 0:
                resultats.extend(mots_trouves)  # ajoute les nouveaux mots trouvés au résultat
        scores[i] = len(list(set(resultats)))  # compte le nombre de mots différents        
        
def Swap(l,i,j):
    # echange 2 valeurs d'une liste
    t=l[i]
    l[i]=l[j]
    l[j]=t

def Tri_Selection(scores,grilles):
    for i in range(len(scores)-1):
        maxi=i
        for j in range(i+1,len(scores)):
            if scores[j]>scores[maxi]:
                maxi=j
        Swap(scores,i,maxi)
        Swap(grilles,i,maxi)

def classement(pop):
    # classe les gènes selon leur score du plus petit au plus grand
    # le plus petit score est le meilleur
    calculer_scores(pop)
    Tri_Selection(scores,grilles)
    # for i in range(pop):
    #     print(grilles[i], scores[i])
    # print()

def eliminer(n,pop):
    # remplace la plus mauvaise solution par la meilleure
    grilles[pop-1] = grilles[0]


trie = creer_trie('dico_ruzzle.txt')
score_max=0
print('Début de la recherche')
n=16                     # nombre de cases
pop = 80               # population (toujours un nombre pair)
grilles = [0]*pop
scores = [0]*pop
score_max = 0
generation = 1
generation_best = 1
nbr_max_gen = 600      # nombre de générations maximum

population_initiale(pop)
classement(pop)
while scores[0]>0 and generation < nbr_max_gen :
    eliminer(n,pop)
    for j in range(pop//2):
        grilles[2*j], grilles[2*j+1] = crossover(n,grilles[2*j],grilles[2*j+1])
    for j in range(pop):
        grilles[j] = mutation(n,grilles[j])
    classement(pop)
    if scores[0] > score_max :
        score_max = scores[0]
        grilles_best=grilles[0]
        generation_best = generation
        print(generation,grilles_best,score_max)
    generation += 1