Su tarea es compilar expresiones regulares ... especificando una sustitución para cada personaje en una expresión regular.

Expresiones regulares

Las expresiones regulares soportan estos

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

¿Por qué solo 1 o 0? Es para simplificar. Por lo tanto, la expresión regular solo tiene los siguientes caracteres:

*()|10

Se interpreta de la siguiente manera:

1. * es la estrella de Kleene (repite el grupo izquierdo o literal 0 o más veces).
2. | es alternancia (coincide si la expresión regular a la izquierda o la expresión regular a la derecha coincide).
3. () está agrupando
4. 1 coincide con el personaje 1.
5. 0 coincide con el caracter 0.

¿Cómo compilar?

Especifica seis fragmentos de código: uno para reemplazar cada carácter regex. Por ejemplo, si su respuesta es:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Luego, reemplaza cada expresión regular con su fragmento de código respectivo, por lo que:

(0|11)*

se convierte en:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

¿Qué se supone que debe hacer el programa resultante?

Tu programa:

1. Toma la entrada.
2. Salida de un valor verdadero si la expresión regular coincide con la entrada completa.
3. Otra salida de un valor falso.

La entrada al exterior 01es un comportamiento indefinido limitado. La entrada puede estar vacía.

Reglas adicionales

1. Para un determinado carácter regex, el fragmento resultante debe ser siempre el mismo.
2. No se agrega ningún prefijo o sufijo después.
3. Se garantiza que la expresión regular no será vacía.

Tanteo

El fragmento menos combinado es el ganador. Por lo tanto, la puntuación para el caso de ejemplo se calcularía de la siguiente manera:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Caracoles , 48 bytes

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Si tuviéramos que buscar coincidencias parciales en lugar de hacer coincidir solo la entrada completa, entonces sería muy fácil. 0se volvería \0, 1se volvería \1, *se volvería ,, y los otros se mapearían a sí mismos. En cambio, hay muchas travesuras para evitar que las partidas comiencen en otro lugar que no sea el principio o terminen en otro lugar que no sea el final. !(l.)es una afirmación que fallará si el comienzo de la coincidencia no está al comienzo de la entrada. ~coincide con una celda fuera de la entrada, por lo que se agrega a todos los caracteres que pueden estar al final de la expresión regular. Si hay otro carácter regex a continuación, se cancela mediante un cuantificador numérico0lo que requiere que coincida 0 veces, esencialmente comentarlo. Para permitir que *( ,) funcione correctamente a pesar de que la prueba ficticia fuera de los límites se interpone en el camino, se utilizan mucho las reglas de coincidencia de paréntesis del idioma. De la documentación:

Los pares coincidentes de paréntesis ()o llaves {}se comportarán como se espera (como paréntesis en expresiones regulares), pero también es posible omitir la mitad de un par y deducirlo, de acuerdo con las siguientes reglas. )o }agrupa todo a la izquierda hasta la instrucción de apertura de grupo no cerrada más cercana del mismo tipo ( (o {respectivamente), o el comienzo del patrón si no existe ninguno. Cierra cualquier instrucción de apertura no cerrada del tipo opuesto en el medio de este rango. De lo contrario, no coincide (o {se cierra al final del patrón.

Claro como el barro, ¿verdad?

CJam, 151 bytes

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Las líneas corresponden a los caracteres 01(|)*(en ese orden). Pruébalo en línea!

Esto no utiliza una expresión regular integrada u otros tipos de coincidencia de patrones. De hecho, CJam no tiene ninguna de estas características. En cambio, comienza a partir de la expresión regular que representa y crea todas las cadenas posibles que podría coincidir, para finalmente verificar si la entrada del usuario es una de ellas.

Pruebas de funcionamiento

Lo siguiente utiliza un programa que lee una expresión regular de STDIN, reemplaza cada uno de sus caracteres por el fragmento apropiado y finalmente evalúa el código generado para ver si coincide con la entrada especificada en el argumento de la línea de comando.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Desafortunadamente, esto no es particularmente rápido. Se ahogará bastante rápido si hay más de 9 caracteres en la entrada o más de una sola estrella de Kleene en la expresión regular.

Con el costo de 5 bytes adicionales, para un total de 156 bytes , podemos generar cadenas más cortas para que coincidan con la entrada potencial y deduplicarlas. Esto no cambia cómo funciona el código; solo lo hace más eficiente.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1