Zadanie

Zdefiniuj proste wyrażenie regularne jako niepuste wyrażenie regularne składające się tylko z

• znaków 0i 1,
• grupowanie nawiasów (i ),
• jeden lub więcej kwantyfikatorów powtórzeń +.

Biorąc niepusty ciąg 0s oraz 1s, Twój program powinien znaleźć najkrótszą proste regex pasujący do pełnego wejścia ciąg. (Oznacza to, że dopasowując proste wyrażenie regularne, udawaj, że jest ono zarezerwowane przez ^ i  $.) Jeśli istnieje wiele najkrótszych wyrażeń regularnych , wydrukuj jeden lub wszystkie z nich.)

code-golf , więc wygrywa najkrótsze przesłanie (w bajtach).

Przypadki testowe

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

Pyth, 20 bajtów

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

Uruchomienie zajmuje około 30 sekund, więc musi być uruchomione w trybie offline.

Wyjaśnienie:

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

Nie jestem całkowicie pewien, że każdy najkrótszy ciąg jest podsekwencją „() 01+” * 4, ale w razie potrzeby 4 można zwiększyć do 9 bez żadnych bajtów.

JavaScript (ES6), 488 341 bajtów

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]

Objaśnienie: Ponieważ sześć wyrażeń regularnych może wyrazić wszystkie możliwe słowa dwójkowe, a najdłuższe dwa mają dziewięć znaków, wystarczy sprawdzić te i wszystkie krótsze wyrażenia regularne. Jednym kandydatem jest oczywiście ciąg znaków z „kodowaniem długości przebiegu” (tzn. Wszystkie przebiegi cyfr zastąpione odpowiednimi +s), ale należy również ()sprawdzić ciągi z jednym zestawem s. Generuję 1596 takich wyrażeń regularnych (obejmuje to duplikaty i niepotrzebne wyrażenia regularne, ale zostaną one po prostu wyeliminowane) i testuję wszystkie 1597, aby zobaczyć, który jest najkrótszy. Wygenerowane wyrażenia regularne dzielą się na dwa typy: \(\d{2,5}\)\+(60 wyrażeń regularnych) i (\d\+?)?\(\d[\d+]?(\d[\d+]?)?\)(\d\+?)?(1536 wyrażeń regularnych, ponieważ unikam generowania wyrażeń regularnych z cyframi wiodącymi i końcowymi).

Pyth - 31 30 29 bajtów

Brutalna siła! Prawdopodobnie trochę golfa iterator.

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

Pakiet testowy .

Rubin, 109 bajtów

To nudne podejście brutalnej siły. Działa, ponieważ żadne wyrażenie regularne nigdy nie musi być dłuższe niż 9 znaków (jak zauważa Neil) i żadna indywidualna postać nie musi być powtarzana więcej niż 4 razy (próbowanie z tym '01()+'.chars*9sprawiło, że mój procesor był niezadowolony).

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+)+

Python 3, 186 bajtów

Badam, czy istnieje podejście do tego problemu oprócz brutalnego forsowania, ale oto na razie rozwiązanie brutalnej siły Pythona.

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