Membalikkan regex dari bunga majemuk

9

Koronkorko adalah kata dalam bahasa Finlandia untuk bunga majemuk . Kami tidak ingin bunga majemuk dalam string kami, jadi mari kita cari persamaan reguler sesingkat mungkin untuk mengecualikannya.

Diberikan string yang hanya terdiri dari karakter alfabet huruf besar AZ, tentukan persamaan reguler sesingkat mungkin yang cocok dengan string jika tidak mengandung substring KORONKORKO. String apa pun yang berisi KORONKORKOsebagai substring tidak boleh dicocokkan dengan regex.

Hanya karakter A- Z, [, ], -, ^, , ?, *, +, |, (, dan )harus digunakan dalam ekspresi.

Saya pikir ini bisa dilakukan dengan 118 karakter dalam ekspresi. Bisakah Anda membuatnya lebih pendek?

Catatan: Tantangan ini dari Ohjelmointiputka (dalam bahasa Finlandia).

code-golf regular-expression tamu
sumber
Jika !karakter yang diizinkan, Anda bisa melakukannya ^((?!KORONKORO).)*$selama 19 byte.
Mama Fun Roll
3
@MamaFunRoll Saya pikir itu sebabnya ! tidak diizinkan.
Alex A.
Saya bersenang-senang mencoba bekerja di sekitar situs Finlandia, dan saya percaya apa yang Anda cari adalah ekspresi regex teoretis yang cocok dengan / menolak string input. Sebagai contoh, situs ini tampaknya hanya memungkinkan penggunaan kelas karakter dalam -dan ^dalam (jadi ^tidak dapat digunakan sebagai jangkar), dan kecocokan hanya dihitung jika seluruh string dicocokkan oleh regex (yaitu sekitar implisit ^$, seperti menentang "regex" normal yang menganggap string cocok dengan jika ada bagian yang cocok dengan regex)
Sp3000
Karena itu saya telah menghapus jawaban PCRE saya yang, meskipun seharusnya berfungsi bahkan dalam PHP, hampir pasti tidak diinginkan dalam kasus ini.
Sp3000
Saya lupa mengatakan bahwa situs memeriksa apakah ekspresi itu valid oleh fungsi ereg PHP. Dikatakan dalam diskusi di ohjelmointiputka.net/keskustelu/…
tamu

Jawaban:

6

204 karakter

(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?[^KO]|[^KR])|[^KO])|[^K])|[^KN])|[^KO])|[^KR])|[^KO])|[^K])*(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?)?)?)?)?)?)?)?)?

Dihasilkan dengan mengubah .*KORONKORKO.*menjadi mesin kondisi terbatas, membalikkan mesin kondisi terbatas, dan mengubahnya kembali menjadi regex.

orlp
sumber
Mengapa ini menjadi jawaban terbaik?
Bálint
1

Python, 77 79 97 118 byte

Sunting 3: Tulis ulang. Menggunakan lookaheads bersarang

^([^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^O]|O(?=$|[^N]|N(?=$|[^K]|K(?=$|[^O]|O(?=$|[^R]|R(?=$|[^K]|K(?=$|[^O]))))))))))*$

Regex 101

Edit 2: Ditambahkan '$ |' di seluruh regex. Sekarang, jika awalan KORONKORKO telah dicocokkan, item berikutnya yang cocok adalah end-of-string, karakter yang mengakhiri awalan, atau karakter yang memperluas awalan jika diikuti oleh sesuatu yang mengakhiri awalan.

Regex ini berfungsi dengan re.fullmatch(), yang ditambahkan dengan Python 3.4. Untuk digunakan dengan re.match(), ^dan $perlu ditambahkan ke awal dan akhir pola, masing-masing, untuk 2 byte lebih.

([^K]|K($|[^O]|O($|[^R]|R($|[^O]|O($|[^N]|N($|[^K]|K($|[^O]|O($|[^R]|R($|[^K]|K($|[^O]))))))))))*

Tautan Regex101

Solusi yang salah sebelumnya (lihat komentar):

K|([^K]|K([^O]|O([^R]|R([^O]|O([^N]|N([^K]|K([^O]|O([^R]|R([^K]|K[^O])))))))))*

Edit: Menambahkan single K

RootTwo
sumber
2
Saya tidak percaya ini cocok K.
orlp
@orip - Tangkapan yang bagus. Tetap.
RootTwo
Pembaruan terbaru gagal untukKKORONKORKO
Sp3000
Apakah bisa diperbaiki? Ada ide?
RootTwo
1
Awal ^dan akhir $tidak perlu. Juga, =dan $tidak diizinkan.
LegionMammal978