Hasilkan ekspresi reguler untuk mencocokkan bilangan asli antara `m` dan` n`

8

Jenis ekspresi reguler adalah PCRE.

Tulis program yang mengeluarkan PCRE yang valid sehingga cocok dengan semua bilangan asli antara mdan ndan tidak cocok dengan yang lain. Tidak ada angka nol di depan.

Sebagai contoh, biarkan mdan nmenjadi 123dan 4321, maka program mungkin menghasilkan 1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

Ini cocok dengan string yang tepat, jadi ^dan $jangkar adalah implisit.

Seseorang harus mencoba menyeimbangkan keduanya:

  1. Ekspresi reguler harus memiliki ukuran yang masuk akal.

  2. Kode harus pendek.

Mari kita optimalkan

code length in characters + 2 *regular expression length for input 123456 and 7654321

Catatan Sisi: Sangat menarik jika kita dapat membuktikan bahwa ekspresi reguler PCRE terpendek adalah dari ukuran O (log n log n) atau sesuatu.

code-golf regular-expression Chao Xu
sumber
1
Bisakah Anda menentukan kriteria kemenangan? Mungkin sesuatu seperti re_size*5 + prog_size(lebih kecil = lebih baik), di mana re_sizemaksimum mdan nhingga 5 digit. Ada banyak cara lain untuk melakukannya - yang penting adalah kita bisa menilai jawabannya.
ugoren
"Tulis program yang mengeluarkan PCRE yang valid sehingga cocok dengan semua bilangan asli antara m dan n" Agaknya "dan gagal mencocokkan semua input lainnya", bukan? Jangan sampai beberapa tawaran sok pintar print .*dalam beberapa bahasa.
dmckee --- ex-moderator kitten
Akan lebih menyenangkan dengan angka negatif :-D
JB
if(min == 123456 && max == 7654321){print_hardcoded_regex}else{enumerate_range_and_join}
John Dvorak

Jawaban:

7

Perl, skor 455

191 karakter, panjang 132 regex

sub b{my$a=shift;$_=(@_>0&&$a.b(@_).($a-->0&&'|')).($a>=0&&($a>1
?"[0-$a]":$a));/\|/?"($_)":$_}sub a{b(@a=split//,<>-1+$x++).(@a>
1&&"|.{1,$#a}")}print'(?!0|('.a.')$)(?=('.a.'$))^\d{1,'.@a.'}$'

Memasukkan: 123456, 7654321

(?!0|((1(2(3(4(5[0-5]|[0-4])|[0-3])|[0-2])|1)|0)|.{1,5})$)(?=((7(6(5(4(3(21|1)|[0-2])|[0-3])|[0-4])|[0-5])|[0-6])|.{1,6}$))^\d{1,7}$

Pembaruan: Saya dapat lebih menyederhanakan ini ketika saya menyadari bahwa sebagian besar pola diakhiri dengan hal-hal seperti \d{3}. Ini melakukan tidak lebih dari menegakkan panjang string - dan melakukannya dengan sangat berulang, karena mereka terjadi pada setiap istilah. Saya menghilangkan ini dengan menggunakan lookahead lain untuk memberlakukan kondisi "kurang dari", hanya memeriksa apakah: 1) bagian pertama dari angka tidak melebihi input atau 2) angka lebih sedikit digit daripada input. Kemudian regex utama hanya memverifikasi bahwa itu tidak terlalu banyak digit.

Saya juga memasukkan ide Peter Taylor tentang pandangan negatif untuk memeriksa kondisi "lebih besar dari".

Kunci untuk menyederhanakan masalah ini (setidaknya bagi saya) adalah memecah regex menjadi dua: pandangan ke depan memastikan jumlahnya tidak kurang dari minimum, maka bagian utama dari regex memeriksa bahwa ia tidak lebih besar dari maksimum. Agak konyol untuk input kecil, tetapi tidak terlalu buruk untuk input besar.

Catatan: 0|di awal adalah untuk mengecualikan apa pun yang dimulai dengan nol dari pencocokan. Ini diperlukan karena sifat rekursif dari fungsi regex: bagian dalam pertandingan dapat dimulai dengan nol, tetapi seluruh jumlahnya tidak bisa. Fungsi regex tidak dapat membedakannya, jadi saya mengecualikan angka apa pun yang dimulai dengan nol sebagai kasus khusus.

Memasukkan: 1, 4

(?!0|(0)$)(?=([0-4]$))^\d{1,1}$

Versi Regex Panjang yang Tidak Pantas, 29 karakter:

print'^',join('|',<>..<>),'$'

sumber
Jangan lupa bahwa ada kasus khusus khusus, yaitu jika m0 maka Anda harus mengizinkan 0 meskipun memiliki nol di depannya.
Peter Taylor
2
@ PeterTaylor, saya pikir "bilangan alami" berarti bilangan bulat positif. Memeriksa wikipedia, saya melihat bahwa sebenarnya tidak ada kesepakatan apakah nol adalah angka alami. Pada titik ini, saya memilih untuk berlindung dalam ambiguitas daripada mengubah solusi saya :)
3

Javascript, skor 118740839

function makere(m,n){r='(';for(i=m;i<n;)r+=i+++'|';return (r+i)+')';}

Saya kira Anda suka atau tidak tergantung pada bagaimana Anda mendefinisikan 'ukuran yang masuk akal.' :-)

Gareth
sumber
2
Tidak akan menguji ini. Aku percaya kamu.
tomsmeding
2

Haskell 2063 + 2 * 151 = 2365

Dijamin regex yang dihasilkan memiliki panjang O (log n log n).

matchIntRange 12345 7654321

1(2(3(4(5[6-9]|[6-9]\d)|[5-9]\d\d)|[4-9]\d{3})|[3-9]\d{4})|[2-9]\d{5}|[1-6]\d{6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([012]\d\d|3([01]\d|2[01])))))

import Data.Digits

data RegEx = Range Int Int | MatchNone | All Int
            | Or RegEx RegEx | Concat [RegEx] 

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | i+1 == j  = concat ["[",show i,show j,"]"]
   | i+2 == j  = concat ["[",show i,show (i+1), show (i+2),"]"]
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = show a ++ "|" ++ show b
  show MatchNone = "^$"
  show (All n) 
   | n < 3     = concat $ replicate n alphabet
   | otherwise = concat [alphabet,"{",show n,"}"] 
  show e@(Concat xs) 
   | atomic e  = concatMap show xs
   | otherwise = concatMap show' xs
   where show' (Or a b) = "("++show (Or a b)++")"
         show' x = show x
         atomic (Concat xs) = all atomic xs
         atomic (Or _ _)    = False
         atomic _           = True

-- Match integers in a certain range
matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat [] 
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y       = Concat [Range x x, build xs ys]
         | sl && all9 && all0 = Concat [Range x y, All n]
         | sl && all0         = Or (Concat [Range x (y-1), All n]) upper
         | sl && all9         = Or lower (Concat [Range (x+1) y, All n])
         | sl && x+1 <= y-1   = Or (Or lower middle) upper
         | sl                 = Or lower upper
         | otherwise          = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), All n]
               all9    = all (==9) ys
               all0    = all (==0) xs
       zeros n   = replicate n 0
       nines n   = replicate n 9
       d 0 = [0]
       d n = digits 10 n

Kode di bawah ini adalah versi sederhana yang membantu memahami algoritma, tetapi tidak melakukan optimasi untuk meningkatkan ukuran regex.

matchIntRange 123 4321

(((1((2((3|[4-8])|9)|[3-8]((0|[1-8])|9))|9((0|[1-8])|9))|[2-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|((1((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|[2-3]((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-8]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|9((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))))|4((0((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9))|[1-2]((0((0|[1-8])|9)|[1-8]((0|[1-8])|9))|9((0|[1-8])|9)))|3((0((0|[1-8])|9)|1((0|[1-8])|9))|2(0|1)))))

Ekspresi reguler memiliki 680 karakter. Ini kodenya

import Data.Digits

data RegEx = Range Int Int | MatchNone | Or RegEx RegEx | Concat [RegEx] 

alphabet = "\\d"

instance Show RegEx where
  show (Range i j)
   | i == j    = show i
   | otherwise = concat ["[",show i,"-",show j,"]"]
  show (Or a b)  = concat ["(",show a,"|",show b,")"]
  show MatchNone = "^$"
  show (Concat xs) = concatMap show xs

matchIntRange :: Int->Int->RegEx
matchIntRange a b
 | 0 > min a b = error "Negative input"
 | a > b       = MatchNone
 | otherwise = build (d a) (d b)
 where build :: [Int]->[Int]->RegEx
       build [] [] = Concat [] 
       build (a@(x:xs)) (b@(y:ys))
         | sl && x == y     = Concat [Range x x, build xs ys]
         | sl && x+1 <= y-1 = Or (Or lower middle) upper
         | sl               = Or lower upper
         | otherwise        = Or (build a (nines la)) (build (1:zeros la) b)
         where (la,lb) = (length a, length b)
               sl      = la == lb
               n       = length xs
               upper   = Concat [Range y y, build (zeros n) ys]
               lower   = Concat [Range x x, build xs (nines n)]
               middle  = Concat [Range (x+1) (y-1), build (zeros n) (nines n)]
       zeros n = replicate n 0
       nines n = replicate n 9
       d 0 = [0]
       d n = digits 10 n
Chao Xu
sumber
2

GolfScript (126 + 2 * 170 = 466)

~)]{`:&,:_,{:i'('\_(<:/i&=48-:D 2<{D^i!!D*|1,*}{'['\i>2D<'-'*D(']?'3$)<}if/D!!*{'\d{'/i>'1,'*_(i-'}|'D}*}%_')'*]}%'(?!'\~'$)'\

Untuk nilai yang diberikannya memberikan

(?!(\d{1,5}|1([01]\d{4}|2([0-2]\d{3}|3([0-3]\d{2}|4([0-4]\d{1}|5([0-5]))))))$)([1-6]?\d{1,6}|7([0-5]\d{5}|6([0-4]\d{4}|5([0-3]\d{3}|4([0-2]\d{2}|3([01]\d{1}|2([01])))))))

Diseksi untuk diikuti, tetapi ide dasarnya adalah untuk mendefinisikan blok kode yang memetakan nomor alami tunggal ke regex yang cocok dengan nomor alami yang lebih kecil, dan kemudian mengubah input lbdan ubmenjadi pencarian yang negatif (nomor alami lebih kecil darilb ) dikombinasikan dengan regex untuk (angka alami lebih kecil dari ub+1).

Logikanya cukup rumit, bahkan oleh standar GolfScript itu samar. Sampai saya selesai menulis pembedahan terperinci, berikut adalah daftar variabel:

&  the whole number string
i  the current idx
D  the current digit
/  not-the-last-digit
_  total number of digits
Peter Taylor
sumber
@ dan1111, saya melihat dokumentasi untuk PCRE tapi saya tidak melihat apa pun yang melarang kelas karakter out-of-order, dan tester yang saya gunakan tidak memberikan kesalahan. Aku harus memeriksanya. OTOH jika mesin regex Anda tidak suka ekspresi yang berakhir |maka itu adalah bug di mesin regex Anda, bukan di regex saya.
Peter Taylor
maaf, saya tidak menyadari itu (a|)sebenarnya valid. Namun, [1-0]di regex Anda sebelumnya tidak berfungsi di Perl atau penguji online yang saya coba.
@ dan1111, setelah Anda menunjukkannya, saya menyadari bahwa tester online yang saya gunakan sedang menelan kesalahan. Saya mereproduksi pada mesin dengan Perl, dan menulis kerangka kerja pengujian menggunakan Perl untuk memeriksa regex. Terima kasih telah menunjukkannya.
Peter Taylor