Policías y ladrones: Reverse Regex Golf

76

Nota : Este desafío ahora está cerrado. Cualquier presentación de policías futuros no será considerada para la respuesta aceptada. Esto es para garantizar que nadie pueda publicar una expresión regular muy simple en el futuro que solo permanezca sin descifrar porque ya nadie está interesado en el desafío.

El desafío de los policías

Debe escribir una expresión regular breve y ofuscada, que satisfaga la siguiente especificación:

  • Puede elegir cualquier sabor que se pueda probar libremente en línea. Hay una buena lista de probadores en línea en StackOverflow . En particular, Regex101 debería ser bueno para comenzar, ya que admite los sabores PCRE, ECMAScript y Python. Puede aumentar el límite de tiempo de espera haciendo clic en la llave en la esquina superior derecha si es necesario. Incluya el probador que elija en su respuesta.

    Si no hay un probador adecuado disponible para su gusto, también puede usar un intérprete en línea como ideone y escribir un pequeño guión en el idioma anfitrión que las personas pueden usar para probar su presentación.

  • Puede usar cualquier función de ese sabor, que no invoque directamente el idioma del host (como las funciones de evaluación de código de Perl).
  • Del mismo modo, puede usar cualquier modificador (si su sabor los tiene), a menos que resulten en una evaluación del código.
  • Su expresión regular debe aceptar al menos una cadena S y rechazar al menos una cadena T , cada una de las cuales tiene al menos 16 y no más de 256 caracteres de longitud, en un período de tiempo razonable (no significativamente más de un minuto). S y T pueden contener caracteres Unicode que no son ASCII, siempre que haya una forma de ingresarlos en el probador en línea. Cualquier par de cadenas de este tipo será clave para su envío.
  • Su expresión regular puede tomar arbitrariamente mucho tiempo en cualquier otra entrada.

El núcleo del desafío es crear una expresión regular cuya clave sea ​​difícil de encontrar. Es decir, debería ser difícil saber con qué cadena no coincide o con qué cadena coincide (o potencialmente incluso ambas si la expresión regular tarda días en completarse excepto las cadenas de la tecla).

El desafío de los ladrones

Se alienta a todos los usuarios, incluidos aquellos que han enviado sus propias expresiones regulares, a "descifrar" otras presentaciones. Un envío se agrieta cuando una de sus claves se publica en la sección de comentarios asociados.

Importante: asegúrese de que ambas cadenas que publique tengan entre 16 y 256 caracteres inclusive, incluso si se pudiera usar casi cualquier cadena para una parte de la clave.

Si un envío persiste durante 72 horas sin ser modificado o agrietado, el autor puede revelar una clave válida editándola en una etiqueta de spoiler en su respuesta. Esto hará que su respuesta sea "segura", es decir, ya no se puede descifrar.

Solo se permite un intento de craqueo por envío por usuario. Por ejemplo, si envío al usuario X: "Su clave es 0123456789abcdef/ fedcba9876543210". y me equivoco, el usuario X rechazará mi suposición como incorrecta y ya no podré enviar conjeturas adicionales para ese envío, pero aún puedo descifrar otros envíos (y otros aún pueden descifrar ese envío).

Los envíos craqueados se eliminan de la contienda (siempre que no sean "seguros"). No deben ser editados o eliminados. Si un autor desea enviar una nueva expresión regular, debe hacerlo en una respuesta por separado.

¡No rompas tu propia sumisión!

Nota: Para cadenas largas en los comentarios sin espacios, SE inserta saltos de línea manuales en forma de dos caracteres Unicode. Por lo tanto, si publica una clave en backticks que es tan larga que se ajusta entre caracteres que no son espacios, no será posible copiar la clave directamente en un probador de expresiones regulares. En este caso, proporcione un enlace permanente al probador de expresiones regulares correspondiente con la expresión regular del policía y su clave; la mayoría de los probadores incluyen esta función.

Puntuación

El puntaje de un policía será el tamaño de su expresión regular en bytes (el patrón más los modificadores, los delimitadores potenciales no se cuentan), siempre que no haya sido descifrado. Ganará el puntaje más bajo de una presentación "segura".

El puntaje de un ladrón será la cantidad de envíos que descifraron. En caso de empate, el tamaño total de bytes de los envíos que descifraron se usará como un desempate. Aquí, el conteo de bytes más alto gana.

Como se indicó anteriormente, cualquier policía puede participar como ladrón y viceversa.

Mantendré tablas de clasificación separadas para las dos partes del desafío.

Tablas de clasificación

Última actualización: 19/10/2014, 20:33 UTC

Policías:

Los envíos en cursiva aún no son seguros.

  1. nneonneo , 841 bytes
  2. Wumpus Q. Wumbley , 10,602 bytes
  3. Sp3000 , 52,506 bytes
  4. user23013 , 53,884 bytes
  5. nneonneo , 656.813 bytes

Ladrones:

  1. user23013 , Agrietado: 11, Tamaño Total: 733 + 30 + 2.447 + 71 + 109 + 121 + 97 + 60 + 141 + 200,127 + 7,563 = 211,499 bytes
  2. nneonneo , Agrietado: 10, Tamaño total: 4,842 + 12,371 + 150 + 3,571 + 96 + 168 + 395 + 1,043 + 458 + 17,372 = 40,466 bytes
  3. Wumpus Q. Wumbley , Agrietado: 6, Tamaño total: 22 + 24 + 158 + 32 + 145,245 + 145,475 = 290,956 bytes
  4. Dennis , Agrietado: 2, Tamaño total: 70 + 73 = 143 bytes
  5. harius , Cracked: 1, Tamaño total: 9,998 bytes
  6. g.rocket , Agrietado: 1, Tamaño total: 721 bytes
  7. stokastic , Cracked: 1, Tamaño total: 211 bytes
  8. Sp3000 , Agrietado: 1, Tamaño total: 133 bytes
  9. TwiNight , Cracked: 1, Tamaño total: 39 bytes
Martin Ender
fuente
66
Me pregunto cuántas líneas de código hemos escrito colectivamente para construir estos acertijos e intentar resolverlos ... y si valdría la pena recopilarlo todo y pegarlo en Github cuando hayamos terminado. Todo el mundo podría contribuir con lo que sea que tengan (codificadores, decodificadores, solucionadores exitosos y no exitosos), tal cual, sin comentar y hackear aunque puedan ser. Con un README si te apetece. Sería como las actas de nuestra conferencia.
Si bien ya no se publican nuevas respuestas, puede valer la pena "cerrar" la pregunta en algún momento. De lo contrario, puede ser posible que alguien responda cuando el interés haya disminuido y permanezca sin oposición por un período más largo.
nneonneo
@nneonneo Hm, generalmente no me gusta cerrar mis desafíos, pero en este caso puede ser una buena idea. Incluso creo que las últimas 3 entradas ya se beneficiaron de recibir menos atención. Estableceré una fecha límite para el viernes.
Martin Ender
@ MartinBüttner: Creo que tendrá que ser estándar para que los desafíos de policías y ladrones tengan una fecha de vencimiento. Los desafíos solo siguen siendo interesantes por tanto tiempo. (Para que conste, este desafío es probablemente mi favorito personal, pero puedo ser parcial en esa opinión :)
nneonneo

Respuestas:

19

.NET regex, 841 bytes [¡Seguro!]

Ahora que tengo una entrada segura, ¡veamos cuán pequeño puedo hacer la expresión regular!

^(?<a>){53}((0(((?<-a>)(?<A>){7}|){997}((?<-b>)(?<B>){7}|){997}((?<-c>)(?<C>){7}|){997}((?<-d>)(?<D>){7}|){997}((?<-e>)(?<E>){7}|){997}((?<-f>)(?<F>){7}|){997}((?<-g>)(?<G>){7}|){997}(?<A>){5})|1(((?<-a>)(?<A>){3}|){997}((?<-b>)(?<B>){3}|){997}((?<-c>)(?<C>){3}|){997}((?<-d>)(?<D>){3}|){997}((?<-e>)(?<E>){3}|){997}((?<-f>)(?<F>){3}|){997}((?<-g>)(?<G>){3}|){997}(?<A>)))((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}((?<-G>){997}|){9}((?<-G>)(?<g>)|){997}){256}$(?<-a>){615}(?(a)(?!))(?<-b>){59}(?(b)(?!))(?<-c>){649}(?(c)(?!))(?<-d>){712}(?(d)(?!))(?<-e>){923}(?(e)(?!))(?<-f>){263}(?(f)(?!))(?<-g>){506}(?(g)(?!))

Prettified :

^(?<a>){53}
(
    (0(
        ((?<-a>)(?<A>){7}|){997}
        ((?<-b>)(?<B>){7}|){997}
        ((?<-c>)(?<C>){7}|){997}
        ((?<-d>)(?<D>){7}|){997}
        ((?<-e>)(?<E>){7}|){997}
        ((?<-f>)(?<F>){7}|){997}
        ((?<-g>)(?<G>){7}|){997}
        (?<A>){5})
    |1(
        ((?<-a>)(?<A>){3}|){997}
        ((?<-b>)(?<B>){3}|){997}
        ((?<-c>)(?<C>){3}|){997}
        ((?<-d>)(?<D>){3}|){997}
        ((?<-e>)(?<E>){3}|){997}
        ((?<-f>)(?<F>){3}|){997}
        ((?<-g>)(?<G>){3}|){997}
        (?<A>))
    )
    ((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}
    ((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}
    ((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}
    ((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}
    ((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}
    ((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}
    ((?<-G>){997}|){9}      ((?<-G>)(?<g>)|){997}
){256}$

(?<-a>){615}(?(a)(?!))
(?<-b>){59}(?(b)(?!))
(?<-c>){649}(?(c)(?!))
(?<-d>){712}(?(d)(?!))
(?<-e>){923}(?(e)(?!))
(?<-f>){263}(?(f)(?!))
(?<-g>){506}(?(g)(?!))

caracteristicas:

  • Corto , 841 bytes
  • Golf y escrito a mano
  • No se sabe que codifique un problema NP-hard
  • Tiempo de espera en la mayoría de las entradas no válidas :)
  • Probado en http://regexhero.net/tester/ , toma ~ 5 segundos para la entrada válida

Gracias a Sp3000 y user23013 por informarme sobre .NET regex.


Después de 72 horas, estoy revelando la clave para que esta presentación sea segura.

Partido :

1110111111110010000110011000001011011110101111000011101011110011001000000111111111001010000111100011111000000100011110110111001101011001000101111110010111100000000010110001111011011111100000011001101110011111011010100111011101111001110111010001111011000000

No partido :Aren'tHashFunctionsFun?

Explicación:

Esta expresión regular implementa una función hash muy simple y bastante estúpida. La función hash calcula un solo entero xcomo salida. xcomienza igual a 53. Se ajusta en función de cada carácter encontrado: si ve un 0, se establecerá x = 7x + 5, y si ve un 1, se establecerá x = 3x + 1. xentonces se reduce el mod 997 7 . El resultado final se compara con una constante predefinida; la expresión regular no coincide si el valor hash no es igual.

Se usan siete grupos de captura (ag) para almacenar los dígitos de base 997 x, con siete grupos de captura más (AG) que sirven como almacenamiento temporal. Utilizo la extensión "equilibrio de grupos de captura" de .NET regex para almacenar enteros en grupos de captura. Técnicamente, el número entero asociado con cada grupo de captura es el número de coincidencias desequilibradas capturadas por ese grupo; "capturar" una cadena vacía usando (?<X>)incrementa el número de capturas, y "equilibrar" el grupo usando (?<-X>)disminuye el número de capturas (lo que provocará una falla de coincidencia si el grupo no tiene capturas). Ambos pueden repetirse para sumar y restar constantes fijas.

Este algoritmo de hash es solo uno que inventé rápidamente, y es el algoritmo de hash más pequeño que se me ocurrió que parecía razonablemente seguro usando solo sumas y multiplicaciones. Definitivamente no es cripto-calidad, y no es probable que sean las debilidades que hacen que sea posible encontrar una colisión en menos de 997 7 /2 evaluaciones de patata.

nneonneo
fuente
Tuve una idea ... Luego me di por vencido porque no tengo más de 500 GB de espacio libre en mi disco duro.
jimmy23013
3
Al verlo ahora en 3 presentaciones sin descifrar, estoy registrando oficialmente mi completa ignorancia del propósito de la construcción (?<a>){53}. Parece estar capturando el patrón vacío en un grupo con nombre a53 veces. Entonces, establezca a=""y repita 52 veces más. Pero realmente no sé si (?<significa lo mismo en la idea de Microsoft de una expresión regular. Su documentación ni siquiera lo menciona . Si incluso un concurso regexp termina con extensiones indocumentadas de Microsoft sobre las personas de Unix, mi existencia no tiene ningún propósito.
Es una captura grupal que no captura nada 53 veces. .NET tiene una extensión llamada equilibrar capturas de grupo, que es su respuesta a la coincidencia de parentesco. Cada grupo nombrado actúa como una pila, por lo que (?<a>){53}empuja la cadena vacía 53 veces. Puedes reventar la pila usando (?<-a>). Esperemos que ahora esté claro por qué esta construcción es tan útil.
nneonneo
2
@ WumpusQ.Wumbley Soy la gente de Unix que encontró esto útil.
jimmy23013
44
@ WumpusQ.Wumbley MSDN tiene una página completa sobre agrupación de construcciones . Que se puede encontrar en la referencia rápida . Cuál es el primer resultado para "referencia de expresiones regulares .net" , de forma análoga a su término de búsqueda de Perl. (Lo mismo para "sintaxis", "manual" o "especificación").
Martin Ender
29

Basic Regex, 656813 bytes [¡seguro!]

La expresión regular para finalizar todas las expresiones regulares. Un último hurra en la noche.

Probable bajo PCRE, Perl, Python y muchos otros.

bzip2'd y la versión codificada en base64 en Pastebin: http://pastebin.com/9kprSWBn (Pastebin no quería la versión en bruto porque era demasiado grande).

Para asegurarse de obtener la expresión regular correcta, puede verificar que su hash MD5 sea

c121a7604c6f819d3805231c6241c4ef

o comprueba que comienza con

^(?:.*[^!0-9@-Za-z].*|.{,255}|.{257,}|.[U-Za-z].{34}[12569@CDGHKLOPSTWXabefijmnqruvyz].{8}[02468@BDFHJLNPRTVXZbdfhjlnprtvxz].{210}

y termina con

.{56}[7-9@-DM-Tc-js-z].{121}[3-6A-DI-LQ-TYZabg-jo-rw-z].{28}[!0-9@-T].{48})$

La clave sigue siendo un agradable y cómodo 256 bytes.

Probé esta expresión regular con Python, pero tenga en cuenta que esta expresión regular no utiliza ninguna característica especial de Python. De hecho, con la excepción de (?:)(como mecanismo de agrupación), en realidad no utiliza características especiales de ningún motor de expresiones regulares: solo clases básicas de caracteres, repeticiones y anclaje. Por lo tanto, debe ser comprobable en una gran cantidad de motores de expresión regular.

Bueno, en realidad, todavía puedo aumentar la dificultad, suponiendo que alguien no solo resuelva instantáneamente los problemas más pequeños ... sino que apuesto a que las personas tendrán problemas con una expresión regular de 1GB ...


¡Después de 72 horas, esta presentación permanece sin descifrar! Por lo tanto, ahora estoy revelando la clave para hacer que la presentación sea segura. Esta es la primera presentación segura, después de que más de 30 presentaciones fueron descifradas seguidas por ladrones persistentes.

Coincidencia : Massive Regex Problem Survives The Night!
No coincidencia :rae4q9N4gMXG3QkjV1lvbfN!wI4unaqJtMXG9sqt2Tb!0eonbKx9yUt3xcZlUo5ZDilQO6Wfh25vixRzgWUDdiYgw7@J8LgYINiUzEsIjc1GPV1jpXqGcbS7JETMBAqGSlFC3ZOuCJroqcBeYQtOiEHRpmCM1ZPyRQg26F5Cf!5xthgWNiK!8q0mS7093XlRo7YJTgZUXHEN!tXXhER!Kenf8jRFGaWu6AoQpj!juLyMuUO5i0V5cz7knpDX0nsL

Explicación de expresiones regulares:

La expresión regular se generó a partir de un problema 3SAT "difícil" con una solución aleatoria introducida deliberadamente. Este problema se generó usando el algoritmo de [Jia, Moore & Strain, 2007]: "Generando fórmulas duras y satisfactorias ocultando soluciones engañosamente". Seis variables booleanas se empaquetan en cada byte de la clave, para un total de 1536 variables.
La expresión regular en sí misma es bastante simple: expresa cada una de las cláusulas 7680 3SAT como una condición invertida (según las leyes de Morgan), y coincide con cualquier cadena que no cumpla con una de las cláusulas 3SAT. Por lo tanto, la clave es una cadena que no coincide con la expresión regular, es decir, una que satisface cada una de las cláusulas.

nneonneo
fuente
1
Entonces, intenté cargar una expresión regular de 60MB en Python. Como era de esperar, no fue muy feliz. La compilación tardó varios minutos, pero lo bueno es que fue casi instantáneo responder consultas. Sospecho que la carga de una expresión regular de 1 GB en Python tomará un par de horas para compilar ...
nneonneo
3
O no tan fácil. Según mi primer intento de reducirlo a un tamaño solucionable, necesitaremos alrededor de 2 ** 61 CPU para terminar a tiempo.
12
El desafío comienza: "Debes escribir una expresión regular breve y ofuscada" (énfasis agregado)
Ypnypn
55
@Ypnypn El desafío hasta ahora ha sido incluso obtener expresiones regulares indescifrables en el tablero; parece que este será el primero en romper esa barrera :)
Sp3000
3
@ MartinBüttner: ¡Gracias! Ya lo hice. Ahora tengo que salir y probar algunos de estos otros problemas de regex NP-hard ...
nneonneo
17

ECMAScript (10602 bytes)

(Nota de idioma: veo muchas publicaciones etiquetadas como ruby, o python, o lo que sea, cuando realmente no usan ninguna característica específica del idioma. Esta solo requiere (?!...)y (?=...)encima de POSIX ERE con referencias. Es probable que esas características estén en el motor de expresiones regulares de su idioma favorito, así que no se desanime de probar el desafío porque elegí usar el probador en línea de JavaScript).

Solo un poco de diversión, no tan computacionalmente difícil como algunos de los otros.

^(?!(.).*\1.|.+(.).*\2)(?=(.))(?=(((?![ҁѧѦЩ]{2}).)*(?=[ҁѧѦЩ]{2}).){2}(?!.*[ЩѦҁѧ]{2}))(?=(((?![ɿqԼϚ]{2}).)*(?=[ϚqԼɿ]{2}).){2}(?!.*[ԼϚɿq]{2}))(?=((?![ϼλҡՄ]{2}).)*(?=[ҡλϼՄ]{2}).(?!.*[Մλϼҡ]{2}))(?=(((?![ʯֆɎF]{2}).)*(?=[FֆʯɎ]{2}).){2}(?!.*[FɎֆʯ]{2}))(?=(((?![AɔbУ]{2}).)*(?=[ɔbAУ]{2}).){3}(?!.*[ɔAbУ]{2}))(?=(((?![ʈͽՄɒ]{2}).)*(?=[ͽՄɒʈ]{2}).){2}(?!.*[ͽՄɒʈ]{2}))(?=(((?![ϙшѭϢ]{2}).)*(?=[Ϣϙѭш]{2}).){2}(?!.*[ѭшϙϢ]{2}))(?=(((?![ՐɏƋѠ]{2}).)*(?=[ƋՐɏѠ]{2}).){2}(?!.*[ѠƋՐɏ]{2}))(?=(((?![Жտʓo]{2}).)*(?=[Жտʓo]{2}).){2}(?!.*[Жʓտo]{2}))(?=(((?![ƆʙƸM]{2}).)*(?=[ƆʙMƸ]{2}).){2}(?!.*[ƆʙMƸ]{2}))(?=(((?![dNѤѯ]{2}).)*(?=[ѤѯNd]{2}).){2}(?!.*[ѤѯdN]{2}))(?=(((?![ҎvȵҜ]{2}).)*(?=[vҜȵҎ]{2}).){2}(?!.*[ҎvҜȵ]{2}))(?=(((?![ҹɀҀҤ]{2}).)*(?=[ɀҤҀҹ]{2}).){2}(?!.*[ҹҤҀɀ]{2}))(?=(((?![OɄfC]{2}).)*(?=[fOɄC]{2}).){3}(?!.*[ɄOfC]{2}))(?=((?![ǷϗЋԒ]{2}).)*(?=[ЋϗԒǷ]{2}).(?!.*[ԒϗЋǷ]{2}))(?=((?![էҹϞҀ]{2}).)*(?=[ҹҀէϞ]{2}).(?!.*[ϞէҹҀ]{2}))(?=(((?![QԶϧk]{2}).)*(?=[QkϧԶ]{2}).){2}(?!.*[ϧԶkQ]{2}))(?=(((?![cիYt]{2}).)*(?=[իYct]{2}).){2}(?!.*[tcYի]{2}))(?=(((?![ɐҷCɄ]{2}).)*(?=[CɄɐҷ]{2}).){3}(?!.*[CҷɐɄ]{2}))(?=(((?![ҥմѾϢ]{2}).)*(?=[ϢѾմҥ]{2}).){2}(?!.*[մϢѾҥ]{2}))(?=((?![Ϛǝjɰ]{2}).)*(?=[Ϛǝjɰ]{2}).(?!.*[jɰϚǝ]{2}))(?=((?![ϭBѾҸ]{2}).)*(?=[ѾҸϭB]{2}).(?!.*[ѾҸBϭ]{2}))(?=((?![ϼλyՎ]{2}).)*(?=[λՎyϼ]{2}).(?!.*[λՎyϼ]{2}))(?=((?![MԋƆƻ]{2}).)*(?=[ƻƆԋM]{2}).(?!.*[MƆԋƻ]{2}))(?=(((?![uԳƎȺ]{2}).)*(?=[uԳƎȺ]{2}).){3}(?!.*[ȺƎuԳ]{2}))(?=((?![ɂƐϣq]{2}).)*(?=[qϣƐɂ]{2}).(?!.*[ɂƐϣq]{2}))(?=(((?![ϫճωƺ]{2}).)*(?=[ωϫճƺ]{2}).){2}(?!.*[ճƺϫω]{2}))(?=((?![ζɏΞƋ]{2}).)*(?=[ɏƋζΞ]{2}).(?!.*[ɏƋζΞ]{2}))(?=(((?![Ӄxԏϣ]{2}).)*(?=[Ӄxԏϣ]{2}).){2}(?!.*[ԏxϣӃ]{2}))(?=(((?![ԈʄʫԻ]{2}).)*(?=[ԻʄԈʫ]{2}).){2}(?!.*[ʫԈԻʄ]{2}))(?=(((?![ɒէƣʈ]{2}).)*(?=[ʈɒէƣ]{2}).){2}(?!.*[ʈƣɒէ]{2}))(?=(((?![Ϥϟƺϫ]{2}).)*(?=[Ϥϫϟƺ]{2}).){3}(?!.*[ƺϫϤϟ]{2}))(?=((?![ɋȡþͼ]{2}).)*(?=[ȡþͼɋ]{2}).(?!.*[þͼȡɋ]{2}))(?=((?![ҡʈԄՄ]{2}).)*(?=[ʈԄՄҡ]{2}).(?!.*[ՄԄҡʈ]{2}))(?=(((?![ʌkȿՌ]{2}).)*(?=[Ռȿkʌ]{2}).){3}(?!.*[kՌȿʌ]{2}))(?=(((?![gǝժʮ]{2}).)*(?=[ǝgʮժ]{2}).){2}(?!.*[gǝʮժ]{2}))(?=((?![ɧƸȝՊ]{2}).)*(?=[ƸɧȝՊ]{2}).(?!.*[ՊȝɧƸ]{2}))(?=(((?![ɜȶʟɀ]{2}).)*(?=[ɀȶʟɜ]{2}).){3}(?!.*[ȶɀʟɜ]{2}))(?=((?![ƅѿOf]{2}).)*(?=[ѿfƅO]{2}).(?!.*[Oѿfƅ]{2}))(?=(((?![GҠƪԅ]{2}).)*(?=[ҠGԅƪ]{2}).){2}(?!.*[GԅƪҠ]{2}))(?=(((?![Һӻѩͽ]{2}).)*(?=[ӻͽҺѩ]{2}).){2}(?!.*[ͽҺѩӻ]{2}))(?=(((?![ʊLՅϪ]{2}).)*(?=[ՅʊLϪ]{2}).){3}(?!.*[LʊϪՅ]{2}))(?=(((?![ɅՈƪԅ]{2}).)*(?=[ƪԅՈɅ]{2}).){2}(?!.*[ԅՈƪɅ]{2}))(?=((?![ʇɊƈѹ]{2}).)*(?=[Ɋƈʇѹ]{2}).(?!.*[ʇƈѹɊ]{2}))(?=(((?![նЏYI]{2}).)*(?=[IYնЏ]{2}).){2}(?!.*[նЏIY]{2}))(?=((?![ͼխɷȡ]{2}).)*(?=[ͼȡɷխ]{2}).(?!.*[ɷխȡͼ]{2}))(?=((?![ҝɞҎv]{2}).)*(?=[ɞҎvҝ]{2}).(?!.*[Ҏҝvɞ]{2}))(?=(((?![eƪGω]{2}).)*(?=[Geƪω]{2}).){3}(?!.*[ƪeGω]{2}))(?=(((?![ɂɿƱq]{2}).)*(?=[Ʊqɿɂ]{2}).){2}(?!.*[Ʊqɂɿ]{2}))(?=((?![ƣЖoɒ]{2}).)*(?=[Жɒoƣ]{2}).(?!.*[ƣoɒЖ]{2}))(?=(((?![Ҵԉձϻ]{2}).)*(?=[ձԉϻҴ]{2}).){2}(?!.*[ϻԉձҴ]{2}))(?=((?![ɆɟѧE]{2}).)*(?=[EѧɆɟ]{2}).(?!.*[ѧEɆɟ]{2}))(?=((?![ѪɝȾѸ]{2}).)*(?=[ѪѸɝȾ]{2}).(?!.*[ѪѸȾɝ]{2}))(?=(((?![ßΩԂɥ]{2}).)*(?=[ɥΩßԂ]{2}).){2}(?!.*[ɥßԂΩ]{2}))(?=(((?![ӃդƐϣ]{2}).)*(?=[ƐդӃϣ]{2}).){2}(?!.*[ϣդƐӃ]{2}))(?=(((?![ѪլѸԿ]{2}).)*(?=[ԿѪѸլ]{2}).){2}(?!.*[ԿѪլѸ]{2}))(?=((?![ɉшƻϙ]{2}).)*(?=[ɉƻшϙ]{2}).(?!.*[ϙƻɉш]{2}))(?=((?![ѹփʯΨ]{2}).)*(?=[ʯփΨѹ]{2}).(?!.*[ѹʯփΨ]{2}))(?=((?![ƕϯʮҏ]{2}).)*(?=[ƕҏʮϯ]{2}).(?!.*[ҏϯʮƕ]{2}))(?=((?![ՌȿSբ]{2}).)*(?=[բՌSȿ]{2}).(?!.*[SȿբՌ]{2}))(?=(((?![ИщɌK]{2}).)*(?=[ɌщИK]{2}).){2}(?!.*[ɌИщK]{2}))(?=(((?![aҵɸւ]{2}).)*(?=[ւҵaɸ]{2}).){2}(?!.*[aւɸҵ]{2}))(?=(((?![լѸխɷ]{2}).)*(?=[ɷѸլխ]{2}).){2}(?!.*[խɷլѸ]{2}))(?=(((?![ՉLʝϥ]{2}).)*(?=[LϥʝՉ]{2}).){2}(?!.*[ՉϥʝL]{2}))(?=((?![ʬϬȝɣ]{2}).)*(?=[Ϭɣȝʬ]{2}).(?!.*[ȝɣϬʬ]{2}))(?=(((?![ɺȴҵւ]{2}).)*(?=[ȴɺҵւ]{2}).){3}(?!.*[ҵȴɺւ]{2}))(?=(((?![ΞʇɊζ]{2}).)*(?=[ζɊʇΞ]{2}).){2}(?!.*[ΞɊζʇ]{2}))(?=(((?![դփӃΨ]{2}).)*(?=[ΨփդӃ]{2}).){2}(?!.*[ΨփդӃ]{2}))(?=((?![ԳuҦc]{2}).)*(?=[uԳҦc]{2}).(?!.*[ҦucԳ]{2}))(?=(((?![ԻЭɌщ]{2}).)*(?=[ԻɌщЭ]{2}).){2}(?!.*[ɌщԻЭ]{2}))(?=((?![ЉջѮӺ]{2}).)*(?=[ӺЉѮջ]{2}).(?!.*[ѮӺЉջ]{2}))(?=(((?![ӿѤɹN]{2}).)*(?=[ӿɹѤN]{2}).){3}(?!.*[ѤNɹӿ]{2}))(?=(((?![ƕʮBg]{2}).)*(?=[Bʮgƕ]{2}).){3}(?!.*[Bʮgƕ]{2}))(?=((?![կƛȸԓ]{2}).)*(?=[ƛȸԓկ]{2}).(?!.*[կԓƛȸ]{2}))(?=(((?![ɥДȸh]{2}).)*(?=[ɥhДȸ]{2}).){2}(?!.*[ɥhȸД]{2}))(?=(((?![ʁԺեW]{2}).)*(?=[եWԺʁ]{2}).){2}(?!.*[ԺʁWե]{2}))(?=((?![ɮςϿʢ]{2}).)*(?=[ʢϿɮς]{2}).(?!.*[ɮςʢϿ]{2}))(?=(((?![ձУAƾ]{2}).)*(?=[ƾУձA]{2}).){2}(?!.*[УAձƾ]{2}))(?=(((?![ԻϠɌʄ]{2}).)*(?=[ʄɌԻϠ]{2}).){2}(?!.*[ϠɌʄԻ]{2}))(?=((?![ɜҥմȶ]{2}).)*(?=[ҥȶɜմ]{2}).(?!.*[ҥȶɜմ]{2}))(?=(((?![ƏՀթϞ]{2}).)*(?=[թՀƏϞ]{2}).){2}(?!.*[ƏՀթϞ]{2}))(?=((?![ҩɃȽϛ]{2}).)*(?=[ɃȽϛҩ]{2}).(?!.*[ҩϛɃȽ]{2}))(?=((?![ҠȺԃD]{2}).)*(?=[ȺҠԃD]{2}).(?!.*[DԃҠȺ]{2}))(?=((?![ɆʊLϥ]{2}).)*(?=[LϥʊɆ]{2}).(?!.*[ʊϥɆL]{2}))(?=(((?![ͽѩɒЖ]{2}).)*(?=[ͽɒѩЖ]{2}).){2}(?!.*[ѩɒЖͽ]{2}))(?=(((?![ςϪʢƩ]{2}).)*(?=[ƩʢςϪ]{2}).){3}(?!.*[ςƩϪʢ]{2}))(?=(((?![ҁϥѧɆ]{2}).)*(?=[ϥѧҁɆ]{2}).){2}(?!.*[ѧҁϥɆ]{2}))(?=((?![Жϗѩʓ]{2}).)*(?=[ʓϗЖѩ]{2}).(?!.*[ʓЖϗѩ]{2}))(?=(((?![ʁեɋþ]{2}).)*(?=[ʁɋեþ]{2}).){2}(?!.*[þեʁɋ]{2}))(?=((?![Mnƻɉ]{2}).)*(?=[Mɉƻn]{2}).(?!.*[ƻMnɉ]{2}))(?=(((?![HʬϬѺ]{2}).)*(?=[HѺʬϬ]{2}).){2}(?!.*[ϬѺʬH]{2}))(?=(((?![cիըҦ]{2}).)*(?=[ըҦիc]{2}).){2}(?!.*[cիҦը]{2}))(?=((?![ȸɥկΩ]{2}).)*(?=[ɥΩկȸ]{2}).(?!.*[ɥȸկΩ]{2}))(?=(((?![ʫҝԲɞ]{2}).)*(?=[ʫԲɞҝ]{2}).){2}(?!.*[ʫɞԲҝ]{2}))(?=(((?![ҺЋϗѩ]{2}).)*(?=[ѩҺϗЋ]{2}).){3}(?!.*[ҺѩЋϗ]{2}))(?=((?![ʯΨɎч]{2}).)*(?=[ʯΨɎч]{2}).(?!.*[ʯΨɎч]{2}))(?=(((?![ѮɔЉA]{2}).)*(?=[ЉɔѮA]{2}).){2}(?!.*[ѮɔAЉ]{2}))(?=(((?![ʞӶdN]{2}).)*(?=[dNʞӶ]{2}).){2}(?!.*[ӶNdʞ]{2}))(?=(((?![ԀŋҔɴ]{2}).)*(?=[ŋԀҔɴ]{2}).){3}(?!.*[ҔɴŋԀ]{2}))(?=(((?![ΠЪƏթ]{2}).)*(?=[ƏΠթЪ]{2}).){3}(?!.*[ΠթЪƏ]{2}))(?=(((?![OՌѿբ]{2}).)*(?=[ՌOբѿ]{2}).){2}(?!.*[OբՌѿ]{2}))(?=((?![ɮȾʢѪ]{2}).)*(?=[ɮȾʢѪ]{2}).(?!.*[ѪȾɮʢ]{2}))(?=((?![ЪϤՋΠ]{2}).)*(?=[ϤΠЪՋ]{2}).(?!.*[ՋΠЪϤ]{2}))(?=((?![Մͽӻϼ]{2}).)*(?=[ͽϼՄӻ]{2}).(?!.*[ϼͽՄӻ]{2}))(?=((?![ԋҳѦЩ]{2}).)*(?=[ѦԋЩҳ]{2}).(?!.*[ѦЩҳԋ]{2}))(?=((?![gҶҸB]{2}).)*(?=[BҶgҸ]{2}).(?!.*[ҸBgҶ]{2}))(?=(((?![ɢλҡѥ]{2}).)*(?=[λҡɢѥ]{2}).){2}(?!.*[ѥλɢҡ]{2}))(?=(((?![AϻЉձ]{2}).)*(?=[ϻձЉA]{2}).){2}(?!.*[ϻձЉA]{2}))(?=((?![tRիp]{2}).)*(?=[Rtpի]{2}).(?!.*[tpRի]{2}))(?=(((?![ɮȹϿÞ]{2}).)*(?=[ϿɮÞȹ]{2}).){2}(?!.*[ϿɮȹÞ]{2}))(?=((?![ϯժʮџ]{2}).)*(?=[ժџϯʮ]{2}).(?!.*[џϯʮժ]{2}))(?=(((?![HʬȠҨ]{2}).)*(?=[HҨȠʬ]{2}).){2}(?!.*[ȠҨʬH]{2}))(?=((?![ՒԉPϻ]{2}).)*(?=[ԉϻPՒ]{2}).(?!.*[PϻԉՒ]{2}))((?=Գ[նƎuc]|ƕ[Bʮȴҏ]|ϣ[ԏɂӃƐ]|Ʊ[ɿϬӄɂ]|Ѿ[ϭϢҸҥ]|ͽ[ѩӻՄɒ]|ɷ[խͼլ]|փ[դiѹΨ]|ϛ[ɅɃȽՀ]|Ԃ[ɥѭմß]|խ[ȡɐѸɷ]|P[ȠՒԉ]|ӷ[ЩEՊƆ]|Ə[ΠթƣϞ]|ч[xɎΨ]|ʄ[ԈϠԻҺ]|Љ[AѮϻջ]|ɒ[ʈƣЖͽ]|ʞ[ӶɔNЦ]|Ɛ[ϣɰqդ]|ʮ[ϯժƕg]|ɥ[ȸДԂΩ]|Ҕ[ŋՐɺɴ]|χ[Ԏѯ]|Ջ[ΠϤԾտ]|Ɏ[чʯֆ]|ҥ[մѬѾȶ]|ɞ[ҝҎԲ]|ҏ[ƕՐϯɺ]|Հ[ϛթϞw]|y[ϼԈҝՎ]|λ[ѥՎϼҡ]|Մ[ͽҡϼʈ]|ϟ[ϫϤԾ]|Ћ[ǷϠҺϗ]|ʫ[ԲԈҝԻ]|ǝ[gjɰժ]|Ԅ[ҡҹʟʈ]|ʌ[kՌэC]|ȶ[ҥЊɜʟ]|Ɍ[щИԻϠ]|ի[Rtըc]|Ո[ƪƺЪɅ]|ƺ[ՈϤϫω]|ß[ԂΩɜҤ]|I[նЏљ]|ҷ[ȡэCɐ]|Ц[ςbʞɹ]|Ǝ[ǂȺԳG]|ӄ[ƱӾѺ]|ʇ[ζiɊѹ]|ֆ[ɎF]|ɏ[ѠΞƋ]|Բ[ɞʫЭ]|Ի[ɌЭʫʄ]|ƪ[ԅωGՈ]|ȡ[խɋͼҷ]|Ϡ[ɌдʄЋ]|ɋ[эʁþȡ]|U[ɝɄՅʝ]|ɺ[ҵȴҏҔ]|Ƚ[ԅϛDҩ]|Ɋ[ƈʇΞ]|ժ[Φʮǝџ]|Ӿ[ӄɂԏ]|Ψ[Ӄчʯփ]|Ω[Ղկßɥ]|щ[KɌЭ]|ɉ[nҶшƻ]|Ժ[WԱե]|G[ƎeҠƪ]|ղ[կՂՑɃ]|Ӷ[ԷʞdѮ]|u[ȺԳQҦ]|Ѡ[ɴɏՐ]|ƛ[ԓՑѿկ]|ɜ[ɀմßȶ]|Ҵ[ԉձʡɧ]|ȿ[kSՌԃ]|ɂ[qӾϣƱ]|Պ[ӷɧƸʡ]|Щ[ѧѦӷԋ]|Ⱦ[ѪɝʢՅ]|Ƀ[ղҩwϛ]|Ҏ[vҜɞ]|ɐ[ҷɄɝխ]|ԏ[ϣxӾ]|Ҁ[ҹϞҤw]|մ[ԂҥɜϢ]|ҳ[ДԋϙѦ]|Ϛ[jɰqԼ]|w[ҀՀɃՂ]|E[ӷɟѧʡ]|У[μAbƾ]|ձ[ҴϻƾA]|ɟ[ɆμEƾ]|Ҥ[ҀßՂɀ]|v[ȵҎՎҝ]|ш[ϢϙɉҸ]|Ͽ[ɹɮςÞ]|O[fCՌѿ]|ʁ[ԶեWɋ]|ȹ[ÞԿɮ]|Ϟ[ՀէҀƏ]|ԋ[ƻҳЩƆ]|ƅ[fԓՉѿ]|ω[ƺeճƪ]|ʈ[ɒԄՄէ]|Ԉ[ʫʄӻy]|Ƌ[ζՐϯɏ]|ɰ[ǝƐΦϚ]|ȴ[ƕϭւɺ]|Δ[Չhҁԓ]|Π[ՋЪoƏ]|Ϫ[ʢƩʊՅ]|ӻ[ҺԈͽϼ]|ʝ[ՉLfU]|Ծ[ϟrՋ]|þ[ɋեͼ]|ӿ[ѤɹÞ]|բ[ՌՑSѿ]|ҡ[λՄɢԄ]|ɸ[ȻՃaҵ]|д[ϠИǷ]|ճ[ωϫл]|ɀ[ҹҤʟɜ]|л[ճeљ]|Ϥ[ϟЪƺՋ]|c[ԳYҦի]|Ռ[Oʌբȿ]|ն[ԳǂYI]|Ʌ[ԅϛՈթ]|ҝ[yɞʫv]|p[ƜRt]|ƣ[էƏɒo]|Ҷ[Ҹɉgj]|A[УձɔЉ]|Þ[ȹϿӿ]|Ƿ[дЋԒ]|k[QԶȿʌ]|ջ[ՒӺЉ]|Ɇ[ʊѧϥɟ]|ʢ[ςϪɮȾ]|ѭ[ДϢϙԂ]|ʘ[ЏƜt]|ѹ[ʇʯփƈ]|ʟ[Ԅȶɀɢ]|ϯ[ҏƋʮџ]|լ[ԿɷѸ]|Ƹ[ՊʙƆȝ]|N[ɹʞdѤ]|ς[ЦϿʢƩ]|ǂ[eƎљն]|ѧ[ɆEҁЩ]|ɴ[ѠҔԀ]|Ʉ[ɐfCU]|ҹ[ԄҀէɀ]|Ւ[ջPϻ]|ѥ[ɢλaՃ]|o[ΠտЖƣ]|g[BҶʮǝ]|Կ[լѪȹ]|Џ[ʘIY]|Y[ctЏն]|Ҡ[ȺDGԅ]|Ѧ[Щҁҳh]|Ѻ[HϬӄ]|ɹ[NЦϿӿ]|ԓ[ƛƅΔȸ]|f[OƅɄʝ]|L[ʝʊՅϥ]|ϼ[yӻλՄ]|џ[ζժiϯ]|ҩ[SɃȽՑ]|Ʃ[Ϫμbς]|դ[փƐӃΦ]|Ѯ[ӶӺЉɔ]|ƻ[ɉԋϙM]|ѩ[ҺϗͽЖ]|ʊ[μɆϪL]|Ж[ɒʓѩo]|B[ƕҸgϭ]|ԅ[ҠɅƪȽ]|ɔ[ʞѮAb]|ϗ[ЋʓԒѩ]|Ɔ[ӷMƸԋ]|љ[лǂI]|ȸ[ɥԓhկ]|q[ƐɿϚɂ]|Ҹ[шҶBѾ]|ʡ[ҴƾEՊ]|Ԏ[dχԷ]|j[ϚnǝҶ]|Ҧ[uըcϧ]|ϻ[ՒЉԉձ]|ʙ[ƸԼɣM]|ե[ʁþԺ]|Ƞ[PHҨ]|Φ[ɰդiժ]|Њ[ɢaѬȶ]|b[ɔƩЦУ]|Չ[ʝƅϥΔ]|ϧ[ԶҦWQ]|Ճ[ѥɸȵՎ]|Ҩ[ɧԉȠʬ]|ҁ[ΔѧѦϥ]|Ց[ҩƛղբ]|ɿ[qԼɣƱ]|μ[УƩɟʊ]|e[ωǂGл]|Һ[Ћʄѩӻ]|ѯ[dѤχ]|Ԓ[Ƿюϗ]|ҵ[ɸɺŋւ]|տ[Ջʓro]|ϙ[ѭƻҳш]|R[իԱp]|Ɯ[pʘ]|r[Ծюտ]|ƈ[ɊѹF]|M[ʙnƆƻ]|i[փʇΦџ]|ƾ[ձУʡɟ]|ɝ[ѸȾɐU]|ю[Ԓʓr]|Д[hҳѭɥ]|a[Њѥւɸ]|Յ[LUϪȾ]|ϭ[ѬBѾȴ]|Ѹ[Ѫɝխլ]|D[ԃȽҠS]|Ⱥ[ԃuƎҠ]|Ȼ[ŋȵɤɸ]|э[ʌԶҷɋ]|Ѥ[ѯӿN]|ԃ[ȺDȿQ]|ȵ[ҜȻՃv]|S[բȿҩD]|Ղ[ҤwΩղ]|ɢ[ѥҡʟЊ]|ɣ[Ϭɿȝʙ]|Վ[yvλՃ]|Ϭ[ɣʬƱѺ]|Ӄ[ϣxΨդ]|թ[ƏɅЪՀ]|ȝ[ʬƸɧɣ]|Ԁ[ɤɴŋ]|ѿ[ƅOƛբ]|H[ȠʬѺ]|F[ֆƈʯ]|Ѫ[ѸȾɮԿ]|է[ʈƣϞҹ]|ʯ[ѹFɎΨ]|ŋ[ȻҔԀҵ]|ɤ[ԀҜȻ]|ԉ[ҴPҨϻ]|ͼ[ȡɷþ]|t[իʘpY]|Ϣ[ѭմѾш]|Э[щԲԻ]|ɮ[ʢѪϿȹ]|ϫ[ƺճϟ]|Ѭ[Њւϭҥ]|Լ[Ϛnɿʙ]|Ξ[ζɊɏ]|Է[ԎӺӶ]|Q[ϧkԃu]|ւ[ҵaѬȴ]|Ր[ѠҏҔƋ]|ը[իԱWҦ]|ʓ[տϗюЖ]|K[щИ]|Ӻ[ԷѮջ]|x[чӃԏ]|И[KɌд]|ʬ[HҨȝϬ]|Ա[RըԺ]|ɧ[ȝҴՊҨ]|n[jɉMԼ]|C[ʌҷɄO]|W[ϧըʁԺ]|h[ДѦΔȸ]|ϥ[ՉLɆҁ]|Ъ[ΠՈϤթ]|կ[Ωղƛȸ]|ζ[џΞʇƋ]|Ҝ[ɤҎȵ]|Զ[ϧkʁэ]|d[ԎNѯӶ]).){3,}\3

Prueba aquí: http://regex101.com/r/kF2oQ3/1

(grillos chirriando)

No hay tomadores? Es extrañamente decepcionante pensar en publicar el spoiler sin evidencia de que alguien lo haya mirado lo suficiente como para comprender qué tipo de problema es.

Estoy escribiendo una explicación completa para publicar más tarde, pero creo que sería más feliz si alguien me ganara.

Cuando dije que no era "computacionalmente difícil" ... es una instancia de un problema de NP completo, pero no una gran instancia.

Sugerencia: es un tipo de rompecabezas de lápiz y papel. Pero estaría bastante impresionado si puede resolver esto solo con lápiz y papel (después de decodificar la expresión regular en una forma adecuada para imprimir).

Tiempo de spoiler

Hay múltiples niveles de spoilers aquí. Si aún no resolvió la expresión regular, es posible que desee volver a intentarlo después de leer solo el primer bloque de spoiler. La clave real que coincide con la expresión regular es después del último bloque de spoiler.

Esta expresión regular codifica un rompecabezas Slitherlink .

Una vez que descubra lo que está sucediendo y convierta la expresión regular en una cuadrícula Slitherlink, descubrirá rápidamente que es más difícil que el Slitherlink promedio. Está en una cuadrícula cuadrada de 16x16, más grande que el habitual 10x10. También es un poco inusual en no tener 0pistas y una relativa escasez de 3's. 0's y 3' s son las pistas más fáciles para trabajar, así que no quería darte muchas de ellas.

rompecabezas de slitherlink

Segunda capa de deterioro:

Cuando resuelva el rompecabezas Slitherlink, se presenta una sorpresa adicional: este Slitherlink tiene más de una solución. Si eres un solucionador habitual de Slitherlink y tienes el hábito de hacer deducciones basadas en el supuesto de una solución única, es posible que te hayas confundido. Si es así, ¡eres un tramposo y este es tu castigo! Parte del trabajo de un solucionador de acertijos es descubrir cuántas soluciones hay.

Capa final de deterioro:

El giro final: las 2 soluciones para Slitherlink son en su mayoría idénticas, pero una es un poco más larga que la otra. Necesitas encontrar el corto. Si solo encontró el largo y lo codificó como una cadena para que coincida con la expresión regular, la cadena tendría 257 caracteres de longitud. La ruta pasa por 256 nodos, pero debe repetir el primer nodo al final para cerrar el ciclo. Y si llegaste tan lejos, podrías haber pensado que cometí un error y se me olvidó contar ese personaje extra. ¡No! y / o Gotcha! (y / o Boosh! y / o Kakow!)

La solución corta tiene una longitud de 254 segmentos y codifica una cadena de 255 caracteres, que es la clave. Como puede comenzar en cualquier nodo del bucle y continuar en sentido horario o antihorario, hay 254 * 2 = 508 respuestas posibles.

solución slitherlink

No coincidencia: bananabananabanana
coincidencia: ƜpRԱԺեþɋэʌkȿՌOfɄCҷɐխɷլԿѪɮȹÞӿѤNɹЦʞӶdѯχԎԷӺջՒϻЉAɔbУƾձҴԉҨʬHѺӄӾԏxчɎֆFƈɊΞζџiփΨӃϣɂƱϬɣɿqϚɰƐդΦժʮgBƕȴւҵɺҏϯƋՐѠɴҔŋԀɤȻɸaЊѬҥѾҸшɉҶjnMʙƸՊʡEɟμƩςʢϪʊLՅȾɝUʝՉϥҁѧЩӷƆԋҳϙѭϢմԂɥȸhΔԓƛѿբՑҩSDȽԅҠGeωƪՈɅϛɃwҀҤՂΩßɜȶʟɀҹԄҡλѥՃȵҜҎɞԲЭщɌИдϠʄԻʫҝyϼӻҺЋϗѩͽɒʈէϞՀթЪΠƏƣoտʓюrԾϟϤƺϫճлљIնǂƎԳuȺԃQϧԶʁWըիcYЏʘƜ
prueba: http://regex101.com/r/pJ3uM9/2


fuente
¡Felicitaciones por haber superado las 72 horas! Ahora puede bloquear su respuesta contra grietas al revelar la clave. Hasta que lo haga, la respuesta aún puede ser descifrada.
Martin Ender
Lo intenté pero no encontré que sea plano ...
jimmy23013
14

Sabor Perl, 158 [agrietado]

Aquí está mi primer intento:

(?(R)|^(?=[a-z]))((?!.*(?&K))(((?|([?-K])|(?'K'$)|(?'k'j'k'?)|(?'k'C[^_^]{3,33}))(?(3)\3|3)){3}(?(R)R(-.-)|(?R))(?'k'<grc>-(?!(?&k))\4(?(R)|\$\4(?5)$)))|(?R))

Pruébalo en ideone.com

(?(R)|^(?=[a-z]))el primer carácter debe ser una letra minúscula
(?!.*(?&K))la cadena no puede contener letras en el rango ASCII [?-K]
(?|...|(?'k'j'k'?)|...)partidos j'k(los otros grupos son pistas esencialmente rojos)
(?(3)\3|3){3}coincide de forma recursiva el 3er grupo o '3' después de 3 niveles de recursividad, que se repite 3 veces
(?(R)...|(?R))Recurse sobre el regex completo una vez o coincidir con algunos caracteres
...(?!(?&k))...Creo que esto es de [?-K]nuevo, pero no puedo recordar
(?(R)|...$)después de la recursión, hacer coincidir algunos grupos y finalizar la cadena
|(?R)si algo no coincide, entonces es hora de una recursión infinita: D

grc
fuente
44
Coincidencia: j'k3j'kj'k3j'kj'kj'k3j'k3j'kj'k3j'kj'kj'k3R-k-<grc>-j'k<grc>-j'k$j'k-k-No coincidencia: HOLYCRAPTHATWASEVIL(coincidencia disponible en ideone.com/pXaGaX para prueba)
16
Todos los que intentaron resolver esto y llegaron a la mitad ahora están preparados para enviar 2 informes de errores y 3 parches de documentación para el motor perl regexp. (Y todos nosotros por diferentes cosas)
77
+1 para una clave genial y tener un emoticón en tu expresión regular[^_^] (-.-)
solo el
@ WumpusQ.Wumbley ¡Bien hecho! Creo que los ladrones están ganando este :(
grc
3
Mi comentario anterior fue principalmente una broma, pero tal vez alguna explicación sería buena. El uso de grupos de captura con nombre en el interior (?|...)es complicado, pero está documentado. Vea el pasaje perlreque comienza con Be careful when using the branch reset pattern in combination with named captures.El truco es que los grupos que tienen el mismo número pero nombres diferentes son el mismo grupo , mientras que los grupos que tienen el mismo nombre pero números diferentes son grupos diferentes .
12

Sabor JS, 9998 bytes [agrietado]

^(?!.*(.).*\1)(?=M)((?=!7|!D|!a|!§|!¾|!Ö|!ù|!Ě|!į|!Ň|"C|"s|"t|"¡|"°|"»|"è|"ñ|"÷|"ķ|"ļ|"Œ|#W|#k|#l|#o|#q|#¶|#À|#Â|#Æ|#č|%!|%1|%O|%ÿ|%Ĕ|%Ğ|%Ī|%ĭ|&e|&q|&Õ|&æ|&ü|&đ|&Ĩ|'%|'`|'k|'¯|'É|'í|'þ|'ė|'Ğ|'ĩ|'IJ|'ļ|'ł|,%|,'|,l|,ª|,®|,¸|,¹|,ã|,õ|,Ċ|,Ġ|,Ī|,İ|,Ņ|-U|-V|-»|-Ï|-Þ|-ì|0_|0u|0°|0Ġ|0İ|0ł|1#|1-|1g|1å|1é|1ą|1Ļ|1ń|2B|2O|2¬|2ë|2ò|2õ|2Ğ|2ĩ|2į|2IJ|2ļ|3d|3²|3Ï|3Þ|3ß|3ç|3ø|3ĉ|3ķ|3ĸ|3Ŀ|4c|4£|4ß|4ã|4Ċ|4ģ|4Ĩ|4ő|4Œ|5&|5Q|5û|5Ā|5ě|5ĩ|6ú|6Ķ|6Ł|7Q|7V|7e|7²|7Á|7Þ|7à|7đ|7Ġ|7ĵ|8w|8¯|8¾|8ņ|8ő|9H|9Y|9i|:6|:s|:¬|:ð|:ü|:Ĉ|:Ċ|:Ĵ|:ĸ|:Ŀ|;X|;®|;¯|;²|;¸|;Ó|;à|;ĥ|;Œ|<-|<t|<å|<ø|<Į|<Ľ|<ō|=&|=l|=¨|=Á|=Ý|=Č|=Ĩ|=Ń|>-|>±|>¸|>Ä|>à|>ð|>ó|>Ī|@B|@F|@_|@³|@´|@Ó|@Ü|@ã|@û|@Ğ|@ğ|@Ĭ|@İ|@Ŀ|A5|AV|A_|Ax|A¹|AÅ|AĞ|AĶ|Aņ|Aō|B¼|BÂ|Bä|Bç|BĊ|Bį|Bİ|BĻ|BŅ|C1|C<|CG|Cy|C~|C¼|Cì|Cù|Cō|DT|DU|Dc|Dj|D¤|DÂ|DÑ|DĀ|Dİ|E,|E¬|E¼|E×|Eā|Eė|Eń|FZ|Ft|F»|F¿|FÈ|FØ|Fç|Fì|Fć|FĬ|Fı|FŅ|Gj|Gl|Gv|G¯|Gâ|Gï|GĖ|Gę|GĦ|Gĭ|H8|HB|HS|Hu|H¥|HÃ|HÌ|Hø|HĆ|HĒ|HĬ|Hĭ|I=|It|I©|Iæ|IĿ|Iō|J1|J3|J5|JQ|JÉ|JÔ|J×|Jă|JIJ|K-|KP|KÄ|Kî|Kā|KĐ|Kġ|KĨ|KĴ|L!|LÐ|Lá|LĚ|LĠ|M5|M¿|MÅ|Må|MĈ|MŊ|N,|N2|N5|NB|Nh|NÂ|NØ|NÜ|NĖ|Nĝ|NŃ|O;|Of|O¯|O¸|Oå|OĈ|Oď|Oē|OIJ|P7|PQ|Pp|P£|Pđ|PĴ|Pŀ|Q7|QR|Q¥|QÝ|Qî|Qī|Qĸ|Qŀ|Qő|R0|RA|RI|RN|R¥|R¼|Rö|Rû|RĬ|RĮ|RŎ|S;|SC|ST|Sd|Sy|S§|TX|Td|Tw|Tª|T¿|Tõ|U0|U:|UÊ|Uĉ|Uę|UĢ|UĦ|Uį|UĶ|Uň|V:|Vq|Vs|V¦|VÂ|Vó|Vþ|Wh|WÅ|WÉ|Wê|Wô|Wģ|Wň|X:|XI|XS|X`|Xâ|Xċ|Xė|XĠ|Xģ|Y"|YX|Yb|Yn|Yo|Y£|Y§|YÌ|YÎ|YÚ|Yá|Yă|YĜ|Yĥ|YĿ|Yʼn|Z6|Z:|Z;|Z¶|Zå|Zæ|Zċ|Zĺ|ZŊ|_,|_-|_c|_g|_à|_ĉ|_Ħ|_ł|`I|`z|`ð|`ă|`IJ|`ij|a4|a9|aF|a½|aä|añ|aď|aĝ|aĸ|b&|b7|b¸|bÝ|bë|bĺ|bņ|bŊ|c&|cP|cr|cÄ|cÑ|cÖ|cČ|cę|cĩ|cIJ|cķ|cĿ|d"|dI|d¥|d¦|dä|dģ|eK|e²|eý|eą|eČ|eĔ|eIJ|eĶ|eń|fM|fm|f¥|fÇ|fÒ|fæ|fì|fć|fě|fĝ|g!|gN|gx|gz|gÍ|gĚ|gĞ|h"|h¬|h¶|hä|hì|hï|hĆ|hņ|hŋ|hŏ|i'|i9|i¢|i¤|iÓ|iÖ|iā|iĕ|iĝ|iį|iĶ|jH|jT|j£|jµ|j·|jø|jĸ|jŐ|k0|k2|kA|k~|k¨|k½|kÙ|l&|lX|lc|ln|l£|l¥|lµ|lÃ|lå|lé|lĩ|lŌ|lŒ|m-|mW|mÐ|mĘ|mĮ|mĸ|n!|n2|nJ|nU|n¬|n½|nĆ|nĒ|nĔ|nĭ|nŇ|o5|o<|oD|oM|oÖ|oĂ|ps|pz|pº|pê|pĢ|pĥ|pIJ|qK|qa|q§|qÛ|qç|qý|qă|qĒ|qĴ|qĶ|qń|rA|re|rj|r§|r«|r¿|rÃ|rß|rò|rĔ|rĖ|rĢ|rķ|sD|sc|sÍ|sĀ|tT|tW|ta|t£|t¯|t±|tÊ|tÑ|tĚ|tļ|uV|ua|ub|uf|u¦|u´|u»|u¾|uË|uØ|uĞ|uĪ|uĹ|v:|vi|vw|v§|v½|vÄ|vÈ|vÌ|vù|vĮ|vļ|vʼn|vŎ|w!|w0|wZ|wg|wÞ|wæ|wò|wù|wĥ|wħ|wŎ|xD|x©|x®|xá|xû|xģ|xľ|xł|yC|ya|yr|y²|yÉ|yò|yĆ|yĠ|yĵ|yŒ|zM|zi|z¯|zø|zú|zć|zđ|~5|~Y|~¨|~º|~Û|~å|~ê|~ô|~ü|~ą|~ĥ|~Ī|~İ|~Ľ|~ō|¡J|¡±|¡¼|¡Ê|¡Ë|¡Ñ|¡ã|¡Ă|¡Ġ|¡Ĩ|¡ī|¡Œ|¢@|¢G|¢±|¢º|¢ç|¢Đ|¢İ|¢Ŀ|£F|£e|£Þ|£ä|£Ĵ|¤P|¤p|¤¯|¤µ|¤þ|¤ď|¤Ģ|¤ī|¥Z|¥¤|¥È|¥Ñ|¥û|¥Ď|¦T|¦Y|¦Z|¦a|¦b|¦e|¦q|¦r|¦¡|¦³|¦ĩ|¦IJ|¦ĺ|§b|§n|§w|§¿|§Ç|§Đ|¨3|¨Ã|¨Ë|¨Î|¨ë|¨÷|¨Č|¨ġ|¨Ī|¨Ĺ|¨ł|¨Œ|©I|©Z|©Ý|©ë|©ü|©ġ|©ŋ|ªP|ªo|ªr|ª¨|ª¯|ª²|ª¾|ªÇ|ªÔ|ªÙ|ªĉ|«K|«p|«£|«¨|«©|«¬|«®|«Õ|«Þ|«ß|«ö|«Đ|¬!|¬j|¬ª|¬¼|¬À|¬Ã|¬Ì|¬ú|¬ő|®#|®´|®É|®č|®đ|®ī|®ʼn|¯9|¯g|¯n|¯¹|¯È|¯Ē|¯ę|¯ġ|°N|°d|°k|°m|°s|°²|°È|°Î|°ê|°ó|°ʼn|±%|±R|±Y|±r|±æ|±Ŀ|±ń|²D|²H|²U|²×|²ã|²ä|²ç|²ą|²ħ|³`|³Ë|³ã|³ë|³ò|³ô|³ø|³Ċ|³Ĥ|³Ŀ|´~|´§|´Ê|´è|´Ķ|´Ŏ|µ:|µC|µ¢|µØ|µó|µĠ|µģ|µĤ|¶!|¶0|¶7|¶Y|¶¤|¶À|¶Ö|¶Ħ|¶ő|·p|·Á|·Ç|·ë|·î|·Ļ|·Ŋ|¸X|¸Z|¸¦|¸÷|¸ú|¸Đ|¸ĝ|¹,|¹>|¹M|¹Z|¹a|¹¢|¹Ì|¹×|¹Ø|¹þ|¹ĉ|¹Ĩ|º>|ºj|ºá|ºç|ºý|ºć|»2|»c|»°|»Ä|»ñ|»Ġ|»Ŋ|¼3|¼F|¼c|¼d|¼x|¼y|¼Ä|¼É|¼û|¼Č|¼ē|¼Ĩ|¼Ĭ|¼Ĵ|¼Ĺ|½k|½Ø|½ø|½ħ|¾2|¾:|¾L|¾¿|¾Á|¾ñ|¾ô|¾÷|¾đ|¾ĥ|¾Ń|¿D|¿«|¿ö|¿ø|¿Ĕ|¿ę|¿Ļ|¿ō|À3|ÀW|À°|ÀÆ|Àđ|ÀĘ|ÀĞ|Àģ|Àİ|Á§|Áé|Áõ|ÁĜ|Áĝ|ÁĪ|Áʼn|Â&|ÂB|ÂM|¿|Âø|Âħ|Âĺ|ÂĻ|ÂŁ|Âʼn|Ã`|Ãt|â|é|ÃĆ|ÃĖ|Ãĥ|Ãĩ|Ä_|Ä¥|ÄÌ|ÄÞ|Äð|ÄĆ|Äİ|ÄŁ|Å@|ÅY|Å«|ÅĄ|Åı|Åĸ|Æ;|ÆK|Æv|Ƶ|ƹ|ƽ|ÆÇ|ÆÛ|Æõ|Æü|ÆĆ|ÆĤ|Çd|Ǻ|ÇĔ|Çě|Çģ|ÇĶ|ÇĽ|Èd|Èz|È~|È´|Ƚ|ÈÂ|Èæ|Èõ|ÈŅ|ÉH|ÉO|ÉÌ|Éï|ÉČ|Éę|ÉĬ|Éĭ|ÉĴ|ÉŎ|Ê%|Ê6|ÊI|Êk|Êy|ʳ|ÊÁ|Êñ|Êą|ÊŃ|Ë!|ËH|Ëh|˺|Ë»|ËÆ|Ëğ|ËŌ|Ì3|Ì7|ÌG|Ìp|Ì«|Ìè|Ìï|ÌĮ|ÌŎ|ÍZ|Íd|Í©|ÍÖ|Íá|Íê|Íø|Íā|ÍŊ|Î-|Î_|ÎÊ|Îæ|Îó|Îù|ÎĀ|ÎĐ|Îġ|Îĭ|ÎŇ|Ï"|Ï5|Ï7|ÏA|ÏH|Ïl|ϱ|Ϲ|ÏÈ|ÏØ|ÏÚ|ÏÛ|ÏĻ|Ïʼn|ÐR|з|ÐÀ|ÐÓ|ÐĒ|Ðě|ÐĶ|Ðľ|Ñ©|ѵ|ÑÅ|ÑÈ|Ñʼn|ÒV|ÒÇ|Òĉ|Òħ|ÒŃ|Ó2|ÓD|ÓÎ|Óç|Ó÷|Óù|ÓĈ|Óķ|ÔE|ÔJ|Ôf|Ôy|ÔÆ|ÔÞ|Ôâ|ÔĂ|ÔĨ|Õ3|ÕG|Õh|Õ¹|ÕÁ|ÕÐ|Õÿ|Õğ|Õī|Ö7|ÖB|Öª|Ö¼|Öÿ|Öħ|Öij|×6|×>|×f|×¢|×µ|×·|×Â|×Ê|×Ñ|×ã|ØG|د|ØÄ|ØÊ|Øé|Øë|ØĊ|ØŇ|ØŐ|Øő|Ù:|Ùh|Ùx|Ù²|Ùč|Ùē|Ùę|Ùě|ÙĨ|ÙŇ|ÚE|Úq|Ú®|ÚÄ|ÚÒ|ÚÜ|Úä|Úí|Úı|Úķ|Û'|ÛW|Ûo|Ût|ÛÓ|Ûô|Ûõ|Ûû|Ûʼn|Ûŋ|Ü!|ÜJ|ÜÆ|ÜŐ|ÝR|Ýg|Ýq|Ýu|ÝÜ|Ýß|Ýð|Ýø|Ýč|ÝĶ|Ýʼn|Þº|ÞÝ|ÞĂ|Þą|Þć|ÞĠ|ÞĨ|ßu|ßÀ|ßė|à4|àS|à`|àk|à§|àé|àø|àĊ|àę|àģ|àĬ|á3|á£|á¶|áÄ|áÏ|áÑ|áâ|áü|áČ|áĽ|áņ|áŌ|â#|âY|â£|âº|âÓ|âġ|âĭ|âı|âŐ|âŒ|ã,|ã1|ã7|ã8|ãé|ãĭ|ä3|ä6|äN|ä¢|ä©|ä¬|äÏ|äĖ|äį|äŏ|åN|å¡|å¾|åØ|åë|åû|åč|åě|æ7|æT|æt|æ¸|æá|æï|æā|æij|ç2|çA|çJ|çl|ç¥|ç¬|çĝ|çĸ|èl|èq|èÓ|èÙ|èČ|èĖ|èĩ|èņ|èʼn|èő|éV|éZ|é®|é´|éí|éó|éû|éą|éě|éĭ|éŃ|ê5|êv|ê«|ê¶|êº|êÃ|êÔ|êİ|ëB|ëb|ë¤|ë¨|ëÎ|ëę|ëĞ|ì#|ì,|ì=|ì>|ìQ|ìS|ìV|ìº|ìā|ìġ|íJ|íV|í~|í¶|íò|íø|íă|íė|íĭ|î<|î=|îD|îR|îµ|îÚ|îÛ|îå|îê|îþ|îĒ|îĜ|îğ|ï%|ï,|ïa|ïu|ïÀ|ïÁ|ïá|ïĄ|ïą|ïċ|ïġ|ïĿ|ïŁ|ïŌ|ð6|ðE|ðp|ð¬|ðÞ|ðä|ðĚ|ðğ|ðļ|ñ1|ñ2|ñX|ñi|ñá|ñú|ñû|ñü|ñį|ñŊ|òB|ò«|ò¿|òÝ|òê|òď|ó5|óÄ|óÇ|óÈ|óÓ|óÕ|óĨ|óļ|ô4|ôh|ôÖ|ôî|ôþ|ôğ|ôŅ|õo|õ¢|õ¶|õÆ|õÓ|õä|õČ|õĕ|õģ|ö7|ö@|ön|ö¢|öÉ|öÒ|öÛ|öâ|öĝ|÷-|÷J|÷p|÷Ò|÷Ģ|÷ĭ|÷ı|÷ʼn|ø,|øo|ø¥|øÆ|øç|øè|øù|øĤ|øĥ|øħ|øň|ù7|ù9|ùs|ùu|ù¹|ùÍ|ùĆ|ùę|ùě|ùĹ|úG|úÅ|úÕ|úÖ|úÜ|úã|úç|úĂ|úĦ|û%|û;|ûR|ûh|ûu|ûz|û´|ûÐ|ûë|ûń|ûŊ|ü_|ü²|üê|üē|üğ|üł|üŅ|ý8|ý¨|ý©|ýÍ|ýÜ|ýĄ|ýċ|ýĩ|ýı|ýIJ|ýĸ|ýł|ýň|ýŎ|þ;|þD|þJ|þT|þr|þ·|þè|þĆ|ÿO|ÿÒ|ÿæ|ÿð|ÿć|ÿğ|ÿŇ|ĀA|ĀR|Ā_|Āv|Āá|ĀĘ|Āģ|Āİ|ā6|āM|ā¸|āä|āĮ|ĂX|ĂÁ|ĂÕ|ĂĚ|Ăķ|ĂĹ|ă"|ă°|ă¸|ăÉ|ăĆ|ăĚ|ăğ|ăĸ|ăĻ|ăŃ|ĄG|ĄJ|ĄK|Ą`|Ąc|Ąd|Ąg|Ąl|Ą³|ĄÄ|ĄÊ|ĄÌ|Ąú|ĄĽ|ą;|ąL|ąc|ąd|ąo|ąr|ą®|ą±|ąÄ|ąÅ|ąÇ|ąÍ|ą×|ąĈ|ąĎ|ąĐ|ąĩ|ąŌ|Ć´|Ƹ|Ć¼|ĆÑ|ĆØ|Ćí|ĆĊ|Ćņ|ĆŌ|ć4|ćx|ćy|ć¦|ć«|ćù|ćŃ|Ĉ&|Ĉ8|ĈE|ĈK|Ĉn|Ĉ¨|Ĉà|Ĉé|Ĉû|Ĉđ|Ĉĥ|ĈĪ|Ĉī|Ĉņ|ĉ@|ĉa|ĉÇ|ĉ×|ĉĩ|ĉň|Ċ#|Ċb|Ċt|Ċ»|ĊÁ|ĊÚ|Ċä|Ċÿ|Ċĝ|Ċĩ|Ċį|ċ'|ċD|ċ¶|ċÖ|ċê|ċþ|ċğ|ċņ|ČM|Čs|Č£|ČĨ|Čį|č±|čÖ|čè|čć|čğ|čń|čʼn|Ď`|Ď¡|Ď·|Ď¾|Ď¿|Ďą|Ďij|Ďŋ|ď"|ď5|ď8|ď=|ďD|ďs|ďØ|ďÚ|ďí|ďġ|ďĩ|ďļ|ĐF|ĐS|Đg|Đk|Đn|Đv|Đ~|ĐÖ|ĐÚ|ĐÜ|Đâ|ĐĞ|đA|đf|đ´|đ¸|đ¿|đÈ|đÖ|đà|đĽ|đŀ|đŌ|Ē%|ĒH|ĒÍ|ĒĹ|ĒĻ|ĒŁ|ĒŃ|ĒŇ|ē;|ēG|ēa|ēe|ēq|ē¶|ē»|ē÷|ēň|Ĕ"|Ĕ4|ĔÃ|Ĕý|Ĕą|ĔĆ|ĔĚ|ĔĞ|ĔĨ|ĕ"|ĕm|ĕw|ĕ¨|ĕ®|ĕÌ|ĕÑ|ĕĤ|Ė#|ĖR|Ėe|Ėu|Ė~|Ė¯|Ėĩ|ĖĬ|ėH|ė¹|ėö|ėú|ėÿ|ėĨ|Ęs|ĘÝ|Ęą|ĘČ|Ęĝ|Ęī|Ęĺ|Ęʼn|ęA|ęk|ęp|ę»|ęè|ęą|ęĐ|ęĨ|Ě'|Ě9|Ěe|Ěm|Ěo|Ě£|Ěª|Ě¾|Ěå|Ěë|Ěă|ĚĎ|ĚĜ|ĚĞ|ěP|ěx|ěê|ěî|ěö|ěĂ|ěĤ|ěĭ|ěļ|Ĝ%|ĜÜ|ĜĽ|ĝJ|ĝh|ĝ¹|ĝÃ|ĝÈ|ĝĖ|ĝĞ|ĝŇ|ĝŒ|Ğ&|Ğe|Ğs|ĞÖ|ğX|ğ²|ğ´|ğ¼|ğÙ|ğò|ğĂ|ğđ|ğĕ|ğĨ|ğĬ|ĠB|Ġc|Ġµ|ĠÈ|Ġè|Ġì|Ġđ|Ġě|ġ5|ġ<|ġH|ġm|ġº|ġÒ|ġü|ġă|ġĶ|ġŀ|Ģ;|Ģ¤|Ģ«|ĢÍ|ĢØ|Ģù|Ģă|ĢĐ|Ģđ|ģ-|ģL|ģ«|ģë|ģþ|ģċ|ģČ|ģĨ|ģĻ|Ĥf|Ĥª|Ĥñ|ĥM|ĥN|ĥU|ĥf|ĥz|ĥ»|ĥõ|ĥň|Ħ`|Ħj|Ħu|Ħ°|Ħ´|ĦÁ|ĦÈ|ĦÕ|Ħæ|ĦĤ|ħ4|ħp|ħ¡|ħ¦|ħ¶|ħß|ħç|ħĴ|ħĵ|ĨC|Ĩ°|ĨÂ|ĨÌ|Ĩç|Ĩõ|ĨĔ|Ĩŏ|ĩ8|ĩl|ĩt|ĩw|ĩċ|ĩđ|ĩĥ|ĩī|ĩŅ|Ī4|Ī9|ĪP|Īz|Ī±|ĪÅ|ĪÈ|ĪÝ|Īä|Īđ|ĪĦ|ĪĬ|ĪĽ|īb|īl|ī¥|ī¦|īÌ|īì|īČ|īĎ|īĐ|Ĭ#|Ĭ4|ĬF|Ĭ¤|Ĭê|Ĭí|Ĭû|Ĭĝ|ĬŌ|ĭ1|ĭK|ĭL|ĭz|ĭ¡|ĭ¯|ĭÌ|ĭâ|ĭĘ|ĭě|ĭĺ|ĮM|ĮR|Įd|Įx|Į¤|ĮÃ|ĮË|ĮÚ|Įå|ĮĤ|ĮĦ|Įī|į&|įD|įI|į¥|į«|įÉ|įÕ|įÛ|įĉ|įđ|įĒ|İQ|İi|ݬ|ݾ|İÕ|İ×|İĄ|İĬ|İľ|ı4|ıa|ıd|ıe|ıf|ı¡|ıĐ|ıĖ|ıIJ|IJ:|IJT|IJU|IJm|IJÛ|IJķ|IJŎ|ij0|ijb|ij¢|ij«|ijé|ijí|ijĎ|ijĘ|ijķ|Ĵ#|ĴF|ĴG|Ĵµ|Ĵ¹|ĴÈ|ĴÏ|Ĵý|Ĵþ|ĴĖ|ĵ8|ĵE|ĵK|ĵ¦|ĵ±|ĵÙ|ĵó|ĵõ|ĵĹ|Ķ6|ĶE|Ķl|Ķm|Ķ£|Ķ²|ĶÅ|Ķ÷|ĶĀ|Ķă|ĶĆ|ķv|ķ«|ķå|ķĢ|ķŌ|ĸ9|ĸH|ĸ¼|ĸè|ĸý|ĸĕ|ĸį|ŧ|Ĺ·|ĹÇ|ĹÈ|Ĺġ|Ĺĩ|ĺ#|ĺ6|ĺp|ĺr|ĺu|ĺæ|ĺí|ĺĖ|Ļ@|ĻI|Ļn|Ļ£|Ļ¶|ĻÂ|Ļú|ĻĮ|ĻŎ|ļ=|ļK|ļO|ļ_|ļ´|ļÀ|ļÄ|ļó|Ľ>|ĽC|ĽD|ĽG|ĽZ|Ľk|Ľr|Ľ¼|ĽÌ|Ľâ|ĽĮ|ĽŒ|ľf|ľÙ|ľÞ|ľĂ|ľī|ľł|ľņ|ĿÊ|Ŀď|Ŀđ|ĿĚ|Ŀĵ|ĿĻ|Ŀŏ|ŀC|ŀM|ŀ®|ŀà|ŀð|ŀõ|ŀČ|ŁE|ŁÁ|ŁÄ|Łõ|Łķ|ŁĿ|ł4|łG|łu|ł¬|łÏ|łò|łČ|łč|łĐ|łŌ|Ń6|Ń¿|ŃÅ|ŃË|ŃÚ|Ńü|Ńě|Ńņ|ń4|ń<|ńE|ńx|ń»|ńÄ|ńď|ńĺ|Ņ,|ŅP|Ņe|Ņn|Ņo|Ņ©|Ņ¯|Ņ½|ŅÛ|ŅĂ|ņî|ņð|ņô|ņĈ|ņī|ņĬ|ņı|Ň8|Ň:|ŇD|ŇT|Ň_|Ňd|Ňu|Ňª|Ňā|Ňć|ŇĈ|Ňň|ňK|ňL|ň¬|ňÇ|ňÏ|ňþ|ňĐ|ňĠ|ňŐ|ʼnQ|ʼn_|ʼnf|ʼnÉ|ʼnË|ʼnĨ|ʼnŃ|Ŋ0|ŊM|ŊW|ŊÔ|ŊĠ|ŋC|ŋH|ŋK|ŋÍ|ŋÒ|ŋØ|ŋÞ|ŋı|ŋĹ|Ō,|Ōl|Ō³|Ōò|Ōā|ŌĖ|ŌĚ|ŌĬ|ŌĮ|Ōĸ|ŌŒ|ōJ|ō¿|ōÀ|ōÝ|ōʼn|Ŏ8|Ŏ;|ŎQ|ŎV|Ŏ§|ŎÄ|ŎÏ|ŎĎ|ŎŇ|ŏ=|ŏD|ŏV|ŏ¹|ŏÈ|ŏÒ|ŏč|ŏĐ|ŏī|ŏĿ|ŏʼn|Ő2|Ő<|ŐC|ŐX|Őg|Ől|Őp|Ő®|Őİ|ő8|ő¹|őÀ|őó|őć|őĊ|őĖ|őĦ|őķ|őĸ|őŀ|ŒB|Œv|ŒÀ|ŒÒ|Œā|Œĉ|Œė|ŒĜ|ŒĦ|Œķ|Œľ).){255}Ň$

Probado en Regex101

Cada cadena coincidente es un camino de Hamilton desde Mhasta Ň.
Sé que esto no es lo suficientemente seguro. Tampoco sé cómo generar problemas difíciles en el camino de Hamilton. Tiene demasiadas soluciones. Y como dijo Martin Büttner, Mathematica lo hizo al instante . Pero este es solo otro enfoque de NP completo además de COTO. Siéntase libre de mejorar esta idea y publicar nuevas respuestas.
La solución que he generado originalmente es: https://regex101.com/r/tM1vX8/2

La solución que he generado:

MĈàękÙēGâġ<øÆv:ĴÏĻĮ¤ĢùĹ·îĜĽDÂŁEā6ĶĆŌĸ¼yò¿Ĕýı¡Ë!į&qKPpzđȽħ¶YÌïÁéVþèlåN2O¸úÜŐİľfćx®čńďļ=¨3d"÷ĭ¯9i'ĞsĀAÅĄ³`ðĚmĘĝŒBç¬ő¹>-ìS§nUĉňĠěĤª¾ôŅ,ĊtÊIĿĵ±RĬíăÉČĨŏĐÖij0°²ã1gÍáÑʼnŃÚÒÇģLÐĒ%ĪĦu¦añû´~ą;ĥ»créüêºjµó5ĩċğĕwŎÄ¥ĎŋØëÎæTXėH8ņībŊÔÞÝßÀWhäĖeIJÛõÓķ«ö7QŀCōJ×¢@_ł4£FZĺ#oĂÕÿŇ
jimmy23013
fuente
3
Coincidencias: consulte regex101.com/r/wK9hI1/1 No coincide: good_job_user23013!
harius
14
Me imagino divididos en 2 campamentos en este momento: aquellos que están quemando CPU y esperando tener suerte, y aquellos que intentan probar P = NP en un par de días.
1
@ WumpusQ.Wumbley Y aquellos de nosotros que usamos Mathematica. ;)
Martin Ender
2
Como Harius no puede comentar para elaborar cómo lo descifró, resumiré rápidamente cómo lo hice: el patrón de hecho codifica un gráfico dirigido con 256 vértices (representados como caracteres) y 2270 bordes (representados como pares de caracteres que están permitidos ser consecutivos) y cada partido es un camino hamiltoniano a través de ese gráfico de Ma Ň. Mathematica tiene una función FindHamiltonianCycle. Podemos convertir esto en un ciclo que atraviese Ň -> Magregando un nuevo borde y conectando Ňy a Mtravés de él. Afortunadamente, Mathematica encuentra ese ciclo al instante. :)
Martin Ender
1
Bueno, soy el tercero, pero de todos modos tuve ganas de terminar mi buscador de caminos. Me dio esto: regex101.com/r/nT2xM6/1
10

RegEx compatible con JS - 3,571 bytes [agrietado]

Yo ... tendré ... al menos ... uno ... sin descifrar ... sumisión. o \ __ / o

[^,;]|^(.{,255}|.{257,})$|^(?!.*,;,,;;)|^(?!.*,;;,,;)|^(?!.*..,;;;,..,.)|^(?!.*.,.;.;.,.,,)|^(?!.*....,,....;;.;.;)|^(?!.*;.{8};,;;;..)|^(?!.*.{8};;.{6};,.,;)|^(?!.*..;....,.;;.{5};;...)|^(?!.*;,.;.{7},...;.{6};...)|^(?!.*...,.,..,,...,.{7};....)|^(?!.*.,;.;.{11};.{9};..,.)|^(?!.*.,.{6},....;.{11};,...,)|^(?!.*..;.{5};....,.{6};,.{12};.)|^(?!.*,,.,,.{8};.{11};.{10})|^(?!.*...,.{9};..,....;.{6},...;.{8})|^(?!.*.{6},.{8},.{6},.{8},..;.,....)|^(?!.*.{7};..;.{5},....;.{10};...;.{9})|^(?!.*..;.{7},.{5};;.{12},.{13},.)|^(?!.*.{5},..;...;.{5};..;.{6},.{22})|^(?!.*.{10},.{8},.{6},;.{14};.;.{6})|^(?!.*..,.;...,.{19};.;..;.{22})|^(?!.*.{6};..;.{14},,.{11};....,.{13})|^(?!.*.{8},.{12};.{19},.{6},;.{6},....)|^(?!.*.,.{11},...,.{7},.{16},.{11},.{6})|^(?!.*.{15};.{7};..;..,.{24},.{7},...)|^(?!.*...,,.{25};...;...;.{19},.{7})|^(?!.*.{26},....,....,.{15},.{6},.{6};....)|^(?!.*.{6};.,.{28};.{6},.{21},.;..)|^(?!.*.{21};..;..,.{22},.{21};,..)|^(?!.*.{5};.{22};,.{17};.{18},,.{8})|^(?!.*.{9};.{25};,.{20},.{6},.{14};.)|^(?!.*.,.{9},.{8};.{8};.{10};.,.{38})|^(?!.*.{18};.{8},.,.;.{5};.{6},.{41})|^(?!.*.{15},.{16};.{7};.{17};.{8};..,.{15})|^(?!.*.{18};.,.{25};..,..;.{13};.{24})|^(?!.*.{10};.{16},.{33};...;.{17},....,..)|^(?!.*.{13},.{46},.{9},.{11},,.,.{10})|^(?!.*.{14},.{33},.{18};....,.;.{16},....)|^(?!.*.{16};....;,.{8},.{30},.{31},.{6})|^(?!.*.{9},;.{15};.{22};.{30},.{16};...)|;.,,;;.;|,;,;,.,.|.;;,.;;;|;.;,,,.;|,...;.;.,,.;.|,.,.;.{5},,;|...;;....;;;;|;..,,,.;..;..|..;;,,..;.{7};.|;..,.,,...;...,...|...;;,.,.;.;.{6}|.;...;,....;.;...,|.;.{8};,.{6},.;.;|.{5},...,...;...;.;..;|...;....;..,..,.;..;...|...;.{5};,.{5},...,.;|;.,.{12},..;;.{7};|...;.{5},..;;.{9},..;.|.;,,..;.{13};....;..|.,;.{15},,...,.,..|.{8};.,....,...,..,.{9};|...;.;.{11},..,...;....;...|.,.,.{9};;....;..,.{10}|.{5};.,;....,.{15};..,|....;.{10};.;....,.{10},;...|....;.{8};;.{6},...;.{5};.{6}|..,;;.{16};....,;.{10}|.{18};.{9};,.,.,..;.|.{11},.{10};.;.;.{10};....,|....;.{11},.{10},..;.,.;.{8}|..,....,.;.{5},.{9},.{7};.{9}|.{7};.;.{5},.{13};.;.{7};...|.{5},.{15};;.{5},.{15},..;|.{12};...;..,.,..;.{5},.{17}|.{12},..;...;.{22},.,..,|.{10},.{11},.,.;.{11};;.{8}|.{11},.{9},.{5},...,.{14};.;....|;.{22};....,.;.{10};.{10};|.{13};...;.{13},.{6};.,.{10};.|.{11};....;.{17},.{9},.{5};,.|,.{14},.{12};.{6};...;.{14};...|..;.;.{19},.{16},.{5};.{6},...|.{27};..,;.{8};;.{8};.{7}|,.{6};.,.{20},.{13},.;.{11}|.{12};.{9},.{8};,.,.{17},.{10}|;.{22};..;.{5},..;....,.{22}|.{6},.{19};.{22};;,.{5};.{5}|;.{5},.{10};..;.;;.{39}|.{11};.{7};.;.{23};.{19};.;|,.{13};.{12},.,.{27};.{6},...|...;.;.{9};.{18};.;.{27},...|...;,.{12},..;.{28},.{15};..|....;.{8};..;...;.{17},.{19},.{14}|.{8};.{29};.{17};.{5};.{5};;...|...,..;.{14},.{8};.{12};.{18},.{10}|..;.;.{7};.{17},.{11},.{24},.{5}|;.{17},.;.{29};.{9};....;.{12}|.{5},..,.{6},.{16};;.{15},.{28}|...,.{12};..;.{10};.{31};.{14};|.{24},.{6},.{22},.,..,.{10};.{7}|.{10},.{12},.{5};.{12},.{7};.{23};.{8}|.{19};.,.{6},.{22},,.{7};.{22}|.{27};,.{14},..,.{7};.{15},.{12}|....;.{18},.{22},,..,.{27};....|...,.{11},.;.;.{9},.{46},.{11}|.{19},....,.{23},.{5},.{7};.{14},.{10}|.{19};,.{11};..,.{11};.{23};.{16}|.{11};.{34},.{14},.{9},.;.{13};|.{11};....,.{41},.{9};;.{8};.{14}|.{5};.;.,.{5};...;.,.{71}|.{6};.{13};....;....;.{20};.{24},.{16}|.{26};,.{19};....;.{11},.;.{26}|.{9},.{9},.{21},.{14};.{10};.{16};.{13}|.{10},.{5},.{9};.{13},...,.{24},.{28}|.{12},.{7};.{8};.{6};;.{36};.{23}|....;.{10},.{21};.{10};.{20},.{10},.{17}|.{19},.{7},.{17},.{9};.{13},.{22};.{10}|....,.{41};.{5},..,.{21};.{6};.{18}|.{25};....;.{28},.{12},.{19};.{8};.|.{10};....,.,.{22};.{11};.{44},.{5}

Se resuelve en prácticamente cualquier cadena instantáneamente. Probable en cualquier consola JS.

+100 repeticiones a cualquiera que descifre a esta bestia.

COTO
fuente
1
Desafío aceptado ...
Unihedron
10
Partido : ThatWasActuallyFun. No coincidencia : ,,;,;,,;,;;;,;,;,;;,,,,;,,,;,;;,,,,,,;;,,,,;;,;,,,;,;;;;,;;,;;,;,,;,,;,;;;,;,;,;;,,,;,;;;;,;,;;;,;,,;,,,;,,,,;,;;;;;;,,,,,;,;,;;;;;,;;;,;;,,,;;;,,;,;;,,,;,,,,,,;,;,,;;,,;;,,,;,;;,,,;,,;;,;,;,;;;;,,;,;,,;;;;;,,;,,;;,,;,,;;,,,,;,,;,,;;,;;;,,,,,;,,,,,,,,;,,,,.
nneonneo
55
¡POR FAVOR! ¡NO! ¡SER! ¡ENTONCES! ¡RÁPIDO!
TwiNight
66
amigo, estás loco, este RegExp tiene 122 alternancias, 40 de las cuales son negativas, WTG ++
CSᵠ
2
@nneonneo: pésimos solucionadores de SAT eficientes. > ___ <Pero accesorios para transformar el problema y hacer uso de las herramientas disponibles por ahí. Otorgaré el 100 representante a una de sus respuestas lo antes posible, que es de aproximadamente 19 horas.
COTO
10

PCRE - 96bytes UTF8, sin delimitadores, sin banderas

[Derrotado] porque nneonneo es un sabio

(?<Warning>[You] \Will (*FAIL)!|\So just (*SKIP)this one!|\And (*ACCEPT)defeat!|[^\d\D]{16,255})

Nada que ver aquí, muévanse...

CSᵠ
fuente
1
Partido So just *SKIPthis one!:; Sin partido:This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is still not accepted. Snow leopards FTW.
COTO
Esta no es la sintaxis PCRE; Es una sintaxis simple de Perl. (Los modificadores de retroceso no funcionan en PCRE, AFAIK)
nneonneo
66
Partido : Do just this one!. No coincidencia : WellThatWasTooEasy. (Probado con Perl 5.12 y Perl 5.18 en mi máquina)
nneonneo
@nneonneo correcto! PD: * Los VERBOS existen en PCRE durante al menos 5 años, no lo suficientemente documentados.
CSᵠ
@COTO la coincidencia es incorrecta, NonMatch está bien.
CSᵠ
8

RegEx compatible con JS - 733 bytes [agrietado]

Intentemos esto por segunda vez con las métricas invertidas: una expresión regular enorme pero una clave relativamente pequeña (lo más importante, dentro del límite de 256 bytes).

[^a-e]|^(?:.{0,33}|.{35,}|.{11}.(?!babcde).{22}|.{17}.(?!daacde).{16}|.{23}.(?!ecacbd).{10}|.{29}.(?!ab).{4}|.{31}.(?!cd)..|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..)$

Se resuelve en prácticamente cualquier cadena instantáneamente. Probado en RegExr.

Ampliado (por conveniencia):

[^a-e] |
^(?:
    .{0,33}|
    .{35,}|
    .{11}.(?!babcde).{22}|
    .{17}.(?!daacde).{16}|
    .{23}.(?!ecacbd).{10}|
    .{29}.(?!ab).{4}|
    .{31}.(?!cd)..|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..
)$

La mejor de las suertes para todos. ;)

COTO
fuente
55
Partido: aaaabaaacaaadaaa, no coincidencia:cacdbbcabdeababcdedaacdeecacbdabcd
jimmy23013
@ user23013: esperaba un crack, pero no tan rápido. ¿Lo hiciste en papel?
COTO
1
Si. Solo quedan dos posibilidades después de las dos primeras expresiones largas. Y solo hay un personaje desconocido después de tres, así que simplemente puedo intentarlo varias veces para obtener la solución.
jimmy23013
8

.NET sabor, 60 bytes [agrietado]

^((\d)(?!(|(\d\d)*\d|(\d{3})*\d\d|(\d{5})*\d{4}|\d{6})\2))+$

Probado con Regex Storm .

Dennis
fuente
3
Partido: 1234567890012345. No coincidencia: 1111222233334444.
jimmy23013
8
٠߀०০੦૦୦௦౦೦൦๐໐༠၀႐០᠐᥆᧐᭐᮰᱀᱐꘠꣐꤀꩐0Así que todos estos son considerados dígitos en .NET ...
jimmy23013
2
Eso es una locura, la mitad de ellos ni siquiera aparecen en mi navegador
Sp3000
7

Sabor Python: 211 bytes [agrietado]

Nota: esta respuesta se publicó antes del cambio de regla sobre la longitud máxima de la clave

Pensé que haría rodar la pelota con esto:

(((((((((((((((\)\\\(58\)5\(58\(\\5\))\15\)9)\14\\919\)\)4992\)5065\14\(5)\13\\\14\\71\13\(\13\)4\\\13\\)\12\12\\28\13)\11)\10\\7217)\9\\)\8\\04)\7\)\(\8\()\6\(183)\5)\4\)65554922\\7624\)7)\3\)8\(0)\2\4\\8\\8)\1

(Probado en RegExr )


Explosión de referencia simple de los personajes. \()0123456789

Sp3000
fuente
Te puedo decir que la cadena aceptada es de aprox. 7 millones de caracteres de longitud. En cuanto a representarlo de alguna manera, ¿tal vez un archivo de texto de 7 MB en alguna parte?
COTO
Sí, ese es prácticamente el único camino a seguir. Pensé que comenzaría con algo que no es difícil de descifrar, pero el truco estaba en la generación de salida. Si el límite de minutos no estuviera en su lugar, esto hubiera sido mucho más largo: P
Sp3000
Ingresar lo que creo que es la única cadena que coincide con su expresión regular en RegExr.com bloquea de manera confiable mi navegador Chrome. En Safari funciona, pero RegExr informa un "tiempo de espera". ¿Lo has probado con éxito en línea?
Emil
@Emil Lo probé con éxito en Firefox. Y todavía estoy esperando salvarlo.
jimmy23013
55
La clave es 5281064 bytes por mi cuenta. Archivo
cargado
7

RegEx compatible con JS: 12,371 bytes [agrietado]

Después de un poco de aliento por parte de Martin, y al ver que otros policías están felizmente enviando expresiones regulares de más de 600 KB, decidí dar el paso una vez más con esto (y la versión prettified aquí ).

Se resuelve en prácticamente cualquier cadena instantáneamente. Probable en cualquier consola JS. Desafortunadamente, el tamaño hace que sea imposible de probar por muchos probadores de expresiones regulares en línea.

COTO
fuente
Jaja, intentaré no volverme
regulares,
2
Partido : this was not NP-hard. No partido :nerdnydeprdoypoypwwwdprelwsprwssddayaeeeysyaaaypowroplsaoprdaolasnoylaeaeadeosladnnosyoywyesorlrydwddadoeyponneeyaaapesenaalnneydaewndplredlerwaawlnrssapapaopnrdwnslowdoanlrernpwyyarpprwnrssdlaopsnnrnnnardpaessldalroleswnnooarlpllasapsesaorardwreylayrr
nneonneo
Simplemente lo forcé por completo (tardé ~ 0.06 segundos en Python) y obtuve cuatro soluciones admisibles, pero debido a un error en su expresión regular, su expresión rechaza muchas más soluciones. (Básicamente, no verifica que todos los caracteres de una "subcadena" determinada se usen, y no verifica que una "subcadena" solo consta de 84 caracteres)
nneonneo
1
(Nota final: regexpal.com maneja esta expresión regular muy bien; supongo que probablemente solo usa el motor de expresiones regulares del navegador).
nneonneo
1
Con 12k bytes no hay necesidad de vincular a una fuente externa. Las respuestas SE pueden tener hasta 30k caracteres.
Martin Ender
7

Sabor .NET, 458 bytes [agrietado]

^(?=[01]{10},[01]{10}$)(0|1((?<=^.)(?<l>){512}|(?<=^..)(?<l>){256}|(?<=^...)(?<l>){128}|(?<=^.{4})(?<l>){64}|(?<=^.{5})(?<l>){32}|(?<=^.{6})(?<l>){16}|(?<=^.{7})(?<l>){8}|(?<=^.{8})(?<l>){4}|(?<=^.{9})(?<l>){2}|(?<=^.{10})(?<l>){1})(?(l)(?<-l>(?=.*,(?:0|1(?<m>){512})(?:0|1(?<m>){256})(?:0|1(?<m>){128})(?:0|1(?<m>){64})(?:0|1(?<m>){32})(?:0|1(?<m>){16})(?:0|1(?<m>){8})(?:0|1(?<m>){4})(?:0|1(?<m>){2})(?:0|1(?<m>){1})$))|){1024})*,(?<-m>){669043}(?(m)(?!)|)

Este es fácil. Pero publicaré uno más difícil más tarde.

Creo que estoy bastante cerca de la respuesta criptográficamente segura.

Probado en RegexStorm .

Esto es básicamente sobre factorización de enteros. La cadena coincidente debe ser la representación binaria de dos enteros Ay B. Por cada 1 de A, coincidirá con 512, 256, ..., 1 grupo de veces l, que se puede agregar para obtener A. Y para cada vez l, coincidirá Busando lookahead y el Bgrupo de tiempos mque es similar a los Atiempos l. Entonces mse iguala un total de A*Bveces. Finalmente, elimina el grupo m669043 veces y comprueba si no hay más m. Entonces A*Bdebe ser exactamente 669043.

Por simplicidad: 669043 = 809 * 827y la solución es la forma binaria de estos dos números.

Este método no funciona con números demasiado grandes para que sea seguro, porque el motor Regex tiene que aumentar el número tantas veces. Pero he publicado una nueva respuesta para trabajar con 289 enteros grandes de base. Tiene un producto de 1536 bits de largo.

También agradece a Martin Büttner por presentar la función de grupo de equilibrio de .NET Regex en su respuesta .

jimmy23013
fuente
Esta idea, wow ...
Sp3000
44
Partido : 1100101001,1100111011. No partido :ThatsWhatIWantedToDo,Nice
nneonneo
1
Creo que el único problema es que la coincidencia dura exponencialmente y que el entero objetivo debe expresarse como un recuento repetido (por lo que lo más probable es que se limite a 32/64/128 bits, que son triviales al factor). Tengo algunas ideas sobre cómo superar estas limitaciones usando la multiplicación de Karatsuba, pero luego obtengo log (n) ^ expresiones regulares de tamaño 2 ...
nneonneo
1
@ Sp3000 pastebin.com/SW0YbQar Esto funciona. No estoy seguro de por qué. Quizás su desarrollador piense que combinar cadenas vacías repetidamente no tiene sentido.
jimmy23013
1
@ Sp3000: no es una sorpresa; básicamente le está pidiendo al motor regex que cuente hasta 800000+. Esto va a ser muy lento (especialmente cuando el "conteo" se realiza a través de una máquina virtual del evaluador de expresiones regulares).
nneonneo
6

RegEx compatible con JS: 2,447 bytes [agrietado]

Mi último intento.

Espero que este dure al menos unas pocas horas antes de que se rompa. Después de eso, me rindo. :PAGS

[^a-f]|^(?:.{0,51}|.{53,}|.{11}.(?!d).{40}|.{12}.(?!a).{39}|.{13}.(?!a).{38}|.{14}.(?!f).{37}|.{15}.(?!d).{36}|.{16}.(?!a).{35}|.{17}.(?!d).{34}|.{18}.(?!c).{33}|.{19}.(?!f).{32}|.{20}.(?!d).{31}|.{21}.(?!d).{30}|.{22}.(?!d).{29}|.{23}.(?!f).{28}|.{24}.(?!d).{27}|.{25}.(?!b).{26}|.{26}.(?!f).{25}|.{27}.(?!f).{24}|.{28}.(?!e).{23}|.{29}.(?!c).{22}|.{30}.(?!c).{21}|.{31}.(?!b).{20}|.{32}.(?!d).{19}|.{33}.(?!e).{18}|.{34}.(?!c).{17}|.{35}.(?!a).{16}|.{36}.(?!a).{15}|.{37}.(?!e).{14}|.{38}.(?!b).{13}|.{39}.(?!f).{12}|.{40}.(?!d).{11}|.{41}.(?!f).{10}|.{42}.(?!c).{9}|.{43}.(?!f).{8}|.{44}.(?!e).{7}|.{45}.(?!c).{6}|.{46}.(?!b).{5}|.{47}.(?!b).{4}|.{48}.(?!f).{3}|.{49}.(?!a).{2}|.{50}.(?!d).{1}|....(.)(.)(.).....(?!\1|\2|\3).{40}|.(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|(.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|(.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|.(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|.(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|(.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|(.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|(.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|(.)(.)(.).........{17}.(?!\52|\53|\54).{23}|.(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|(.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|.......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|.(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|.(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|(.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|.....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|(.).(.).(.).......{28}.(?!\85|\86|\87).{12}|..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|(.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|.(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|....(.)(.)....(.).{39}.(?!\118|\119|\120).{1})$

Como todas las presentaciones anteriores, se resuelve instantáneamente. A diferencia de las presentaciones anteriores, es demasiado largo para RegExr.

Expandido:

[^a-f]|
^(?:
    .{0,51}|
    .{53,}|
    .{11}.(?!d).{40}|
    .{12}.(?!a).{39}|
    .{13}.(?!a).{38}|
    .{14}.(?!f).{37}|
    .{15}.(?!d).{36}|
    .{16}.(?!a).{35}|
    .{17}.(?!d).{34}|
    .{18}.(?!c).{33}|
    .{19}.(?!f).{32}|
    .{20}.(?!d).{31}|
    .{21}.(?!d).{30}|
    .{22}.(?!d).{29}|
    .{23}.(?!f).{28}|
    .{24}.(?!d).{27}|
    .{25}.(?!b).{26}|
    .{26}.(?!f).{25}|
    .{27}.(?!f).{24}|
    .{28}.(?!e).{23}|
    .{29}.(?!c).{22}|
    .{30}.(?!c).{21}|
    .{31}.(?!b).{20}|
    .{32}.(?!d).{19}|
    .{33}.(?!e).{18}|
    .{34}.(?!c).{17}|
    .{35}.(?!a).{16}|
    .{36}.(?!a).{15}|
    .{37}.(?!e).{14}|
    .{38}.(?!b).{13}|
    .{39}.(?!f).{12}|
    .{40}.(?!d).{11}|
    .{41}.(?!f).{10}|
    .{42}.(?!c).{9}|
    .{43}.(?!f).{8}|
    .{44}.(?!e).{7}|
    .{45}.(?!c).{6}|
    .{46}.(?!b).{5}|
    .{47}.(?!b).{4}|
    .{48}.(?!f).{3}|
    .{49}.(?!a).{2}|
    .{50}.(?!d).{1}|
    ....(.)(.)(.).....(?!\1|\2|\3).{40}|
    .(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|
    ...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|
    ......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|
    ....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|
    ..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|
    (.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|
    ..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|
    (.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|
    ...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|
    .(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|
    .(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|
    (.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|
    ...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|
    ..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|
    (.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|
    (.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|
    (.)(.)(.).........{17}.(?!\52|\53|\54).{23}|
    .(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|
    (.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|
    .......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|
    .(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|
    ..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|
    ..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|
    ...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|
    .(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|
    (.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|
    .....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|
    (.).(.).(.).......{28}.(?!\85|\86|\87).{12}|
    ..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|
    (.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|
    ....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|
    ...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|
    ..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|
    ..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|
    ..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|
    .(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|
    ..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|
    ...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|
    ....(.)(.)....(.).{39}.(?!\118|\119|\120).{1}
)$
COTO
fuente
2
Partido: aaaabaaacaaadaaa. No coincidencia: fdeacdbfbdcadaafdadcfdddfdbffeccbdecaaebfdfcfecbbfad.
jimmy23013
Reemplace (.)con el personaje coincidente, y ordene por ese personaje, y será obvio.
jimmy23013
1
Tenga en cuenta que esto es NP-complete, pero no es criptográficamente seguro. Y hay demasiadas restricciones y muy pocas variables para dificultarlo.
jimmy23013
1
@ user23013: Bien jugado, señor. ;) Y de hecho creo que esto es reducible a SAT, que era mi intención. Simplemente no hay suficientes trozos para dificultarlo, como usted dice.
COTO
5

Sabor Python (721 bytes) [agrietado]

Es hora del "Problema de análisis v2":

^(((?(8)S)(((?(9)I|\\)(?(3)\]|Z)((?(7)l|R)(((((((?(4)p)((?(7)x)(?(1)B|Z)(?(11)\()(?(9)X)(?(8)P|T)(?(6)a|E)((?(5)E)(((?(8)3|\[)((?(3)\(|1)((?(1)M|L)(?(3)v|b)(?(2)t|l)(?(1)q)(?(1)K|H)(?(2)\)|R)(?(3)O|K)(?(5)l|l)(((?(2)\[|3)((?(2)N)((?(2)\\)((?(1)E|\])(?(1)\[)([(?(1)Q)])(?(24)\[)(?(24)q))(?(24)g))(?(22)s|U)(?(22)H)(?(23)c|U))(?(24)Q)(?(24)Q)(?(24)H)(?(23)K|\[))(?(22)e|y))(?(24)\\)(?(21)P|4)(?(19)T)(?(24)\))))(?(24)M)(?(17)\()(?(24)2))(?(19)7)(?(21)t|X)(?(22)v))(?(24)\[)(?(19)A|L)(?(16)E|1))(?(19)1|c)(?(14)K|\\)(?(19)4|5)(?(24)\\)(?(20)r)))(?(24)B)(?(24)w)(?(24)5))(?(24)\())(?(24)\\))(?(24)T))(?(9)\[))(?(15)z|w))(?(24)K)\7F(?(24)m)(?(24)R))(?(24)\[))(?(24)h))(?(14)x|t)(?(3)R|M)(?(24)\])(?(24)w))(?(21)z|6)(?(16)r)()$

Probado en Regex101 .


Esta expresión regular es efectivamente "ocultar un árbol en un bosque". La mayor parte de la expresión regular consiste en (?(id)yes-pattern|no-pattern)expresiones, que coinciden con el patrón apropiado dependiendo de si existe o no un grupo con la identificación especificada. La mayoría de estas expresiones no contribuyen a la clave, pero algunas sí. Sin embargo, no tan sutilmente oculto en la expresión regular era [(?(1):Q)]que en realidad es un conjunto de caracteres y \7que requiere que de alguna manera sigas a los grupos. Ambos aparecerán en cualquier editor con resaltado, pero estaban destinados a hacer tropezar a cualquiera que no fuera cauteloso.

Sp3000
fuente
Hombre, esto tomará algo de trabajo.
stokastic
44
\ZRZTE[1LblHRKl3]?sHcKePT(7tvAE1K4r[zZTE[1LblHRKl3]?sHcKePT(7tvAE1K4rFxRzrpartidos. ano coincide
g.rocket
Además, el conjunto de todas las coincidencias posibles es (mi comentario anterior) con ambos ?reemplazados por cualquier personaje en(?(1)Q)
g.rocket
(en Regex101, te dice exactamente lo que estaba tratando de hacer coincidir cuando la coincidencia falló. Esto hizo que encontrar las cosas coincidentes fuera algo más fácil (al menos para detectar errores tipográficos en mi solución)).
g.rocket
Yo estaba cerca, sólo estaba perdiendo la ?'s
stokastic
5

Sabor Python (4842 bytes) [agrietado]

Gracias a @COTO por sus ideas y consejos.

Me gustó tanto la idea 3-SAT de @ COTO que pensé que intentaría hacer mi propia expresión regular basada en ella. Sin embargo, no estoy tan familiarizado con la teoría de 3-SAT, así que solo voy a rezar a los dioses del RNG y espero tener suficientes restricciones.

Traté de mantener la expresión regular de menos de 5000 caracteres para ser justa: obviamente, las expresiones regulares más largas serían imposibles de descifrar, pero tampoco serían muy divertidas de descifrar.

[^01]|^(.{0,81}|.{83,}|....0.{10}1.{22}0.{43}|....0.{14}0.{35}0.{26}|....0.{16}0.{5}1.{54}|....0.{17}1.{34}0.{24}|....1.{11}0.{41}1.{23}|....1.{12}1.{27}1.{36}|....1.{22}1.{38}1.{15}|....1.{30}0.{35}1.{10}|....1.{46}0.1.{28}|....1.{6}1.{65}0....|...0....1.1.{71}|...0.{18}0.{23}0.{35}|...1.{11}1.{33}1.{32}|..0...0.{53}1.{21}|..0.{30}1.{17}0.{30}|..1.{41}0.{10}0.{26}|.0.{13}0.{39}1.{26}|.0.{18}0.{49}0.{11}|.0.{27}1.{36}0.{15}|.0.{31}11.{47}|.00.{37}1.{41}|.1.{32}0.{31}1.{15}|.1.{38}0.{25}0.{15}|.1.{7}0.{38}0.{33}|.{10}0.{14}0.{15}0.{40}|.{10}0.{15}1.{15}1.{39}|.{10}0.{27}1.{11}1.{31}|.{10}0.{39}0.{7}0.{23}|.{10}0.{42}10.{27}|.{10}0.{9}0.{38}0.{22}|.{10}1.{45}1.{16}0.{8}|.{10}1.{47}0.{15}0.{7}|.{10}1.{59}0.{5}1.{5}|.{11}0.{11}0.{54}0...|.{11}0.{29}1.{35}0....|.{11}1.{32}0.{25}1.{11}|.{11}1.{48}1.{6}1.{14}|.{11}11.{50}1.{18}|.{12}0.{27}1.{18}0.{22}|.{12}0.{45}1.{7}1.{15}|.{12}1.{15}0.{42}1.{10}|.{13}0.{40}1...0.{23}|.{13}1.{20}1.{5}1.{41}|.{13}1.{22}0.{31}0.{13}|.{13}1.{24}1.{39}1...|.{13}1.{58}0.{8}0|.{14}0.{22}0....1.{39}|.{14}0.{23}0.{23}1.{19}|.{14}0.{53}10.{12}|.{14}1.{19}1.{11}0.{35}|.{14}1.{19}1.{21}1.{25}|.{14}1.{23}0.{14}0.{28}|.{14}1.{24}1.{12}1.{29}|.{14}1.{35}0.{22}0.{8}|.{14}1.{48}0.{15}1..|.{14}1.{58}0....1...|.{14}1.{65}11|.{14}1.{6}1.0.{58}|.{15}0...01.{61}|.{15}0.{12}0.{30}0.{22}|.{15}0.{15}0.{34}0.{15}|.{15}0.{30}1.{25}0.{9}|.{15}0.{31}0.{32}1.|.{15}0.{36}0.{25}1...|.{15}1.{14}1.{21}1.{29}|.{15}1.{16}1.{16}1.{32}|.{15}1.{20}0.{32}1.{12}|.{16}0.{35}1.{24}0....|.{16}0.{36}1.{15}1.{12}|.{16}1.{13}1.{22}0.{28}|.{16}1.{16}1.{14}0.{33}|.{16}1.{48}1.0.{14}|.{17}1.{29}1.{31}0..|.{17}1.{47}1.{8}0.{7}|.{17}1.{9}0.{20}0.{33}|.{18}0..0.{59}1|.{18}0.{33}1.{6}0.{22}|.{18}0.{36}1.{24}1.|.{18}0.{39}0.{17}1.{5}|.{18}1..0.{35}0.{24}|.{18}1.{16}0.{7}1.{38}|.{19}0.{17}0.{8}1.{35}|.{19}1.{42}00.{18}|.{20}0.{25}1.{31}1...|.{20}0.{43}1.{12}0....|.{20}0.{8}1.{40}0.{11}|.{20}00.{56}1...|.{20}1.{38}0.{7}1.{14}|.{21}0.{39}1.{16}0...|.{22}1....0.{44}1.{9}|.{22}1..1.{20}1.{35}|.{23}0.{39}1.{8}0.{9}|.{23}0.{8}1.{41}1.{7}|.{23}1.{18}1.{25}0.{13}|.{23}1.{20}0.{6}0.{30}|.{24}0.{17}1.{16}0.{22}|.{24}0.{21}1.{13}0.{21}|.{24}1...1.{49}0...|.{24}1.{5}0.{37}0.{13}|.{24}1.{8}1.{37}0.{10}|.{25}0.{36}0....0.{14}|.{25}1....0.{29}0.{21}|.{25}1....1.{10}1.{40}|.{25}1.{13}1.{13}0.{28}|.{25}1.{40}0.{7}0.{7}|.{26}0.{13}1.{21}0.{19}|.{26}0.{13}1.{25}1.{15}|.{27}0.{20}1.{11}0.{21}|.{27}0.{36}0.{6}0.{10}|.{27}1....1.0.{47}|.{27}1...0.{13}1.{36}|.{27}1.{10}0.{26}0.{16}|.{27}1.{30}1.{15}0.{7}|.{28}0.{14}1.{37}0|.{28}0.{21}1.0.{29}|.{28}0.{26}0.{16}0.{9}|.{28}1.{18}1.{23}1.{10}|.{29}0.{17}0.0.{32}|.{29}1.{24}0.{19}1.{7}|.{29}1.{46}1....0|.{30}1.{18}1.{9}0.{22}|.{30}1.{28}0....1.{17}|.{32}0.{25}1.{6}1.{16}|.{33}0.{22}1.{12}0.{12}|.{33}0.{6}0.{11}0.{29}|.{33}1.{5}1.{31}0.{10}|.{34}0.{13}0.{8}0.{24}|.{34}1...1.{35}0.{7}|.{34}1..1.{29}1.{14}|.{34}1.{38}01.{7}|.{34}1.{5}0.{40}1|.{34}1.{6}1.{38}1.|.{34}1.{7}0.{31}0.{7}|.{34}11...1.{42}|.{35}0.{19}0..0.{23}|.{35}1.{12}1.{24}0.{8}|.{36}0.{6}1.{17}1.{20}|.{36}0.{7}1.{17}1.{19}|.{36}0.{8}0.{13}1.{22}|.{36}1.{14}0.{9}1.{20}|.{37}0.{26}1.{16}0|.{37}1.{27}0.{10}0.{5}|.{38}1.{21}1.{7}1.{13}|.{39}0..0.{20}0.{18}|.{39}0.{15}0.{19}1.{6}|.{40}0....0.{28}1.{7}|.{40}0.{15}1.0.{23}|.{40}0.{5}1.{16}0.{18}|.{40}0.{8}1.{29}1..|.{40}00.0.{38}|.{41}0.0.{20}0.{17}|.{41}00.{32}0.{6}|.{41}1.{16}1.{21}1.|.{41}1.{8}1.{18}0.{12}|.{42}1.{31}1.{6}1|.{42}11.{27}0.{10}|.{43}0.{34}10..|.{44}1.0.{10}1.{24}|.{45}0.{9}0.{5}0.{20}|.{45}1.{12}0.{22}1|.{45}1.{17}1....0.{13}|.{45}1.{9}0...0.{22}|.{46}0.{11}1.{19}1...|.{46}1.{24}0.{5}0....|.{47}11.{8}1.{24}|.{48}0.{12}1....0.{15}|.{48}0.{15}0.{13}1...|.{48}1...0.{13}0.{15}|.{48}1.{11}0..0.{18}|.{48}11.{21}0.{10}|.{49}1.{7}1.{14}0.{9}|.{51}1.{12}1.{5}1.{11}|.{54}0.{13}0.{6}1.{6}|.{54}1.{11}1.1.{13}|.{56}0.{16}0..1.{5}|.{56}1.{11}0.{6}0.{6}|.{58}1....1.{6}0.{11}|.{5}0.{17}0.{42}0.{15}|.{5}0.{23}1.{26}1.{25}|.{5}0.{34}1.{22}0.{18}|.{5}0.{6}1.{13}1.{55}|.{5}1.{12}0.{31}1.{31}|.{5}1.{16}0.{39}1.{19}|.{5}1.{16}1.1.{57}|.{5}1.{24}1.{15}1.{35}|.{5}1.{24}1.{47}1...|.{66}0.0.{5}1.{7}|.{6}0....1.{24}0.{45}|.{6}0.{19}0.{7}1.{47}|.{6}0.{23}0.{14}0.{36}|.{6}0.{25}1.{41}0.{7}|.{6}0.{46}1.{22}0.{5}|.{6}0.{52}11.{21}|.{6}1.{35}10.{38}|.{7}0.{20}0.{16}0.{36}|.{7}0.{34}1.{20}1.{18}|.{7}0.{6}0.{36}0.{30}|.{7}0.{7}0.{15}0.{50}|.{7}0.{8}1.{42}1.{22}|.{7}1.{5}1.{56}1.{11}|.{7}1.{67}0..1...|.{8}0.{10}0.{38}0.{23}|.{8}0.{41}11.{30}|.{8}0.{9}1.{37}1.{25}|.{8}1.{50}1.{14}1.{7}|.{9}0..1.{55}0.{13}|.{9}0.{21}1.{42}0.{7}|.{9}0.{59}00.{11}|.{9}0.{9}0....1.{57}|.{9}00.{41}1.{29}|.{9}1....0.{20}0.{46}|.{9}1...0.{41}1.{26}|.{9}1.{30}0.{16}1.{24}|.{9}1.{30}0.{37}1...|.{9}1.{30}1.{14}1.{26}|.{9}1.{40}01.{30}|0.{17}1.{34}0.{28}|0.{23}1.{43}1.{13}|0.{30}1.{26}1.{23}|1.{13}00.{66}|1.{28}0.{42}1.{9}|1.{36}0.{35}1.{8}|1.{42}1.{32}1.{5}|1.{49}0.{16}0.{14}|1.{52}0.{7}0.{20}|)$

Y aquí está en una forma que es un poco más fácil de leer:

[^01]|
^(
  .{0,81}|
  .{83,}|
  ....0.{10}1.{22}0.{43}|
  ....0.{14}0.{35}0.{26}|
  ....0.{16}0.{5}1.{54}|
  ....0.{17}1.{34}0.{24}|
  ....1.{11}0.{41}1.{23}|
  ....1.{12}1.{27}1.{36}|
  ....1.{22}1.{38}1.{15}|
  ....1.{30}0.{35}1.{10}|
  ....1.{46}0.1.{28}|
  ....1.{6}1.{65}0....|
  ...0....1.1.{71}|
  ...0.{18}0.{23}0.{35}|
  ...1.{11}1.{33}1.{32}|
  ..0...0.{53}1.{21}|
  ..0.{30}1.{17}0.{30}|
  ..1.{41}0.{10}0.{26}|
  .0.{13}0.{39}1.{26}|
  .0.{18}0.{49}0.{11}|
  .0.{27}1.{36}0.{15}|
  .0.{31}11.{47}|
  .00.{37}1.{41}|
  .1.{32}0.{31}1.{15}|
  .1.{38}0.{25}0.{15}|
  .1.{7}0.{38}0.{33}|
  .{10}0.{14}0.{15}0.{40}|
  .{10}0.{15}1.{15}1.{39}|
  .{10}0.{27}1.{11}1.{31}|
  .{10}0.{39}0.{7}0.{23}|
  .{10}0.{42}10.{27}|
  .{10}0.{9}0.{38}0.{22}|
  .{10}1.{45}1.{16}0.{8}|
  .{10}1.{47}0.{15}0.{7}|
  .{10}1.{59}0.{5}1.{5}|
  .{11}0.{11}0.{54}0...|
  .{11}0.{29}1.{35}0....|
  .{11}1.{32}0.{25}1.{11}|
  .{11}1.{48}1.{6}1.{14}|
  .{11}11.{50}1.{18}|
  .{12}0.{27}1.{18}0.{22}|
  .{12}0.{45}1.{7}1.{15}|
  .{12}1.{15}0.{42}1.{10}|
  .{13}0.{40}1...0.{23}|
  .{13}1.{20}1.{5}1.{41}|
  .{13}1.{22}0.{31}0.{13}|
  .{13}1.{24}1.{39}1...|
  .{13}1.{58}0.{8}0|
  .{14}0.{22}0....1.{39}|
  .{14}0.{23}0.{23}1.{19}|
  .{14}0.{53}10.{12}|
  .{14}1.{19}1.{11}0.{35}|
  .{14}1.{19}1.{21}1.{25}|
  .{14}1.{23}0.{14}0.{28}|
  .{14}1.{24}1.{12}1.{29}|
  .{14}1.{35}0.{22}0.{8}|
  .{14}1.{48}0.{15}1..|
  .{14}1.{58}0....1...|
  .{14}1.{65}11|
  .{14}1.{6}1.0.{58}|
  .{15}0...01.{61}|
  .{15}0.{12}0.{30}0.{22}|
  .{15}0.{15}0.{34}0.{15}|
  .{15}0.{30}1.{25}0.{9}|
  .{15}0.{31}0.{32}1.|
  .{15}0.{36}0.{25}1...|
  .{15}1.{14}1.{21}1.{29}|
  .{15}1.{16}1.{16}1.{32}|
  .{15}1.{20}0.{32}1.{12}|
  .{16}0.{35}1.{24}0....|
  .{16}0.{36}1.{15}1.{12}|
  .{16}1.{13}1.{22}0.{28}|
  .{16}1.{16}1.{14}0.{33}|
  .{16}1.{48}1.0.{14}|
  .{17}1.{29}1.{31}0..|
  .{17}1.{47}1.{8}0.{7}|
  .{17}1.{9}0.{20}0.{33}|
  .{18}0..0.{59}1|
  .{18}0.{33}1.{6}0.{22}|
  .{18}0.{36}1.{24}1.|
  .{18}0.{39}0.{17}1.{5}|
  .{18}1..0.{35}0.{24}|
  .{18}1.{16}0.{7}1.{38}|
  .{19}0.{17}0.{8}1.{35}|
  .{19}1.{42}00.{18}|
  .{20}0.{25}1.{31}1...|
  .{20}0.{43}1.{12}0....|
  .{20}0.{8}1.{40}0.{11}|
  .{20}00.{56}1...|
  .{20}1.{38}0.{7}1.{14}|
  .{21}0.{39}1.{16}0...|
  .{22}1....0.{44}1.{9}|
  .{22}1..1.{20}1.{35}|
  .{23}0.{39}1.{8}0.{9}|
  .{23}0.{8}1.{41}1.{7}|
  .{23}1.{18}1.{25}0.{13}|
  .{23}1.{20}0.{6}0.{30}|
  .{24}0.{17}1.{16}0.{22}|
  .{24}0.{21}1.{13}0.{21}|
  .{24}1...1.{49}0...|
  .{24}1.{5}0.{37}0.{13}|
  .{24}1.{8}1.{37}0.{10}|
  .{25}0.{36}0....0.{14}|
  .{25}1....0.{29}0.{21}|
  .{25}1....1.{10}1.{40}|
  .{25}1.{13}1.{13}0.{28}|
  .{25}1.{40}0.{7}0.{7}|
  .{26}0.{13}1.{21}0.{19}|
  .{26}0.{13}1.{25}1.{15}|
  .{27}0.{20}1.{11}0.{21}|
  .{27}0.{36}0.{6}0.{10}|
  .{27}1....1.0.{47}|
  .{27}1...0.{13}1.{36}|
  .{27}1.{10}0.{26}0.{16}|
  .{27}1.{30}1.{15}0.{7}|
  .{28}0.{14}1.{37}0|
  .{28}0.{21}1.0.{29}|
  .{28}0.{26}0.{16}0.{9}|
  .{28}1.{18}1.{23}1.{10}|
  .{29}0.{17}0.0.{32}|
  .{29}1.{24}0.{19}1.{7}|
  .{29}1.{46}1....0|
  .{30}1.{18}1.{9}0.{22}|
  .{30}1.{28}0....1.{17}|
  .{32}0.{25}1.{6}1.{16}|
  .{33}0.{22}1.{12}0.{12}|
  .{33}0.{6}0.{11}0.{29}|
  .{33}1.{5}1.{31}0.{10}|
  .{34}0.{13}0.{8}0.{24}|
  .{34}1...1.{35}0.{7}|
  .{34}1..1.{29}1.{14}|
  .{34}1.{38}01.{7}|
  .{34}1.{5}0.{40}1|
  .{34}1.{6}1.{38}1.|
  .{34}1.{7}0.{31}0.{7}|
  .{34}11...1.{42}|
  .{35}0.{19}0..0.{23}|
  .{35}1.{12}1.{24}0.{8}|
  .{36}0.{6}1.{17}1.{20}|
  .{36}0.{7}1.{17}1.{19}|
  .{36}0.{8}0.{13}1.{22}|
  .{36}1.{14}0.{9}1.{20}|
  .{37}0.{26}1.{16}0|
  .{37}1.{27}0.{10}0.{5}|
  .{38}1.{21}1.{7}1.{13}|
  .{39}0..0.{20}0.{18}|
  .{39}0.{15}0.{19}1.{6}|
  .{40}0....0.{28}1.{7}|
  .{40}0.{15}1.0.{23}|
  .{40}0.{5}1.{16}0.{18}|
  .{40}0.{8}1.{29}1..|
  .{40}00.0.{38}|
  .{41}0.0.{20}0.{17}|
  .{41}00.{32}0.{6}|
  .{41}1.{16}1.{21}1.|
  .{41}1.{8}1.{18}0.{12}|
  .{42}1.{31}1.{6}1|
  .{42}11.{27}0.{10}|
  .{43}0.{34}10..|
  .{44}1.0.{10}1.{24}|
  .{45}0.{9}0.{5}0.{20}|
  .{45}1.{12}0.{22}1|
  .{45}1.{17}1....0.{13}|
  .{45}1.{9}0...0.{22}|
  .{46}0.{11}1.{19}1...|
  .{46}1.{24}0.{5}0....|
  .{47}11.{8}1.{24}|
  .{48}0.{12}1....0.{15}|
  .{48}0.{15}0.{13}1...|
  .{48}1...0.{13}0.{15}|
  .{48}1.{11}0..0.{18}|
  .{48}11.{21}0.{10}|
  .{49}1.{7}1.{14}0.{9}|
  .{51}1.{12}1.{5}1.{11}|
  .{54}0.{13}0.{6}1.{6}|
  .{54}1.{11}1.1.{13}|
  .{56}0.{16}0..1.{5}|
  .{56}1.{11}0.{6}0.{6}|
  .{58}1....1.{6}0.{11}|
  .{5}0.{17}0.{42}0.{15}|
  .{5}0.{23}1.{26}1.{25}|
  .{5}0.{34}1.{22}0.{18}|
  .{5}0.{6}1.{13}1.{55}|
  .{5}1.{12}0.{31}1.{31}|
  .{5}1.{16}0.{39}1.{19}|
  .{5}1.{16}1.1.{57}|
  .{5}1.{24}1.{15}1.{35}|
  .{5}1.{24}1.{47}1...|
  .{66}0.0.{5}1.{7}|
  .{6}0....1.{24}0.{45}|
  .{6}0.{19}0.{7}1.{47}|
  .{6}0.{23}0.{14}0.{36}|
  .{6}0.{25}1.{41}0.{7}|
  .{6}0.{46}1.{22}0.{5}|
  .{6}0.{52}11.{21}|
  .{6}1.{35}10.{38}|
  .{7}0.{20}0.{16}0.{36}|
  .{7}0.{34}1.{20}1.{18}|
  .{7}0.{6}0.{36}0.{30}|
  .{7}0.{7}0.{15}0.{50}|
  .{7}0.{8}1.{42}1.{22}|
  .{7}1.{5}1.{56}1.{11}|
  .{7}1.{67}0..1...|
  .{8}0.{10}0.{38}0.{23}|
  .{8}0.{41}11.{30}|
  .{8}0.{9}1.{37}1.{25}|
  .{8}1.{50}1.{14}1.{7}|
  .{9}0..1.{55}0.{13}|
  .{9}0.{21}1.{42}0.{7}|
  .{9}0.{59}00.{11}|
  .{9}0.{9}0....1.{57}|
  .{9}00.{41}1.{29}|
  .{9}1....0.{20}0.{46}|
  .{9}1...0.{41}1.{26}|
  .{9}1.{30}0.{16}1.{24}|
  .{9}1.{30}0.{37}1...|
  .{9}1.{30}1.{14}1.{26}|
  .{9}1.{40}01.{30}|
  0.{17}1.{34}0.{28}|
  0.{23}1.{43}1.{13}|
  0.{30}1.{26}1.{23}|
  1.{13}00.{66}|
  1.{28}0.{42}1.{9}|
  1.{36}0.{35}1.{8}|
  1.{42}1.{32}1.{5}|
  1.{49}0.{16}0.{14}|
  1.{52}0.{7}0.{20}|
)$

Probado en Regex101 .


La expresión regular busca una cadena Sde 82 caracteres de 0s y 1s. Realiza un gran número de verificaciones del formulario (después de aplicar el de Morgan) S[index1] != digit1OR S[index2] != digit2OR S[index3] != digit3, que conforman las cláusulas 3-SAT. El tamaño de la expresión regular es lineal en el número de pistas y logarítmico en el número de caracteres en la clave (debido a la .{n}notación). Desafortunadamente, para estar seguro, la cantidad de pistas tiene que aumentar con el tamaño de la clave, y aunque es ciertamente posible hacer una clave indescifrable de esta manera, terminaría siendo una expresión regular bastante larga.

Sp3000
fuente
1
Partido: x. No partido:0011001101000000000111010001101101011000010011011010000000010001011111000100010000
nneonneo
Partido: aaaabaaacaaadaaa. No partido: 011100110010001010111101001010010011110010011010110101010001101100101111111111+ 0000. Solo unos segundos más lento ...
jimmy23013
Wow, eso fue rápido, ¿la fuerza bruta?
Sp3000
1
@ Sp3000 Lo hice casi manualmente ... Sorprendentemente, el método estadístico funcionó.
jimmy23013
2
@ Sp3000: lo habría forzado brutalmente, pero eso no fue divertido. En cambio, convertí tu secuencia a 3SAT y la descifré con minisat. Tomó 0.3 segundos (tiempo dedicado a la conversión, ~ 10 minutos)
nneonneo
5

Sabor Perl, 133 [agrietado]

Bien, este debería ser más difícil de fuerza bruta:

^([^,]{2,}),([^,]{2,}),([^,]{2,}),(?=.\2+,)(?=.\3+,)\1+,(?=.\1+,)(?=.\3+,)\2+,(?=.\1+,)(?=.\2+,)\3+,(?=.{16,20}$)(\1{3}|\2{3}|\3{3})$

Y una versión más larga, que no forma parte del desafío:

^([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),(?=.\2+,)(?=.\3+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\1+,(?=.\1+,)(?=.\3+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\2+,(?=.\1+,)(?=.\2+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\3+,(?=.\1+,)(?=.\2+,)(?=.\3+,)(?=.\5+,)(?=.\6+,)\4+,(?=.\1+,)(?=.\2+,)(?=.\3+,)(?=.\4+,)(?=.\6+,)\5+,(?=.\1+$)(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)\6+$

Se puede probar en Regex101 (sabor pcre).


La idea detrás de este patrón es que podemos codificar un sistema simple de ecuaciones de congruencia en una expresión regular usando lookaheads. Por ejemplo, la expresión regular ^(?=(..)*$)(...)*$coincide con cualquier cadena cuya longitud es un múltiplo común de 2 y 3 , es decir, un múltiplo de 6 . Esto se puede ver como la ecuación 2x ≡ 0 mod 3 . Podemos parametrizar la ecuación usando grupos de captura: la expresión regular ^(.*),(.*),(?=\1*$)\2*$coincide con cadenas donde el número de caracteres después de la última coma es un múltiplo común de la longitud de la primera y segunda subcoincidencias. Esto puede verse como la ecuación parametrizada ax ≡ 0 mod b , donde a y b son las longitudes de las dos subcoincidencias.

La expresión regular anterior comienza por tomar tres "parámetros" de longitud de al menos dos, y es seguida por tres "sistemas de ecuaciones" de la (?=.\1+,)(?=.\2+,)\3+,que corresponden a {ax + 1 ≡ 0 mod c, por + 1 ≡ 0 mod c, ax = por} , donde un , b y c son las longitudes de los subcoincidencias correspondientes. Este sistema de ecuaciones tiene una solución si y sólo si una y b están coprimo con c . Como tenemos tres sistemas de este tipo, uno para cada subcoincidencia, las longitudes de las subcoincidencias deben ser coprime por pares.

La última parte de la expresión regular está ahí para garantizar que uno de los subcoincidentes sea de longitud 6 . Esto obliga a las otras dos subpartidas a serDe 5 y 7 caracteres, ya que los valores más pequeños no serán coprimos y los valores más grandes darán como resultado una clave de más de 256 caracteres. Las soluciones más pequeñas a las ecuaciones producen subcadenas de longitudes 85 , 36 y 91 , lo que da como resultado una cadena de longitud 254, aproximadamente el tiempo que podamos obtener.

La expresión regular más larga utiliza el mismo principio, solo con 6 parámetros de longitud de al menos tres y sin restricciones adicionales. El conjunto coprime por pares más pequeño de seis enteros mayor que 2 es {3, 4, 5, 7, 11, 13} , que produce subcadenas de longitudes mínimas 40041, 15016, 24025, 34321, 43681 y 23101. Por lo tanto, la cadena más corta que coincide con la expresión regular más larga es a{3},a{4},a{5},a{7},a{11},a{13},a{40041},a{15016},a{24025},a{34321},a{43681},a{23101} (hasta el orden de los parámetros). ¡Eso es 180,239 caracteres!

Ana
fuente
Eso {16,20}.
Sp3000
2
Coincidencia: No aaaaa,aaaaaa,aaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaacoinciden:aaaaaaaaaaaaaaaa
Sp3000
Creo que SE sigue agregando as adicionales por alguna razón: debería haber 5,6,7,85,36,91,18 as entre las comas: /
Sp3000
@ Sp3000 Elige una carta, cualquier carta;) Sí, la descifraste. Parece que algunas de las 'a' en su comentario no son ASCII, pero los números son correctos.
Ell
@Ell Los as son todos ASCII, pero hay dos caracteres Unicode no imprimibles para cada salto de línea manual que hace SE.
Martin Ender
5

Sabor .NET, 141 bytes [agrietado]

(?=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))^.*$(?<=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))

¡Otro para los ladrones! Estoy seguro de que esto se descifrará, pero espero que la persona que lo descifre aprenda algo interesante sobre el sabor de .NET en el proceso.

Probado en RegexStorm y RegexHero .

Pensé que este sería interesante porque se basa en la interacción de las tres características históricas de expresiones regulares que solo puedes encontrar en .NET: retrospectivas de longitud variable, grupos de equilibrio y coincidencia de derecha a izquierda.

Antes de comenzar con los detalles de .NET, aclaremos una cosa simple sobre las clases de caracteres. Las clases de personajes no pueden estar vacías, por lo que si uno comienza con a ], eso en realidad es parte de la clase sin necesidad de escapar. Del mismo modo, un [en una clase de caracteres puede tratarse sin ambigüedad como un miembro de la clase sin escapar. Por []]lo tanto, coincide exactamente con un solo \], y [[]es el mismo \[y, lo que es más importante, [][]es una clase de caracteres que contiene ambos corchetes.

Ahora echemos un vistazo a la estructura de la expresión regular:(?=somePattern)^.*$(?<=somePattern). Entonces, la coincidencia real es realmente cualquier cosa (la ^.*$), pero aplicamos un patrón dos veces, anclando al inicio una vez y al final una vez.

Veamos ese patrón: (?<![][])asegúrese de que no haya corchetes antes del patrón. (?![][])(al final) se asegura de que no haya corchetes después del patrón. Esto se cumple en los extremos de una cadena o adyacente a cualquier otro carácter.
Esta cosa, (?(c)(?!))al principio es realmente redundante por ahora, porque solo se asegura de que el grupo de captura nombrado cno coincida con nada. Nos qué necesitamos esto al final, así que por lo menos es agradable y simétrica. Ahora la parte principal del modelo es la siguiente: ((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!)). Estos grupos se denominan grupos de equilibrio, y lo que hacen aquí es hacer coincidir una cadena de al menos 15corchetes equilibrados . Hay mucho que decir sobre el equilibrio de grupos, demasiado para esta publicación, pero puedo remitirlo a una discusión bastante completa que publiqué en StackOverflow hace un tiempo.

Bien, entonces lo que hace la búsqueda anticipada es asegurarse de que el patrón comience con esos corchetes equilibrados, y que no haya más corchetes junto a eso.

Ahora el lookbehind al final contiene exactamente el mismo patrón. Entonces, ¿no debería ser esto redundante? No debe algo así como [][][][][][][][]cumplir con ambos lookarounds y hacer que el patrón que corresponda?

No. Porque aquí es donde se pone difícil. Aunque no están documentados, los retrospectivos de .NET coinciden de derecha a izquierda. Esta es la razón por la cual .NET es el único sabor que admite revisiones de longitud variable. Por lo general, no se da cuenta de esto porque el orden de coincidencia es irrelevante. Pero en este caso particular, significa que los corchetes de apertura ahora deben venir a la derecha de los corchetes de cierre. Por lo tanto, la mirada atrás realmente comprueba los corchetes anti-coincidentes, como en ][][][o ]]][[[. Es por eso que también necesito el cheque (?(c)(?!))al comienzo del patrón, porque ahora es el final del partido.

Por lo tanto, queremos 15 (o 16) paréntesis coincidentes al comienzo de la cadena y 15 (o 16) paréntesis anti-coincidencia al final de la cadena. Pero esos dos no se pueden conectar debido a la(?![][])Lookarounds. ¿Asi que que hacemos? Tomamos una cadena coincidente y una cadena anti-coincidente y las unimos con un carácter arbitrario, por ejemplo [][][][][[[[]]]]!][][][][]]]][[[[.

Supongo que eso deja una pregunta ... ¿cómo demonios me di cuenta de que coinciden los lookbehinds de derecha a izquierda? Bueno, una vez probé un poco de magia argenta de expresiones regulares y no pude entender por qué mi mirada atrás no funcionaría. Entonces le pregunté al amigable sitio de preguntas y respuestas al lado . Ahora estoy muy contento con esta característica, porque hace que los grupos de equilibrio sean aún más potentes si sabes cómo usarlos correctamente. :)

Martin Ender
fuente
1
Partido: [][][][][][][][]a][][][][][][][][. No partido:That's interesting...
jimmy23013
@ user23013 ¡Sí! Eso fue rápido. ¿Ya estabas familiarizado con esas peculiaridades de .NET? :)
Martin Ender
Ojalá hubiera descubierto la peculiaridad de mirar atrás 5 minutos antes
TwiNight
No. Pero ya sé que los cuantificadores no están permitidos en retrospectiva en PCRE. Creo que mirar hacia atrás es mucho mejor que eso.
jimmy23013
@ MartinBüttner Entonces, para confirmar, ¿los lookbehinds realmente coinciden de atrás hacia adelante?
TwiNight
5

Sabor Python (200127 bytes) [agrietado]

Solo para que podamos (con suerte) ver algo durar un día, es hora de sacar las armas grandes :)

El problema con la ruta 3-SAT y Hamiltoniana es que la complejidad está en términos del tamaño de la clave. Esta vez he elegido algo que depende de la expresión regular, en lugar de la clave.

Aquí está: regex . También puede encontrar este archivo útil. (No te preocupes, no he escondido nada extraño allí esta vez;))

Utilicé RegexPlanet para probar este, fue difícil encontrar algo que no se agotara : /. Para verificar si hubo una coincidencia, vea si su cadena aparece debajo findall().

¡Buena suerte!


La expresión regular es simplemente "encontrar una cadena de longitud 64 que aparece como una subsecuencia común en un conjunto de 20 cadenas de longitud 5000". Sin embargo, había demasiadas soluciones, probablemente.

Sp3000
fuente
55
Partido: d,mE~JZ0,_:3kBdLdgBSzJ!@MLrrAgKsf@Pl35N9bxsIf@ReVU>:YDg`d1MjL@_-. No partido:{ line|fold -w1 >filea; while line >filec; do fold -w1 <filec >fileb; diff -d --old-line-format= --new-line-format= --unchanged-line-format=%L filea fileb >filec;mv filec filea;done;cat filea;} <file1|tr -d $'\n'|head -c64;echo
jimmy23013
Jajaja, estoy vencido - Supongo que las secuencias fueron demasiado largas y hubo demasiadas soluciones
Sp3000
@ user23013 Eso suena mucho, pero en realidad no es tan malo, ya que hay 5437589409196755010929519821645784067024309122301926366910354757626905801389085035074667925844349168139762829668081680641 diferentes cadenas de 77 caracteres disponibles.
Martin Ender
Pues me equivoco. No solo hay soluciones 718406958841. Y mi script tiene un error, por lo que ignoró el último patrón. Pero la subsecuencia común de los primeros 19 patrones resultó ser también una subsecuencia del último
jimmy23013 del
@ MartinBüttner Quiero decir que no sé exactamente cuántas soluciones hay, y ese número está equivocado. Su subsecuencia común más larga tiene 718406958841 (valor corregido: 97082021465) subsecuencias de longitud 64. Pero hay otras CS que no son subsecuencias de LCS.
jimmy23013
5

Python, 145475 bytes [agrietado]

Gracias a Wumpus por enseñarme la importancia de revisar nuestros índices :)

El mismo trato que la última solución, solo espero que no se rompa esta vez. Regex sin formato: http://pastebin.com/MReS2R1k

EDITAR: No estaba roto, pero aparentemente todavía era demasiado fácil. Al menos no se resolvió "al instante";)

nneonneo
fuente
44
No partido: 1040060321170122554027333022674205250442151362365165773421664173556667110413375720720711725045122733213710556062114131057357354554245723416516004761215632214223735570625116160162051407026445600345370604702671021412723536217011007021752560474402200436670402Partido:minisat2hoursCPU
Ayup Me tienes. Eso fue bastante rápido. Tal vez tengo que sacar mi regex de 1GB después de todo ...
#
5

Implementación de Java Pattern / Oracle (75 caracteres / 150 bytes UTF-16) [agrietado]

(Nombre en clave: Bad Coffee 101)

Este es el Patternobjeto, con CANON_EQbandera, que se utilizará con matches()(ancla implícita):

Pattern.compile("(\\Q\u1EBF\\\\E)?+[\\w&&[\\p{L1}]\\p{Z}]+|\\1[\uD835\uDC00-\uD835\uDC33]{1927027271663633,2254527117918231}", Pattern.CANON_EQ)

Prueba tu clave aquí en ideone

Se garantiza que habrá una clave. Lea el spoiler si desea alguna confirmación.

Como puede ver, no es una expresión regular normal. Sin embargo, se ejecuta sin Exceptionla versión 1.6.0u37 de Java de Java y la versión 1.7.0u11 de Java, y también debería ejecutarse para la versión más actual en el momento de la escritura.

Esto hace uso de 4 errores: CANON_EQretención de texto capturado de intento fallido, pérdida de clase de caracteres y desbordamiento del cuantificador.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
fuente
44
Partido : "(?:e\u0302\u0301\\|\u00ea\u0301\\|\u1ebf\\|\u00ea\\\u0301|e\u0302\\\u0301|\u00ea\\\u0301|\u00ea\u0301\\|\u1ebf\\|e\\\u0302\u0301)\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00"(forma citado). No coincidencia : JavaRegexSoBuggy. ideone for match: ideone.com/DEesdk
nneonneo
Errores encontrados: (1) CANON_EQexpande los caracteres precompuestos en alternancias internas, que se rompen hilarantemente en el interior \Q\E; (2) las longitudes de repetición se truncan a 32 bits; (3) está ocurriendo algo extraño con el clasificador de clase de personaje que hace que se salte la alternancia (no se dio cuenta de qué era exactamente el error).
nneonneo
@nneonneo: Tu explicación es correcta. Pero olvidaste el \1error de backref . Y sí, hay un error en la clase de personaje. ¿Cómo resolviste todo esto en menos de 2 horas?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
Empecé a trabajar en eso hace 20 minutos. Hiciste bastante obvio qué partes del problema enfatizaban qué errores (porque cada error estaba básicamente en su propio grupo), así que descubrí cómo satisfacer cada parte de forma independiente y luego los combiné. Tuve la suerte de no tener que averiguar qué estaba haciendo la clase de personajes. (También tuve mucha suerte de que Java escupe el patrón interno "expandido" cuando tienes un error de sintaxis :)
nneonneo
¡También! No creo que la retención de texto capturado sea necesariamente un error. Así parece ser cómo funcionan los cuantificadores posesivos. (También es una propiedad bastante útil para ciertos hacks de
expresiones
5

Sabor .NET, 17.372 bytes [agrietado]

Esta sigue siendo una versión fácil. Necesita más optimización para trabajar con cadenas más largas.

La expresión regular está aquí: http://pastebin.com/YPE4zyBB

Sin golf: http://pastebin.com/PLJp0KhF

Probado en RegexStorm y este blog y RegExLib (con todas las opciones sin marcar ).

La solución a esta expresión regular es la factorización de 5122188685368916735780446744735847888756487271329 = 2147852126374329492975359 * 2384795779221263457172831, con el resultado codificado en base 289, el menos significativo primero.

Cada dígito se divide en primer lugar en dos números base 17 para hacer los cálculos más rápidos. Así también se codifica el producto en la expresión regular.

Cada par de dígitos en los dos números se multiplica en el grupo de captura a0a a38. Cada uno de ellos es un dígito del producto. La posición actual se mantiene por py q. Y el acarreo se procesa después de la multiplicación, mientras se compara el producto.

Está en la base 289 porque fue diseñado para aceptar dos números de 1024 bits, que tiene 128 dígitos de base 256 cada uno, y no pensé en eliminar la coma, por lo que la cadena completa con base 256 tendría 257 caracteres.

La versión de 1536 bits está aquí . Acepta dos números de 768 bits. Los números en esta versión fácil cada uno tiene solo 81 bits.

jimmy23013
fuente
2
Partido : Ľê¯6Aĝ4aþĀ,lŃŝĿBİŢŞĩï(escapado:) \u013d\xea\xaf6A\u011d4a\xfe\u0100,l\u0143\u015d\u013fB\u0130\u0162\u015e\u0129\xef. No partido :VeryNiceMultiplier
nneonneo
4

Sabor ECMAScript, 30 bytes [agrietado]

^((?![\t- ]|[^\s])(.)(?!\2))+$

Aquí hay uno bastante simple para que los ladrones quiebren. Conceptualmente no es demasiado difícil, pero puede requerir un poco de investigación (o secuencias de comandos). No tengo la intención de enumerarme en la tabla de clasificación, pero si alguien lo descifra dentro de las 72 horas, esto contará para la puntuación de su ladrón.

Probado en Regex101 y RegExr con Chrome.

Bueno, eso fue rápido!

Se suponía que la expresión regular coincidía con cualquier cadena que constara de caracteres de espacio en blanco distintos de ASCII. Sin embargo, olvidé un .*antes del \2, por lo que en realidad coincide con cualquier cadena de espacio en blanco que no sea ASCII, que no contenga dos caracteres idénticos consecutivos. Hay 18 de estos caracteres en el rango Unicode hasta el punto de código 0xFFFF. La coincidencia publicada por user23013 es una de esas cadenas, que consta de 16 caracteres.

Martin Ender
fuente
1
Partido (base64):, wqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBnw==No partido:aaaabaaacaaadaaa
jimmy23013
No es distinto sino que solo se alterna, con solo dos caracteres distintos.
jimmy23013
@ user23013 Maldición, olvidé una .*en el futuro. Buena atrapada. Debería haber probado más a fondo.
Martin Ender
4

Con sabor a rubí , 24 bytes [agrietado]

^(?!.*(.+)\1)([\[\\\]]){256}$
histocrat
fuente
Incluya un enlace a un probador donde esté funcionando la clave deseada (como rubular.com ). (También, consejo profesional de ofuscación / golf: si usa PCRE en su lugar, la clase de personaje podría escribirse como []\\[];))
Martin Ender
Enlace agregado. Sospecho que Wumpus lo ha descifrado, podría probarlo con un enlace permanente a rubular.com
histocrat
2
No coincidencia: soylentgreenispeople. Coincidencia disponible en rubular.com/r/TCqjcaGsU1 no publicado aquí debido a cómo el sistema de comentarios maneja palabras largas.
@ WumpusQ.Wumbley ¡Genial! Si incluye la no coincidencia en el mismo comentario, podemos limpiar todo el desorden por encima de esto.
Martin Ender
4

PHP, 168 bytes [descifrado por nneonneo ]

^((?![!?$]*[^!?$]))?(?:[^!]\2?+(?=(!*)(\\\3?+.(?!\3)))){4}(?(1)|Ha! No one will ever get this one...)|(?!(?1))\Q\1?!($!?)?\E\1?!($!?)?(?<!.{12})\Q(?=(?1))\E(?=(?1))!\?$

Aquí hay una demostración de expresiones regulares .

PD: este juego es difícil.

Unihedron
fuente
2
Partido : \1?!($!?)?!(?=(?1))!?. No partido :IncrementalRegexTestingWorks
nneonneo
@nneonneo Ah, eres demasiado bueno;)
Unihedron
4

PCRE (1043 bytes) [agrietado]

Después de que las expresiones regulares generadas aleatoriamente me fallaron (las ideas eran buenas, pero no pude generar instancias de problemas adecuadas), decidí crear esta a mano. Yo lo llamo "Un montón de reglas para satisfacer".

^(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)(?!^\(.*)(?!.*\(.{250}\).*)(?=.*\[.{250}\].*)(?=.*\{.{250}\}.*)(?=.*\[.\(\).\{\}.\].*)(?=.*\}...\[...\[...\]...\]...\{.*)(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)(?=.*\[\{\{\[\(\{.*)(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)(?!.*\(\{\(\(.*)(?!.*\(\)\[\].*)(?=(.*?\].*?\)){15,}.*)(?=(.*\[.*\(.*\{){5,9}.*)(?=.*\({3}.{105}\[{3}.{105}[^}{].*)(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)(?!.*\(\(.{178}\])(?=(.*\[..\]){8,10}.*)(?!(.*\([^\(\)]{5}\(){4,}.*).{63}(.{6}).{130}\11.{51}$

Y ampliado:

^
(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)
(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)
(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)
(?!^\(.*)
(?!.*\(.{250}\).*)
(?=.*\[.{250}\].*)
(?=.*\{.{250}\}.*)
(?=.*\[.\(\).\{\}.\].*)
(?=.*\}...\[...\[...\]...\]...\{.*)
(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)
(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)
(?=.*\[\{\{\[\(\{.*)
(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)
(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)
(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)
(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)
(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)
(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)
(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)
(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)
(?!.*\(\{\(\(.*)
(?!.*\(\)\[\].*)
(?=(.*?\].*?\)){15,}.*)
(?=(.*\[.*\(.*\{){5,9}.*)
(?=.*\({3}.{105}\[{3}.{105}[^}{].*)
(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)
(?!.*\(\(.{178}\])
(?=(.*\[..\]){8,10}.*)
(?!(.*\([^\(\)]{5}\(){4,}.*)
.{63}(.{6}).{130}\11.{51}
$

Probado en Regex101 : dependiendo de su computadora, puede necesitar aumentar el tiempo máximo de ejecución.


Esta expresión regular codifica un montón de reglas que solo deben cumplirse. Cualquier solución servirá, es solo encontrar una.

  • Las primeras tres reglas básicas requieren que, por separado, todos los ([{corchetes deban equilibrarse dentro de la clave.
  • La mayoría de las expresiones requieren que cierta "forma" deba estar o no en la clave. Por ejemplo, la octava fila requiere algo de la forma [.(.).].
  • Reglas como (?=(.*\[.*\(.*\{){5,9}.*), por ejemplo, requieren que la [({alternancia ocurra al menos 5 veces. Tenga en cuenta que esta línea en particular tiene errores en muchos niveles, sin querer.
  • La referencia inversa \11requiere que una subcadena de seis caracteres aparezca dos veces en posiciones particulares.

Sp3000
fuente
2
Partido : [((({.[.[](){{}{].{.(({){(.[]()....}}].{{[[....).[..]()(}..[..]([....(([{((({).](){.{}{}{}....}[[()[}}][{{[({[[[.]]}()]].{}.]{[..]{.[]]}}}())))(())[(.].{[.{[[..[()].()}{{.[...[}{.]..)]...{.])))).}}..([......{.....[.]}[...}.{[.}...}})}.))).]}}]]]}]]].)]]..}. No coincidencia: WhatANastySetOfRulesYouHave.
nneonneo
Aumenté el tiempo de ejecución a 50 segundos. Por cierto, si solo usa los cuantificadores adecuados no codiciosos (?=(.*\[.*\(.*\{){5,9}.*), entonces no necesitará aumentar el tiempo máximo de ejecución (mismo resultado): las coincidencias serán instantáneas.
nneonneo
@nneonneo Ahaha sí, me di cuenta de eso después de publicar. ¿Puede publicar, digamos, un enlace pastebin para su clave? Los comentarios de SE parecen estar actuando de nuevo
Sp3000
@nneonneo Además, si tiene tantos puntos en su solución, claramente no tenía suficientes reglas: P
Sp3000
2
Aquí hay un enlace regex101 con mi solución visible: regex101.com/r/gP2aX7/1
nneonneo
4

Sabor .NET (7563 bytes) [agrietado]

Inspirado en la idea de @ user23013

^(?:(?=1(?<1>){5632})|(?=0)).(?:(?=1(?<1>){79361})|(?=0)).(?:(?=1(?<1>){188421})|(?=0)).(?:(?=1(?<1>){164870})|(?=0)).(?:(?=1(?<1>){63496})|(?=0)).(?:(?=1(?<1>){116233})|(?=0)).(?:(?=1(?<1>){112138})|(?=0)).(?:(?=1(?<1>){47447})|(?=0)).(?:(?=1(?<1>){85005})|(?=0)).(?:(?=1(?<1>){17936})|(?=0)).(?:(?=1(?<1>){108053})|(?=0)).(?:(?=1(?<1>){88599})|(?=0)).(?:(?=1(?<1>){91672})|(?=0)).(?:(?=1(?<1>){178716})|(?=0)).(?:(?=1(?<1>){199710})|(?=0)).(?:(?=1(?<1>){166661})|(?=0)).(?:(?=1(?<1>){190496})|(?=0)).(?:(?=1(?<1>){184494})|(?=0)).(?:(?=1(?<1>){199203})|(?=0)).(?:(?=1(?<1>){116778})|(?=0)).(?:(?=1(?<1>){78891})|(?=0)).(?:(?=1(?<1>){192556})|(?=0)).(?:(?=1(?<1>){24995})|(?=0)).(?:(?=1(?<1>){1071})|(?=0)).(?:(?=1(?<1>){192561})|(?=0)).(?:(?=1(?<1>){108082})|(?=0)).(?:(?=1(?<1>){1593})|(?=0)).(?:(?=1(?<1>){26967})|(?=0)).(?:(?=1(?<1>){197983})|(?=0)).(?:(?=1(?<1>){97034})|(?=0)).(?:(?=1(?<1>){86965})|(?=0)).(?:(?=1(?<1>){60480})|(?=0)).(?:(?=1(?<1>){149571})|(?=0)).(?:(?=1(?<1>){100932})|(?=0)).(?:(?=1(?<1>){40519})|(?=0)).(?:(?=1(?<1>){173492})|(?=0)).(?:(?=1(?<1>){80972})|(?=0)).(?:(?=1(?<1>){115790})|(?=0)).(?:(?=1(?<1>){29265})|(?=0)).(?:(?=1(?<1>){91730})|(?=0)).(?:(?=1(?<1>){173140})|(?=0)).(?:(?=1(?<1>){52821})|(?=0)).(?:(?=1(?<1>){176726})|(?=0)).(?:(?=1(?<1>){170211})|(?=0)).(?:(?=1(?<1>){150105})|(?=0)).(?:(?=1(?<1>){23131})|(?=0)).(?:(?=1(?<1>){81503})|(?=0)).(?:(?=1(?<1>){77412})|(?=0)).(?:(?=1(?<1>){106086})|(?=0)).(?:(?=1(?<1>){4284})|(?=0)).(?:(?=1(?<1>){142610})|(?=0)).(?:(?=1(?<1>){167534})|(?=0)).(?:(?=1(?<1>){190577})|(?=0)).(?:(?=1(?<1>){147731})|(?=0)).(?:(?=1(?<1>){133748})|(?=0)).(?:(?=1(?<1>){194750})|(?=0)).(?:(?=1(?<1>){49257})|(?=0)).(?:(?=1(?<1>){49274})|(?=0)).(?:(?=1(?<1>){120767})|(?=0)).(?:(?=1(?<1>){172668})|(?=0)).(?:(?=1(?<1>){24703})|(?=0)).(?:(?=1(?<1>){108160})|(?=0)).(?:(?=1(?<1>){60546})|(?=0)).(?:(?=1(?<1>){56963})|(?=0)).(?:(?=1(?<1>){30340})|(?=0)).(?:(?=1(?<1>){95368})|(?=0)).(?:(?=1(?<1>){59530})|(?=0)).(?:(?=1(?<1>){53388})|(?=0)).(?:(?=1(?<1>){14477})|(?=0)).(?:(?=1(?<1>){28302})|(?=0)).(?:(?=1(?<1>){182927})|(?=0)).(?:(?=1(?<1>){59024})|(?=0)).(?:(?=1(?<1>){146200})|(?=0)).(?:(?=1(?<1>){153746})|(?=0)).(?:(?=1(?<1>){39571})|(?=0)).(?:(?=1(?<1>){134293})|(?=0)).(?:(?=1(?<1>){158362})|(?=0)).(?:(?=1(?<1>){170139})|(?=0)).(?:(?=1(?<1>){182940})|(?=0)).(?:(?=1(?<1>){7327})|(?=0)).(?:(?=1(?<1>){143525})|(?=0)).(?:(?=1(?<1>){119464})|(?=0)).(?:(?=1(?<1>){82090})|(?=0)).(?:(?=1(?<1>){170667})|(?=0)).(?:(?=1(?<1>){49522})|(?=0)).(?:(?=1(?<1>){69806})|(?=0)).(?:(?=1(?<1>){15535})|(?=0)).(?:(?=1(?<1>){16049})|(?=0)).(?:(?=1(?<1>){163358})|(?=0)).(?:(?=1(?<1>){181876})|(?=0)).(?:(?=1(?<1>){58044})|(?=0)).(?:(?=1(?<1>){16062})|(?=0)).(?:(?=1(?<1>){39616})|(?=0)).(?:(?=1(?<1>){31425})|(?=0)).(?:(?=1(?<1>){94404})|(?=0)).(?:(?=1(?<1>){86848})|(?=0)).(?:(?=1(?<1>){16589})|(?=0)).(?:(?=1(?<1>){195280})|(?=0)).(?:(?=1(?<1>){199377})|(?=0)).(?:(?=1(?<1>){43731})|(?=0)).(?:(?=1(?<1>){67534})|(?=0)).(?:(?=1(?<1>){106198})|(?=0)).(?:(?=1(?<1>){54999})|(?=0)).(?:(?=1(?<1>){52952})|(?=0)).(?:(?=1(?<1>){125828})|(?=0)).(?:(?=1(?<1>){169691})|(?=0)).(?:(?=1(?<1>){184542})|(?=0)).(?:(?=1(?<1>){177888})|(?=0)).(?:(?=1(?<1>){43233})|(?=0)).(?:(?=1(?<1>){127203})|(?=0)).(?:(?=1(?<1>){116518})|(?=0)).(?:(?=1(?<1>){117990})|(?=0)).(?:(?=1(?<1>){67815})|(?=0)).(?:(?=1(?<1>){62202})|(?=0)).(?:(?=1(?<1>){165611})|(?=0)).(?:(?=1(?<1>){197356})|(?=0)).(?:(?=1(?<1>){29933})|(?=0)).(?:(?=1(?<1>){90862})|(?=0)).(?:(?=1(?<1>){90863})|(?=0)).(?:(?=1(?<1>){149232})|(?=0)).(?:(?=1(?<1>){61681})|(?=0)).(?:(?=1(?<1>){137970})|(?=0)).(?:(?=1(?<1>){90357})|(?=0)).(?:(?=1(?<1>){47351})|(?=0)).(?:(?=1(?<1>){172509})|(?=0)).(?:(?=1(?<1>){78293})|(?=0)).(?:(?=1(?<1>){66303})|(?=0)).(?:(?=1(?<1>){66262})|(?=0)).(?:(?=1(?<1>){158471})|(?=0)).(?:(?=1(?<1>){5676})|(?=0)).(?:(?=1(?<1>){127242})|(?=0)).(?:(?=1(?<1>){51979})|(?=0)).(?:(?=1(?<1>){162060})|(?=0)).(?:(?=1(?<1>){27405})|(?=0)).(?:(?=1(?<1>){153874})|(?=0)).(?:(?=1(?<1>){150291})|(?=0)).(?:(?=1(?<1>){1814})|(?=0)).(?:(?=1(?<1>){193815})|(?=0)).(?:(?=1(?<1>){82200})|(?=0)).(?:(?=1(?<1>){59161})|(?=0)).(?:(?=1(?<1>){78620})|(?=0)).(?:(?=1(?<1>){123678})|(?=0)).(?:(?=1(?<1>){147232})|(?=0)).(?:(?=1(?<1>){71457})|(?=0)).(?:(?=1(?<1>){118562})|(?=0)).(?:(?=1(?<1>){129830})|(?=0)).(?:(?=1(?<1>){161841})|(?=0)).(?:(?=1(?<1>){60295})|(?=0)).(?:(?=1(?<1>){165426})|(?=0)).(?:(?=1(?<1>){107485})|(?=0)).(?:(?=1(?<1>){171828})|(?=0)).(?:(?=1(?<1>){166200})|(?=0)).(?:(?=1(?<1>){35124})|(?=0)).(?:(?=1(?<1>){160573})|(?=0)).(?:(?=1(?<1>){7486})|(?=0)).(?:(?=1(?<1>){169279})|(?=0)).(?:(?=1(?<1>){151360})|(?=0)).(?:(?=1(?<1>){6978})|(?=0)).(?:(?=1(?<1>){136003})|(?=0)).(?:(?=1(?<1>){56133})|(?=0)).(?:(?=1(?<1>){8520})|(?=0)).(?:(?=1(?<1>){87436})|(?=0)).(?:(?=1(?<1>){57162})|(?=0)).(?:(?=1(?<1>){197965})|(?=0)).(?:(?=1(?<1>){145230})|(?=0)).(?:(?=1(?<1>){95459})|(?=0)).(?:(?=1(?<1>){180564})|(?=0)).(?:(?=1(?<1>){157850})|(?=0)).(?:(?=1(?<1>){109399})|(?=0)).(?:(?=1(?<1>){191832})|(?=0)).(?:(?=1(?<1>){110223})|(?=0)).(?:(?=1(?<1>){75102})|(?=0)).(?:(?=1(?<1>){140639})|(?=0)).(?:(?=1(?<1>){49504})|(?=0)).(?:(?=1(?<1>){197987})|(?=0)).(?:(?=1(?<1>){52744})|(?=0)).(?:(?=1(?<1>){96615})|(?=0)).(?:(?=1(?<1>){13672})|(?=0)).(?:(?=1(?<1>){73068})|(?=0)).(?:(?=1(?<1>){104814})|(?=0)).(?:(?=1(?<1>){66929})|(?=0)).(?:(?=1(?<1>){23410})|(?=0)).(?:(?=1(?<1>){122686})|(?=0)).(?:(?=1(?<1>){44918})|(?=0)).(?:(?=1(?<1>){101752})|(?=0)).(?:(?=1(?<1>){3961})|(?=0)).(?:(?=1(?<1>){31807})|(?=0)).(?:(?=1(?<1>){54933})|(?=0)).(?:(?=1(?<1>){140096})|(?=0)).(?:(?=1(?<1>){49026})|(?=0)).(?:(?=1(?<1>){5507})|(?=0)).(?:(?=1(?<1>){96132})|(?=0)).(?:(?=1(?<1>){167303})|(?=0)).(?:(?=1(?<1>){57877})|(?=0)).(?:(?=1(?<1>){88461})|(?=0)).(?:(?=1(?<1>){111853})|(?=0)).(?:(?=1(?<1>){126531})|(?=0)).(?:(?=1(?<1>){110998})|(?=0)).(?:(?=1(?<1>){7575})|(?=0)).(?:(?=1(?<1>){7064})|(?=0)).(?:(?=1(?<1>){59289})|(?=0)).(?:(?=1(?<1>){122203})|(?=0)).(?:(?=1(?<1>){175005})|(?=0)).(?:(?=1(?<1>){28025})|(?=0)).(?:(?=1(?<1>){49057})|(?=0)).(?:(?=1(?<1>){6373})|(?=0)).(?:(?=1(?<1>){50084})|(?=0)).(?:(?=1(?<1>){70565})|(?=0)).(?:(?=1(?<1>){75178})|(?=0)).(?:(?=1(?<1>){142763})|(?=0)).(?:(?=1(?<1>){56237})|(?=0)).(?:(?=1(?<1>){32176})|(?=0)).(?:(?=1(?<1>){113073})|(?=0)).(?:(?=1(?<1>){149939})|(?=0)).(?:(?=1(?<1>){16308})|(?=0)).(?:(?=1(?<1>){12725})|(?=0)).(?:(?=1(?<1>){75190})|(?=0)).(?:(?=1(?<1>){54711})|(?=0)).(?:(?=1(?<1>){180664})|(?=0)).(?:(?=1(?<1>){68540})|(?=0)).(?:(?=1(?<1>){93117})|(?=0)).(?:(?=1(?<1>){161781})|(?=0)).(?:(?=1(?<1>){15808})|(?=0)).(?:(?=1(?<1>){130814})|(?=0)).(?:(?=1(?<1>){162379})|(?=0)).(?:(?=1(?<1>){80836})|(?=0)).(?:(?=1(?<1>){149943})|(?=0)).(?:(?=1(?<1>){16841})|(?=0)).(?:(?=1(?<1>){149452})|(?=0)).(?:(?=1(?<1>){182733})|(?=0)).(?:(?=1(?<1>){56270})|(?=0)).(?:(?=1(?<1>){163792})|(?=0)).(?:(?=1(?<1>){34770})|(?=0)).(?:(?=1(?<1>){101843})|(?=0)).(?:(?=1(?<1>){199124})|(?=0)).(?:(?=1(?<1>){129493})|(?=0)).(?:(?=1(?<1>){43990})|(?=0)).(?:(?=1(?<1>){113112})|(?=0)).(?:(?=1(?<1>){71129})|(?=0)).(?:(?=1(?<1>){61402})|(?=0)).(?:(?=1(?<1>){145852})|(?=0)).(?:(?=1(?<1>){98781})|(?=0)).(?:(?=1(?<1>){141790})|(?=0)).(?:(?=1(?<1>){163235})|(?=0)).(?:(?=1(?<1>){110566})|(?=0)).(?:(?=1(?<1>){117737})|(?=0)).(?:(?=1(?<1>){67050})|(?=0)).(?:(?=1(?<1>){68075})|(?=0)).(?:(?=1(?<1>){124047})|(?=0)).(?:(?=1(?<1>){181587})|(?=0)).(?:(?=1(?<1>){125429})|(?=0)).(?:(?=1(?<1>){112118})|(?=0)).(?:(?=1(?<1>){196088})|(?=0)).(?:(?=1(?<1>){25082})|(?=0)).(?:(?=1(?<1>){178684})|(?=0)).(?:(?=1(?<1>){13822})|(?=0)).(?<-1>){10094986}(?(1)(?!))$

¡Simplemente no podemos tener suficientes problemas de NP completo! Aquí está la versión ampliada:

^
(?:(?=1(?<1>){5632})|(?=0)).
(?:(?=1(?<1>){79361})|(?=0)).
(?:(?=1(?<1>){188421})|(?=0)).
(?:(?=1(?<1>){164870})|(?=0)).
(?:(?=1(?<1>){63496})|(?=0)).
(?:(?=1(?<1>){116233})|(?=0)).
(?:(?=1(?<1>){112138})|(?=0)).
(?:(?=1(?<1>){47447})|(?=0)).
(?:(?=1(?<1>){85005})|(?=0)).
(?:(?=1(?<1>){17936})|(?=0)).
(?:(?=1(?<1>){108053})|(?=0)).
(?:(?=1(?<1>){88599})|(?=0)).
(?:(?=1(?<1>){91672})|(?=0)).
(?:(?=1(?<1>){178716})|(?=0)).
(?:(?=1(?<1>){199710})|(?=0)).
(?:(?=1(?<1>){166661})|(?=0)).
(?:(?=1(?<1>){190496})|(?=0)).
(?:(?=1(?<1>){184494})|(?=0)).
(?:(?=1(?<1>){199203})|(?=0)).
(?:(?=1(?<1>){116778})|(?=0)).
(?:(?=1(?<1>){78891})|(?=0)).
(?:(?=1(?<1>){192556})|(?=0)).
(?:(?=1(?<1>){24995})|(?=0)).
(?:(?=1(?<1>){1071})|(?=0)).
(?:(?=1(?<1>){192561})|(?=0)).
(?:(?=1(?<1>){108082})|(?=0)).
(?:(?=1(?<1>){1593})|(?=0)).
(?:(?=1(?<1>){26967})|(?=0)).
(?:(?=1(?<1>){197983})|(?=0)).
(?:(?=1(?<1>){97034})|(?=0)).
(?:(?=1(?<1>){86965})|(?=0)).
(?:(?=1(?<1>){60480})|(?=0)).
(?:(?=1(?<1>){149571})|(?=0)).
(?:(?=1(?<1>){100932})|(?=0)).
(?:(?=1(?<1>){40519})|(?=0)).
(?:(?=1(?<1>){173492})|(?=0)).
(?:(?=1(?<1>){80972})|(?=0)).
(?:(?=1(?<1>){115790})|(?=0)).
(?:(?=1(?<1>){29265})|(?=0)).
(?:(?=1(?<1>){91730})|(?=0)).
(?:(?=1(?<1>){173140})|(?=0)).
(?:(?=1(?<1>){52821})|(?=0)).
(?:(?=1(?<1>){176726})|(?=0)).
(?:(?=1(?<1>){170211})|(?=0)).
(?:(?=1(?<1>){150105})|(?=0)).
(?:(?=1(?<1>){23131})|(?=0)).
(?:(?=1(?<1>){81503})|(?=0)).
(?:(?=1(?<1>){77412})|(?=0)).
(?:(?=1(?<1>){106086})|(?=0)).
(?:(?=1(?<1>){4284})|(?=0)).
(?:(?=1(?<1>){142610})|(?=0)).
(?:(?=1(?<1>){167534})|(?=0)).
(?:(?=1(?<1>){190577})|(?=0)).
(?:(?=1(?<1>){147731})|(?=0)).
(?:(?=1(?<1>){133748})|(?=0)).
(?:(?=1(?<1>){194750})|(?=0)).
(?:(?=1(?<1>){49257})|(?=0)).
(?:(?=1(?<1>){49274})|(?=0)).
(?:(?=1(?<1>){120767})|(?=0)).
(?:(?=1(?<1>){172668})|(?=0)).
(?:(?=1(?<1>){24703})|(?=0)).
(?:(?=1(?<1>){108160})|(?=0)).
(?:(?=1(?<1>){60546})|(?=0)).
(?:(?=1(?<1>){56963})|(?=0)).
(?:(?=1(?<1>){30340})|(?=0)).
(?:(?=1(?<1>){95368})|(?=0)).
(?:(?=1(?<1>){59530})|(?=0)).
(?:(?=1(?<1>){53388})|(?=0)).
(?:(?=1(?<1>){14477})|(?=0)).
(?:(?=1(?<1>){28302})|(?=0)).
(?:(?=1(?<1>){182927})|(?=0)).
(?:(?=1(?<1>){59024})|(?=0)).
(?:(?=1(?<1>){146200})|(?=0)).
(?:(?=1(?<1>){153746})|(?=0)).
(?:(?=1(?<1>){39571})|(?=0)).
(?:(?=1(?<1>){134293})|(?=0)).
(?:(?=1(?<1>){158362})|(?=0)).
(?:(?=1(?<1>){170139})|(?=0)).
(?:(?=1(?<1>){182940})|(?=0)).
(?:(?=1(?<1>){7327})|(?=0)).
(?:(?=1(?<1>){143525})|(?=0)).
(?:(?=1(?<1>){119464})|(?=0)).
(?:(?=1(?<1>){82090})|(?=0)).
(?:(?=1(?<1>){170667})|(?=0)).
(?:(?=1(?<1>){49522})|(?=0)).
(?:(?=1(?<1>){69806})|(?=0)).
(?:(?=1(?<1>){15535})|(?=0)).
(?:(?=1(?<1>){16049})|(?=0)).
(?:(?=1(?<1>){163358})|(?=0)).
(?:(?=1(?<1>){181876})|(?=0)).
(?:(?=1(?<1>){58044})|(?=0)).
(?:(?=1(?<1>){16062})|(?=0)).
(?:(?=1(?<1>){39616})|(?=0)).
(?:(?=1(?<1>){31425})|(?=0)).
(?:(?=1(?<1>){94404})|(?=0)).
(?:(?=1(?<1>){86848})|(?=0)).
(?:(?=1(?<1>){16589})|(?=0)).
(?:(?=1(?<1>){195280})|(?=0)).
(?:(?=1(?<1>){199377})|(?=0)).
(?:(?=1(?<1>){43731})|(?=0)).
(?:(?=1(?<1>){67534})|(?=0)).
(?:(?=1(?<1>){106198})|(?=0)).
(?:(?=1(?<1>){54999})|(?=0)).
(?:(?=1(?<1>){52952})|(?=0)).
(?:(?=1(?<1>){125828})|(?=0)).
(?:(?=1(?<1>){169691})|(?=0)).
(?:(?=1(?<1>){184542})|(?=0)).
(?:(?=1(?<1>){177888})|(?=0)).
(?:(?=1(?<1>){43233})|(?=0)).
(?:(?=1(?<1>){127203})|(?=0)).
(?:(?=1(?<1>){116518})|(?=0)).
(?:(?=1(?<1>){117990})|(?=0)).
(?:(?=1(?<1>){67815})|(?=0)).
(?:(?=1(?<1>){62202})|(?=0)).
(?:(?=1(?<1>){165611})|(?=0)).
(?:(?=1(?<1>){197356})|(?=0)).
(?:(?=1(?<1>){29933})|(?=0)).
(?:(?=1(?<1>){90862})|(?=0)).
(?:(?=1(?<1>){90863})|(?=0)).
(?:(?=1(?<1>){149232})|(?=0)).
(?:(?=1(?<1>){61681})|(?=0)).
(?:(?=1(?<1>){137970})|(?=0)).
(?:(?=1(?<1>){90357})|(?=0)).
(?:(?=1(?<1>){47351})|(?=0)).
(?:(?=1(?<1>){172509})|(?=0)).
(?:(?=1(?<1>){78293})|(?=0)).
(?:(?=1(?<1>){66303})|(?=0)).
(?:(?=1(?<1>){66262})|(?=0)).
(?:(?=1(?<1>){158471})|(?=0)).
(?:(?=1(?<1>){5676})|(?=0)).
(?:(?=1(?<1>){127242})|(?=0)).
(?:(?=1(?<1>){51979})|(?=0)).
(?:(?=1(?<1>){162060})|(?=0)).
(?:(?=1(?<1>){27405})|(?=0)).
(?:(?=1(?<1>){153874})|(?=0)).
(?:(?=1(?<1>){150291})|(?=0)).
(?:(?=1(?<1>){1814})|(?=0)).
(?:(?=1(?<1>){193815})|(?=0)).
(?:(?=1(?<1>){82200})|(?=0)).
(?:(?=1(?<1>){59161})|(?=0)).
(?:(?=1(?<1>){78620})|(?=0)).
(?:(?=1(?<1>){123678})|(?=0)).
(?:(?=1(?<1>){147232})|(?=0)).
(?:(?=1(?<1>){71457})|(?=0)).
(?:(?=1(?<1>){118562})|(?=0)).
(?:(?=1(?<1>){129830})|(?=0)).
(?:(?=1(?<1>){161841})|(?=0)).
(?:(?=1(?<1>){60295})|(?=0)).
(?:(?=1(?<1>){165426})|(?=0)).
(?:(?=1(?<1>){107485})|(?=0)).
(?:(?=1(?<1>){171828})|(?=0)).
(?:(?=1(?<1>){166200})|(?=0)).
(?:(?=1(?<1>){35124})|(?=0)).
(?:(?=1(?<1>){160573})|(?=0)).
(?:(?=1(?<1>){7486})|(?=0)).
(?:(?=1(?<1>){169279})|(?=0)).
(?:(?=1(?<1>){151360})|(?=0)).
(?:(?=1(?<1>){6978})|(?=0)).
(?:(?=1(?<1>){136003})|(?=0)).
(?:(?=1(?<1>){56133})|(?=0)).
(?:(?=1(?<1>){8520})|(?=0)).
(?:(?=1(?<1>){87436})|(?=0)).
(?:(?=1(?<1>){57162})|(?=0)).
(?:(?=1(?<1>){197965})|(?=0)).
(?:(?=1(?<1>){145230})|(?=0)).
(?:(?=1(?<1>){95459})|(?=0)).
(?:(?=1(?<1>){180564})|(?=0)).
(?:(?=1(?<1>){157850})|(?=0)).
(?:(?=1(?<1>){109399})|(?=0)).
(?:(?=1(?<1>){191832})|(?=0)).
(?:(?=1(?<1>){110223})|(?=0)).
(?:(?=1(?<1>){75102})|(?=0)).
(?:(?=1(?<1>){140639})|(?=0)).
(?:(?=1(?<1>){49504})|(?=0)).
(?:(?=1(?<1>){197987})|(?=0)).
(?:(?=1(?<1>){52744})|(?=0)).
(?:(?=1(?<1>){96615})|(?=0)).
(?:(?=1(?<1>){13672})|(?=0)).
(?:(?=1(?<1>){73068})|(?=0)).
(?:(?=1(?<1>){104814})|(?=0)).
(?:(?=1(?<1>){66929})|(?=0)).
(?:(?=1(?<1>){23410})|(?=0)).
(?:(?=1(?<1>){122686})|(?=0)).
(?:(?=1(?<1>){44918})|(?=0)).
(?:(?=1(?<1>){101752})|(?=0)).
(?:(?=1(?<1>){3961})|(?=0)).
(?:(?=1(?<1>){31807})|(?=0)).
(?:(?=1(?<1>){54933})|(?=0)).
(?:(?=1(?<1>){140096})|(?=0)).
(?:(?=1(?<1>){49026})|(?=0)).
(?:(?=1(?<1>){5507})|(?=0)).
(?:(?=1(?<1>){96132})|(?=0)).
(?:(?=1(?<1>){167303})|(?=0)).
(?:(?=1(?<1>){57877})|(?=0)).
(?:(?=1(?<1>){88461})|(?=0)).
(?:(?=1(?<1>){111853})|(?=0)).
(?:(?=1(?<1>){126531})|(?=0)).
(?:(?=1(?<1>){110998})|(?=0)).
(?:(?=1(?<1>){7575})|(?=0)).
(?:(?=1(?<1>){7064})|(?=0)).
(?:(?=1(?<1>){59289})|(?=0)).
(?:(?=1(?<1>){122203})|(?=0)).
(?:(?=1(?<1>){175005})|(?=0)).
(?:(?=1(?<1>){28025})|(?=0)).
(?:(?=1(?<1>){49057})|(?=0)).
(?:(?=1(?<1>){6373})|(?=0)).
(?:(?=1(?<1>){50084})|(?=0)).
(?:(?=1(?<1>){70565})|(?=0)).
(?:(?=1(?<1>){75178})|(?=0)).
(?:(?=1(?<1>){142763})|(?=0)).
(?:(?=1(?<1>){56237})|(?=0)).
(?:(?=1(?<1>){32176})|(?=0)).
(?:(?=1(?<1>){113073})|(?=0)).
(?:(?=1(?<1>){149939})|(?=0)).
(?:(?=1(?<1>){16308})|(?=0)).
(?:(?=1(?<1>){12725})|(?=0)).
(?:(?=1(?<1>){75190})|(?=0)).
(?:(?=1(?<1>){54711})|(?=0)).
(?:(?=1(?<1>){180664})|(?=0)).
(?:(?=1(?<1>){68540})|(?=0)).
(?:(?=1(?<1>){93117})|(?=0)).
(?:(?=1(?<1>){161781})|(?=0)).
(?:(?=1(?<1>){15808})|(?=0)).
(?:(?=1(?<1>){130814})|(?=0)).
(?:(?=1(?<1>){162379})|(?=0)).
(?:(?=1(?<1>){80836})|(?=0)).
(?:(?=1(?<1>){149943})|(?=0)).
(?:(?=1(?<1>){16841})|(?=0)).
(?:(?=1(?<1>){149452})|(?=0)).
(?:(?=1(?<1>){182733})|(?=0)).
(?:(?=1(?<1>){56270})|(?=0)).
(?:(?=1(?<1>){163792})|(?=0)).
(?:(?=1(?<1>){34770})|(?=0)).
(?:(?=1(?<1>){101843})|(?=0)).
(?:(?=1(?<1>){199124})|(?=0)).
(?:(?=1(?<1>){129493})|(?=0)).
(?:(?=1(?<1>){43990})|(?=0)).
(?:(?=1(?<1>){113112})|(?=0)).
(?:(?=1(?<1>){71129})|(?=0)).
(?:(?=1(?<1>){61402})|(?=0)).
(?:(?=1(?<1>){145852})|(?=0)).
(?:(?=1(?<1>){98781})|(?=0)).
(?:(?=1(?<1>){141790})|(?=0)).
(?:(?=1(?<1>){163235})|(?=0)).
(?:(?=1(?<1>){110566})|(?=0)).
(?:(?=1(?<1>){117737})|(?=0)).
(?:(?=1(?<1>){67050})|(?=0)).
(?:(?=1(?<1>){68075})|(?=0)).
(?:(?=1(?<1>){124047})|(?=0)).
(?:(?=1(?<1>){181587})|(?=0)).
(?:(?=1(?<1>){125429})|(?=0)).
(?:(?=1(?<1>){112118})|(?=0)).
(?:(?=1(?<1>){196088})|(?=0)).
(?:(?=1(?<1>){25082})|(?=0)).
(?:(?=1(?<1>){178684})|(?=0)).
(?:(?=1(?<1>){13822})|(?=0)).
(?<-1>){10094986}
(?(1)(?!))
$

Cada (?:(?=1(?<1>){n})|(?=0)).fila empuja ncadenas vacías para agrupar 1si se encuentra el dígito 1, y no hace nada si 0se encuentra uno. (?<-1>){10094986}(?(1)(?!))luego verifica que el número total de cadenas vacías en el grupo 1 al final sea 10094986. Por lo tanto, nuestro objetivo es encontrar un subconjunto de los números de modo que su total sea 10094986. Este es exactamente el problema de la suma del subconjunto, que es un caso especial de el problema de la mochila, y está NP completo.

Probado en Regex Hero (Regex Storm agota el tiempo de espera para este).

Sp3000
fuente
2
Coincidencia: 01111111111111111111111011001111111111011111111111111111111101111111111 11111111111111111111011111111000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000 (eliminar esos espacios). No coincidencia: KnapsackAlgorithm . No es fácil instalar Silverlight en mi máquina Ubuntu. Pero esto funcionó en algún otro probador.
jimmy23013
@ user23013 Ah, vaya, olvidé que eso requería Silverlight. Pero honestamente, o tengo mala suerte o hay muchas soluciones, porque esa es una cadena estúpidamente larga de ceros al final allí. Por otra parte, primero tendré que superar la barrera int de 32 bits, creo que tengo una idea ...
Sp3000
¡Ya tenía un entero de más de 700 bits en mi última respuesta!
jimmy23013
@ user23013 ¿Y nos está diciendo que lo factoricemos? ¡Tan malo! : P
Sp3000
2
El entero para factorizar es 1536 bit.
jimmy23013
4

Sabor .NET (52506 bytes)

Subconjunto suma, edición de lujo.

Regex aquí , versión ampliada aquí , probado en RegExLib y Regex Hero


Coincidencia: No 1000010001000000001101011000001101110101001010011101000101010011011101000001010101001000010010000111011101100101001101001111000111010101100000101000101010110001010101001100100001110010001101010101100010110011000000110110000000011111101000001000011111100010

coincidencia: Huzzah for NP-complete regexes

esta expresión regular es un problema de suma de subconjuntos gigante y utiliza 16 grupos para almacenar datos. Cada uno 1en la cadena representa 16 números de 10 bits, que juntos representan un número entero de 160 bits. Las últimas líneas de la expresión regular llevan los valores en los grupos para que los grupos 2-16 suban a 1023 (por ejemplo, 1 * 1023 + 1024 se convierten en 2 * 1023 + 1), de lo contrario solo estaríamos resolviendo 16 mini subconjuntos simultáneos problemas de suma en lugar de uno grande.

Sp3000
fuente
¡Felicitaciones por haber superado las 72 horas! Ahora puede bloquear su respuesta contra grietas al revelar la clave. Hasta que lo haga, la respuesta aún puede ser descifrada.
Martin Ender
4

Sabor .NET, 53,884 bytes [seguro]

Generado por GnuPG! Y extraído por pgpdump. Es de 1536 bits porque las versiones más largas fallaron en el probador en línea.

La expresión regular está aquí: http://pastebin.com/PkJnj9ME

Probado en RegExLib (sin opciones seleccionadas). Espero no haberles causado demasiados problemas.

Probablemente quieras descifrar la versión fácil primero. Es lo mismo que este, excepto por tener una clave mucho más corta.

Probablemente también quieras este número:

1877387013349538768090205114842510626651131723107399383794998450806739516994144298310401108806926034240658300213548103711527384569076779151468208082508190882390076337427064709559437854062111632001332811449146722382069400055588711790985185172254011431483115758796920145490044311800185920322455262251745973830227470485279892907738203417793535991544580378895041359393212505410554875960037474608732567216291143821804979045946285675144158233812053215704503132829164251

La clave

Partido:

Ëòčĵċsïݲ¤ėGâĥÓŧÿÃiTüū&0EĚĵŒR@bĵ¤¿Ĉ=ķüÙļÞďYaŃīŲĢŪÕďųïyĘŊŢĝĪĘŠćĢmtŠîĽþĽłŶāĨĩģTő!ĺw=aŧïųţĨíœą¸Ëč!,ĵţ¨ŌąŜ7ć<ůū¹"VCæ>õêqKËĖ¡ôÕÂúëdčÜÇĺřGĝ¢ÈòTdĩŤŭi§aćŎŭųä«´3ĚΦîŇĬÒÕ¥ńü½å±ì³Jõ«D>ìYũʼn5öķ@ŪĠďàÂIĭųė!

No partido:

1111111111111111

Los números primos:

1332079940234179614521970444786413763737753518438170921866494487346327879385305027126769158207767221820861337268140670862294914465261588406119592761408774455338383491427898155074772832852850476306153369461364785463871635843192956321
1409365126404871907363160248446313781336249368768980464167188493095028723639124224991540391841197901143131758645183823514744033123070116823118973220350307542767897614254042472660258176592286316247065295064507580468562028846326382331

La explicación está en la versión fácil .

El script generador (en CJam)

'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

"
^
(?=["T",]{"FG+)`"}$)
(?=.{"F`"},)
(?!.*,.*,)
(?:
    (?(X)
        (?<-X>)
        (?(L)(?<-L>)(?<l>)|){16}
    |
        (?:
            "
            [T289,]z
            {[~17md["(?<l>){"\'}]["(?<L>){"@'}]]}%'|*
            "
        )
        (?<X>)
    )
    (?=.*,
        (?:
            (?(Y)
                (?<-Y>)
                (?(R)(?<-R>)(?<r>)|){16}
            |
                (?:
                    "
                    [T289,]z
                    {[~17md["(?<r>){"\'}]["(?<R>){"@'}]]}%'|*
                    "
                )
                (?<Y>)
            )

            (?(l)
                (?<-l>)(?<x>)
                (?(r)(?<-r>)(?<y>)(?<v>)|){16}
                (?(y)(?<-y>)(?<r>)|){16}
            |){16}
            (?(x)(?<-x>)(?<l>)|){16}

            (?(p)(?<-p>)(?<s>)(?<z>)|){"F2*(`"}
            (?(z)(?<-z>)(?<p>)|){"F2*(`"}
            (?(q)(?<-q>)(?<s>)(?<z>)|){"G2*(`"}
            (?(z)(?<-z>)(?<q>)|){"G2*(`"}
            "
            "
            (?(s)
                (?<-s>)
            "FG+(2**
            "
                (?(v)(?<-v>)(?<a"FG+(2*`">)|){256}
            "
            ["
            |
                (?(v)(?<-v>)(?<a"">)|){256}
            )
            "]aFG+(2*,W%m*{~\~@`\}/
            "
            (?(r)(?<-r>)|){16}
            (?<q>)
        ){"G2*`"}
        (?<-q>){"G2*`"}
    )
    (?(l)(?<-l>)|){16}
    (?<p>)
){"F2*`"},

"
[
l~17bW%_,FG+2*\- 0a*+
FG+2*,
]z
{
~:A`:B;:C;
"
(?<-a"B">){"C`"}
(?(a"B")(?<-a"B">){17}(?<a"A)`">)|){4100}
(?(a"B")(?!)|)"
}/

]:+N9c+-

La entrada debe ser el número anterior.

Una vez que haya terminado, la solución puede ser generada por este programa:

'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

{
r~289bW%_,FG:F;\- 0a*+
{T=}%
}2*',\

La entrada debe ser dos enteros.

jimmy23013
fuente
Demasiado. RegExLib está caído. Creo que la gente debería usar un Silverlight o un probador local. Pero no puedo probarlos.
jimmy23013
IIRc, RegexHero es un probador .NET en el navegador, que utiliza Silverlight.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
Otra idea sobre los enteros grandes es calcular los números primos de mod de producto cerca de 200. Debería ser más rápido. Pero el código sería mucho más largo y no voy a hacer eso en respuestas de factorización de enteros.
jimmy23013
¡Felicitaciones por haber superado las 72 horas! Ahora puede bloquear su respuesta contra grietas al revelar la clave. Hasta que lo haga, la respuesta aún puede ser descifrada.
Martin Ender
4

PHP, 395 bytes [descifrado por nneonneo ]

^( *)( *)( *)(['.-])((?!\4)(?4)+?)((?!\4|\5)(?4)++)\1\3whale
(?=.(.))\6.\7\4(?!\4|\6)([_\/])\3(?!(?11))\8\2(?=\2)\3\1_((?=\4+.).\5(?!\6)\5)(?!.?')\7\4
(?=.\7)\6.([,`])\3{2}(?=.((?!\8)[_\/])\11)\Q(_\E.\4{2}(?!\.)\5((?!\10)(?10)(?!\4+|\5|\6))\1\3{3}(\\)
(\3{3})\13\2{2}\1{1}\3+(?<=\S {10})\4\1\3\|
\1(?=\12)(?12)(?!`,)\10\4(\11{2})\4\14\10\15\9\8
\14{2}(?=\6)['-]\4(?<!-)\11\8\11\4\6\11\15\.-|(?!)

Un rompecabezas mejor que mi última entrada.

Nota: La clave coincidente es multilínea, con cada línea separada por el nuevo carácter de línea \n. ¡Reconstruye algo de arte ASCII!

Aquí hay una demostración de expresiones regulares .

Unihedron
fuente
3
Coincidencia : 202e272d207768616c650a2d3a3a2e2f202f205f2e27273a2e0a2d3a2c2020285f5f2e2e27602020205c0a2020205c202020202020202020202e207c0a602c2e5f5f2e2020202c5f5f2e27272f0a2020202020202d2e5f2f5f2e2d5f5f5f2e2d(codificado en hexadecimal). No coincidencia : IDon'tThinkIGotTheRightPicture. Espacio de
nneonneo
1
@nneonneo ¡Guau! Lo resolvió: D Pero la imagen correcta está aquí: regex101.com/r/oM9rC4/1
Unihedron
1
Sí, pensé que no tenía suficientes espacios (pero la expresión regular no se controló demasiado). Y, parece que me he intercambiado .-'al principio .'-. En retrospectiva, lo primero es mucho más plausible para el arte ASCII;)
nneonneo
3

Sabor Perl, 97 [agrietado]

Me temo que esto será demasiado fácil debido al límite de longitud de la clave.

^([^,]+),(?!\1)([^,]+),(?!\1|\2,)([^,]+),(?!\1|(?:\2|\3),)([^,]+),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

Si cree que se le ocurrió la idea, pruebe la versión más larga (que no forma parte del desafío)

^((?:[^,]{3})+),(?!\1)([^,]+),(?!\1|\2,)([^,]+),(?!\1|(?:\2|\3),)([^,]+),(?!\1|(?:\2|\3|\4),)([^,]+),(?!\1|(?:\2|\3|\4|\5),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6|\7),)([^,]+),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$
Ana
fuente
1
Partido: aaaaaaa,a,aa,aaa,aaaaaaa. No coincidencia: aaaabaaacaaadaaa.
jimmy23013
Versión más larga: Match: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,a,aa,(eliminar estos caracteres) aaaa,aaaaaaa,aaaaaaaa,aaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaa,(eliminar estos caracteres) aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. No partido:aaaabaaacaaadaaa
jimmy23013
@ user23013: ¡La versión corta es correcta! Me refería a que los grupos de captura debían tener al menos dos caracteres, lo que habría alargado un poco la clave, pero olvidé cambiarla: P Sin embargo, la versión más larga es incorrecta.
Ell
Este sitio agregó algunos caracteres especiales invisibles cuando los publiqué. Creo que ya está arreglado. (Sin el (remove these characters).)
jimmy23013
@ user23013 Sí, eso es un partido. Realmente no planeé que fuera tan fácil: P
Ell