Matthias Goergens tiene una expresión regular de 25.604 caracteres (en comparación con los 63.993 caracteres originales) para que coincida con los números divisibles por 7, pero eso incluye mucha pelusa: paréntesis redundantes, distribución (en xx|xy|yx|yylugar de [xy]{2}) y otros problemas, aunque estoy seguro de que Un nuevo comienzo sería útil para ahorrar espacio. ¿Qué tan pequeño se puede hacer esto?
Se permite cualquier variedad razonable de expresiones regulares, pero no hay código ejecutable en la expresión regular.
La expresión regular debe coincidir con todas las cadenas que contienen la representación decimal de un número divisible por 7 y ninguna otra. Crédito adicional para una expresión regular que no permite ceros iniciales.
code-golf
math
regular-expression
Charles
fuente
fuente
Respuestas:
10791 caracteres, se permiten ceros a la izquierda
10795 caracteres, ceros a la izquierda prohibidos
0|((foo)0*)+, donde está la expresión regular anterior(0|foo)+.Explicación
Los números divisibles por 7 se corresponden con el obvio autómata finito con 7 estados Q = {0, ..., 6}, estado inicial y final 0, y transiciones d: i ↦ (10i + d) mod 7. Convertí este autómata finito en una expresión regular, usando recursividad en el conjunto de estados intermedios permitidos:
Dado i, j ∈ Q y S ⊆ Q, que f (i, S, j) sea una expresión regular que coincida con todas las rutas de autómatas de i a j utilizando solo estados intermedios dentro de S. Entonces,
f (i, ∅, j) = (j - 10i) mod 7,
f (i, S ∪ {k}, j) = f (i, S, j) ∣ f (i, S, k) f (k, S, k) * f (k, S, j).
Usé la programación dinámica para elegir k para minimizar la longitud de la expresión resultante.
fuente
0|((foo)0*)+13,75512,699 12,731PersonajesEsta expresión regular no rechaza el cero inicial.
Esto se prueba con The Regex Coach .
Cómo llegamos allí
El Regex anterior se produce al construir primero un DFA que acepte la entrada que queremos (decimales divisibles por 7) y luego convertir a una Expresión regular y corregir la nota
Para comprender esto, es útil hacer primero un DFA que acepte el siguiente idioma:
Es decir, 'coincidirá' con los números binarios que son divisibles por 7.
El DFA se ve así:
Cómo funciona
Mantiene un valor actual
Aque representa el valor de los bits que ha leído el DFA. Cuando lees un0entoncesA = 2*Ay cuando lees un1A = 2*A + 1. En cada paso que calculaA mod 7, pasa al estado que representa la respuesta.Entonces una prueba de funcionamiento:
Estamos leyendo en
10101cuál es la representación binaria para 21 en decimal.q0, actualmenteA=01, de la 'regla' anteriorA = 2*A + 1asíA = 1.A mod 7 = 1entonces nos movemos al estadoq10,A = 2*A = 2,A mod 7 = 2así que nos movemos aq21,A = 2*A + 1 = 5,A mod 7 = 5, mover aq50,A = 2*A = 10,A mod 7 = 3, mover aq31,A = 2*A + 1 = 21,A mod 7 = 0, mover aq010101es divisible por 7.Convertir el DFA en una expresión regular es una tarea difícil, así que conseguí que JFLAP lo hiciera por mí, produciendo lo siguiente:
Para números decimales
El proceso es muy parecido:
Construí un DFA que acepta el lenguaje:
Aquí está el DFA:
La lógica es similar, el mismo número de estados solo muchas más transiciones para manejar todos los dígitos adicionales que traen los números decimales.
Ahora la regla para cambiar
Aen cada paso es: cuando se lee un dígito decimaln:A = 10*A + n. Por otra parte, solomodApor 7 y pasa al siguiente estado.Revisiones
Revisión 5
La expresión regular anterior ahora rechaza los números que llevan ceros, aparte del cero, por supuesto.
Esto hace que el DFA sea ligeramente diferente, básicamente se ramifica desde el nodo inicial cuando lee el primer cero. Leer otro cero te pone en un bucle infinito en el estado ramificado. No he arreglado el diagrama para mostrar esto.
Revisión 7
Hice algo de "metaregex" y acorté mi regex reemplazando algunas de las uniones con clases de caracteres.
Revisión 10 y 11 (por nhahtdh)
La modificación del autor para rechazar el cero inicial es incorrecta. Hace que las expresiones regulares no coincidan con números válidos, como 1110 (decimal = 14) en el caso de expresiones regulares binarias y 70 en el caso de expresiones regulares decimales. Esta revisión revierte la modificación y, en consecuencia, permite que coincidan los ceros iniciales arbitrarios y la cadena vacía.
Esta revisión aumenta el tamaño de la expresión regular decimal, ya que corrige un error en la expresión regular original, causado por la falta de un borde (9) del estado 5 al estado 3 en el DFA original.
fuente
1110, y el decimal no coincide70. Esto fue probado tanto en python como en perl. (Python requería convertir cada uno(al(?:primero).NET regex,
119118105 bytes111 caracteres que no permiten los 0 iniciales:
113 caracteres que no permiten 0 iniciales y admiten números negativos:
Pruébalo aquí.
Explicación (de la versión anterior)
Utiliza las técnicas utilizadas por varias respuestas en esta pregunta: Policías y ladrones: Reverse Regex Golf . La expresión regular .NET tiene una característica llamada grupo de equilibrio, que se puede usar para hacer aritmética.
(?<a>)empuja a un grupoa.(?<-a>)aparece eso y no coincide si no hay un grupoaemparejado antes.(?>...)Empareja y no retrocedas más tarde. Por lo tanto, siempre coincidirá solo con la primera alternativa coincidente.((?<-t>)(){3}|){6}Multiplique el número del grupo t por 3. Guarde el resultado en el número del grupo 2.(?=[1468](?<2>)|)(?=[2569](?<2>){2}|)([3-6](?<2>){3}|\d)Empareja un número y ese número del grupo 2.((?<-2>){7}|){3}Eliminar el grupo 2 un múltiplo de 7 veces.((?<t-2>)|){6}Eliminar el grupo 2 y hacer coincidir el mismo número de grupo t.$(?(t)a)Si todavía hay un grupo t emparejado, coincidaadespués del final de la cadena, lo cual es imposible.Pensé que esta versión de 103 bytes también debería funcionar, pero no encontré una solución del error en el compilador.
fuente
468 caracteres
El sabor de expresiones regulares de Ruby permite la recursividad (aunque es una especie de trampa), por lo que es sencillo implementar un DFA que reconozca los números divisibles por 7 usando eso. Cada grupo nombrado corresponde a un estado, y cada rama en las alternancias consume un dígito y luego salta al estado apropiado. Si se alcanza el final del número, la expresión regular coincide solo si el motor está en el grupo "A"; de lo contrario, falla.
Reconoce ceros a la izquierda.
fuente
{a*b*|a and b an equal amount of times})¡Estaba realmente impresionado con la respuesta de Griffin y necesitaba descubrir cómo funcionaba! El resultado es el siguiente JavaScript. (¡Son 3.5k caracteres, que es más corto en cierto modo!) La
genfunción toma un divisor y una base y genera una expresión regular que coincide con los números en la base especificada que son divisibles por ese divisor.He generalizado el NFA de Griffin para cualquier base: la
nfafunción toma un divisor y una base y devuelve una matriz bidimensional de transiciones. La entrada requerida para pasar del estado 0 al estado 2, por ejemplo, esstates[0][2] == "1".La
reducefunción toma lastatesmatriz y la ejecuta a través de este algoritmo para traducir el NFA a expresiones regulares. Las expresiones regulares que se generan son enormes y parece que tienen muchas cláusulas redundantes, a pesar de mis intentos de optimización. La expresión regular para 7 base 10 tiene aproximadamente ~ 67k caracteres de largo; Firefox lanza un "InternalError" para n> 5 tratando de analizar la expresión regular; ejecutar la expresión regular en Chrome comienza a ser lento para n> 6.También existe la
testfunción que toma una expresión regular y una base y la ejecuta contra los números del 0 al 100, entoncestest(gen(5)) == [0, 5, 10, 15, ...].A pesar del resultado subóptimo, esta fue una oportunidad de aprendizaje fantástica, ¡y espero que parte de este código sea útil en el futuro!
fuente
Perl / PCRE, 370 caracteres
Rechaza la cadena vacía, así como las cadenas con ceros a la izquierda (excepto "0").
fuente