El golf de regex de xkcd: el puzzle detrás del cómic 1313

El golf de regex, el puzzle que popularizó el cómic 1313 de xkcd, es el juego de escribir la expresión regular más corta que coincida con todas las palabras de una lista y con ninguna de otra. Como en el golf de verdad, gana quien da menos golpes. Aquí tienes la idea completa en un solo tablero; pruébalo:

Ese es todo el juego. Lo divertido es lo rápido que deja de ser fácil.

01El cómic que le dio nombre

En enero de 2014, el xkcd #1313, “Regex Golf”, presentó el juego a muchísimos programadores. Su primera viñeta muestra una regex que coincide con los subtítulos de Star Wars pero no con los de Star Trek:

Y el texto emergente del cómic sube la apuesta: un patrón de 63 caracteres que coincide con los apellidos de todos los presidentes electos de EE. UU. pero con ninguno de los candidatos a los que derrotaron.

Parece un galimatías, pero léela como una lista: cada fragmento entre las barras | atrapa a unos cuantos presidentes. Solo con j caen Jefferson, Jackson y Johnson.

02El error del remate

Ese mismo mes, Peter Norvig, entonces director de investigación de Google y coautor del libro de texto de referencia sobre IA, escribió un notebook para resolver el golf de regex de forma automática. Lo primero que hizo su prueba fue comprobar la respuesta del cómic. Falló:

[rn]t atrapa a fremont: John C. Frémont, que perdió las elecciones de 1856 frente a James Buchanan. Norvig dedujo que Randall había tomado como rival de Buchanan a Millard Fillmore, el candidato de un tercer partido ese año. Una respuesta de golf de regex solo es tan buena como sus listas de palabras.

03Cómo juega al golf de regex una máquina

El solucionador de Norvig es un razonamiento elegante, y merece la pena conocerlo porque es también como piensan los buenos golfistas humanos:

1. Reunir fragmentos candidatos. Toma todos los fragmentos cortos de los nombres de los ganadores, de uno a cuatro caracteres y con algunas letras cambiadas por ., como bu, a.a o r.e$.
2. Quedarse solo con los seguros. Un fragmento solo sirve si coincide con al menos un ganador y con ningún perdedor.
3. Cubrir a los ganadores. Ahora elige fragmentos hasta que todos los ganadores coincidan. Es el clásico problema de cobertura de conjuntos, que es NP-difícil, así que el solucionador elige de forma voraz: cada vez toma el fragmento con el mejor equilibrio entre ganadores cubiertos y caracteres gastados.
4. Unirlos con |.

El resultado mejoró al cómic en 9 caracteres:

También recortó la viñeta de Star Wars, de 10 caracteres a 9:

04Del puzzle al ritual diario

Juegos de navegador como regex.alf.nu convirtieron la idea en packs de niveles para ir superando uno tras otro. Regex Hunter toma el otro camino, el de Wordle:

05Un tablero del notebook de Norvig

Norvig también enfrentó entre sí los nombres de bebé más populares. Aquí tienes cinco nombres de niño y cinco de niña; el par es la longitud de su respuesta. ¿Puedes igualarlo, o superarlo?

06Juega al golf de regex hoy

Jugar la caza del día → Un nuevo puzzle de golf de regex cada día: atrapa a los monstruos, deja libres a los inocentes, iguala o mejora el par. Gratis, en tu navegador, sin registro.

Si prefieres técnica en lugar de historia, lee Estrategias de golf de regex: cómo superar el par.