Kryptic Kicker

Un método común pero inseguro de cifrar texto es permutar las letras del alfabeto. En otras palabras, cada letra del alfabeto se reemplaza constantemente en el texto por alguna otra letra. Para garantizar que el cifrado sea reversible, no se reemplazan dos letras por la misma letra. Su tarea es descifrar varias líneas de texto codificadas, suponiendo que cada línea utiliza un conjunto diferente de reemplazos, y que todas las palabras en el texto descifrado provienen de un diccionario de palabras conocidas.

Entrada

La entrada consta de palabras en minúsculas, en orden alfabético. Estas palabras componen el diccionario de palabras que pueden aparecer en el texto descifrado. Siguiendo el diccionario hay varias líneas de entrada. Cada línea se cifra como se describe anteriormente.

No hay más de 1,000 palabras en el diccionario. Ninguna palabra supera las 16 letras. Las líneas encriptadas contienen solo letras minúsculas y espacios y no exceden los 80 caracteres de longitud.

Salida

Descifre cada línea e imprímala en la salida estándar. Si hay múltiples soluciones, cualquiera lo hará. Si no hay solución, reemplace cada letra del alfabeto por un asterisco.

Entrada de muestra

and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Salida de muestra

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

Aquí está la solución. Tenga en cuenta que no soy un caballo corriendo en la carrera por los bytes más cortos / programador competitivo. ¡Simplemente me gustan los rompecabezas!

( Fuente )

Python 3, 423 bytes

import sys,re
S=re.sub
D,*L=sys.stdin.read().split('\n')
def f(W,M=[],V="",r=0):
 if len({d for(s,d)in M})==len(M):
  if[]==W:return V.lower()
  for d in D.split():p='([a-z])(?%s.*\\1)';m=re.match(S(p%'=',')\\1=P?(',S(p%'!',').>\\1<P?(',W[0].translate(dict(M))[::-1]))[::-1]+'$',d.upper());r=r or m and f(W[1:],M+[(ord(s),m.group(s))for s in m.groupdict()],V+d+" ")
  return r
for l in L:print(f(l.split())or S('\w','*',l))

Lee la entrada de STDIN y escribe la salida en STDOUT, utilizando el mismo formato que la entrada / salida de muestra.

Explicación

Para cada línea de texto cifrado, realizamos el siguiente procedimiento:

Mantenemos un mapa, M , de todas las transformaciones de letras que ya hemos establecido (que inicialmente está vacío). Lo hacemos de tal manera que las letras de origen están en minúsculas y las letras de destino están en mayúsculas.

Procesamos las palabras en el texto cifrado en orden. Para cada palabra, encontramos todas las palabras en el diccionario que podrían coincidir, de la siguiente manera:

Supongamos que nuestra palabra, w , es glpplppljjly que M contiene la regla j -> P. Primero transformamos w usando las reglas existentes en M , obteniendo glpplpplPPl. Luego transformamos w en la siguiente expresión regular con sabor a pitón:

(?P<g>.)(?P<l>.)(?P<p>.)(?P=p)(?P=l)(?P=p)(?P=p)(?P=l)PP(?P=l)

Las reglas de la transformación son las siguientes:

• La primera aparición de cada letra minúscula x, se reemplaza con . Esto define un grupo de captura con nombre, llamado , que coincide con un solo carácter.(?P<x>.)x
• Cada aparición posterior, cada letra minúscula x, se reemplaza con . Esta es una referencia al personaje previamente capturado por el grupo nombrado .(?P=x)x

Realizamos esta transformación invirtiendo w , luego aplicando las dos siguientes sustituciones de expresiones regulares:

s/([a-z])(?!.*\1)/)>\1<P?(/
s/([a-z])(?=.*\1)/)\1=P?(/

y luego invirtiendo el resultado. Tenga en cuenta que los caracteres previamente transformados por M aparecen en mayúsculas y, por lo tanto, permanecen sin cambios.

Hacemos coincidir la expresión regular resultante con cada una de las palabras del diccionario, donde las palabras del diccionario aparecen en mayúsculas. Por ejemplo, la expresión regular anterior coincidiría con la palabra MISSISSIPPI. Si nos encontramos con un partido, extraemos las nuevas reglas de transformación de ella, y añadirlos a M . Las nuevas reglas de transformación son simplemente los personajes capturados por cada uno de los grupos de captura. En la expresión regular anterior, el grupo gcoincide M, el grupo lcoincide Iy el grupo pcoincide S, dándonos las reglas g -> M, l -> I, p -> S. Tenemos que asegurarnos de que las reglas resultantes sean consistentes, es decir, que no haya dos letras de origen asignadas a la misma letra de destino; de lo contrario, rechazamos el partido.

Luego procedemos a la siguiente palabra, usando las reglas de transformación aumentada. Si podemos unir todas las palabras de texto cifrado utilizando este proceso, hemos descifrado el texto. Si no podemos hacer coincidir una palabra con ninguna de las palabras del diccionario, retrocedemos e intentamos hacer coincidir las palabras anteriores con diferentes palabras del diccionario. Si este proceso falla, no hay solución, e imprimimos una fila de asteriscos.

CJam, 62 56 bytes

qN%Sf/(f{\:C,m*{C..+`Sa`m2/Q|z_''f-Qf|=},C:,'*f*a+0=S*N}

Bastante lento y hambriento de memoria, pero funciona para el caso de prueba con el intérprete de Java.

Ejecución de ejemplo

$ cat input; echo
and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
$ time cjam kicker.cjam < input
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

real    5m19.817s
user    6m41.740s
sys     0m1.611s