Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > fr.comp.lang.python > #4125
| From | Michel <michel@domain.invalid> |
|---|---|
| Newsgroups | fr.comp.lang.python |
| Subject | Re: Tricher au scrabble... |
| Date | 2023-11-28 19:23 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87sf4p4uek.fsf@gnus.org> (permalink) |
| References | <uk4fm4$852n$1@dont-email.me> <recherche-20231128131821@ram.dialup.fu-berlin.de> |
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))
Back to fr.comp.lang.python | Previous | Next — Previous in thread | Find similar
Tricher au scrabble... Dominique <dominique.sextant@orange.fr.invalid> - 2023-11-28 11:33 +0100
Re: Tricher au scrabble... Dominique <dominique.sextant@orange.fr.invalid> - 2023-11-28 16:39 +0100
Re: Tricher au scrabble... Dominique <dominique.sextant@orange.fr.invalid> - 2023-11-28 16:43 +0100
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-12-01 17:39 +0000
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-12-01 17:56 +0000
Re: Tricher au scrabble... Michel <michel@domain.invalid> - 2023-12-02 03:48 +0100
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-12-06 22:22 +0000
Re: Tricher au scrabble... Michel <michel@domain.invalid> - 2023-12-07 10:28 +0100
Re: Tricher au scrabble... Thierry Pinelli <olmia2b+news@gmail.com> - 2023-12-07 16:35 +0100
Re: Tricher au scrabble... Thierry Pinelli <olmia2b+news@gmail.com> - 2023-12-07 17:52 +0100
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-12-07 18:00 +0000
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-12-07 18:07 +0000
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-11-28 16:05 +0000
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-11-28 16:17 +0000
Re: Tricher au scrabble... Dominique <dominique.sextant@orange.fr.invalid> - 2023-11-29 05:55 +0100
Re: Tricher au scrabble... yves <yves@free.invalid> - 2023-11-28 20:16 +0000
Re: Tricher au scrabble... Michel <michel@domain.invalid> - 2023-11-28 17:52 +0100
Re: Tricher au scrabble... Dominique <dominique.sextant@orange.fr.invalid> - 2023-11-29 05:57 +0100
Re: Tricher au scrabble... Michel <michel@domain.invalid> - 2023-11-28 19:23 +0100
csiph-web