Sesuaikan permutasi!

15

Tantangan Anda adalah membuat regex yang cocok dengan setiap permutasi string itu sendiri, dan tidak ada yang lain. Pertandingan juga harus peka terhadap huruf besar-kecil.

Jadi, misalnya, jika regex Anda adalah:

ABC

Itu harus cocok (dan hanya cocok) string ini:

ABC
ACB
BAC
BCA
CAB
CBA

Seharusnya tidak cocok dengan hal-hal seperti:

AABC (contains an extra A)
ABCD (contains an extra D)
AC   (no B)
AAA  (no B and C, extra 2 A's)
abc  (case-sensitive)

Aturan:

  • Anda diizinkan menggunakan rasa regex yang Anda sukai.
  • Celah standar berlaku.
  • Anda harus memiliki setidaknya dua karakter berbeda dalam kode Anda. Itu berarti solusi seperti 1tidak valid.
  • Regex harus hanya berisi ASCII yang dapat dicetak, dan tidak ada yang lain.
clismique
sumber
Juga terkait: Karakter dihitung dalam kode sumber
jimmy23013
Saya pikir (ABC|ACB|BAC|BCA|CAB|CBA)tetapi Anda menginginkan jawaban umum.
Stephen Quan

Jawaban:

11

JavaScript, 64 57 byte

4 byte dihapus berkat Martin Ender.

^(?!.*([^])(.*\1){3}]?)[$$[-^?!!.'''-*11{33}5577\\-]{57}$

Coba di sini.

Penjelasan (kedaluwarsa)

^                                  # Beginning of the string.
(?!.*                              # Match only the strings that don't contain...
  (.)(.*\1){4}                     #     5 occurrences of the same character.
  [^1]?[^1]?                       #     Something that doesn't matter.
)
[]zzz^(?!!!.**[)\\1{{44}}666]{64}  # 64 occurrences of these 16 characters.
                                   # Some are duplicated to make sure the regex
                                   # contains 4 occurrences of each character.
\z                                 # End of the string.
jimmy23013
sumber
2
Saya pikir ini bekerja untuk 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101
Martin Ender
Ini hampir berfungsi di .NET:^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]*
jimmy23013
Apa yang tidak berhasil? Mengejar umpan baris?
Martin Ender
@ MartinEnder Ya.
jimmy23013
2

Perl dan PCRE regex, 280 byte

^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z

(Sedikit) lebih mudah dibaca:

^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z

Ini berjalan dalam O (2 ^ n) waktu seperti yang ditulis, sehingga sangat tidak efisien. Cara termudah untuk mengujinya adalah mengganti setiap kemunculan.* dengan .*?, yang menyebabkan case yang cocok diperiksa terlebih dahulu (artinya cocok dengan waktu linier, tetapi masih membutuhkan waktu eksponensial jika gagal mencocokkan).

Ide dasarnya adalah bahwa kita menegakkan panjang regex menjadi sama dengan 280, dan menggunakan pernyataan lookahead untuk memaksa setiap karakter dalam regex untuk muncul setidaknya beberapa kali, misalnya (?=(.*z){2})memaksa zkarakter untuk tampil setidaknya dua kali. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23adalah 280, jadi kami tidak dapat memiliki "ekstra" kemunculan karakter apa pun.

Ini adalah contoh pemrograman autogram , sebuah kalimat yang menggambarkan dirinya dengan mencantumkan jumlah setiap karakter yang dikandungnya (dan, dalam hal ini, juga total panjang). Saya cukup beruntung dalam membangunnya (biasanya Anda harus menggunakan brute force tetapi saya menemukan solusi ini saat menguji program brute-force saya sebelum saya sepenuhnya selesai menulisnya).

Perl dan PCRE regex, 253 byte, bekerja sama dengan Martin Ender

Saya berhipotesis bahwa mungkin ada solusi yang lebih pendek yang menghilangkan beberapa digit (kemungkinan besar 9, 8, atau 7). Martin Ender menemukan satu, ditunjukkan di bawah:

^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z

Versi yang dapat dibaca:

^
(? = (. * z) {2})
(? = (. * * () {39})
(? = (. * *)) {39})
(? = (. * * *) {20})
(? = (. * *.) {21})
(? = (. * 0) {4})
(? = (. * 1) {6})
(? = (. * 2) {11})
(? = (. * 3) {6})
(? = (. * 4) {3})
(? = (. * 5) {2})
(? = (. * 6) {3})
(? = (. * 9) {4})
(? = (. * *) {20})
(? = (. * *?) {20})
(? = (. * \\) {9})
(? = (. * * ^) {2})
(? = (. * *) {21})
(? = (. *}) {21})
. {253} \ z

sumber
Saya tidak berpikir Anda perlu melarikan diri dari mereka {}dalam dua pencarian terakhir. Anda juga tidak perlu menambahkan hal-hal seperti (?=(.*5){1})karena tidak akan ada 5jika Anda tidak memiliki tampilan itu. Satu masalah adalah bahwa $memungkinkan linefeed line, jadi Anda harus menggunakan di \zsana daripada $seperti jimmy lakukan, tapi itu tidak akan dikenakan biaya satu byte saya pikir karena Anda menyimpan \di lookahead pertama.
Martin Ender
Saya sadar bahwa mungkin untuk menghilangkan hal-hal seperti angka. Namun, mereka ada di sana untuk membuat autogram berfungsi. Menghapus bagian mana pun dari program akan menyebabkan semua sisanya rusak, karena tidak lagi menggambarkan program dengan benar. (Hitungan untuk setiap baris menghitung jumlah untuk setiap baris! Dengan demikian secara umum pada dasarnya tidak mungkin untuk mengubah program.) Adapun $memungkinkan baris baru di akhir string, yang umumnya tergantung pada bagaimana regex dipanggil oleh sekitarnya. program (mereka biasanya dijalankan pada kode yang sudah diuraikan ke dalam baris).
Atau lebih tepatnya: Saya perlu (?=(.*5){1})dalam hal ini. Jika saya menghapusnya, akan ada angka 5 di program, karena (?=(.*1){6})baris sekarang harus membaca (?=(.*1){5}).
Adapun garis trafeedfeed tampaknya tidak ada batasan dalam tantangan pada jenis input ke regex Anda, sehingga biasanya berarti itu harus bekerja untuk string apa pun, dan berubah $menjadi \ztidak ada salahnya (dan tidak dapat mematahkan autogram).
Martin Ender
Oh begitu; Anda mengubah \$... $untuk z... \z. Itu bekerja; Saya akan mengubahnya.