Journal sur le fonctionnement du jeu Wordle

Posté par  . Licence CC By‑SA.
23
13
jan.
2022

J'ai croisé le jeu wordle dans plusieurs articles récents lors de ma veille.
C'est un peu comme un mastermind mais avec des mots du dictionnaire. Il y a un mot par jour à deviner, de cinq lettres. Le mot d'hier était 'favor'.
Vous proposez un mot du dictionnaire (lequel ?), le jeu vous dit quelles lettres sont dans le mot à trouver et quelles lettres sont à la bonne place, quelles lettres n'y sont pas.
J'ai joué mais je ne suis pas doué. Je connais combien de mots de cinq lettres en anglais …

Par contre mon pc connaît plus de 15k mots d'anglais de cinq lettres, oui oui. Et il est capable de valider ces mots par une liste de règles (contient un "a", a un "e" à telle position, ne contient pas de "p", …). J'ai pu trouver 'favor' en quatre essais à coup de grep et grep -v. C'est donc un travail pour un ordinateur.

Je cherche tout d'abord à comprendre comment marche le jeu. Je lance le lien avec les outils de dev Firefox ouverts (F12). Je m'attends à des aller-retours avec le serveur pour valider les propositions de mots. Mais rien, tout est côté client ! Et quand c'est côté client, on regarde le source (CTRL+U).

Il y a un gros script de 177kB, très obfusqué, clairement passé dans la moulinette d'un builder JS. Je l'ouvre dans cudatext. Je browse un peu et vois rapidement une liste de mots de cinq lettres (le dictionnaire) … et juste après une autre liste de mots de cinq lettre (?).

obfuscated

J'extrais les deux listes et compte les mots : 2315 dans la première, 10657 dans la seconde, pas loin de mes 15k. À leur tête, je comprends que la première liste sont des mots courants, qui seront proposé à la devinette et que la deuxième est une liste de mots autorisés car dans le dictionnaire anglais mais beaucoup moins courant donc moins drôle à jouer.

En résumé, le jeu prends chaque jour un mot dans la première liste et valide les propositions du joueur sur l'union des deux listes.

Je suis assez curieux de savoir comment est choisi le mot du jour. Dans le javascript, je supprime la quasi totalité les mots des listes. Reste 77kB quand même. Je cherche format javascript sur le web et tombe sur un outil qui accepte de me reformater le script. Je remets ça dans cudatext, cherche un mot que j'ai laissé.

clear

Je vois que la liste (La) est utilisée dans une fonction (Na) un peu plus bas. J'instrumente à coup de console.log et je remets ça dans la source HTML. Miracle ou presque le script reformaté fonctionne parfaitement et mes traces apparaissent. L'algo est des plus simple : date du jour - date de début du jeu, en jours => index du mot dans la première liste. La liste n'étant pas triée, cela donne un mot "aléatoire".

Pour preuve, le mot d'aujourd'hui :

13jan

Promis je ne vous spoile pas le reste.

Exercice laissé au lecteur ou à moi même : implémenter le jeu en client-serveur afin de ne pas divulguer la liste et pourvoir tenir un leaderborad (et blinder le truc de pubs et de cryptominers pour faire des bouzoufs).

  • # SUTOM

    Posté par  (site Web personnel) . Évalué à 7 (+4/-0).

    On voit passer aussi du SUTOM https://sutom.nocle.fr/ (framagit https://framagit.org/JonathanMM/sutom ), en plus de Wordle. Par exemple les derniers gazouillis de B. Tréguier sont Wordle https://twitter.censors.us/btreguier/status/1481565919402987521 et SUTOM https://twitter.censors.us/btreguier/status/1481522325380120578

  • # Autre approche : grep

    Posté par  (site Web personnel) . Évalué à 9 (+7/-0). Dernière modification le 13/01/22 à 14:29.

    Note : je me base sur la liste des mots présents dans le dictionnaire américain de Debian, accessible via le paquet wamerican et listé dans le fichier /usr/share/dict/american-english

    Il est également possible de choisir ses mots en fonction de la quantité d’information contenus dans chacun d’eux. Par exemple, le dictionnaire anglais contient 102.774 entrées :

    $ wc -l american-english 
    102774 american-english

    et l’on se rend compte que le a est présent dans 52% d’entre eux :

    $ grep -i "a" american-english  | wc -l
    53715

    Si l’on choisi un mot avec un a, sans meme savoir quel sera le résultat, nous éliminons la moitié des mots possibles. Comme nous avons 5 lettres possibles, autant choisir celles qui permettent de discréminer un max de résultat. Et c’est parti pour une plongée en bash pour trouver la solution !

    $ grep -o . <<< "abcdefghijklmnopqrstuvwxyz"| while read letter; do echo $letter $(grep -i $letter american-english | wc -l); done
    a 53715
    
    e 65692
    
    n 47826
    
    r 50018
    
    t 44232
    
    $ grep "^.....$"  american-english | grep -i "a" | grep -i "r" | grep -i "n" | grep -i "t"
    Brant
    Grant
    Rutan
    Trina
    grant
    rants
    train

    essayons train avec le mot du jour : le a est reconnu, mais pas les autres lettres ! Parfait, il ne reste que 878 mots présents :

    $ grep "^.....$"  american-english | grep -i "a" | grep -iv "[trin]" > /tmp/iter1
    $ wc -l /tmp/iter1
    878

    On recommence notre itération :

    $ grep -o . <<< "abcdefghijklmnopqrstuvwxyz"| while read letter; do echo $letter $(grep -i $letter /tmp/iter1 | wc -l); done
    b 124
    c 169
    d 181
    e 370
    h 135
    l 342
    m 175
    o 137
    p 139
    s 504
    y 139
    
    $ grep "^.....$"  american-english | grep -i "s" | grep -i "l" | grep -i "e" | grep -i "d" | grep -i "m"
    melds

    31 mots restants ! On s’approche !

    $ grep "^.....$"  /tmp/iter1 | grep -i "a" | grep -i "e" | grep -iv "[trinmlds]" > /tmp/iter2
    $ wc -l /tmp/iter2
    31 /tmp/iter2
    $ grep -o . <<< "abcdefghijklmnopqrstuvwxyz"| while read letter; do echo $letter $(grep -i $letter /tmp/iter2 | wc -l); done
    b 6
    c 11
    f 2
    g 8
    h 9
    k 5
    o 2
    p 9
    q 2
    u 8
    v 6
    w 3
    x 1
    y 4
    z 1
    
    $ grep "^.....$"  /tmp/iter2 | grep -i "c" | grep -i "h" | grep -i "p"
    cheap
    peach

    Prenons-en un des deux, et faisant notre test : plus que 14 possibilité, et il reste 3 coups !

    $ grep "^.....$"  /tmp/iter1 | grep -i "a" | grep -i "e" | grep -iv "[trinmldspch]" > /tmp/iter3
    $ wc -l /tmp/iter3
    14 /tmp/iter3
    
    $ grep -o . <<< "abcdefghijklmnopqrstuvwxyz"| while read letter; do echo $letter $(grep -i $letter /tmp/iter3 | wc -l); done | grep -v [01]
    b 4
    g 5
    k 4
    o 2
    q 2
    u 6
    v 4
    w 3
    
    $ grep "^.....$"  /tmp/iter3 | grep -i "u" 
    
    quake

    Plus que 5 mots dans la liste, et encore deux coup restants ! Je pense qu’on est bon !

    $ grep "^.....$"  /tmp/iter3 | grep -i "a" | grep -i "e" | grep -iv "[trinmldspchquk]"
    abbey
    above
    agave
    gaffe
    weave

    En fait, si l’on tient compte des informations sur le placement des lettres, on sait à ce moment là que le e n’est pas en dernière position, et il ne reste plus qu’une seule possibilité.

    Y a-t-il un volontaire pour mettre tout ça dans un petit scritp interractif qui s’occupe de nous trouver la solution ? :)

    • [^] # Re: Autre approche : grep

      Posté par  (site Web personnel) . Évalué à 3 (+1/-0). Dernière modification le 13/01/22 à 14:43.

      Notes en vrac :

      • ici, je me suis contenté d’appliquer un algorithme de type arbre de décision, afin de choisir quel est l’élément le plus pertinent à retenir.
      • avec le français, cela aurait été plus compliqué, à cause des accents dans les mots qu’il faut transformer pour uniformiser les lettres
      • enfin, j’ai commencé l’analyse en partant du dictionnaire complet, cela aurait été plus efficace si j’avais dès le début choisi les mots de 5 lettres pour identifier les fréquences.
    • [^] # Re: Autre approche : grep

      Posté par  . Évalué à 6 (+4/-0).

      Je remplacerais bien :

      grep -i "a" american-english  | wc -l

      par (pas juste plus court mais un processus en moins aussi) :

      grep -ic a american-english

      On peut appliquer la même à

      grep -o . <<< "abcdefghijklmnopqrstuvwxyz" |
      while read letter
      do 
        echo $letter $(grep -i $letter american-english | wc -l)
      done

      et aussi minimiser l'appel à une commande externe

      for letter in a b c d e f g h i j k l m n o p q r s t u v w x y z
      do
        echo "$letter $(grep -ic $letter american-english)"
      done

      Mais en fait, on connait déjà la fréquence des lettres discriminantes grâce à l'analyse fréquentielle : ETAOIN SHRDLU pour les douze premières…

      Dans le cas présent, on pourrait appliquer ton algo à un dictionnaire fixe, words5letters obtenu par

      grep '^.....$'  american-english

      que j'aurais tendance à juste écrire :

      grep -w '.....'  american-english
      # ou encore
      grep -Ew '.{5}'  american-english

      Mieux, le dictionnaire fixe pourrait ne contenir que la liste mise à nue par la rétro-ingénierie de ce journal.

      Dans cette liste, on pourra donc retrouver melds et ses anagrammes avec :

      grep -Eiw '[sledm]{5}' words5letters

      Et cheap et peach à partir de trois lettres seront donnés par (sauf erreur de ma part) :

      grep -Ei '(?[chp]?){3}' words5letters

      “It is seldom that liberty of any kind is lost all at once.” ― David Hume

      • [^] # Re: Autre approche : grep

        Posté par  (site Web personnel) . Évalué à 4 (+2/-0).

        J’avoue ne pas avoir preté vraiment attention à la beauté des lignes de code, elles étaient davantage là pour appuyer mon propos !

        Je m’en sors mieux en OCaml (solution trouvée au quatrième coup avec le mot du jour)

        • [^] # Re: Autre approche : grep

          Posté par  . Évalué à 4 (+2/-0).

          Pas de souci ; toute façon faire du script shell n'est pas toujours évident (raison pour laquelle dès que ça dépasse quelques lignes il vaut mieux se tourner vers un langage plus évolué que l'on maîtrise) ; et en mode exploration (usage interactif donc, comme ici) on ne se focalise pas sur la « beauté du code » (il vaut mieux d'ailleurs que ce soit les plus simple + intuitif + compréhensible…)
          J'ai voulu surtout rendre hommage à l'ami grep en pointant quelques raccourcis que l'on oublie souvent.

          Comme souvent avec OCaml, ton gist est juste beau (et on suit littéralement le raisonnement de l'arbre de décision.) Merci.

          “It is seldom that liberty of any kind is lost all at once.” ― David Hume

          • [^] # Re: Autre approche : grep

            Posté par  . Évalué à 2 (+0/-0).

            Une approche en ligne de commande mais pas vraiment optimisée est proposée ici.

            Surtout, ne pas tout prendre au sérieux !

  • # lexique d'entrainement en poche

    Posté par  . Évalué à 3 (+1/-0).

    Vous proposez un mot du dictionnaire (lequel ?), le jeu vous dit quelles lettres sont dans le mot à trouver et quelles lettres sont à la bonne place, quelles lettres n'y sont pas.
    J'ai joué mais je ne suis pas doué. Je connais combien de mots de cinq lettres en anglais …

    Pour le vocabulaire, il faut pratiquer comme on dit.

    J'étais tombé sur des jeux intéressants, de type Boggle, sur smartphone droid : Lexic puis Lexica qui prend en charge d'autres langues en plus de moderniser l'interface (par contre le code a pris un embonpoint terrible ces derniers temps…)

    Un peu dans le même esprit, mais plutôt comme Le mot le plus long sans le célèbre plateau de Hasbro, il y a 9P

    Par contre mon pc connaît plus de 15k mots d'anglais de cinq lettres, oui oui. Et il est capable de valider ces mots par une liste de règles (contient un "a", a un "e" à telle position, ne contient pas de "p", …). J'ai pu trouver 'favor' en quatre essais à coup de grep et grep -v. C'est donc un travail pour un ordinateur.

    Pour rester sur l'appareil de poche, en tant que cruciverbiste et un peu verbicruciste, j'étais tombé sur Crossword et peut-être Regex Crosword que je n'ai pas testé.

    “It is seldom that liberty of any kind is lost all at once.” ― David Hume

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.