Stratégies pour le golf de regex : comment battre le par

Le golf de regex est un jeu simple : vous recevez deux listes de mots. Écrivez l'expression régulière la plus courte qui correspond à tout ce qui est dans la première liste (les monstres) et à rien de la seconde (les innocents). Chaque caractère compte, et chaque plateau a un par : la longueur à battre.

L'astuce, c'est que le golf de regex ne parle pas vraiment de syntaxe. Il s'agit de voir. Voici sept réflexes qui séparent une réponse de 28 caractères d'une réponse de 5. Tous les exemples sont interactifs : tapez dans les plateaux, ou cliquez sur Essayer pour ouvrir le motif dans le bac à sable.

01Décrivez la différence, pas les mots

Le réflexe du débutant, c'est de décrire les monstres. Celui du golfeur, c'est de trouver le plus petit point commun que seuls les monstres partagent.

Les cinq monstres commencent par c et ont un t quelque part après. Aucun innocent ne remplit ces deux conditions. Cette observation vaut 23 caractères.

02Les ancres sont le filtre le moins cher qui soit

^ et $ coûtent un caractère chacune et peuvent éliminer des groupes entiers d'innocents. Regardez ce qui se passe quand on retire le ^ de la réponse ci-dessus :

Deux caractères d'ancre coûtent presque toujours moins cher que de rendre le reste du motif plus malin. Quand un plateau se départage par la position (le début ou la fin des mots), pensez d'abord aux ancres.

03Cherchez, ne faites pas correspondre le mot entier

Le golf de regex utilise une sémantique de recherche : votre motif doit seulement correspondre quelque part dans un mot, pas au mot entier. Inutile donc de tout entourer de ^…$ ou de rembourrer avec .* :

Au lieu de	Écrivez	Gain
^.*ing$	ing$	3
.*foo.*	foo	4
^(a|b)	^[ab]	1

Les .* en début et en fin ne sont que du rembourrage. (Le panneau de diagnostic de Regex Hunter les signale exactement pour cette raison.)

04Dépensez vos caractères là où ils comptent

Beaucoup de fonctionnalités des regex ont une écriture courte et une longue. Les golfeurs prennent toujours la courte :

Long	Court	Gain
[0-9]	\d	3
[A-Za-z0-9_]	\w	10
(a|b|c)	[abc]	2
.{2}	..	2
aa*	a+	1
(?:ab)+	(ab)+	2

Les groupes non capturants sont une bonne hygiène dans du code de production, et des caractères gaspillés au golf.

05Laissez les références arrière voir les motifs à votre place

Quand les monstres partagent une forme plutôt que des lettres précises (une lettre doublée, un bloc répété), une référence arrière fait le travail. (.) capture n'importe quel caractère ; \1 exige à nouveau le même.

Essayez sur un plateau. Le par est la longueur de ce motif :

06L'espace négatif : dites ce qui ne peut pas y être

Parfois, les monstres se définissent par ce qui leur manque. Il y a deux façons de dire « aucun e nulle part », et l'une est plus courte :

Les lookaheads se rendent utiles quand il vous faut plusieurs conditions à la fois (« contient un chiffre et aucun espace »). Pour une seule lettre absente, la classe négative l'emporte.

07Quand rien n'est partagé, couvrez l'ensemble

Certains plateaux n'ont pas de règle unique et élégante. Le jeu devient alors un puzzle de couverture : trouvez quelques minuscules fragments (j, bu, a.a) qui attrapent chacun quelques monstres et aucun innocent, et reliez-les avec |. C'est exactement comme ça que fonctionne le célèbre solveur de Peter Norvig ; nous en parlons dans Le golf de regex de xkcd : l'énigme derrière la BD 1313.

08À vous de jouer

Un dernier plateau. Les monstres partagent une structure, et les innocents sont choisis pour punir les réponses évidentes : (.)\1 attrape les mauvais mots, et (.).\1 attrape presque tout. Saurez-vous atteindre le par ?

09Continuez à jouer

• Chaque jour, une nouvelle chasse avec un par à battre : jouez celle du jour.
• Les packs d'entraînement regroupent les plateaux par technique (ancres, classes, quantificateurs, références arrière) : commencez par les bases.
• Bloqué sur la syntaxe ? Le Guide des regex couvre chaque élément, et le bac à sable vous permet de tout tester.