# Cherche la meilleure grille de Ruzzle avec un recuit simulé

from trie_fr import Trie
from ruzzlefr import *
from random import *
from math import exp

# ****************************** 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):
    p=randint(0,n-1)              # position de la mutation
    grille = grille[:p] + lettre() + grille[p+1:]
    return grille

def score(donnees):
    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
    return len(list(set(resultats)))  # compte le nombre de mots différents        


trie = creer_trie('dico_ruzzle.txt')
print('Début de la recherche')
n=16                     # nombre de cases
k_max = 1000
coef = 0.95           # coefficient de décroissance
palier = k_max//100   # longueur des paliers de température
very_best_score = 0
very_best_grille = 'z'


for i in range(100):         # on fait 100 essais
    T = 70                  # température initiale
    k = 1
    grille = grille_aleatoire()
    sc1 = score(grille)
    best_score = sc1
    while k < k_max :
        nouvelle_grille = mutation(n,grille)
        sc2 = score(nouvelle_grille)
        delta = sc1-sc2
        if delta <= 0:     # modification acceptée, car meilleur score
            if sc2 > best_score :
                best_score = sc2
                best = nouvelle_grille
            sc1 = sc2
            grille = nouvelle_grille
        elif random()<exp(-delta/T):  # on modifie quand même
            grille = nouvelle_grille
        k += 1
        if k%palier == 0:
            T = T * coef
    print(best,best_score)
    if best_score > very_best_score:
        very_best_score = best_score
        very_best_grille = best
    
print()
print(very_best_grille,very_best_score)