задача

Определите простое регулярное выражение как непустое регулярное выражение, состоящее только из

персонажи 0и 1,
группировка скобок (и ),
один или более квантификатор повторения +.

Учитывая непустую строку 0s и 1s, ваша программа должна найти самое короткое простое регулярное выражение, соответствующее полной входной строке. (То есть, когда вы сопоставляете простое регулярное выражение, представьте, что оно добавлено ^ и $.) Если имеется несколько кратчайших регулярных выражений, выведите любое или все из них.)

Code-Golf , поэтому выигрывает самое короткое представление (в байтах).

Контрольные примеры

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 Линн
источник

3

Вы должны уточнить, что вы хотите, чтобы мы написали программу, которая пишет регулярное выражение, а не пишем регулярное выражение самостоятельно. Но это выглядит интересно.

gcampbell

1

В моем тестировании 01100110интересный случай ... наивный алгоритм написал бы 01+0+1+0или (0+1+)+0неоптимальный.

Нил

Связанный.

Дрянная Монахиня

2

Pyth, 20 байт

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

Это займет примерно 30 секунд, поэтому его нужно запустить в автономном режиме.

Объяснение:

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

Я не совсем уверен, что каждая самая короткая строка является подпоследовательностью "() 01+" * 4, но 4 может быть увеличено до 9 без стоимости байта, если это необходимо.

isaacg
источник

9

JavaScript (ES6), 488 341 байт

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]

Объяснение: Поскольку шесть регулярных выражений могут выражать все возможные двоичные слова, а два самых длинных имеют длину девять символов, достаточно проверить эти и все более короткие регулярные выражения. Очевидно, что одним из кандидатов является строка с «кодировкой длины серии» (т. Е. Все +последовательности цифр заменены на соответствующие s), но также ()необходимо проверить строки с одним набором s. Я генерирую 1596 таких регулярных выражений (включая дубликаты и бесполезные регулярные выражения, но они будут просто удалены) и проверяю все 1597, чтобы определить, какое совпадение является самым коротким. Сгенерированные регулярные выражения делятся на два типа: $\d{2,5}$\+(60 регулярных выражений) и (\d\+?)?$\d[\d+]?(\d[\d+]?)?$(\d\+?)?(1536 регулярных выражений, поскольку я избегаю генерировать регулярные выражения как с начальной, так и с конечной цифрой).

Нил
источник

@LeakyNun Первоначально я думал, что было 4 регулярных выражения длины 9, но это, очевидно, неправильно, поэтому я разъяснил свое объяснение.

Нил

2

Pyth - 31 30 29 байт

Грубая сила! Может быть, гольф-итератор немного.

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

Тестовый пакет .

Maltysen
источник

1

Рубин, 109 байт

Это скучный метод грубой силы. Работает, потому что никакое регулярное выражение никогда не должно быть длиннее 9 символов (как отмечает Нил), и нет необходимости повторять отдельный символ более 4 раз (попытка сделать это '01()+'.chars*9сделала мой процессор несчастным).

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
источник

1

Python 3, 186 байт

Я выясняю, есть ли подход к этой проблеме, кроме грубого принуждения, но здесь пока есть грубое силовое решение Python.

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
источник

Кратчайшее простое регулярное выражение, соответствующее двоичному слову