Tugas

Tetapkan regex sederhana sebagai ekspresi reguler tidak kosong yang hanya terdiri dari

karakter 0dan 1,
tanda kurung pengelompokan (dan ),
pengukur pengulangan satu atau lebih +.

Dengan string 0s dan 1s yang tidak kosong , program Anda harus menemukan regex sederhana terpendek yang cocok dengan string input penuh . (Yaitu, ketika mencocokkan regex sederhana, berpura-pura itu dibukukan oleh ^ dan $.) Jika ada beberapa regex terpendek, cetak salah satu atau semuanya.)

kode-golf , jadi pengiriman terpendek (dalam byte) menang.

Uji kasus

1 -> 1
00 -> 00 or 0+
010 -> 010
1110 -> 1+0
01010 -> 01010
0101010 -> 0(10)+ or (01)+0
011111 -> 01+
10110110 -> (1+0)+
01100110 -> (0110)+ or (01+0)+
010010010 -> (010)+
111100111 -> 1+001+ or 1+0+1+
00000101010 -> 0+(10)+ or (0+1)+0
1010110001 -> 1(0+1+)+ or (1+0+)+1

code-golf regular-expression metagolf search Lynn
sumber

3

Anda harus mengklarifikasi bahwa Anda ingin kami menulis program yang menulis regex, bukan menulis regex sendiri. Tapi ini terlihat menarik.

gcampbell

1

Dalam pengujian saya, 01100110adalah kasus yang menarik ... algoritma naif akan menulis 01+0+1+0atau (0+1+)+0yang tidak optimal.

Neil

Terkait

Leaky Nun

2

Pyth, 20 byte

hf.x}z:zT1Zy*4"()01+

Ini membutuhkan waktu sekitar 30 detik untuk dijalankan, sehingga perlu dijalankan secara offline.

Penjelasan:

hf.x}z:zT1Zy*4"()01+
                        Implicit: z is the input string.
              "()01+    "()01+"
            *4          Repeated 4 times
           y            All subsequences in length order
hf                      Output the first one such that
      :zT1              Form all regex matches of z with the candidate string
    }z                  Check if the input is one of the strings
  .x      Z             Discard errors

Saya tidak sepenuhnya yakin bahwa setiap string terpendek adalah urutan dari "() 01+" * 4, tetapi 4 dapat ditingkatkan menjadi 9 tanpa biaya byte jika diperlukan.

isaacg
sumber

9

JavaScript (ES6), 488 341 byte

s=>[s.replace(/(.)\1+/g,'$1+'),...[...Array(60)].map((_,i)=>`(${(i+4).toString(2).slice(1)})+`),...[...Array(1536)].map((_,i)=>`${i>>10?(i>>8&1)+(i&2?'+':''):''}(${i&1}${i&4?i>>4&1:i&16?'+':''}${i&8?''+(i>>7&1)+(i&64?i>>5&1:i&32?'+':''):''})+${i&512?(i>>8&1)+(i&2?'+':''):''}`)].filter(r=>s.match(`^${r}$`)).sort((a,b)=>a.length-b.length)[0]

Penjelasan: Karena enam regex dapat mengekspresikan semua kata biner yang mungkin, dan dua terpanjang panjangnya sembilan karakter, cukup untuk memeriksa semuanya dan semua regex yang lebih pendek. Satu kandidat jelas merupakan string dengan "run length encoding" (yaitu semua digit berjalan diganti dengan +s yang sesuai ), tetapi juga string dengan satu set ()s perlu diperiksa. Saya menghasilkan 1596 regex semacam itu (ini termasuk duplikat dan regex yang tidak berguna tetapi mereka hanya akan dihilangkan) dan menguji semua 1597 untuk melihat mana yang paling cocok. Regex yang dihasilkan terbagi dalam dua jenis: $\d{2,5}$\+(60 regex) dan (\d\+?)?$\d[\d+]?(\d[\d+]?)?$(\d\+?)?(1536 regex karena saya menghindari menghasilkan regex dengan digit terdepan dan tambahan).

Neil
sumber

@ LeakyNun Awalnya saya pikir ada 4 regex dengan panjang 9 tapi ini jelas salah jadi saya sudah menjelaskan penjelasan saya.

Neil

2

Pyth - 31 30 29 byte

Paksaan! Mungkin bisa sedikit golf iterator.

 f=+Yf.x:zjY"^$")Z^"10+()"T1Y

Test Suite .

Maltysen
sumber

1

Ruby, 109 byte

Ini adalah pendekatan brute force yang membosankan. Berfungsi karena tidak ada regex yang perlu lebih dari 9 karakter (seperti yang dicatat Neil) dan tidak ada karakter individu yang perlu diulang lebih dari 4 kali (mencobanya dengan '01()+'.chars*9membuat CPU saya tidak senang).

10.times{|i|('01()+'.chars*4).combination(i).map{|s|begin
/^#{s*''}$/=~$*[0]&&[puts(s*''),exit]
rescue
end}}

$ for word in `grep -Po '^\S+' test_cases.txt`; do nice -n20 ruby sre.rb $word; done
1
0+
010
1+0
01010
0(10)+
01+
(1+0)+
(01+0)+
(010)+
1+0+1+
0+(10)+
1(0+1+)+

ezrast
sumber

1

Python 3, 186 byte

Saya sedang menyelidiki apakah ada pendekatan untuk masalah ini selain brute-forcing, tapi di sini ada solusi brute-force Python untuk saat ini.

import re,itertools
def a(b):
 for z in range(10):
  for i in itertools.combinations("01()+"*4,z):
   j=''.join(i)
   try:
    if re.fullmatch(j,b)and len(j)<=len(b):return j
   except:1

Sherlock9
sumber

Regex sederhana terpendek yang cocok dengan kata biner