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
\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.
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 :
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
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 :
-
S
-
on veut un A
-
on ne veut pas de I, G, L
-
on revient aprĂšs le S, on met deux lettres nâimporte lesquelles
-
on met un N
-
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.
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 !â :)
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 ;)