Tarefa
Defina uma regex simples como uma expressão regular não vazia que consiste apenas em
- caracteres
0
e1
, - agrupar parênteses
(
e)
, - um ou mais quantificadores de repetição
+
.
Dada uma sequência não vazia de 0
s e 1
s, seu programa deve encontrar a regex simples mais curta que corresponda à sequência de entrada completa . (Ou seja, ao corresponder a uma regex simples, finja que ela é reservada por ^
e $
.) Se houver várias regexes mais curtas, imprima uma ou todas elas.
code-golf , de modo que o menor envio (em bytes) vence.
Casos de teste
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
01100110
é um caso interessante ... um algoritmo ingênuo escreveria01+0+1+0
ou(0+1+)+0
não seria o ideal.Respostas:
Pitão, 20 bytes
Isso leva aproximadamente 30 segundos para ser executado, portanto, ele precisa ser executado offline.
Explicação:
Não tenho certeza absoluta de que toda seqüência mais curta seja uma subsequência de "() 01+" * 4, mas 4 pode ser aumentado para 9 sem custo de bytes, se necessário.
fonte
JavaScript (ES6),
488341 bytesExplicação: Como seis regexes podem expressar todas as palavras binárias possíveis e os dois mais longos têm nove caracteres, basta verificar essas e todas as regexes mais curtas. Um candidato é obviamente a string com "codificação do comprimento da execução" (ou seja, todas as execuções de dígitos substituídas por
+
s apropriadas ), mas também as strings com um conjunto de()
s precisam ser verificadas. Eu gero 1596 dessas expressões regulares (isso inclui duplicatas e expressões inúteis, mas elas serão eliminadas) e testo todas as 1597 para ver qual é a correspondência mais curta. As regexes geradas se enquadram em dois tipos:\(\d{2,5}\)\+
(60 regexes) e(\d\+?)?\(\d[\d+]?(\d[\d+]?)?\)(\d\+?)?
(1536 regexes, pois evito gerar regexes com os dígitos inicial e posterior).fonte
Pitão -
313029 bytesForça bruta! Provavelmente pode jogar um pouco no iterador.
Suíte de teste .
fonte
Ruby, 109 bytes
É a abordagem chata da força bruta. Funciona porque nenhum regex precisa ter mais de 9 caracteres (como observa Neil) e nenhum caractere individual precisa ser repetido mais de 4 vezes (tentar isso
'01()+'.chars*9
deixou minha CPU infeliz).fonte
Python 3, 186 bytes
Estou investigando se existe uma abordagem para esse problema além da força bruta, mas aqui está uma solução de força bruta do Python por enquanto.
fonte