Matthias Goergens memiliki regex 25.604 karakter (turun dari karakter asli 63.993) untuk mencocokkan angka yang dapat dibagi dengan 7, tetapi itu termasuk banyak bulu: kurung redundan, distribusi ( xx|xy|yx|yydaripada [xy]{2}) dan masalah lainnya, meskipun saya yakin ada awal baru akan sangat membantu dalam menghemat ruang. Seberapa kecil ini bisa dibuat?
Setiap variasi ekspresi reguler yang masuk akal diizinkan, tetapi tidak ada kode yang dapat dieksekusi di regex.
Ekspresi reguler harus cocok dengan semua string yang berisi representasi desimal dari angka yang dapat dibagi oleh 7 dan tidak ada yang lain. Kredit ekstra untuk regex yang tidak memungkinkan 0s awal.
code-golf
math
regular-expression
Charles
sumber
sumber
Jawaban:
10791 karakter, angka nol di depan diizinkan
10795 karakter, angka nol di depan dilarang
0|((foo)0*)+, tempat regex di atas berada(0|foo)+.Penjelasan
Angka-angka yang dapat dibagi oleh 7 dicocokkan oleh otomat berhingga yang jelas dengan 7 keadaan Q = {0, ..., 6}, keadaan awal dan akhir 0, dan transisi d: i ↦ (10i + d) mod 7. Saya mengubah robot terbatas ini menjadi ekspresi reguler, menggunakan rekursi pada set negara perantara yang diizinkan:
Mengingat i, j ∈ Q dan S ⊆ Q, misalkan f (i, S, j) menjadi ekspresi reguler yang cocok dengan semua jalur otomat dari i ke j hanya menggunakan kondisi antara dalam S. Kemudian,
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S ∪ {k}, j) = f (i, S, j) ∣ f (i, S, k) f (k, S, k) * f (k, S, j).
Saya menggunakan pemrograman dinamis untuk memilih k sehingga meminimalkan panjang ekspresi yang dihasilkan.
sumber
0|((foo)0*)+13.75512.69912.731 KarakterRegex ini tidak menolak awalan nol.
Ini diuji dengan The Regex Coach .
Bagaimana Kami Sampai di Sana
Regex di atas diproduksi dengan terlebih dahulu membangun DFA yang akan menerima input yang kita inginkan (desimal dapat dibagi dengan 7) dan kemudian mengonversi ke Ekspresi Reguler dan memperbaiki notaion
Untuk memahami ini, ada baiknya terlebih dahulu membuat DFA yang menerima bahasa berikut:
Artinya, itu akan 'mencocokkan' angka-angka biner yang dapat dibagi oleh 7.
DFA terlihat seperti ini:
Bagaimana itu bekerja
Anda menyimpan nilai saat ini
Ayang mewakili nilai bit yang telah dibaca DFA. Ketika Anda membaca0laluA = 2*Adan ketika Anda membaca a1A = 2*A + 1. Pada setiap langkah Anda menghitungA mod 7maka Anda pergi ke negara yang mewakili jawabannya.Jadi uji coba:
Kita membaca di
10101mana representasi biner untuk 21 dalam desimal.q0, saat iniA=01, dari 'aturan' di atasA = 2*A + 1begituA = 1.A mod 7 = 1jadi kami pindah ke negaraq10,A = 2*A = 2,A mod 7 = 2jadi kami pindah keq21,A = 2*A + 1 = 5,A mod 7 = 5, pindah keq50,A = 2*A = 10,A mod 7 = 3, pindah keq31,A = 2*A + 1 = 21,A mod 7 = 0, pindah keq010101habis dibagi 7!Mengubah DFA ke Ekspresi Reguler adalah tugas yang sulit, jadi saya meminta JFLAP melakukannya untuk saya, menghasilkan yang berikut:
Untuk Angka Desimal
Prosesnya hampir sama:
Saya membuat DFA yang menerima bahasa:
Inilah DFA:
Logikanya mirip, jumlah negara yang sama hanya lebih banyak transisi untuk menangani semua angka desimal angka tambahan.
Sekarang aturan untuk mengubah
Apada setiap langkah adalah: ketika Anda membaca angka desimaln:A = 10*A + n. Kemudian lagi Anda hanyamodAdengan 7 dan pergi ke negara bagian berikutnya.Revisi
Revisi 5
Ekspresi reguler di atas sekarang menolak angka yang mengarah nol - selain dari nol itu sendiri tentu saja.
Ini membuat DFA sedikit berbeda, pada dasarnya Anda bercabang dari simpul awal ketika Anda membaca nol pertama. Membaca nol lainnya membuat Anda menjadi loop tak terbatas pada status bercabang. Saya belum memperbaiki diagram untuk menunjukkan ini.
Revisi 7
Melakukan beberapa "metaregex" dan mempersingkat regex saya dengan mengganti beberapa serikat pekerja dengan kelas karakter.
Revisi 10 dan 11 (oleh nhahtdh)
Modifikasi penulis untuk menolak memimpin nol tidak benar. Itu membuat regex gagal untuk mencocokkan angka yang valid, seperti 1110 (desimal = 14) dalam kasus binary regex, dan 70 dalam kasus regex desimal. Revisi ini mengembalikan modifikasi, dan akibatnya, memungkinkan nol nol di awal dan string kosong yang cocok.
Revisi ini meningkatkan ukuran regex desimal, karena mengoreksi bug di regex asli, yang disebabkan oleh hilangnya tepi (9) dari negara 5 ke negara 3 di DFA asli.
sumber
1110, dan yang untuk desimal tidak cocok70. Ini diuji dalam python dan perl. (Diperlukan python untuk mengonversi setiap(menjadi yang(?:pertama).NET regex,
119118105 byte111 karakter menolak 0s awal:
113 karakter yang menolak 0s awal dan mendukung angka negatif:
Coba di sini.
Penjelasan (dari versi sebelumnya)
Ini menggunakan teknik yang digunakan oleh berbagai jawaban dalam pertanyaan ini: Polisi dan Perampok: Reverse Regex Golf . .NET regex memiliki fitur yang disebut grup balancing, yang dapat digunakan untuk melakukan aritmatika.
(?<a>)mendorong grupa.(?<-a>)muncul itu dan tidak cocok jika tidak ada grup yangacocok sebelumnya.(?>...)Cocokkan dan jangan mundur nanti. Jadi itu akan selalu cocok hanya dengan alternatif yang cocok pertama.((?<-t>)(){3}|){6}Lipat gandakan jumlah grup t dengan 3. Simpan hasilnya dalam jumlah grup 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Cocokkan angka, dan jumlah grup 2 itu.((?<-2>){7}|){3}Hapus grup 2 beberapa dari 7 kali.((?<t-2>)|){6}Hapus grup 2 dan cocokkan dengan jumlah grup yang sama t.$(?(t)a)Jika masih ada grup yang cocok, cocokkanasetelah akhir string, yang tidak mungkin.Saya pikir versi 103 byte ini juga harus berfungsi, tetapi tidak menemukan solusi bug di kompiler.
sumber
468 karakter
Citarasa regex Ruby memungkinkan rekursi (meskipun ini semacam kecurangan), sehingga mudah untuk menerapkan DFA yang mengenali angka yang dapat dibagi dengan 7 menggunakan itu. Setiap grup bernama berkorespondensi dengan status, dan setiap cabang dalam pergantian mengkonsumsi satu digit dan kemudian melompat ke kondisi yang sesuai. Jika akhir angka tercapai, regex hanya cocok jika mesin berada dalam grup "A", jika tidak maka gagal.
Ia mengenali nol di depan.
sumber
{a*b*|a and b an equal amount of times})Saya benar-benar terkesan dengan jawaban Griffin dan perlu memikirkan cara kerjanya! Hasilnya adalah JavaScript berikut. (Ini karakter 3.5k, yang lebih pendek!)
genFungsi mengambil pembagi dan basis dan menghasilkan ekspresi reguler yang cocok dengan angka-angka dalam basis yang ditentukan yang dapat dibagi oleh pembagi itu.Saya telah menggeneralisasi NFA Griffin untuk basis apa pun:
nfafungsinya mengambil pembagi dan basis dan mengembalikan array transisi dua dimensi. Input yang diperlukan untuk beralih dari status 0 ke kondisi 2, misalnya, adalahstates[0][2] == "1".The
reducefungsi mengambil distatesarray dan berjalan melalui algoritma ini untuk menerjemahkan NFA untuk regex. Regex yang dihasilkan sangat besar dan terlihat seperti mereka memiliki banyak klausa yang berlebihan, meskipun ada upaya saya untuk optimasi. Regex untuk 7 basis 10 sekitar ~ 67k karakter; Firefox melempar "InternalError" untuk n> 5 mencoba menguraikan regex; menjalankan regex di Chrome mulai lambat untuk n> 6.Ada juga
testfungsi yang mengambil regex dan basis dan menjalankannya terhadap angka 0 hingga 100, jaditest(gen(5)) == [0, 5, 10, 15, ...].Meskipun hasilnya suboptimal, ini adalah kesempatan belajar yang fantastis, dan saya harap beberapa kode ini akan berguna di masa depan!
sumber
Perl / PCRE, 370 karakter
Menolak string kosong, serta string dengan awalan 0 (kecuali "0").
sumber