Re: Tricher au scrabble...

Path	csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From	Michel <michel@domain.invalid>
Newsgroups	fr.comp.lang.python
Subject	Re: Tricher au scrabble...
Date	Tue, 28 Nov 2023 19:23:19 +0100
Organization	A noiseless patient Spider
Lines	74
Message-ID	<87sf4p4uek.fsf@gnus.org> (permalink)
References	<uk4fm4$852n$1@dont-email.me> <recherche-20231128131821@ram.dialup.fu-berlin.de>
MIME-Version	1.0
Content-Type	text/plain; charset=utf-8
Content-Transfer-Encoding	quoted-printable
Injection-Info	dont-email.me; posting-host="81a25e65b4969cd32590add3d06e4e17"; logging-data="413849"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19nHYqXdHPIGpEQVMQ7tQop"
User-Agent	Gnus
Cancel-Lock	sha1:3tZZ3T9xAAOayvxPEF71sFrj9GE= sha1:idfUTJAB34RNwlNPlcz4ORPS0HM=
Mail-Copies-To	never
Xref	csiph.com fr.comp.lang.python:4125

Show key headers only | View raw

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

Thread

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