# Cherche la meilleure grille de Ruzzle avec une liste de tabous

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

# gestion liste de tabous

class file :
    "Définition d'une file"

    def __init__(self):
        self.nb = 0
        self.elements = []

    def vide(self):
        return self.nb==0

    def ajouter(self,k):
        self.elements.append(k)
        self.nb += 1

    def enlever(self):
        if not self.vide() :
            k = self.elements[0]
            del self.elements[0]
            self.nb -= 1
            return k
        else :
            print("La file est vide")

    def remplissage(self):
        return self.nb

    def present(self,k):
        i=0
        absent = True
        while absent and i<self.nb:
            absent = not k==self.elements[i]
            i+=1
        return not absent
            
    def afficher(self):
        k = 0
        while k<=self.nb-1:
            print(self.elements[k],end=" ")
            k+=1

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

alphabet=['e','s','a','i','r','n','t','o','l','u','c','m','d','p','g','b','f','h','z','v','q','y','x','j','k','w']

def lettre_alea():
    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_alea()
    return grille

def mutation(grille,p,lettre):
    return grille[:p] + lettre + grille[p+1:]

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
tabou = file()          # liste des tabous
long_liste = 37         # longueur de la liste des tabous

grille = grille_aleatoire()
sc1 = score(grille)
very_best_score = sc1
very_best_grille = grille
for i in range(60):
    best_score=0
    for pos in range(n):
        for lettre in alphabet:
            new_grille = mutation(grille,pos,lettre)
            sc2 = score(new_grille)
            if sc2 >= best_score :
                if not tabou.present(new_grille):
                    best_score = sc2
                    best = new_grille
    tabou.ajouter(best)
    if best_score > very_best_score:
        very_best_score = best_score
        very_best_grille = best
    if tabou.remplissage()>long_liste:
        tabou.enlever()
    grille = best
    print(best,best_score)
    
print()
print(very_best_grille,very_best_score)