En el espíritu de este xkcd
Escriba un programa que juegue golf regex con pares arbitrarios de listas. El programa debería al menos intentar acortar la expresión regular, un programa que solo genera /^(item1|item2|item3|item4)$/
o similar no está permitido.
La puntuación se basa en la capacidad de generar la expresión regular más corta. Las listas de prueba son las de candidatos presidenciales estadounidenses exitosos y no exitosos, que se encuentran aquí (gracias @Peter). Por supuesto, el programa debe funcionar para todas las listas disjuntas, por lo que simplemente devolver una respuesta para el presidente no cuenta.
regular-expression
metagolf
Manishearth
fuente
fuente
/^item1|atem2|item3|item4$/
probablemente tiene una precedencia no deseada (la cadena debe comenzaritem1
, conteneratem2
, conteneritem3
o finalizar conitem4
).Respuestas:
Perl (
111110122 caracteres)Utiliza el módulo CPAN llamado
Regexp::Assemble
para optimizar las expresiones regulares. Porque cuál es el mejor lenguaje para expresiones regulares que Perl.Además, versión legible, solo por diversión (hecho con ayuda de
-MO=Deparse
).Salida de muestra (hice CTRL-D después
item4
).Además, como beneficio adicional, estoy escribiendo la expresión regular para cada palabra en la pregunta.
Además, lista de presidentes (262 bytes).
fuente
No es mi solución (¡obviamente no soy Peter Norvig!) Pero aquí hay una solución de la pregunta (ligeramente modificada) cortesía de él: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb
El programa que da es el siguiente (su trabajo, no el mío):
donde ganadores y perdedores son las listas de ganadores y perdedores respectivamente (o cualquiera de las 2 listas, por supuesto), vea el artículo para obtener explicaciones detalladas.
fuente
Mi solución escrita en Factor :
Es el mismo algoritmo que el de Norvig. Si el objetivo es dañar la legibilidad, entonces probablemente puedas jugar muchos más personajes.
fuente
Mi código no es muy de golf y condensado, pero puede consultarlo en https://github.com/amitayd/regexp-golf-coffeescript/ (o específicamente el algoritmo en src / regexpGolf.coffee).
Está basado en el algoritmo de Peter Norvig, con dos mejoras:
(Y también arrojó una aleatoriedad opcional)
Para los conjuntos de ganadores / perdedores en este cuestionario, encontré una expresión regular de 76 caracteres que la usaba:
Algunos detalles más en mi publicación de blog sobre portar el solucionador a coffeescript .
fuente