Meta regex golf

29

Dans l'esprit de ce xkcd

entrez la description du lien ici

Écrivez un programme qui joue au golf regex avec des paires de listes arbitraires. Le programme doit au moins tenter de raccourcir l'expression régulière, un programme qui ne fait que sortir /^(item1|item2|item3|item4)$/ou similaire n'est pas autorisé.

La notation est basée sur la capacité à générer l'expression régulière la plus courte. Les listes de tests sont celles des candidats à la présidentielle américains retenus et non retenus, trouvés ici (merci @Peter). Bien sûr, le programme doit fonctionner pour toutes les listes disjointes, donc le simple retour d'une réponse pour le président ne compte pas.

Manishearth
la source
3
/^item1|atem2|item3|item4$/a probablement une priorité inattendue (la chaîne doit commencer item1, contenir atem2, contenir item3ou se terminer par item4).
Konrad Borowski
7
Ce serait un défi plus intéressant s'il avait un système de notation basé principalement sur la taille des regex générées.
Peter Taylor
1
Dans l'esprit du texte du titre XKCD, candidats à la présidentielle américains réussis et non retenus . (NB j'ai fait cette liste à la main en suivant Wikipedia , donc il pourrait y avoir de petites erreurs; j'ai supprimé de la liste des perdants tous les noms de famille correspondant à un gagnant, car sinon distinguer les listes est impossible, mais je n'ai délibérément pas dédupliqué autrement) .
Peter Taylor
4
Je me demande si Randall Munroe est un meilleur auteur de défis de code-golf que nous ...
Johannes Kuhn
6
Je me demande si Randall Munroe va abandonner cette question.
stand le

Réponses:

8

Perl (111 110 122 caractères)

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

Celui-ci utilise le module CPAN appelé Regexp::Assembleafin d'optimiser les expressions régulières. Parce que quel est le meilleur langage pour les expressions régulières que Perl.

Aussi, version lisible, juste pour le plaisir (faite avec l'aide 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 $_;

Exemple de sortie (j'ai fait CTRL-D après item4).

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

Aussi, en bonus, j'écris l'expression régulière pour chaque mot de la question.

^(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)$

Aussi, liste des présidents (262 octets).

^(((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
la source
Cela semble lire stdin pour une liste et forcer l'autre à être vide. Ce n'est sûrement pas ce que la question demande?
Peter Taylor
1
@PeterTaylor: Eh bien, ce n'est pas que la deuxième liste soit importante. Sauf si la deuxième liste contient des doublons de la première liste, l'expression régulière est valide. Ce serait bien d'avoir une expression rationnelle plus courte, mais je suis en quelque sorte paresseux.
Konrad Borowski
OMI, vous devriez au moins avoir un moyen de le prendre comme entrée, même si vous le jetez ensuite.
Peter Taylor
@PeterTaylor: Si vous le dites. Mon programme prend maintenant deux arguments, l'un d'eux étant la première liste.
Konrad Borowski
4
C'est cool; mais il produit des expressions inutilement longues car il crée une exclusion (pour toute autre liste) en faisant correspondre chaque mot complet possible . Ce qui n'est pas tout à fait le même esprit que le golf d'origine.
Nicole
4

Pas ma solution (évidemment je ne suis pas Peter Norvig!) Mais voici une solution de la question (légèrement modifiée) avec l'aimable autorisation de lui: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

le programme qu'il donne est le suivant (son travail, pas le mien):

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'

où les gagnants et les perdants sont les listes des gagnants et des perdants respectivement (ou 2 listes bien sûr) voir l'article pour des explications détaillées.

Mike HR
la source
8
Bien que l'article lié soit intéressant et que j'aie aimé le lire, il aurait été préférable de le publier sous forme de commentaire sur la question plutôt que de réponse car il ne répond pas à la question posée.
Gareth
1
Vous avez raison, cela aurait peut-être été mieux comme commentaire, je l'ai posté comme réponse simplement parce qu'il répond parfaitement à la question. Je n'ai pas copié la solution car je pensais que ce serait malhonnête et essayer de prendre le crédit pour le travail de quelqu'un d'autre, en plus de fournir un programme qui joue au golf regex avec 2 paires de listes, il donne également une fonction de fitness et un code détaillé explication avec le parallèle au problème de la couverture d'ensemble que je n'avais pas considéré. Si vous pensez toujours que ce n'est pas pertinent, faites-le moi savoir, je vais le supprimer et le poster en tant que commentaire.
Mike HR
1
Si vous êtes inquiet de prendre le crédit pour le travail de quelqu'un d'autre, signalez et demandez un mod pour faire de votre réponse "wiki communautaire".
Peter Taylor
1
@PeterTaylor cool, je ne savais pas que c'était le protocole, fait.
Mike HR du
2

Ma solution écrite 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)

C'est le même algorithme que Norvig. Si le but est de nuire à la lisibilité, vous pouvez probablement jouer au golf avec beaucoup plus de personnages.

Björn Lindqvist
la source
1
Pour info, il vous manque un tas de perdants de la liste officielle (Burr, Jay, Badnarik, probablement d'autres que je ne vois pas). Donc, vos résultats sont incorrects; par exemple, le premier regex ne fonctionne pas, car il correspond à Burr et Jay.
elixenide
1

Mon code n'est pas d'une manière très golfique et condensée, mais vous pouvez le vérifier sur https://github.com/amitayd/regexp-golf-coffeescript/ (ou spécifiquement l'algorithme sur src / regexpGolf.coffee).

Il est basé sur l'algorithme de Peter Norvig, avec deux améliorations:

  1. Créez des parties à utiliser avec des jeux de caractères (c'est-à-dire utilisez [ab] z, [ac] z et [bc] z si les parties valides sont az, bz et cz).
  2. Permet de construire des "chemins optimaux supérieurs" de couvertures, et pas seulement une couverture faite du meilleur candidat à chaque itération.

(Et a également ajouté un caractère aléatoire facultatif)

Pour les ensembles de gagnants / perdants dans ce quiz, j'ai trouvé une expression régulière de 76 caractères en l'utilisant:

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

Plus de détails dans mon article de blog sur le portage du solveur en coffeescript .

Amitay Dobo
la source
2
Pourriez-vous s'il vous plaît contenir votre code dans votre réponse? Sinon, nous ne pouvons pas voir le code sans cliquer sur le lien!
wizzwizz4