Meta Regex Golf

29

Im Geiste dieser xkcd

Geben Sie hier die Beschreibung des Links ein

Schreiben Sie ein Programm, das Regex-Golf mit beliebigen Listenpaaren spielt. Das Programm sollte zumindest versuchen, den regulären Ausdruck kurz zu halten. Ein Programm, das nur ausgibt /^(item1|item2|item3|item4)$/oder ähnliches, ist nicht zulässig.

Die Bewertung basiert auf der Fähigkeit, den kürzesten regulären Ausdruck zu generieren. Die Testlisten sind die der erfolgreichen und erfolglosen US-Präsidentschaftskandidaten, die Sie hier finden (danke @Peter). Natürlich muss das Programm für alle disjunkten Listen funktionieren, also zählt es nicht, einfach eine Antwort für den Präsidenten zurückzugeben.

Manishearth
quelle
3
/^item1|atem2|item3|item4$/Hat wahrscheinlich unbeabsichtigten Vorrang (Zeichenfolge muss entweder beginnen item1, enthalten atem2, enthalten item3oder enden mit item4).
Konrad Borowski
7
Dies wäre eine interessantere Herausforderung, wenn es ein Bewertungssystem gäbe, das in erster Linie auf der Größe der generierten regulären Ausdrücke basiert.
Peter Taylor
1
Im Geiste des XKCD-Titeltextes erfolgreiche und erfolglose US-Präsidentschaftskandidaten . (NB Ich habe diese Liste von Hand nach Wikipedia erstellt , daher kann es zu kleinen Fehlern kommen. Ich habe aus der Liste der Verlierer alle Nachnamen entfernt, die mit einem Gewinner übereinstimmen, da ansonsten eine Unterscheidung der Listen nicht möglich ist, aber ich habe sie absichtlich nicht anderweitig dedupliziert.) .
Peter Taylor
4
Ich frage mich, ob Randall Munroe ein besserer Autor von Code-Golf-Herausforderungen ist als wir ...
Johannes Kuhn
6
Ich frage mich, ob Randall Munroe auf diese Frage verzichten wird.
Stand

Antworten:

8

Perl (111 110 122 Zeichen)

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

Hierbei wird das aufgerufene CPAN-Modul Regexp::Assembleverwendet, um die regulären Ausdrücke zu optimieren. Denn was ist die bessere Sprache für reguläre Ausdrücke als Perl.

Auch lesbare Version, nur zum Spaß (mit Hilfe von -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 $_;

Beispielausgabe (ich habe danach STRG-D ausgeführt item4).

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

Außerdem schreibe ich als Bonus den regulären Ausdruck für jedes Wort in der Frage.

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

Auch Liste der Präsidenten (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
quelle
Dies scheint stdin für eine Liste zu lesen und zu erzwingen, dass die andere leer ist. Sicherlich ist das nicht das, wonach die Frage fragt?
Peter Taylor
1
@ PeterTaylor: Nun, es ist nicht so, dass die zweite Liste von Bedeutung ist. Sofern die zweite Liste keine Duplikate der ersten Liste enthält, ist der reguläre Ausdruck gültig. Es wäre schön, eine kürzere reguläre Ausdrucksweise zu haben, aber ich bin ein bisschen faul.
Konrad Borowski
IMO sollten Sie zumindest eine Möglichkeit haben, es als Eingabe zu verwenden, auch wenn Sie es dann verwerfen.
Peter Taylor
@ PeterTaylor: Wenn du es sagst. Mein Programm akzeptiert jetzt zwei Argumente, von denen eines die erste ist.
Konrad Borowski
4
Das ist cool; Aber es erzeugt unnötig lange Ausdrücke, da es Ausschlüsse (für jede andere Liste) erzeugt, indem es mit jedem möglichen vollständigen Wort übereinstimmt . Das ist nicht ganz der gleiche Geist wie beim ursprünglichen Golf.
Nicole
4

Nicht meine Lösung (offensichtlich bin ich nicht Peter Norvig!), Aber hier ist eine Lösung der (leicht modifizierten) Frage mit freundlicher Genehmigung von ihm: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

Das Programm, das er gibt, ist wie folgt (seine Arbeit, nicht meine):

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'

Wobei Gewinner und Verlierer die Gewinner- bzw. Verliererliste sind (oder natürlich 2 Listen). Detaillierte Erläuterungen finden Sie im Artikel.

Mike HR
quelle
8
Obwohl der verlinkte Artikel interessant ist und ich ihn gerne gelesen habe, wäre es besser gewesen, ihn als Kommentar zu der Frage anstatt als Antwort zu veröffentlichen, da er die gestellte Frage nicht beantwortet.
Gareth
1
Du hast recht, es wäre vielleicht besser als Kommentar gewesen, ich habe es als Antwort gepostet, einfach weil es die Frage perfekt beantwortet. Ich habe die Lösung nicht kopiert, da ich dachte, das wäre unaufrichtig und ich versuche, jemand anderem Anerkennung für seine Arbeit zu zollen. Zusätzlich zu einem Programm, das Regex-Golf mit zwei Listenpaaren spielt, bietet es auch eine Fitnessfunktion und einen detaillierten Code Erklärung zusammen mit der Parallele zum Set-Cover-Problem, die ich nicht berücksichtigt hatte. Wenn Sie immer noch der Meinung sind, dass es nicht relevant ist, lassen Sie es mich wissen. Ich werde es löschen und als Kommentar posten.
Mike HR
1
Wenn du dir Sorgen machst, jemand anderem Anerkennung für seine Arbeit zu zollen, melde dich und frag nach einem Mod, um deine Antwort "Community-Wiki" zu machen.
Peter Taylor
1
@PeterTaylor cool, ich wusste nicht, dass das Protokoll gemacht wurde.
Mike HR
2

Meine Lösung in Faktor geschrieben :

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 ist der gleiche Algorithmus wie bei Norvig. Wenn es darum geht, die Lesbarkeit zu beeinträchtigen, können Sie wahrscheinlich viel mehr Zeichen weggolfen.

Björn Lindqvist
quelle
1
Zu Ihrer Information, Sie vermissen einige der Verlierer aus der offiziellen Liste (Burr, Jay, Badnarik, wahrscheinlich andere, die ich nicht sehe). Ihre Ergebnisse sind also falsch. Beispielsweise funktioniert der erste reguläre Ausdruck nicht, da er mit Burr und Jay übereinstimmt.
Elixenide
1

Mein Code ist nicht sehr golfen und komprimiert, aber Sie können ihn unter https://github.com/amitayd/regexp-golf-coffeescript/ (oder speziell unter src / regexpGolf.coffee) überprüfen.

Es basiert auf dem Algorithmus von Peter Norvig mit zwei Verbesserungen:

  1. Erstellen Sie Teile zur Verwendung mit Zeichensätzen (dh verwenden Sie [ab] z, [ac] z und [bc] z, wenn gültige Teile az, bz und cz sind).
  2. Ermöglichen Sie es, "optimale Pfade" von Deckblättern zu konstruieren, und nicht nur ein Deckblatt, das bei jeder Iteration aus dem besten Kandidaten besteht.

(Und warf auch in einer optionalen Zufälligkeit)

Für die Gruppen von Gewinnern / Verlierern in diesem Quiz habe ich einen Regex mit 76 Zeichen gefunden:

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

Weitere Details in meinem Blogbeitrag zum Portieren des Lösers auf coffeescript .

Amitay Dobo
quelle
2
Könnten Sie bitte Ihren Code in Ihrer Antwort enthalten? Andernfalls können wir den Code nicht sehen, ohne auf den Link zu klicken!
wizzwizz4