Meta regex golf

29

W duchu tego xkcd

wprowadź opis linku tutaj

Napisz program, który gra w wyrażenie regularne z dowolnymi parami list. Program powinien przynajmniej starać się, aby wyrażenie regularne było krótkie, program, który po prostu wyświetla dane wyjściowe /^(item1|item2|item3|item4)$/lub podobny, jest niedozwolony.

Punktacja opiera się na zdolności do generowania najkrótszego wyrażenia regularnego. Listy testowe to listy odnoszących sukcesy i nieudanych kandydatów na prezydenta USA, które można znaleźć tutaj (dzięki @Peter). Oczywiście program musi działać na wszystkich rozłącznych listach, więc zwyczajne zwrócenie odpowiedzi prezydentowi nie jest brane pod uwagę.

Manishearth
źródło
3
/^item1|atem2|item3|item4$/prawdopodobnie ma niezamierzone pierwszeństwo (ciąg musi zaczynać się item1, zawierać atem2, zawierać item3lub kończyć item4).
Konrad Borowski
7
Byłoby to bardziej interesujące wyzwanie, gdyby miał system punktacji oparty głównie na wielkości wygenerowanych wyrażeń regularnych.
Peter Taylor
1
W duchu tekstu tytułowego XKCD zwycięscy i nieudani kandydaci na prezydenta USA . (Uwaga: sporządziłem tę listę ręcznie na podstawie Wikipedii , więc mogą występować niewielkie błędy; usunąłem z listy przegranych wszystkie nazwiska pasujące do zwycięzcy, ponieważ inaczej rozróżnienie list jest niemożliwe, ale celowo nie deduplikowałem inaczej) .
Peter Taylor
4
Zastanawiam się, czy Randall Munroe jest lepszym pisarzem wyzwań związanych z golfem niż my ...
Johannes Kuhn
6
Zastanawiam się, czy Randall Munroe rzuci to pytanie.
stoisko

Odpowiedzi:

8

Perl (111 110 122 znaków)

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

Wykorzystuje moduł CPAN wywoływany Regexp::Assemblew celu optymalizacji wyrażeń regularnych. Ponieważ jaki jest lepszy język dla wyrażeń regularnych niż Perl.

Również wersja do odczytu, dla zabawy (wykonana za pomocą -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 $_;

Przykładowe dane wyjściowe (zrobiłem CTRL-D później item4).

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

Jako bonus piszę wyrażenie regularne dla każdego słowa w pytaniu.

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

Ponadto lista prezydentów (262 bajtów).

^(((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
źródło
Wygląda na to, że odczytuje stdin dla jednej listy i wymusza pustą drugą. Z pewnością nie o to pyta pytanie?
Peter Taylor
1
@PeterTaylor: Cóż, nie jest tak, że druga lista ma jakiekolwiek znaczenie. Jeśli druga lista nie ma duplikatów pierwszej listy, wyrażenie regularne jest poprawne. Byłoby miło mieć krótsze wyrażenie regularne, ale jestem trochę leniwy.
Konrad Borowski
IMO powinieneś mieć przynajmniej sposób, aby wziąć to jako dane wejściowe, nawet jeśli następnie je odrzucisz.
Peter Taylor
@PeterTaylor: Jeśli tak mówisz. Mój program przyjmuje teraz dwa argumenty, z których jeden jest pierwszą listą.
Konrad Borowski
4
To jest fajne; ale generuje niepotrzebnie długie wyrażenia, ponieważ tworzy wykluczenie (dla każdej innej listy) poprzez dopasowanie każdego możliwego pełnego słowa. Co nie jest tym samym duchem, co oryginalny golf.
Nicole
4

Nie moje rozwiązanie (oczywiście nie jestem Peter Norvig!), Ale oto rozwiązanie (nieznacznie zmodyfikowanego) pytania, które dzięki niemu: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

program, który daje, jest następujący (jego praca, nie moja):

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'

gdzie zwycięzcami i przegranymi są odpowiednio listy zwycięzców i przegranych (lub dowolne 2 listy, oczywiście) zobacz artykuł w celu uzyskania szczegółowych wyjaśnień.

Mike HR
źródło
8
Chociaż link do artykułu jest interesujący i lubię go czytać, lepiej byłoby opublikować go jako komentarz do pytania niż jako odpowiedź, ponieważ nie odpowiada na postawione pytanie.
Gareth,
1
Masz rację, mogło być lepiej jako komentarz, opublikowałem to jako odpowiedź, ponieważ doskonale odpowiada na pytanie. Nie skopiowałem rozwiązania, ponieważ myślałem, że byłoby to nieuczciwe i staram się docenić czyjąś pracę, oprócz zapewnienia programu, który gra w regex golfa z 2 parami list, daje również funkcję fitness i szczegółowy kod wyjaśnienie wraz z równoległym do problemu z ustawieniem okładki, którego nie wziąłem pod uwagę. Jeśli nadal uważasz, że to nie ma znaczenia, daj mi znać, usunę je i opublikuję jako komentarz.
Mike HR
1
Jeśli martwisz się o uznanie za czyjąś pracę, oflaguj i poproś o mod, aby Twoja odpowiedź była „Wiki społeczności”.
Peter Taylor
1
@PeterTaylor spoko, nie wiedziałem, że to protokół, gotowe.
Mike HR
2

Moje rozwiązanie napisane w 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)

Jest to ten sam algorytm, co algorytm Norviga. Jeśli celem jest poprawienie czytelności, prawdopodobnie możesz odegrać w golfa wiele innych postaci.

Björn Lindqvist
źródło
1
Do Twojej wiadomości brakuje ci kilku przegranych z oficjalnej listy (Burr, Jay, Badnarik, prawdopodobnie innych, których nie widzę). Twoje wyniki są niepoprawne; na przykład pierwsze wyrażenie regularne nie działa, ponieważ pasuje do Burra i Jaya.
elixenide
1

Mój kod nie jest bardzo golfowy i skondensowany, ale możesz to sprawdzić na https://github.com/amitayd/regexp-golf-coffeescript/ (a konkretnie algorytm w src / regexpGolf.coffee).

Opiera się na algorytmie Petera Norviga, z dwiema ulepszeniami:

  1. Utwórz części do użycia z zestawami znaków (tj. Użyj [ab] z, [ac] z i [bc] z, jeśli poprawnymi częściami są az, bz i cz).
  2. Pozwalaj konstruować „najlepsze optymalne ścieżki” okładek, a nie tylko okładkę wykonaną z najlepszego kandydata podczas każdej iteracji.

(A także wrzucił opcjonalną losowość)

Dla zestawów zwycięzców / przegranych w tym quizie znalazłem 76 wyrażeń regularnych, używając go:

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

Więcej szczegółów w moim blogu na temat przenoszenia solvera do coffeescript .

Amitay Dobo
źródło
2
Czy możesz podać swój kod w swojej odpowiedzi? W przeciwnym razie nie zobaczymy kodu bez kliknięcia linku!
wizzwizz4