Pour un rendu optimal, activez JavaScript

Jouer efficacement au Sutom

 Â·  ☕ 7 min de lecture  Â·  đŸ€– Hohenheim

Utiliser des regex pour résoudre SUTOM

Les regex


En informatique, il existe ce que l’on appelle des Regex, contraction de regular expression en anglais. En français on parle d’expressions rĂ©guliĂšres ou rationnelles. Les regex sont issues de thĂ©ories mathĂ©matiques et ont Ă©tĂ© crĂ©Ă©es initialement pour dĂ©crire des langages formels (ensemble de mots). A ce moment-lĂ  on est aux prĂ©mices de l’informatique moderne.

Aujourd’hui les regex sont utilisĂ©es un peu partout. On en retrouve au niveau des compilateurs et des interprĂštes notamment, mais aussi par exemple au niveau des champs de formulaires. Cela permet de rĂ©aliser des contrĂŽles sur les entrĂ©es faites par un utilisateur. Un exemple qui illustre bien cela : vĂ©rifier que la complexitĂ© d’un mot de passe lors de sa crĂ©ation ou modification respecte la politique de sĂ©curitĂ© mise en place par l’administrateur.

C’est justement cette application qui nous intĂ©resse. En appliquant des regex sur des chaines de caractĂšres, on obtient de puissants outils de filtrage.

Une expression rĂ©guliĂšre peut ĂȘtre simple :

\ba\w*\b

ou plus compliquée :

\b((2[0-4]\d|25[0-5]|[01]?\d\d?)\.){3}(2[0-4]\d|25[0-5]|[01]?\d\d?)\b

C’est pour cela que l’on a tendance à les “oublier”.

Une regex est constituée de motifs dont la syntaxe est trÚs riche. Je vais lister les plus courants :

MĂ©ta-caractĂšres
CaractĂšres Description
. Remplace tout caractĂšre
* Remplace une chaĂźne de 0,1 ou plusieurs caractĂšres
? Remplace exactement un caractĂšre
() Groupe capturant
[] Intervalle de caractĂšre
{} Quantificateur
\ DĂ©spĂ©cialise le caractĂšre spĂ©cial qu’il prĂ©cĂšde
^ Négation ou début de ligne
$ Fin de ligne
| Ou logique entre 2 sous-motifs
+ Numérateur
Répétitions
CaractĂšres Description
* RĂ©pĂšte un nombre de fois quelconque
+ RĂ©pĂšte au moins une fois
? RépÚte zéro ou une fois
{n} RĂ©pĂšte n fois
{n,m} RĂ©pĂšte entre n et m fois
{n,} RĂ©pĂšte au minimum n fois
FrontiĂšres de recherche
CaractĂšres Description
^ DĂ©but de ligne
$ Fin de ligne
\b Extrémité de mot
\B ExtrĂ©mitĂ© d’un non-mot
\A DĂ©but de la chaĂźne soumise
\G Fin de l’occurrence prĂ©cĂ©dente
\Z Fin de la chaüne soumise, à l’exclusion du caractùre final
\z Fin de la chaĂźne
Classe de caractĂšres
CaractĂšres Description
\d Une chiffre, Ă©quivalent Ă  [0-9]
\D Un non-chiffre, [^0-9]
\s Un caractĂšre blanc, [\t\n\x0B\f\r]
\S Un non-caractĂšre blanc, [^\s]
\w Un caractĂšre de mot, [a-zA-Z_0-9]
\W Un caractĂšre de non-mot, [^\w]
. Tout caractĂšre


Donc si l’on reprend mes exemple prĂ©cĂ©dents :

\ba\w*\b

recherche tous les mots commençant par la lettre a

alt-text

\b((2[0-4]\d|25[0-5]|[01]?\d\d?)\.){3}(2[0-4]\d|25[0-5]|[01]?\d\d?)\b

recherche 3 sĂ©quences de 1 Ă  3 digits terminĂ©s par “.” suivi d’une autre expression de 1 Ă  3 digits. Chacune de ces sĂ©quence n’excĂšde pas 255. Cette regex permet donc de capturer des adresses IP.

alt-text

Screenshots provenant de l’excellent site regex101 que je recommande vivement pour tester ses regex.

Mais comment appliquer cela au jeu Sutom ?

Sutom


Sutom est un jeu devenu viral. Le principe est simple : un mot entre 6 et 9 lettres est Ă  deviner. Le joueur dispose de la premiĂšre lettre du mot Ă  deviner, de sa longueur, et de 6 essais. A chaque essai :

  • les lettres bien placĂ©es sont entourĂ©es d’un carrĂ© rouge,
  • celles mal-placĂ©es d’un rond jaune,
  • les lettres restant sur le fond bleu ne font pas parti du mot Ă  deviner.


Prenons un exemple avec le mot Ă  trouver du 28 juillet 2022 :

alt-text

J’ai fait un premier essai avec le mot SIGNAL et j’ai obtenu les indications suivantes :

  • S et N sont bien placĂ©s

  • A est mal placĂ© mais prĂ©sent

  • I, G et L sont exclus (grisĂ©s sur le clavier)


D’essais en essais on accumule des informations sur la prĂ©sence ou non prĂ©sence des lettres et sur leur position.

Trouver le mot du jour avec des regex


On arrive au sujet principal de ce billet. Lorsqu’un humain joue à Sutom, il fait appel à :

  • son vocabulaire

  • sa logique.


Cela tombe bien car un ordinateur peut avoir les deux. Avec un dictionnaire on lui donne le vocabulaire. Quant à la logique, on peut lui apprendre. C’est là qu’interviennent nos regex.

Pour trouver le mot du jour, il faudrait donc donner à notre ordinateur une regex assez puissante pour filtrer dans un dictionnaire et nous donner des résultats à partir des informations données par le jeu. Une telle regex devrait en théorie pouvoir trouver le mot en 3 ou 4 essais.

Reprenons notre exemple du 28 juillet. Nous avons un mot de 6 lettres qui commence par un S.

Pour filtrer les mots de 6 lettres commençant par S il faut utiliser la regex suivante :

\bs.{5}\b

Rappelez-vous la premiĂšre partie du billet :

  • \b indique l’extrĂ©mitĂ© d’un mot,

  • le . qu’il s’agit de n’importe quel caractĂšre

  • le {5} que le caractĂšre prĂ©cĂ©dent est rĂ©pĂ©tĂ© exactement 5 fois.


Mon programme trouve 1003 mots dans le dictionnaire qui sont matchés par cette regex.

Parmi ces 1003 mots, j’ai essayĂ© SIGNAL. On obtient alors de nouvelles informations que l’on peut donner au programme :

  • le N est bien placĂ©

  • le A fait parti du mot mais n’est pas Ă  la bonne position

  • les lettres I, G et L ne sont pas prĂ©sentes dans ce mot

alt-text


Transcrivons ces informations sous la forme d’une nouvelle regex. Nous allons construire la regex en plusieurs Ă©tapes.

→ Nous cherchons les mots qui contiennent un A

Pour capturer cela on va utiliser une assertion positive (ou positive lookahead). L’assertion positive permet dire “je veux un A aprùs le S”. L’assertion positive a la forme (?=REGEX).

Une regex dans une regex, oui oui.

Nous cherchons n’importe quel caractùre (rappelez-vous c’est le ‘.’) suivi d’un A.

(?=.*a)

Si l’on reprend, à ce stade notre regex a la forme suivante :

\b(?=.*a)s.{5}\b

Les assertions servent Ă  matcher des patterns. Elles renvoient simplement True ou False si elles trouvent le pattern.

→ Maintenant il nous faut Ă©liminer les mots contenant lettres I, G ou L.

Pour filtrer ces mots, on va utiliser une assertion nĂ©gative. Cette derniĂšre a la forme (?!REGEX). Si la REGEX Ă  l’intĂ©rieur de l’assertion retourne TRUE, alors l’assertion retourne FALSE. Intuitif non ?

(?!.*[igl])

Concaténons cette assertion avec le reste :

\b(?=.*a)(?!.*[igl])s.{5}\b

→ Enfin n’oublions pas une information importante, la position du N est correcte.

Nous obtenons alors une regex finale :

\b(?=.*a)(?!.*[igl])s..n..\b

Si on la résume sommairement :

  1. S

  2. on veut un A

  3. on ne veut pas de I, G, L

  4. on revient aprùs le S, on met deux lettres n’importe lesquelles

  5. on met un N

  6. on met deux lettres n’importe lesquelles


Cette regex me permet d’obtenir une liste de seulement 18 mots candidats. Pas mal mais c’est encore trop pour trouver notre mot.

Essayons un nouveau mot au hasard à partir de la liste qui nous est retournée : STANDS.

alt-text

Ce coup-ci le A est bien positionné et nous pouvons éliminer les lettres T et D.

\b(?!.*[igltd])s.an..


La liste se rĂ©duit Ă  1 possibilitĂ©. C’est notre mot. “Sutom !” :)

alt-text

Comme on le voit les regex sont des outils bien pratiques. 3 essais au Sutom sont considérés comme un bon score.

J’ai utilisĂ© le dictionnaire qui est fourni par ma distribution : “/usr/share/dict/french”

J’ai des raisons de penser que ce dictionnaire n’est pas le mĂȘme que celui utilisĂ© par le jeu. Lors de la rĂ©daction de ce billet un mot du jour Ă©tait BALAISE. Or le dictionnaire de mon programme ne connait que l’orthographe BALEZE.

Pour ĂȘtre vraiment efficace, il faudrait utiliser le mĂȘme que le jeu. Je mets les sources Ă  dispo sur mon Github pour ceux qui veulent tester.


Note de fin

Le programme marche Ă©galement avec Wordle. Le principe est le mĂȘme que SUTOM mais il y a quelques variations. La longueur du mot Ă  deviner est fixe et on ne connait pas la premiĂšre lettre.

Avec ces paramÚtres, les regex sont moins efficaces que sur Sutom. Le mot est trouvé plutÎt aux alentours du 5Úme ou du 6Úme essai.

Ce comportement est normal puisque sans le filtre de la premiĂšre lettre, on a beaucoup plus de mots qui sont matchĂ©s par les regex. Une amĂ©lioration du programme pourrait ĂȘtre de proposer des mots avantageux en terme d’informations rĂ©cupĂ©rĂ©es. Je pense notamment au dictionnaire prĂ©sent sur le site Lexique qui donne les frĂ©quences d’occurrences.

Peut-ĂȘtre dans une v2 ;)


Hohenheim
RÉDIGÉ PAR
Hohenheim
Computer guy


Contenu