Golf metex regex

29

Dalam semangat xkcd ini

masukkan deskripsi tautan di sini

Tulis program yang memainkan golf regex dengan daftar daftar yang berubah-ubah. Program setidaknya harus berusaha untuk membuat regex pendek, sebuah program yang hanya menghasilkan /^(item1|item2|item3|item4)$/atau serupa tidak diperbolehkan.

Penilaian didasarkan pada kemampuan untuk menghasilkan regex terpendek. Daftar tes adalah daftar kandidat presiden AS yang berhasil dan tidak berhasil, ditemukan di sini (terima kasih @Peter). Tentu saja, program harus bekerja untuk semua daftar yang terpisah, jadi hanya mengembalikan jawaban untuk presiden yang tidak diperhitungkan.

Manishearth
sumber
3
/^item1|atem2|item3|item4$/mungkin memiliki prioritas yang tidak disengaja (string harus dimulai dengan item1, mengandung atem2, berisi item3, atau diakhiri dengan item4).
Konrad Borowski
7
Ini akan menjadi tantangan yang lebih menarik jika memiliki sistem penilaian terutama berdasarkan ukuran regex yang dihasilkan.
Peter Taylor
1
Dalam semangat teks judul XKCD, kandidat presiden AS yang sukses dan tidak berhasil . (NB Saya membuat daftar ini dengan tangan mengikuti Wikipedia , jadi mungkin ada kesalahan kecil; Saya telah menghapus dari daftar pecundang semua nama keluarga yang cocok dengan seorang pemenang, karena kalau tidak, membedakan daftar itu tidak mungkin, tapi saya sengaja tidak sebaliknya didupuplikasi) .
Peter Taylor
4
Saya ingin tahu apakah Randall Munroe adalah penulis tantangan kode-golf yang lebih baik daripada kita ...
Johannes Kuhn
6
Saya ingin tahu apakah Randall Munroe akan menjawab pertanyaan ini.
stan

Jawaban:

8

Perl (111 110 122 karakter)

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

Ini menggunakan modul CPAN yang dipanggil Regexp::Assembleuntuk mengoptimalkan ekspresi reguler. Karena apa bahasa yang lebih baik untuk ekspresi reguler daripada Perl.

Juga, versi yang mudah dibaca, hanya untuk bersenang-senang (dibuat dengan bantuan -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 $_;

Output sampel (saya lakukan setelah CTRL-D item4).

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

Juga, sebagai bonus, saya menulis regex untuk setiap kata dalam pertanyaan.

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

Juga, daftar presiden (262 byte).

^(((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
sumber
Ini tampaknya membaca stdin untuk satu daftar dan memaksa yang lain menjadi kosong. Tentunya bukan itu pertanyaannya?
Peter Taylor
1
@PeterTaylor: Yah, bukan itu daftar kedua yang penting. Kecuali daftar kedua memiliki duplikat daftar pertama, regexp valid. Akan menyenangkan memiliki regexp yang lebih pendek, tapi saya agak malas.
Konrad Borowski
IMO Anda setidaknya harus memiliki cara untuk mengambilnya sebagai input, meskipun Anda kemudian membuangnya.
Peter Taylor
@PeterTaylor: Jika Anda mengatakannya. Program saya sekarang mengambil dua argumen, salah satunya menjadi daftar pertama.
Konrad Borowski
4
Ini keren; tetapi menghasilkan ekspresi yang panjang dan tidak perlu karena membuat pengecualian (untuk daftar lain) dengan mencocokkan setiap kata lengkap yang mungkin . Semangat yang tidak sama dengan golf asli.
Nicole
4

Bukan solusi saya (jelas saya bukan peter norvig!) Tapi inilah solusi dari pertanyaan (sedikit dimodifikasi) dari dia: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb

program yang dia berikan adalah sebagai berikut (pekerjaannya, bukan pekerjaan saya):

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'

di mana pemenang dan pecundang adalah pemenang dan pecundang masing-masing (atau 2 daftar saja) lihat artikel untuk penjelasan rinci.

Mike HR
sumber
8
Walaupun artikel yang ditautkan menarik dan saya senang membacanya, ini akan lebih baik diposting sebagai komentar pada pertanyaan daripada sebagai jawaban karena tidak menjawab pertanyaan yang diajukan.
Gareth
1
Anda benar, mungkin lebih baik sebagai komentar, saya mempostingnya sebagai jawaban hanya karena menjawab pertanyaan dengan sempurna. Saya tidak menyalin solusi karena saya pikir itu akan menjadi tidak jujur ​​dan mencoba mengambil kredit untuk pekerjaan orang lain, selain menyediakan program yang memainkan golf regex dengan 2 pasang daftar itu juga memberikan fungsi kebugaran dan kode rinci Penjelasan bersama dengan paralel ke masalah cover set yang saya tidak mempertimbangkan. Jika Anda masih menganggapnya tidak relevan, beri tahu saya, saya akan menghapus dan memposting sebagai komentar.
Mike HR
1
Jika Anda khawatir tentang mengambil kredit untuk karya orang lain, tandai dan minta mod untuk membuat jawaban Anda "Komunitas wiki".
Peter Taylor
1
@PeterTaylor keren, saya tidak tahu itu protokolnya, sudah selesai.
Mike HR
2

Solusi saya ditulis dalam 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)

Ini algoritma yang sama dengan Norvig. Jika merusak keterbacaan adalah tujuannya, maka Anda mungkin bisa bermain golf lebih banyak karakter.

Björn Lindqvist
sumber
1
FYI, Anda kehilangan sekelompok pecundang dari daftar resmi (Burr, Jay, Badnarik, mungkin orang lain yang tidak saya lihat). Jadi, hasil Anda salah; misalnya, regex pertama tidak berfungsi, karena cocok dengan Burr dan Jay.
elixenide
1

Kode saya tidak dalam mode golf-ish dan kental, tetapi Anda dapat memeriksanya di https://github.com/amitayd/regexp-golf-coffeescript/ (atau secara khusus algoritma di src / regexpGolf.coffee).

Ini didasarkan pada algoritma Peter Norvig, dengan dua peningkatan:

  1. Buat bagian untuk digunakan dengan set karakter (yaitu gunakan [ab] z, [ac] z, dan [bc] z jika bagian yang valid adalah az, bz dan cz).
  2. Izinkan untuk membangun "jalur optimal teratas" dari sampul, dan bukan hanya sampul yang dibuat dari kandidat terbaik di setiap iterasi.

(Dan juga melemparkan keacakan opsional)

Untuk kumpulan pemenang / pecundang dalam kuis ini, saya menemukan 76 chars regex menggunakannya:

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

Beberapa lebih detail di posting blog saya tentang porting solver ke coffeescript .

Amitay Dobo
sumber
2
Bisakah Anda memuat kode Anda dalam jawaban Anda? Kalau tidak, kita tidak dapat melihat kode tanpa mengklik tautan!
wizzwizz4