Tugas Anda adalah mengkompilasi regex ... dengan menentukan subtitusi untuk setiap karakter dalam sebuah regex.

Regex

Regex mendukung ini

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

Kenapa hanya 1 atau 0? Ini untuk penyederhanaan. Jadi regex hanya memiliki karakter berikut:

*()|10

Ini ditafsirkan sebagai berikut:

1. * adalah bintang Kleene (ulangi kelompok kiri atau 0 kali atau lebih).
2. | adalah pergantian (cocok jika regex ke kiri atau regex ke kanan cocok).
3. () adalah pengelompokan.
4. 1 cocok dengan karakter 1.
5. 0 cocok dengan karakter 0.

Bagaimana cara kompilasi?

Anda menentukan enam cuplikan kode: satu untuk mengganti setiap karakter regex. Misalnya, jika jawaban Anda adalah:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Kemudian Anda mengganti setiap regex dengan potongan kode masing-masing, jadi:

(0|11)*

diubah menjadi:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

Apa yang harus dilakukan oleh program yang dihasilkan?

Program Anda akan:

1. Ambil inputnya.
2. Keluarkan nilai kebenaran jika regex cocok dengan seluruh input.
3. Lain menghasilkan nilai falsy.

Input di luar 01adalah perilaku yang tidak terdefinisi. Masukan bisa kosong.

Aturan tambahan

1. Untuk karakter regex yang diberikan, cuplikan yang dihasilkan harus selalu sama.
2. Tidak ada awalan atau karakter sufiks yang ditambahkan sesudahnya.
3. Regex dijamin tidak kosong.

Mencetak gol

Cuplikan yang paling tidak dikombinasi adalah pemenangnya. Jadi skor untuk contoh kasus akan dihitung sebagai berikut:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Siput , 48 byte

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Jika kami harus mencari kecocokan sebagian daripada mencocokkan hanya input lengkap, maka itu akan sangat mudah. 0akan menjadi \0, 1akan menjadi \1, *akan menjadi ,, dan yang lain akan memetakan diri mereka sendiri. Sebaliknya ada banyak kejahatan untuk mencegah pertandingan dimulai di suatu tempat selain awal atau berakhir di tempat lain selain akhir. !(l.)adalah penegasan yang akan gagal jika awal pertandingan tidak di awal input. ~cocok dengan sel di luar input, sehingga ditambahkan ke semua karakter yang diizinkan berada di akhir regex. Jika ada karakter regex lain yang mengikuti, itu dibatalkan oleh kuantifier numerik0yang mengharuskannya dicocokkan 0 kali, pada dasarnya berkomentar. Untuk memungkinkan *( ,) bekerja dengan benar meskipun uji di luar batas dilakukan, aturan pencocokan braket bahasa banyak digunakan. Dari dokumentasi:

Pasangan kurung ()atau kurung kurawal yang cocok {}akan berperilaku seperti yang diharapkan (seperti kurung di regex), tetapi juga memungkinkan untuk meninggalkan setengah dari pasangan dan membuatnya disimpulkan, sesuai dengan aturan berikut. )atau }kelompokkan semua yang ada di sebelah kiri hingga instruksi pembuka grup terdekat yang tertutup dari jenis yang sama ( (atau {masing - masing), atau awal dari pola jika tidak ada. Itu menutup instruksi pembukaan tidak tertutup dari tipe yang berlawanan di tengah kisaran ini. Jika tidak cocok (atau {ditutup pada akhir pola.

Jelas seperti lumpur, bukan?

CJam, 151 byte

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Garis-garis sesuai dengan karakter 01(|)*(dalam urutan itu). Cobalah online!

Ini tidak menggunakan persamaan reguler bawaan atau jenis pencocokan pola lainnya. Faktanya, CJam tidak memiliki fitur ini. Alih-alih, itu dimulai dari ekspresi reguler yang diwakilinya dan membangun semua string yang mungkin cocok, untuk akhirnya memeriksa apakah input pengguna adalah salah satunya.

Tes berjalan

Berikut ini menggunakan program yang membaca ekspresi reguler dari STDIN, menggantikan masing-masing karakter dengan potongan yang tepat, dan akhirnya mengevaluasi kode yang dihasilkan untuk melihat apakah cocok dengan input yang ditentukan dalam argumen baris perintah.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Sayangnya, ini tidak terlalu cepat. Ini akan tersedak agak cepat jika ada lebih dari 9 karakter dalam input atau lebih dari satu bintang Kleene di regex.

Dengan biaya 5 byte tambahan - untuk total 156 byte - kita dapat menghasilkan string yang lebih pendek untuk mencocokkan input potensial terhadap dan mendupuplikasi mereka. Ini tidak mengubah cara kerja kode; itu hanya membuatnya lebih efisien.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1