Tarea

Defina una expresión regular simple como una expresión regular no vacía que consta solo de

personajes 0y 1,
agrupando paréntesis (y ),
cuantificador de repetición de uno o más +.

Dada una cadena no vacía de 0sys 1, su programa debería encontrar la expresión regular simple más corta que coincida con la cadena de entrada completa . (Es decir, al hacer coincidir una expresión regular simple, simule que está marcada por ^ y $.) Si hay varias expresiones regulares más cortas, imprima una o todas ellas).

code-golf , por lo que gana el envío más corto (en bytes).

Casos de prueba

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
fuente

3

Debe aclarar que desea que escribamos un programa que escriba la expresión regular, no que la escribamos nosotros mismos. Pero esto se ve interesante.

gcampbell

1

En mis pruebas, 01100110es un caso interesante ... escribiría un algoritmo ingenuo 01+0+1+0o (0+1+)+0que no son óptimos.

Neil

Relacionado.

Leaky Nun

2

Pyth, 20 bytes

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

Esto tarda aproximadamente 30 segundos en ejecutarse, por lo que debe ejecutarse sin conexión.

Explicación:

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

No estoy completamente seguro de que cada cadena más corta sea una subsecuencia de "() 01+" * 4, pero 4 se puede aumentar a 9 sin costo de byte si es necesario.

isaacg
fuente

9

JavaScript (ES6), 488341 bytes

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]

Explicación: Dado que seis expresiones regulares pueden expresar todas las palabras binarias posibles, y las dos más largas tienen nueve caracteres, es suficiente verificar esas y todas las expresiones regulares más cortas. Un candidato es obviamente la cadena con "codificación de longitud de ejecución" (es decir, todas las ejecuciones de dígitos reemplazadas por +s apropiadas ), pero también ()deben verificarse las cadenas con un conjunto de s. Genero 1596 expresiones regulares (esto incluye duplicados e expresiones regulares inútiles, pero se eliminarán) y pruebo todas las 1597 para ver cuál es la coincidencia más corta. Las expresiones regulares generadas se dividen en dos tipos: $\d{2,5}$\+(60 expresiones regulares) y (\d\+?)?$\d[\d+]?(\d[\d+]?)?$(\d\+?)?(1536 expresiones regulares, ya que evito generar expresiones regulares con dígitos iniciales y finales).

Neil
fuente

@LeakyNun Originalmente pensé que había 4 expresiones regulares de longitud 9, pero esto obviamente es incorrecto, así que he aclarado mi explicación.

Neil

2

Pyth - 31 30 29 bytes

¡Fuerza bruta! Probablemente pueda jugar un poco al iterador.

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

Test Suite .

Maltysen
fuente

1

Ruby, 109 bytes

Es el enfoque de la fuerza bruta aburrida. Funciona porque ninguna expresión regular necesita más de 9 caracteres (como señala Neil) y ningún carácter individual necesita repetirse más de 4 veces (intentarlo '01()+'.chars*9hizo que mi CPU fuera infeliz).

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
fuente

1

Python 3, 186 bytes

Estoy investigando si hay un enfoque para este problema además de la fuerza bruta, pero aquí hay una solución de fuerza bruta de Python por ahora.

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
fuente

Regex simple más corto que coincide con una palabra binaria