¿Cómo resuelvo el ejercicio “Cripta Kicker” se propone en “retos de programación (El Concurso de Programación Manual de Entrenamiento)”?

Question

"Programación desafíos (El Concurso de Programación Manual de Entrenamiento)" es probablemente uno de los mejores ejercicios de reserva en algoritmos. He resuelto los primeros 11 ejercicios, pero ahora estoy atascado con "Cripta Kicker" problema:

  

Cripta Kicker
  Un método común pero insegura de cifrar texto es para permutar las letras del alfabeto.   En otras palabras, cada letra del alfabeto se sustituye constantemente en el texto por alguna otra letra. Para asegurar que el cifrado es reversible, no hay dos cartas son reemplazadas por la misma letra.

     

Su tarea es descifrar varias líneas de texto codificados, suponiendo que cada línea utiliza un conjunto diferente de sustituciones, y que todas las palabras en el texto descifrado son de un diccionario de palabras conocidas.

     

Entrada
  La entrada consiste en una línea que contiene un número entero n, seguido de palabras minúsculas n, uno por línea, en orden alfabético. Estas palabras n componen el diccionario de palabras que pueden aparecer en el texto descifrado.
  Tras el diccionario de varias líneas de entrada. Cada línea está encriptada como se describe anteriormente.

     

No hay más de 1.000 palabras en el diccionario. Ni una palabra excede 16   letras. Las líneas cifrados contienen letras y espacios caso sólo inferiores y   no superar los 80 caracteres de longitud.

     

Salida
  Descifrar cada línea e imprimir en la salida estándar. Si hay varias soluciones, cualquiera va a hacer.
  Si no hay solución, reemplazar cada letra del alfabeto por un asterisco.

     

Ejemplo de entrada 6
    y
    Dick
    Jane
    puff
    detectar
    Yertle

     

bjvg XSB hxsn XSB qymm XSB rqat XSB pnetfn
    xxxx yyy zzzz www aaaa aaa bbbb ccc dddddd

     

Resultados de muestra
   Dick y Jane y calada y punto y Yertle ...

Lo que estrategia debería tomar con el fin de resolver este ejercicio? Estaba pensando en una solución clásica y brutal retroceso, pero estoy tratando de evitar que hasta que encuentre algo más inteligente.

PS:. Esto no está relacionado con la tarea, yo estoy tratando de mejorar mis conocimientos generales

Answer 1

keyarray llevará a cabo la mesa de reemplazo.

• Comenzar con un keyarray vacío, esto es la versión 0

• Partido palabra más larga cifrado a más largo palabra de diccionario y añadir a keyarray (Si hay dos más largo, recoger los hay), se trata de la versión 1.

• Descifrar algunas letras de la palabra al lado más largo encriptado.

• Comprobar si las letras descifrados coincide con la letra de la misma posición en cualquier palabra del diccionario de la misma longitud.
• Si ninguno partidos, se remontan a la versión 0 y otra palabra.

• Si algunas cartas coinciden, añadir el resto de las cartas a keyarray, esta es la versión 2.

• Descifrar algunas letras de la palabra al lado más largo encriptado.

• Comprobar si las letras descifrados coincide con la letra de la misma posición en cualquier palabra del diccionario.
• Si ninguno partidos, se remontan a la versión 1 y la otra palabra
• Si algunas cartas coinciden, añadir el resto de las cartas a keyarray, esta es la versión 3.

Repetir hasta que todas las palabras son descifrados.

Si en la versión 0 ninguna de las palabras más largas crea un descifrado parcial palabras más cortas, muy probablemente, no hay solución.

Answer 2

Una optimización de menor importancia podría hacerse mediante la enumeración de las posibilidades antes de la carrera vuelta hacia atrás. En Python:

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

Salida:

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

Si usted tiene algunas posibilidades de un solo elemento, puede eliminarlos de la entrada y vuelva a ejecutar el algoritmo.

EDIT:. Al cambiar a la serie en lugar de la lista y se añade código de impresión

Answer 3

En realidad intentó un enfoque bastante diferente. Construí un trie de las palabras del diccionario. Entonces ande en el trie y la sentencia en conjunto recursiva (atravesando el trie en un DFS).

En cada espacio me aseguro de que golpeó el final de una palabra en el trie y si es así volver bucle I de la raíz. En el camino puedo realizar un seguimiento de las asignaciones de letras que he hecho hasta ahora. Si alguna vez tengo una misión que contradice una cesión anterior fallo y desentrañar la recursividad hasta el punto que pueden hacer que la próxima assigment posible.

Suena complicado, pero parece que funciona bastante bien. Y en realidad no es tan difícil de código de arriba!

Answer 4

Otra posible optimización, si tiene texto "suficiente" para hacer frente y sabes el idioma del texto, puede utilizar las frecuencias de letras (ver: http://en.wikipedia.org/wiki/Letter_frequency). Esto es por supuesto un enfoque muy aproximado al tratar con 6/7 palabras, sino que será la forma más rápida si tiene unas pocas páginas para decodificar.

EDIT: acerca de la solución de Max, se podría tratar de extraer algunas características de la palabra, también, tales como cartas de repetición. Obviamente, señalando que soplo en el diccionario y qymm en el texto cifrado son las únicas palabras de cuatro letras que terminan con una letra doble da una respuesta directa para 3 de las cartas. En escenarios más complejos, debe ser capaz de reducir las posibilidades de cada pareja letra.

Answer 5

Esta es una aplicación Java con más opciones a la algoritmo propuesto por @Carlos Gutiérrez.

Cripta Kicker Algoritmo y la solución, lo que salió mal?

• El refinamiento es añadir un patrón de la palabra para reducir el espacio de búsqueda para las palabras. Por ejemplo, las palabras "abc" y "ella" tiene el mismo patrón, mientras que "AAC" y "ella" no como una palabra de tres letras distintas podría no coincidir con una palabra distinta cartas de remolque.

• Además, el algoritmo puede ser implementado de forma recursiva, que es más intuitivo y sensible.