Combina cuerdas cuya longitud es una cuarta potencia

Dentro del alcance de esta pregunta, consideremos solo cadenas que consisten en el carácter xrepetido número arbitrario de veces.

Por ejemplo:

<empty>
x
xx
xxxxxxxxxxxxxxxx

^{(Bueno, en realidad no tiene que ser así x; cualquier carácter está bien siempre que la cadena completa solo tenga 1 tipo de carácter)}

Escriba una expresión regular en cualquier expresión de expresión de su elección para que coincida con todas las cadenas cuya longitud es n ⁴ para algún número entero no negativo n (n> = 0). Por ejemplo, las cadenas de longitud 0, 1, 16, 81, etc. son válidas; El resto son inválidos.

^{Debido a la limitación técnica, es difícil probar valores de n mayores que 128. Sin embargo, su expresión regular debería funcionar lógicamente de todos modos.}

Tenga en cuenta que no puede ejecutar código arbitrario en su expresión regular (para usuarios de Perl). Se permite cualquier otra sintaxis (mirar alrededor, referencia inversa, etc.).

Incluya también una breve explicación sobre su enfoque del problema.

^{(No pegue la explicación de sintaxis de expresiones regulares generada automáticamente, ya que son inútiles)}

Esta (ir) expresión regular parece funcionar.

^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

Esta expresión regular es compatible con PCRE, Perl, sabores .NET.

Básicamente, esto sigue a un "árbol de diferencia" (no estoy seguro si hay un nombre propio para él), que le dice a la expresión regular cuántas x más deben coincidir para la próxima cuarta potencia:

1     16    81    256   625   1296  2401 ...
   15    65    175   369   671   1105 ...
      50    110   194   302   434 ...
         60    84    108   132 ...
            24    24    24 ...  # the differences level out to 24 on the 4th iteration

\2, \3, \4Tiendas y actualizaciones de la diferencia, como se muestra en la 2ª, 3ª y 4ª filas, respectivamente.

Esta construcción se puede extender fácilmente para obtener poderes superiores.

Ciertamente no es una solución elegante, pero funciona.

Otra solución

Este es, en mi opinión, uno de los problemas más interesantes del sitio. Necesito agradecer a deadcode por subirlo de nuevo a la cima.

^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 bytes , sin condicionales o afirmaciones ... más o menos. Las alternancias, a medida que se usan ( ^|), son un tipo de condicional en cierto modo, para seleccionar entre "primera iteración" y "no primera iteración".

Se puede ver que esta expresión regular funciona aquí: http://regex101.com/r/qA5pK3/1

Tanto PCRE como Python interpretan la expresión regular correctamente, y también se ha probado en Perl hasta n = 128 , incluyendo n ⁴ -1 , y n ⁴ 1 .

Definiciones

La técnica general es la misma que en las otras soluciones ya publicadas: defina una expresión autorreferenciada que en cada iteración posterior coincida con una longitud igual al siguiente término de la función de diferencia directa, D _f , con un cuantificador ilimitado ( *). Una definición formal de la función de diferencia directa:

Además, también se pueden definir funciones de diferencia de orden superior:

O, más generalmente:

La función de diferencia hacia adelante tiene muchas propiedades interesantes; es a secuencias lo que la derivada es a funciones continuas. Por ejemplo, D _f de un n º polinomio de orden siempre será un n-1 ésimo polinomio de orden, y para cualquier i , si D _f ⁱ = D _f ^{i + 1} , entonces la función f es exponencial, de la misma manera que la derivada de e ^x es igual a sí misma. La función discreta más simple para la cual f = D _f es 2 ⁿ .

f (n) = n ²

Antes de examinar la solución anterior, comencemos con algo un poco más fácil: una expresión regular que coincida con cadenas cuyas longitudes son un cuadrado perfecto. Examinando la función de diferencia directa:

Es decir, la primera iteración debe coincidir con una cadena de longitud 1 , la segunda una cadena de longitud 3 , la tercera una cadena de longitud 5 , etc., y en general, cada iteración debe coincidir con una cadena dos más larga que la anterior. La expresión regular correspondiente se sigue casi directamente de esta declaración:

^(^x|\1xx)*$

Se puede ver que la primera iteración coincidirá solo con una x , y cada iteración posterior coincidirá con una cadena dos veces más larga que la anterior, exactamente como se especifica. Esto también implica una prueba cuadrada perfecta increíblemente corta en perl:

(1x$_)=~/^(^1|11\1)*$/

Esta expresión regular se puede generalizar aún más para que coincida con cualquier longitud n- gonal:

Números triangulares
^(^x|\1x{1})*$

Números cuadrados:
^(^x|\1x{2})*$

Números pentagonales:
^(^x|\1x{3})*$

Números hexagonales:
^(^x|\1x{4})*$

etc.

f (n) = n ³

Pasando a n ³ , una vez más examinando la función de diferencia hacia adelante:

Es posible que no se vea de inmediato cómo implementar esto, por lo que también examinamos la segunda función de diferencia:

Por lo tanto, la función de diferencia directa no aumenta en una constante, sino en un valor lineal. Es bueno que el valor inicial (' -1 °') de D _f ² sea ​​cero, lo que guarda una inicialización en la segunda iteración. La expresión regular resultante es la siguiente:

^((^|\2x{6})(^x|\1))*$

La primera iteración coincidirá con 1 , como antes, la segunda coincidirá con una cadena 6 más larga ( 7 ), la tercera coincidirá con una cadena 12 más larga ( 19 ), etc.

f (n) = n ⁴

La función de diferencia directa para n ⁴ :

La segunda función de diferencia hacia adelante:

La tercera función de diferencia hacia adelante:

Eso sí que es feo. Los valores iniciales para D _f ² y D _f ³ son ambos distintos de cero, 2 y 12 respectivamente, que deberán tenerse en cuenta. Probablemente ya se haya dado cuenta de que la expresión regular seguirá este patrón:

^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Debido a que D _f ³ debe coincidir con una longitud de 12 en la segunda iteración, a es necesariamente 12 . Pero debido a que aumenta en 24 cada término, la siguiente anidación más profunda debe usar su valor anterior dos veces, lo que implica b = 2 . Lo último que debe hacer es inicializar el D _f ² . Debido a que D _f ² influye en D _f directamente, que en última instancia es lo que queremos igualar, su valor puede inicializarse insertando el átomo apropiado directamente en la expresión regular, en este caso (^|xx). La expresión regular final se convierte en:

^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Órdenes superiores

Un polinomio de quinto orden se puede combinar con la siguiente expresión regular:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$

f (n) = n ⁵ es un ejercicio bastante fácil, ya que los valores iniciales para la segunda y cuarta funciones de diferencia directa son cero:

^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

Para polinomios de seis órdenes:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$

Para polinomios de séptimo orden:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$

etc.

Tenga en cuenta que no todos los polinomios pueden coincidir exactamente de esta manera, si alguno de los coeficientes necesarios no son enteros. Por ejemplo, n ⁶ requiere que a = 60 , b = 8 , y c = 3/2 . Esto se puede solucionar, en este caso:

^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Aquí he cambiado de b a 6 y de c a 2 , que tienen el mismo producto que los valores indicados anteriormente. Es importante que el producto no cambie, ya que a · b · c · ... controla la función de diferencia constante, que para un polinomio de sexto orden es D _f ⁶ . Hay dos átomos de inicialización presentes: uno para inicializar D _f a 2 , como con n ⁴ , y el otro para inicializar la función de quinta diferencia a 360 , mientras que al mismo tiempo agrega los dos que faltan de b .

Aquí hay una solución que no utiliza condicionales, referencias hacia atrás declaradas o anidadas, mirar hacia atrás, equilibrar grupos o recurrencia de expresiones regulares. Solo usa referencias previas estándar y de búsqueda anticipada, que son ampliamente compatibles. Me inspiré para operar bajo estas limitaciones debido a Regex Golf , que utiliza el motor de regulares ECMAScript.

La forma en que funciona esta expresión regular de 50 bytes es conceptualmente bastante simple y completamente diferente a todas las otras soluciones presentadas para este rompecabezas. Fue sorprendente descubrir que este tipo de lógica matemática era expresable en una expresión regular.

      \2                     \4  \5
^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+)$)\5){4})*x?$

(Los grupos de captura están etiquetados encima de la expresión regular)

La expresión regular se puede generalizar a cualquier poder simplemente sustituyendo el 4de{4} con la potencia deseada.

Pruébalo en línea!

Funciona dividiendo repetidamente la cuarta potencia más pequeña de un primo por el que el valor actual es divisible. Como tal, el cociente en cada paso es siempre una cuarta potencia, si el valor original era una cuarta potencia. Un cociente final de 1 indica que el valor original era de hecho una cuarta potencia; Esto completa el partido. Zero también es igualado.

Primero usa un grupo de captura diferida \2para capturar el factor más pequeño del número mayor que 1. Como tal, se garantiza que este factor es primo. Por ejemplo, con 1296 (6 ^ 4) inicialmente capturará \2= 2.

Luego, al comienzo de un ciclo que se repite 4 veces, se prueba para ver si el número actual es divisible por \2, con (?=\2+$). La primera vez a través de este ciclo, esta prueba es inútil, pero su propósito se hará evidente más adelante.

A continuación dentro de este bucle interno, se utiliza el grupo de captura codiciosos \4para capturar el factor más importante del número más pequeño que sí: (?=(x+)(\4+)$). En efecto, esto divide el número por su factor primo más pequeño \2; por ejemplo, 1296 se capturará inicialmente como \4= 1296/2 = 648. Tenga en cuenta que la división del número actual por \2es implícita. Si bien es posible dividir explícitamente el número actual por un número contenido en un grupo de captura (que solo descubrí cuatro días después de publicar esta respuesta), hacer esto generaría una expresión regular más lenta y difícil de entender, y no es necesario, ya que el factor más pequeño de un número mayor que 1 siempre coincidirá con su factor más grande más pequeño que él mismo (de modo que su producto sea igual al número mismo).

Dado que este tipo de expresión regular solo puede "comerse" de la cadena (haciéndola más pequeña) al dejar un resultado al final de la cadena, necesitamos "mover" el resultado de la división al final de la cadena. Esto se realiza capturando el resultado de la resta (el número actual menos \4), en el grupo de captura \5, y luego, fuera de la búsqueda anticipada, haciendo coincidir una parte del comienzo del número actual correspondiente \5. Esto deja la cadena restante sin procesar en el extremo que coincide \4en longitud.

Ahora vuelve al principio del ciclo interno, donde se hace evidente por qué hay una prueba de divisibilidad por el factor primo. Acabamos de dividir entre el factor primo más pequeño del número; si el número sigue siendo divisible por ese factor, significa que el número original podría ser divisible por la cuarta potencia de ese factor. La primera vez que se realiza esta prueba es inútil, pero las siguientes 3 veces, determina si el resultado de dividir implícitamente entre \2todavía es divisible por \2. Si todavía es divisible por \2al comienzo de cada iteración del bucle, esto prueba que cada iteración dividió el número por\2 .

En nuestro ejemplo, con una entrada de 1296, esto se repetirá de la siguiente manera:

\2= 2
\4= 1296/2 = 648
\4= 648/2 = 324
\4= 324/2 = 162
\4= 162/2 = 81

Ahora la expresión regular puede volver al primer paso; Esto es lo que hace la final *. En este ejemplo, 81 se convertirá en el nuevo número; el siguiente ciclo irá de la siguiente manera:

\2= 3
\4= 81/3 = 27
\4= 27/3 = 9
\4= 9/3 = 3
\4= 3/3 = 1

Ahora volverá al primer paso, con 1 como el nuevo número.

El número 1 no se puede dividir por ningún primo, lo que lo convertiría en no coincidente (?=(xx+?)\2+$), por lo que sale del bucle de nivel superior (el que está *al final). Ahora alcanza elx?$ . Esto solo puede coincidir con cero o uno. El número actual en este punto será 0 o 1 si y solo si el número original era una cuarta potencia perfecta; si es 0 en este punto, significa que el bucle de nivel superior nunca coincidió con nada, y si es 1, significa que el bucle de nivel superior dividió un cuarto poder perfecto hasta que ya no fue divisible por nada (o fue 1 en primer lugar, lo que significa que el ciclo de nivel superior nunca coincidió con nada).

También es posible resolver esto en 49 bytes haciendo una división explícita repetida (que también se generaliza para todas las potencias; reemplace la potencia deseada menos una en el {3}), pero este método es mucho, mucho más lento y una explicación del algoritmo que usa está más allá del alcance de esta respuesta:

^((x+)((\2(x+))(?=(\4*)\2*$)\4*(?=\5$\6)){3})?x?$

Pruébalo en línea!

Solución

^(?:(?=(^|(?<=^x)x|xx\1))(?=(^|\1\2))(^x|\3\2{12}xx))*$

Esta expresión regular es compatible con los sabores Java, Perl, PCRE y .NET. Esta expresión regular utiliza una amplia gama de características: mirar hacia adelante, mirar hacia atrás y referencia hacia atrás declarada hacia adelante. Los tipos de referencia inversa declarados hacia adelante limitan la compatibilidad de esta expresión regular a algunos motores.

Explicación

Esta solución hace uso de la siguiente derivación.

Al expandir completamente la suma, podemos probar la siguiente igualdad:

Combinemos la suma en el lado izquierdo:

Resta las 2 ecuaciones (ecuación superior menos ecuación inferior) y luego combina las sumas en el lado izquierdo, luego simplifícalo:

Obtenemos la diferencia entre las cuartas potencias consecutivas como suma de potencia:

Esto significa que la diferencia entre las cuartas potencias consecutivas aumentará en (12n ² + 2).

Para que sea más fácil pensar, refiérase al árbol de diferencias en la respuesta de Volatility :

• El lado derecho de la ecuación final es la segunda fila del árbol de diferencias.
• El incremento (12n ² + 2) es la 3ra fila en el árbol de diferencia.

Basta de matemáticas. De vuelta a la solución anterior:

• El primer grupo de captura mantiene una serie de números impares para calcular i ² como se ve en la ecuación.

  Precisamente hablando, la longitud del primer grupo de captura será 0 (sin usar), 1, 3, 5, 7, ... a medida que el ciclo itera.

  (?<=^x)xestablece el valor inicial para la serie de números impares. El ^solo está ahí para permitir que la anticipación se satisfaga en la primera iteración.

  xx\1 suma 2 y avanza al siguiente número impar.

• El segundo grupo de captura mantiene la serie de números cuadrados para i ² .

  Hablando con precisión, la longitud del segundo grupo de captura será 0, 1, 4, 9, ... a medida que el ciclo itera.

  ^en (^|\1\2)establece el valor inicial para la serie de números cuadrados. Y \1\2agrega el número impar al número cuadrado actual para avanzar al siguiente número cuadrado.

• El tercer grupo de captura (fuera de cualquier búsqueda anticipada y en realidad consume texto) coincide con todo el lado derecho de la ecuación que derivamos anteriormente.

  ^xen (^x|\3\2{12}xx)establece el valor inicial, que es + 1el lado derecho de la ecuación.

  \3\2{12}xxagrega el aumento en la diferencia (12n ² + 2) usando n ² de la captura del grupo 2, y coincide con la diferencia al mismo tiempo.

Esta disposición es posible debido a que la cantidad de texto coincidente en cada iteración es mayor o igual que la cantidad de texto necesaria para ejecutar la búsqueda anticipada para construir n ² .