Sujet : Re: Tricher au scrabble...
De : michel (at) *nospam* domain.invalid (Michel)
Groupes : fr.comp.lang.pythonDate : 28. Nov 2023, 19:23:19
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <87sf4p4uek.fsf@gnus.org>
References : 1 2
User-Agent : Gnus
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))