Le golf de regex de xkcd : l'énigme derrière la BD 1313

Le golf de regex, l'énigme rendue célèbre par la BD xkcd 1313, c'est le jeu qui consiste à écrire l'expression régulière la plus courte qui correspond à tous les mots d'une liste et à aucun d'une autre. Comme au vrai golf, moins de coups, c'est mieux. Voici toute l'idée en un seul plateau, essayez :

C'est tout le jeu. Le plaisir, c'est de voir à quelle vitesse il cesse d'être facile.

01La BD qui lui a donné son nom

En janvier 2014, xkcd #1313, « Regex Golf » a fait découvrir le jeu à beaucoup de développeurs. Sa première case montre une regex qui correspond aux sous-titres de Star Wars mais pas à ceux de Star Trek :

Et le texte au survol de la BD fait monter les enchères : un motif de 63 caractères qui correspond au nom de famille de chaque président américain élu, mais à aucun des candidats qu'ils ont battus.

On dirait du charabia, mais lisez-la comme une liste : chaque fragment entre deux barres | attrape quelques présidents. j à lui seul attrape Jefferson, Jackson et Johnson.

02Le bug dans la chute

Le même mois, Peter Norvig, alors directeur de la recherche chez Google et coauteur du manuel de référence en IA, a écrit un notebook pour résoudre le golf de regex automatiquement. Son premier test vérifiait la réponse de la BD. Il a échoué :

[rn]t attrape fremont : John C. Frémont, battu à l'élection de 1856 par James Buchanan. Norvig a compris que Randall avait retenu Millard Fillmore, le candidat d'un tiers parti cette année-là, comme adversaire de Buchanan. Une réponse au golf de regex ne vaut que ce que valent ses listes de mots.

03Comment un ordinateur joue au golf de regex

Le solveur de Norvig est un joli raisonnement, et il vaut la peine d'être connu parce que c'est aussi comme ça que pensent les bons golfeurs humains :

1. Rassembler des fragments candidats. Prenez tous les petits morceaux des noms des vainqueurs, d'un à quatre caractères, avec certaines lettres remplacées par ., comme bu, a.a ou r.e$.
2. Ne garder que les fragments sûrs. Un fragment n'est utile que s'il correspond à au moins un vainqueur et à aucun perdant.
3. Couvrir les vainqueurs. Choisissez ensuite des fragments jusqu'à ce que chaque vainqueur soit couvert. C'est le célèbre problème de couverture par ensembles, qui est NP-difficile : le solveur procède donc de façon gloutonne, en prenant à chaque fois le fragment qui offre le meilleur compromis entre vainqueurs couverts et caractères dépensés.
4. Les relier avec |.

Le résultat a battu la BD de 9 caractères :

Il a aussi raboté la case Star Wars, de 10 caractères à 9 :

04Du puzzle au rituel quotidien

Des jeux dans le navigateur comme regex.alf.nu ont transformé l'idée en packs de niveaux à enchaîner. Regex Hunter prend l'autre chemin, celui de Wordle :

05Un plateau tiré du notebook de Norvig

Norvig a aussi opposé les prénoms de bébés les plus populaires. Voici cinq prénoms de garçons et cinq de filles ; le par correspond à la longueur de sa réponse. Saurez-vous l'égaler, voire le battre ?

06Jouer au golf de regex aujourd'hui

Jouer la chasse du jour → Une nouvelle énigme de golf de regex chaque jour : attrapez les monstres, épargnez les innocents, égalez ou battez le par. Gratuit, dans votre navigateur, sans inscription.

Si vous préférez la technique à l'histoire, lisez Stratégies pour le golf de regex : comment battre le par.