Re: Tricher au scrabble...

Le 28 novembre 2023 Stefan Ram a écrit :

  Voici une approche possible (sans essayer d'optimiser quoi que ce
  soit) :

J'ai optimisé ton algo en passant par un dictionnaire pour chaque
longueur de mot. Ca permet de limiter les parcours sur le sous-ensemble.
Ca accélère nettement quand on a plein de lettres qui ne collent pas, et
donc qu'on doit chercher plusieurs longueurs.


# apt install wfrench
fichier = '/usr/share/dict/french'

# on suppose que les mots font 27 caractères maxi
# (désinstitutionnalisassions)
MAX = 27

tests = [ 'emmop', 'aefirs', 'aegnor', 'aberv',
        'axy', 'emmo', 'emmop', 'emmoepat', 'emoepat',
        'aefirs', 'aegnor', 'aegnorer' ]

def possible( mot, mes_lettres ):
    '''
    les lettres de mes_lettres sont-elles suffisantes pour former le mot ?
    '''
    for lettre in mot:
        if mot.count(lettre) > mes_lettres.count(lettre):
            return False
    return True

def mots_possibles( dictionnaire, mes_lettres ):
    '''
    Tous les mots du dictionnaire et qui
    peuvent être formés avec les lettres du « mes_lettres ».
    '''
    résultat = []
    for mot in dictionnaire:
        if possible(mot, mes_lettres):
            résultat.append(mot)
    return résultat

def mots_de_longueur_maximale( dictionnaire, mes_lettres ):
    '''
    Trouve dans le dictionnaire des mots de longueur maximale qui
    peuvent être formés avec les lettres indiquées.
    '''
    for longueur in range( len( mes_lettres ), 1, -1 ):
        résultat = mots_possibles( dictionnaire[longueur], mes_lettres )
        if résultat: return résultat
    return []

def charge_dico():
    '''
    on passe par une array par longueur de mot
    pour lors de la recherche ne parcourir que N mots
    au lieu de N x longueurs recherchées
    ça augmente le temps de chargement mais
    ça divise le temps de recherche par 10
    '''
    dictionnaire = [[] for i in range(MAX + 1)]
    with open(fichier, 'r') as fp:
        while line := fp.readline().rstrip():
            dictionnaire[len(line)].append(line)
    return dictionnaire

dictionnaire = charge_dico()

for lettres in tests:
    print(f'{lettres:8s}:', mots_de_longueur_maximale(dictionnaire, lettres))