Meta regex golf

29

En el espíritu de este xkcd

ingrese la descripción del enlace aquí

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.

Manishearth
fuente
3
/^item1|atem2|item3|item4$/probablemente tiene una precedencia no deseada (la cadena debe comenzar item1, contener atem2, contener item3o finalizar con item4).
Konrad Borowski
77
Este sería un desafío más interesante si tuviera un sistema de puntuación basado principalmente en el tamaño de las expresiones regulares generadas.
Peter Taylor
1
En el espíritu del texto del título XKCD, candidatos presidenciales estadounidenses exitosos y no exitosos . (Nota: hice esta lista a mano siguiendo Wikipedia , por lo que puede haber pequeños errores; he eliminado de la lista de perdedores todos los apellidos que coinciden con un ganador, porque de lo contrario es imposible distinguir las listas, pero deliberadamente no he deduplicado) .
Peter Taylor
44
Me pregunto si Randall Munroe es mejor escritor de desafíos de código de golf que nosotros ...
Johannes Kuhn
66
Me pregunto si Randall Munroe va a rechazar esta pregunta.
stand de

Respuestas:

8

Perl (111 110 122 caracteres)

use Regexp::Assemble;@ARGV=shift;my$r=new Regexp::Assemble;chomp,add$r "^\Q$_\E\$"while<>;$_=as_string$r;s/\(\?:/(/g;print

Utiliza el módulo CPAN llamado Regexp::Assemblepara 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).

use Regexp::Assemble;
my $r = Regexp::Assemble->new;
while (<>) {
    chomp($_);
    $r->add("^\Q$_\E\$");
}
$_ = $r->as_string;
# Replace wasteful (?:, even if it's technically correct.
s/\(\?:/(/g;
print $_;

Salida de muestra (hice CTRL-D después item4).

$ perl assemble.pl
item1
atem2
item3
item4
^(item[134]|atem2)$

Además, como beneficio adicional, estoy escribiendo la expresión regular para cada palabra en la pregunta.

^(a((ttemp)?t|llowed\.|rbitrary)?|\/\^item1\|atem2\|item3\|item4\$\/|s(ho(rt,|uld)|imilar)|p((air|lay)s|rogram)|(Writ|mak|Th)e|l(ists\.|east)|o([fr]|utputs)|t(h(at|e)|o)|(jus|no)t|regex|golf|with|is)$

Además, lista de presidentes (262 bytes).

^(((J(effer|ack|ohn)s|W(ashingt|ils)|Nix)o|Van Bure|Lincol)n|C(l(eveland|inton)|oolidge|arter)|H(a(r(rison|ding)|yes)|oover)|M(cKinley|adison|onroe)|T(a(ylor|ft)|ruman)|R(oosevelt|eagan)|G(arfield|rant)|Bu(chanan|sh)|P(ierce|olk)|Eisenhower|Kennedy|Adams|Obama)$
Konrad Borowski
fuente
Esto parece leer stdin para una lista y forzar a la otra a estar vacía. ¿Seguramente eso no es lo que pregunta?
Peter Taylor
1
@PeterTaylor: Bueno, no es que la segunda lista sea de importancia. A menos que la segunda lista tenga duplicados de la primera lista, la expresión regular es válida. Sería bueno tener una expresión regular más corta, pero soy un poco vago.
Konrad Borowski el
En mi opinión, al menos debería tener una forma de tomarlo como entrada, incluso si luego lo descarta.
Peter Taylor
@PeterTaylor: Si tú lo dices. Mi programa ahora toma dos argumentos, uno de ellos es la primera lista.
Konrad Borowski el
44
Esto es genial pero produce expresiones innecesariamente largas ya que crea exclusión (para cualquier otra lista) al hacer coincidir cada palabra completa posible . Que no es exactamente el mismo espíritu que el golf original.
Nicole
4

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):

def findregex(winners, losers):
    "Find a regex that matches all winners but no losers (sets of strings)."
    # Make a pool of candidate components, then pick from them to cover winners.
    # On each iteration, add the best component to 'cover'; finally disjoin them together.
    pool = candidate_components(winners, losers)
    cover = []
    while winners:
        best = max(pool, key=lambda c: 3*len(matches(c, winners)) - len(c))
        cover.append(best)
        pool.remove(best)
        winners = winners - matches(best, winners)
    return '|'.join(cover)

def candidate_components(winners, losers):
    "Return components, c, that match at least one winner, w, but no loser."
    parts = set(mappend(dotify, mappend(subparts, winners)))
    wholes = {'^'+winner+'$' for winner in winners}
    return wholes | {p for p in parts if not matches(p, losers)}

def mappend(function, *sequences):
    """Map the function over the arguments.  Each result should be a sequence. 
    Append all the results together into one big list."""
    results = map(function, *sequences)
    return [item for result in results for item in result]

def subparts(word):
    "Return a set of subparts of word, consecutive characters up to length 4, plus the whole word."
    return set(word[i:i+n] for i in range(len(word)) for n in (1, 2, 3, 4)) 

def dotify(part):
    "Return all ways to replace a subset of chars in part with '.'."
    if part == '':
        return {''}  
    else:
        return {c+rest for rest in dotify(part[1:]) for c in ('.', part[0]) }

def matches(regex, strings):
    "Return a set of all the strings that are matched by regex."
    return {s for s in strings if re.search(regex, s)}

answer = findregex(winners, losers)
answer
# 'a.a|i..n|j|li|a.t|a..i|bu|oo|n.e|ay.|tr|rc|po|ls|oe|e.a'

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.

Mike HR
fuente
8
Si bien el artículo vinculado es interesante y disfruté leerlo, habría sido mejor publicarlo como un comentario sobre la pregunta en lugar de como una respuesta, ya que no responde la pregunta planteada.
Gareth
1
Tienes razón, podría haber sido mejor como comentario, lo publiqué como respuesta simplemente porque responde a la pregunta perfectamente. No copié la solución porque pensé que sería falso y tratar de tomar el crédito por el trabajo de otra persona, además de proporcionar un programa que juega al golf regex con 2 pares de listas, también ofrece una función de estado físico y un código detallado explicación junto con el problema de la cobertura paralela al conjunto que no había considerado. Si aún cree que no es relevante, hágamelo saber, lo eliminaré y lo publicaré como comentario.
Mike HR
1
Si le preocupa tomar el crédito por el trabajo de otra persona, marque y solicite un mod para responder "Wiki de la comunidad".
Peter Taylor
1
@PeterTaylor genial, no sabía que ese era el protocolo, hecho.
Mike HR
2

Mi solución escrita en Factor :

USING:
    formatting fry
    grouping
    kernel
    math math.combinatorics math.ranges
    pcre
    sequences sets ;
IN: xkcd1313

: name-set ( str -- set )
    "\\s" split members ;

: winners ( -- set )
    "washington adams jefferson jefferson madison madison monroe
monroe adams jackson jackson vanburen harrison polk taylor pierce buchanan
lincoln lincoln grant grant hayes garfield cleveland harrison cleveland     mckinley
 mckinley roosevelt taft wilson wilson harding coolidge hoover roosevelt
roosevelt roosevelt roosevelt truman eisenhower eisenhower kennedy johnson     nixon
nixon carter reagan reagan bush clinton clinton bush bush obama obama" name-set ;

: losers ( -- set )
    "clinton jefferson adams pinckney pinckney clinton king adams
jackson adams clay vanburen vanburen clay cass scott fremont breckinridge
mcclellan seymour greeley tilden hancock blaine cleveland harrison bryan bryan
parker bryan roosevelt hughes cox davis smith hoover landon wilkie dewey dewey
stevenson stevenson nixon goldwater humphrey mcgovern ford carter mondale
dukakis bush dole gore kerry mccain romney" name-set winners diff
    { "fremont" } diff "fillmore" suffix ;

: matches ( seq regex -- seq' )
    '[ _ findall empty? not ] filter ;

: mconcat ( seq quot -- set )
    map concat members ; inline

: dotify ( str -- seq )
    { t f } over length selections [ [ CHAR: . rot ? ] "" 2map-as ] with map ;

: subparts ( str -- seq )
    1 4 [a,b] [ clump ] with mconcat ;

: candidate-components ( winners losers -- seq )
    [
        [ [ "^%s$" sprintf ] map ]
        [ [ subparts ] mconcat [ dotify ] mconcat ] bi append
    ] dip swap [ matches empty? ] with filter ;

: find-cover ( winners candidates -- cover )
    swap [ drop { } ] [
        2dup '[ _ over matches length 3 * swap length - ] supremum-by [
            [ dupd matches diff ] [ rot remove ] bi find-cover
        ] keep prefix
    ] if-empty ;

: find-regex ( winners losers -- regex )
    dupd candidate-components find-cover "|" join ;

: verify ( winners losers regex -- ? )
    swap over [
        dupd matches diff "Error: should match but did not: %s\n"
    ] [
        matches "Error: should not match but did: %s\n"
    ] 2bi* [
        dupd '[ ", " join _ printf ] unless-empty empty?
    ] 2bi@ and ;

: print-stats ( legend winners regex -- )
    dup length rot "|" join length over /
    "separating %s: '%s' (%d chars %.1f ratio)\n" printf ;

: (find-both) ( winners losers legend -- )
    -rot 2dup find-regex [ verify t assert= ] 3keep nip print-stats ;

: find-both ( winners losers -- )
    [ "1 from 2" (find-both) ] [ swap "2 from 1" (find-both) ] 2bi ;



IN: scratchpad winners losers find-both 
separating 1 from 2: 'a.a|a..i|j|li|a.t|i..n|bu|oo|ay.|n.e|ma|oe|po|rc|ls|l.v' (55 chars 4.8 ratio)
separating 2 from 1: 'go|e..y|br|cc|hu|do|k.e|.mo|o.d|s..t|ss|ti|oc|bl|pa|ox|av|st|du|om|cla|k..g' (75 chars 3.3 ratio)

Es el mismo algoritmo que el de Norvig. Si el objetivo es dañar la legibilidad, entonces probablemente puedas jugar muchos más personajes.

Björn Lindqvist
fuente
1
FYI, te estás perdiendo un montón de perdedores de la lista oficial (Burr, Jay, Badnarik, probablemente otros que no estoy viendo). Entonces, sus resultados son incorrectos; por ejemplo, la primera expresión regular no funciona, porque coincide con Burr y Jay.
elixenide
1

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:

  1. Cree partes para usar con conjuntos de caracteres (es decir, use [ab] z, [ac] z y [bc] z si las partes válidas son az, bz y cz).
  2. Permita construir "rutas óptimas superiores" de portadas, y no solo una portada hecha del mejor candidato en cada iteración.

(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:

[Jisn]e..|[dcih]..o|[AaG].a|[sro].i|T[ar]|[PHx]o|V|[oy]e|lev|sh$|u.e|rte|nle

Algunos detalles más en mi publicación de blog sobre portar el solucionador a coffeescript .

Amitay Dobo
fuente
2
¿Podría contener su código en su respuesta? De lo contrario, no podemos ver el código sin hacer clic en el enlace.
wizzwizz4