Path: ...!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>
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
Bytes: 3342

Le 28 novembre 2023 Stefan Ram a =C3=A9crit :

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

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


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

# on suppose que les mots font 27 caract=C3=A8res maxi
# (d=C3=A9sinstitutionnalisassions)
MAX =3D 27

tests =3D [ '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 =C3=AAtre form=C3=A9s avec les lettres du =C2=AB mes_lettres =
=C2=BB.
    '''
    r=C3=A9sultat =3D []
    for mot in dictionnaire:
        if possible(mot, mes_lettres):
            r=C3=A9sultat.append(mot)
    return r=C3=A9sultat

def mots_de_longueur_maximale( dictionnaire, mes_lettres ):
    '''
    Trouve dans le dictionnaire des mots de longueur maximale qui
    peuvent =C3=AAtre form=C3=A9s avec les lettres indiqu=C3=A9es.
    '''
    for longueur in range( len( mes_lettres ), 1, -1 ):
        r=C3=A9sultat =3D mots_possibles( dictionnaire[longueur], mes_lettr=
es )
        if r=C3=A9sultat: return r=C3=A9sultat
    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=C3=A9es
    =C3=A7a augmente le temps de chargement mais
    =C3=A7a divise le temps de recherche par 10
    '''
    dictionnaire =3D [[] for i in range(MAX + 1)]
    with open(fichier, 'r') as fp:
        while line :=3D fp.readline().rstrip():
            dictionnaire[len(line)].append(line)
    return dictionnaire

dictionnaire =3D charge_dico()

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