Pemesanan Parsial Pola Regex

25

Untuk tujuan tantangan ini, kami mengatakan bahwa pola regex cocok dengan string jika seluruh string dicocokkan dengan pola, bukan hanya substring.

Mengingat dua pola regex  A  dan  B , kita mengatakan bahwa  A  adalah lebih khusus dari  B   jika setiap string yang cocok dengan  A  juga cocok dengan  B   tetapi tidak sebaliknya. Kita mengatakan bahwa  A  adalah setara dengan  B  jika kedua pola sama persis dengan set yang sama string. Jika pola tidak lebih khusus dari yang lain mereka juga tidak setara, kita mengatakan bahwa  A  dan  B  yang tak tertandingi .

Misalnya, polanya Hello, .*!lebih khusus daripada .*, .*!; polanya (Hello|Goodbye), World!dan Hello, World!|Goodbye, World!setara; dan pola Hello, .*!dan.*, World! tidak ada bandingannya.

Relasi "lebih terspesialisasi daripada" mendefinisikan urutan parsial ketat pada set pola regex. Khususnya, untuk semua pola  A  dan  B , tepat satu dari yang berikut ini benar:

  • A  lebih khusus daripada  B  ( A < B ).
  • B  lebih khusus daripada  A  ( A > B ).
  • A  dan  B  adalah setara ( A = B ).
  • A  dan  B  tidak tertandingi ( A ∥ B ).

Ketika  A  dan  B  tidak dapat dibandingkan, kita dapat membedakan lebih lanjut antara dua kasus:

  • A  dan  B  adalah saling lepas ( A ∥ B ), yang berarti bahwa ada string cocok dengan mereka berdua.
  • A  dan  B  yang berpotongan ( A ≬ B ), yang berarti bahwa beberapa string dicocokkan oleh keduanya.

Tantangan

Tulis program atau fungsi yang mengambil sepasang pola regex dan membandingkannya menggunakan urutan di atas. Artinya, jika dua pola yang  A  dan  B , program harus menentukan apakah  A < B ,  A > B ,
A = B  atau  A ∥ B .

× 92% Bonus  tambahan diberikan jika, ketika polanya tidak tertandingi, program menentukan apakah mereka berpotongan atau terpisah.

Masukan dan keluaran

Program harus menerima dua pola regex, sebagai string, dalam rasa yang ditentukan di bawah ini. Anda dapat membaca input melalui STDIN , baris perintah , sebagai argumen fungsi atau metode yang setara . Anda dapat mengasumsikan bahwa polanya valid.

Program harus menghasilkan satu dari empat output yang berbeda (atau lima output yang berbeda jika Anda akan mendapatkan bonus di atas,) tergantung pada hasil perbandingan (output yang tepat terserah Anda.) Anda dapat menulis output ke STDOUT , kembalikan sebagai hasil fungsi atau gunakan metode yang setara .

Regex Flavour

Anda dapat mendukung fitur regex apa pun yang Anda suka, tetapi Anda harus mendukung yang berikut:

  • Pergantian dengan |.
  • Kuantifikasi dengan *.
  • Pengelompokan dengan (dan ).
  • Mencocokkan karakter apa pun (mungkin tidak termasuk baris baru) dengan ..
  • (Opsional: × 80% Bonus)  Mencocokkan kelas karakter yang sederhana dan yang dinegasikan dengan […]dan [^…], masing-masing. Anda tidak harus mendukung kelas karakter yang telah ditentukan sebelumnya (mis. [:digit:]) Tetapi Anda harus mendukung rentang karakter.
  • Karakter lolos dengan \. Setidaknya harus dimungkinkan untuk meloloskan karakter khusus (yaitu |*().[^-]\) dan lebih disukai juga karakter khusus yang umum dalam rasa lain (misalnya {}), tetapi perilaku ketika melarikan diri karakter tidak spesifik tidak ditentukan. Khususnya, Anda tidak harus mendukung urutan pelarian khusus seperti \nuntuk baris baru dan sejenisnya. Sebuah implementasi yang mungkin adalah hanya untuk mengambil karakter mengikuti huruf \sebagai literal.

Anda dapat mengasumsikan keberadaan karakter input yang tidak dapat dicocokkan dengan literal apa pun (yaitu hanya dapat dicocokkan dengan .dan kelas karakter yang dinegasikan.)

Aturan tambahan

  • Anda dapat menggunakan pustaka regex atau fungsionalitas regex bawaan hanya untuk tujuan pencocokan dan penggantian string.
  • Anda dapat mengabaikan masalah terkait lokal, seperti aturan pengumpulan.
  • Untuk menyatakan yang sudah jelas: program Anda harus diakhiri. Itu harus dieksekusi dalam jumlah waktu yang wajar diberikan pola-pola khas (pasti tidak lebih dari satu jam, lebih disukai jauh lebih sedikit.)

Mencetak gol

Ini adalah kode-golf. Skor Anda adalah produk dari ukuran kode , dalam byte, dan bonus apa pun . The skor terendah menang.

Uji Kasus

Format kasus uji adalah sebagai berikut:

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

<Test ID>
<Pattern A>
<Ordering>
<Pattern B>

...

Di mana <Test ID>pengenal untuk kasus uji, <Pattern A>dan <Pattern B>merupakan pola regex dan <Ordering>urutan di antara mereka, dan merupakan salah satu dari:

  • <: <Pattern A>lebih terspesialisasi daripada <Pattern B>.
  • >: <Pattern B>lebih terspesialisasi daripada <Pattern A>.
  • =: Polanya sama.
  • |: Pola-pola tidak tertandingi dan terpisah.
  • X: Pola-pola tidak tertandingi dan berpotongan.

Nilai khusus <empty pattern>berarti pola kosong.

A. Pola dasar

Tampilkan cuplikan kode

B. Pola kompleks

Tampilkan cuplikan kode

C. Pola dasar dengan kelas karakter

Tampilkan cuplikan kode

D. Pola kompleks dengan kelas karakter

Tampilkan cuplikan kode

Program Tes

Cuplikan berikut dapat digunakan untuk membandingkan pola regex:

<style>#main {display: none;}#main[loaded] {display: inline;}.pattern_container {position: relative;}.pattern_underlay, .pattern {font: 12pt courier, monospace;overflow: hidden;white-space: pre;padding: 7px;box-sizing: border-box;}.pattern_underlay {background-color: #dddddd;color: #707070;border-radius: 4px;box-shadow: 0.5px 0.5px 2.5px #aaaaaa;}.pattern_underlay[error] {background-color: #ffccbb;}.pattern {position: absolute;left: 0px;top: 0px;background: none;border: none;width: 100%;height: 100%;resize: none;white-space: normal;}#ordering {min-width: 28pt;text-align: center;font-size: 16pt;}#status {padding: 5px;background-color: #fffdce;box-shadow: 1.5px 1.5px 3.5px #aaaaaa;font-size: 10pt;white-space: pre;display: none;}#status[error] {display: inline;background-color: #ffe8df;}#status[loading] {display: inline;}.inline_code {background-color: #dddddd;font: 12pt courier, monospace;padding: 2px;}.placeholder {visibility: hidden;}.error_text {background-color: #fffcb7};</style><span id="main"><table><tr><td><div class="pattern_container"><div class="pattern_underlay" id="pattern1_underlay"></div><textarea class="pattern" id="pattern1" oninput="compare()">Hello, .*!</textarea></div></td><td id="ordering"></td><td><div class="pattern_container"><div class="pattern_underlay" id="pattern2_underlay"></div><textarea class="pattern" id="pattern2" oninput="compare()">.*, .*!</textarea></div></td></tr></table><br></span><span id="status" loading>Loading...</span><script type='text/javascript'>var Module = {setStatus: function (status) {document.getElementById("status").innerHTML = status;if (status == "") {compare();document.getElementById("status").removeAttribute("loading");document.getElementById("main").setAttribute("loaded", 1);}}};function underlay_chars(str) {if (/^\n*$/.exec(str))return str.split("\n").map(function () { return '<span class="placeholder"> \n</span>'; });if (str.indexOf("\n") >= 0)str = str.replace(/\s*$/gm, function (m) { return m.replace(/[^\n]/g, "\0"); });return (str + "\n").split("").map(function (c) {if (c == "\0") return "·";else return '<span class="placeholder">' + c + '</span>';});}function underlay_str(str) {return underlay_chars(str).join("");}function str_to_array32(str) {a = [];for (c of str) {n = c.charCodeAt(0);a.push(n & 0xff, (n >> 8) & 0xff, (n >> 16) & 0xff, n >> 24);}a.push(0, 0, 0, 0);return a;}function compare() {try {for (e of ["pattern1_underlay", "pattern2_underlay", "status"])document.getElementById(e).removeAttribute("error");for (e of ["pattern1", "pattern2"])document.getElementById(e + "_underlay").innerHTML = underlay_str(document.getElementById(e).value);c = Module.ccall("regex_compare", "number", ["array", "array"], [str_to_array32(document.getElementById("pattern1").value),str_to_array32(document.getElementById("pattern2").value)]);if (c >= 0)document.getElementById("ordering").innerHTML = "∥≬<>="[c];else {i = Module.ccall("regex_error_index", "number", [], []);l = Module.ccall("regex_error_length", "number", [], []);e = document.getElementById("pattern" + -c + "_underlay");t = underlay_chars(document.getElementById("pattern" + -c).value);e.setAttribute("error", 1);e.innerHTML =t.slice(0, i).join("") +'<span class="error_text">' + t.slice(i, i + l).join("") + "</span>" +t.slice(i + l).join("");e.setAttribute("error", 1);throw "Pattern error: " + Module.ccall("regex_error", "string", [], []).replace(/`(.*?)'/g, '<span class="inline_code">$1</span>');}} catch (e) {document.getElementById("ordering").innerHTML = "??";document.getElementById("status").innerHTML = e;document.getElementById("status").setAttribute("error", 1);}}</script><script async type="text/javascript" src="https://gist.githack.com/anonymous/91f27d6746566c7b4e4c/raw/c563bf84a01c3a1c6e5f021369a3e730a2e74a1a/rpo.js"></script>
Luaskan cuplikan

code-golf regular-expression Elo
sumber
10
Wow. Jawaban apa pun yang dikirim ke ini mendapat +1 otomatis dari saya. Menentukan apakah dua bahasa formal isomorfis cukup sulit. Menentukan apakah satu adalah subbahasa dari yang lain adalah proyek CS sarjana lengkap. @ ___ @
COTO
Apakah ada perilaku tertentu untuk pola regex yang tidak valid?
Paul Guyot
@ PaulGuyot No. Anda dapat mengasumsikan polanya valid.
Ell
1
Saya bertanya-tanya - apakah Anda menulis memenangkan diri sendiri (untuk melihat seberapa layak untuk pertanyaan kode golf) atau bukan?
haskeller bangga
1
@proudhaskeller saya lakukan; Saya menulis cuplikan tes. Ini adalah tantangan yang sulit, dan tidak akan ada satu kalimat pun di sini, tetapi golf.
Ell

Jawaban:

10

Python 2, 522 byte * .92 = 480,24 537,28

Edit 2 : -60 byte

Edit : Menambahkan penjelasan.

Ditetapkan adalah fungsi fyang mengambil dua string pola sebagai argumen dan kembali '<', '=', '>','|' , atau 'X'. Diperlukan kurang dari satu menit untuk memproses semua kasus uji.

Kode ini terdiri dari berikut ini, tetapi dengan \r, \n \t, dan lolos hex (tapi tidak \0) diganti dengan nilai-nilai byte yang sebenarnya mereka.

#encoding=Latin
exec"""x\xda]RMo\xdb0\x0c\xbd\xe7Wx\'K\x96\x92\xc5mOR\xb8\xdf1@%|\x98%X\x80a\x19\x96\x02\x03n\xf2\xdfG:i;\xec$\x92z|\x8f_\x1b\x84%m~\xca\xbe\x1c\x0e\xbd\x0fU\x10Agi\x0e\x87\xea\n\x1f\xf9n{=\xea\0\x93\x08\xd2\xaez\xd0\x99\xcc,m\x07g\xbb\x80s\x9b\x08\xee\x8cRo"\xf3\x8bHy!-\x95\xd7\xa9\x8aS\xb50O5\xc3&\xb68\x0b\xe7\xb1\x19t\x92\x8a\x1d\xaf]\xc2f\x94\x92\x111T\xf3\xf1j\xba\x1b\x081r\xa2\x97\xea\xa5\x11\x03\x9bI\xca\xe6\xed\xe7\xab\xbd\xde`\xb6\x8b"\xd1\xc5\xf7\xd7?^l\xa7\xaeKK\xd7i\x91\x92\x8b\xaaE\x16\x8e\x9c\x12#3\x86\xe0"\xc6\xc9\x15\xfd\x86\xae\\\xde\xcc^\xa7\x94;,\xea\x94t\x08\x84\xa6J\x82\xee%\xb1\xe8\xacW\xb9\xb3\x14f\xd9\x84\xeb\x89\xe1\x8b\xd5\xa3r\xeb\xbf\x81D\rS\xf5\x8b/\xd7e\xaao\xf0\xeb\xf2\xbbv\xdd\xf1\x15\x1f\x93\xe4Aq\xff\x19\xc6\x98\x8b\xa8E\xad\xb2\xaae-m\x843\xc5\xd7!\x8e\xbe\xca.\x1a4\x01\xe8E;@-\xe4\xad9\xd5\xa7\x10\xa7\x9eg\xcea\x10\x83\x0e\xd2\r\x973\xb2o\xb8\xd7\x06\xc2\x0f\xa8\xdf\xdfk\x1b\x15\xb4v\x84H\xc9\xad]\xc1\x83C;\x03m\xc3\x16p\x1f\xe3\x1d\xbf\xa4\xe2\xbe\x8d\x1eX)\x1e\t\x9dv\xf3\xa9\xcd\xe8xGU\x9e\x0b\t\x97\xd6\x0c\x8c\xf2\nxa\xa9\x19u\xaf\xf2iN3\r\xd1\xae\x0f\xe3\x13\x0c@h\xb5W\xb0\xaad3\xef\t\x91s]R=~\xc3^Lv\xc7\x16\x15\xf4\xfb\xa7\x88ze_~B\x06\x80\x99\x03\x86\x7f\x0bY\x06U\xd2.\xeaV\x95\x87$\xd1\xce\xff\x8b\xbf\x9a\x99\xe0\x03u\xa1 =o0<n\xd0\xef]s`b\xb7\x98\x89\xael\xd2\x85\xceO:>\x80j\xfa\xdeb\x95\x95k\x91N\xbe\xfc'5\xac\xe7\xe8\x15""".decode('zip')

Pernyataan di atas menyebabkan kode berikut ini dijalankan:

z=frozenset
def f(f,s):
 u={s};d,l,f=n(f);w,h,s=n(s);_=0;r=[[z(f[0]),z(s[0])]]
 for e,o in r:
  p=z(zip([e]*h,o)+zip(e,[o]*l))
  if p-u:_|=((l in e)+2*(h in o))*4/3;u|=p;r+=[[reduce(z.__or__,(oo[i+1]for i in ii if ff[i]in[t,4][t<4:]),z())for ii,oo,ff in(e,f,d),(o,s,w)]for t in z([d[i]for i in e]+[w[i]for i in o])]
 return'|=><X'[_-3]
def n(s):
 s=list('('+s+')');i=0
 while s[i:]:f=s[i];h='()|*.'.find(f);s[i]=(h,f)[h<0];s[i:i+1]*=f!='\\';i+=1;l=i;h=1;w=e=[];p=[0];t=[{l}]
 while i:
  d=[i];i-=1;o=[i];f=s[i];t=[{i}]+t
  if f<1:h-=1;e+=zip(o*l,d+s.pop());w.pop()
  if f==1:h+=1;w=w+o;s+=[[]];e+=[o+d]
  if f==2:s[-1]+=d;e+=[(i,w[-1])]
  if h==p[-1]:e+=[t[-1:]+o,[i,1+t.pop()]];p.pop()
  if f==3:p+=[h];t+=o
 for f,o in e:
  for n in t:n|=(n,t[o])[f in n]
 return s+[1],l,t

Jika sampel kode kedua disimpan dalam string s, sesuatu yang mirip dengan yang pertama dapat dihasilkan oleh ekspresi '#encoding=Latin\nexec"""%s"""'%__import__('zlib').compress(s). Mungkin perlu untuk memperbaiki beberapa karakter seperti null bytes atau backslash. Kode unzipped hampir 1000 800 byte jadi mungkin lebih membingungkan daripada golf ... tapi setidaknya saya berhasil sedikit golf encoding: dari Latin1ke Latin.

Penjelasan

Program ini bekerja dengan menggunakan indeks string sebagai cara kasar untuk melacak status parsing string. The nFungsi membangun tabel transisi. Pertama ia mem-parsing string dan menemukan semua contoh dari dua jenis transisi. Pertama, ada transisi yang tidak melibatkan penambahan surat ke string. Misalnya, melompat dari a *ke awal ekspresi terkuantifikasi. Kedua, ada transisi menambahkan karakter, yang hanya bergerak maju dengan satu indeks. Kemudian penutupan transitif dari transisi tanpa-karakter dihitung, dan itu diganti untuk tujuan transisi 1-karakter. Jadi ini mengembalikan pemetaan indeks dan karakter ke satu set indeks.

Fungsi utama melakukan BFS atas kemungkinan string input. Ini melacak satu set semua indeks yang mungkin untuk fragmen string apa pun yang sedang dipertimbangkan. Yang kami tertarik untuk menemukan adalah keadaan yang diterima oleh kedua regex, atau oleh satu dan bukan yang lain. Untuk menunjukkan bahwa suatu regex diterima, Anda hanya perlu menemukan satu jalur transisi yang mungkin ke akhir pola. Tetapi untuk menunjukkan bahwa seseorang ditolak, perlu untuk menganalisis semua jalur yang mungkin. Oleh karena itu, untuk menentukan apakah himpunan status yang mungkin untuk pola A dan pola B sudah dicakup oleh yang telah dianalisis sebelumnya, pasangan negara tunggal dalam satu regex dan himpunan semua negara yang memungkinkan di yang lain dicatat. Jika tidak ada yang baru, maka boleh kembali. Tentu saja, itu juga akan mungkin, dan lebih sedikit karakter,

feersum
sumber
Sangat bagus! Lulus semua tes dalam grup A dan B (sepertinya tidak ada kelas karakter.) Saya tidak bisa menjalankan versi kompresi, atau mendapatkan jumlah byte yang sama. Either way, Anda dapat mengklaim x 0.92bonus saat Anda menghitung skor Anda. Dan, tentu saja, sebuah penjelasan diterima!
Ell
4

Haskell, 560 553 618

mungkin mendapatkan beberapa bonus dilakukan di masa depan.

ini belum sepenuhnya golf.

import Data.List
c%j|'\\':h:s<-j=[s|c==h]|(a,b):_<-[(a,b)|x<-[0..length j],(a,'|':b)<-[splitAt x j],snd(k b)==[]]=c%a++c%b|'(':s<-j,(a,_:'*':b)<-k s=map(++j)(c%a)++c%b|'(':s<-j,(a,_:b)<-k s=map(++b)(c%a)|h:'*':s<-j=map(++j)(c%[h])++c%s
c%"."=[""|c>'\0']
c%s@[_]=c%('\\':s)
c%(a:b)=map(++b)(c%[a])
c%s=[""|c>'\0']
a&b=nub[(x,nub$b>>=(c%))|c<-[' '..'~'],x<-c%a]
g e(k@(a,l):r)|j<-a&l\\e=g(k:e)(j++r)
g e[]=e
a#b=or[all(null.('\0'%))m|(x,m)<-g[][(a,[b])],""<-'\0'%x]
a!b|a#b,b#a='x'|a#b='>'|b#a='<'|0<1='='
k"("=("","(")
k(c:s)|'('<-c,(x,y)<-k$tail b=('(':a++')':x,y)|')'<-c=("",')':s)|0<1=(c:a,b)where(a,b)=k s
k j=(j,j)

penjelasan algoritma yang bergelombang:

reg!reg' mengembalikan karakter yang diperlukan, salah satu dari "= <> x".

a#bbenar jika tidak setiap string yang acocok juga cocok dengan b.

c%regadalah daftar ekspresi reguler yang regcocok dengan c:ssalah satu regexps dalam output yang cocok s. saya pada dasarnya sebagian cocok dengan regex. kecuali jika cadalah '\0'. maka itu memaksa reguntuk tidak mendapatkan input lagi, kembali []jika regharus mendapatkan lebih banyak input untuk mencocokkan dan [""]sebaliknya.

#bekerja dengan menghasilkan daftar yang terbatas dari semua "regex-state" yang mungkin, kedua regexps akan berada di setelah string arbitrer. kemudian untuk memeriksa apakah a<bkita memeriksa cuaca ada "regex-state" di mana asepenuhnya cocok tetapi btidak sepenuhnya cocok.

haskeller bangga
sumber
Keren! Anda jelas berada di jalur yang benar. Namun, saat ini gagal tes B4.
Ell