Sangat mudah untuk menggambarkan mesin keadaan terbatas yang mengenali kelipatan 9: melacak jumlah digit (mod 9) dan menambahkan angka apa pun yang diterima berikutnya. FSM semacam itu hanya memiliki 9 negara, sangat sederhana! Dengan kesetaraan antara FSM-dapat dikenali dan bahasa reguler, ada ekspresi reguler untuk kelipatan 9. Namun, setiap ekspresi reguler seperti itu kemungkinan ... sangat ... lama. Seperti dalam, kemungkinan pada urutan satu gigabyte.

Ada contoh yang berfungsi di https://www.quaxio.com/triple/ untuk kelipatan 3. Di bagian bawah halaman, penulis memberikan solusi yang agak "dioptimalkan dengan tangan" yang sedikit lebih pendek daripada konversi naif dari FSM untuk regex.

Tantangan:

Anda harus membuat regex untuk mendeteksi kelipatan 9. Karena regex seperti itu diperkirakan sangat panjang, saya meminta Anda menyediakan program yang dapat mencetak regex Anda. (Jika Anda benar-benar ingin memberikan seluruh regex, mungkin host di tempat lain dan tautkan di sini!)

Anda harus dapat memberi tahu kami jumlah karakter yang tepat dari output program Anda - jadi memiliki program yang hanya mencoba semua regex hingga panjang tertentu, sampai menemukan yang berfungsi, tidak dapat diterima kecuali jika berjalan cukup cepat sehingga Anda dapat jalankan sampai selesai dan beri kami panjang regex yang dihasilkan!

Poinnya adalah untuk memiliki regex output terpendek, tidak didasarkan pada panjang program, tentu saja. Karena regex adalah "program" yang saya minta, dan terlalu lama untuk mentransmisikan di sini, saya masih menandai golf kode ini.

Aturan:

• Input hanya akan menyertakan karakter yang cocok [0-9]*.
• Regex Anda harus cocok dengan kelipatan 9, tetapi tidak yang lain. Kasing yang tidak seluruhnya terbuat dari angka 0-9 dan input yang tidak valid dapat cocok atau gagal sesuai keinginan.
• Mengingat motivasi bahwa itu mudah dikenali oleh DFA, regex yang dihasilkan harus benar-benar menjadi ekspresi reguler dalam terminologi yang lebih teoretis, yaitu, hanya operator di mana bahasa reguler ditutup. Lebih tepatnya, satu-satunya hal yang diperbolehkan:
  • Literal, rentang karakter ( [ab], [a-f], [^k]), bintang Kleene ( *), jangkar ( ^dan $), pengelompokan melalui kurung, alternatif ( |), istilah opsional ( ?), satu-atau-lebih hal ( +), lookaheads ( (?=)), lookaheads negatif ( (?!)), lookbehinds ( (?<=)), lookbehinds negatif ( (?<!)), conditional (seperti dalam https://www.regular-expressions.info/conditional.html - (?(?=test)then|else)), dan referensi ulang panjang terikat (lihat di bawah).
• Contoh hal-hal yang tidak diperbolehkan:
  • Referensi panjang sewenang-wenang, referensi ke depan, Rekursi, subrutin, konstruksi perulangan, kode yang dapat dieksekusi, variasi apa pun dari 'eval', atau konstruksi bawaan untuk melemparkan string ke nilai aritmatika.
• Referensi balik yang dapat ditunjukkan memiliki string yang terikat-panjang mengikat dapat diterima, karena mereka dapat disimpan dalam keadaan terbatas dan tidak mengubah keteraturan bahasa. Misalnya, regex (..2.[3-5])4\1.\1dapat diterima, karena ada panjang terikat pada kelompok penangkap \1. Ini adalah konstruksi reguler. Konstruk seperti (2*)0\1itu tidak dapat diterima, karena grup yang ditangkap tidak dapat disimpan dalam keadaan terbatas.
• Regex Anda bebas untuk menerima atau menolak bilangan bulat dengan nol terkemuka di luar yang Anda inginkan. Namun, string "0"harus diterima.

Haskell , 207.535 202.073 byte

5.462 byte disimpan dengan menggunakan 0|9alih-alih [09]jika memungkinkan.

digits n
  | x == 0    = "0|9"
  | otherwise = show x
  where x = mod n 9

regex 0 = "[09]*"
regex n = (regex' n (-1) (-1)) ++ "*"

regex' 0 start end = digits (end - start)
regex' n start end = '(':(regex' 0 start end) ++ (concat ['|':(regex' (n-x) (start-x) (-1)) ++ (regex (n-x))
                                                  ++ (regex' (n-x) (-1) (end-x)) | x <- [1..n]]) ++ ")"

main = do
  putStr ("^" ++ (regex 8) ++ "$")

Cobalah online!

Hanya adaptasi cepat dari regex yang diberikan di catatan kaki artikel terkait untuk memulai.

Pastebin dari output regex , milik Herman Lauenstein.

Meskipun saya belum dapat menguji regex lengkap, memodifikasi program untuk memeriksa pembagian dengan 3 sebagai gantinya memberikan sesuatu yang persis sama dengan regex saya berdasarkan ini. Lebih jauh, memodifikasi program untuk mengecek pembagian jumlah digit dengan 4 atau 5 juga tampaknya bekerja pada angka yang saya uji.