Comment puis-je résoudre la « crypte Kicker » exercice proposé dans « Les défis de programmation (Le Manuel de programmation du concours de formation) »?

StackOverflow https://stackoverflow.com/questions/2175356

  •  24-09-2019
  •  | 
  •  

Question

« Les défis de programmation (Le concours de programmation Manuel de formation) » est probablement l'un des plus beaux exercices livre sur les algorithmes. J'ai résolu les 11 premiers exercices, mais maintenant je suis coincé avec le problème « Crypte Kicker »:

  

Crypt Kicker   Une méthode commune, mais peu sûr de texte à chiffrer est permute les lettres de l'alphabet.   En d'autres termes, chaque lettre de l'alphabet est constamment remplacé dans le texte par une autre lettre. Pour vous assurer que le cryptage est réversible, pas deux lettres sont remplacées par la même lettre.

     

Votre tâche consiste à déchiffrer plusieurs lignes de texte codé, en supposant que chaque ligne utilise un ensemble différent de remplacement, et que tous les mots dans le texte déchiffré sont d'un dictionnaire de mots connus.

     

Entrée
  L'entrée se compose d'une ligne contenant un entier n, suivi de n mots de minuscules, une par ligne, dans l'ordre alphabétique. Ces n mots composent le dictionnaire des mots qui peuvent apparaître dans le texte déchiffré.
  A la suite du dictionnaire sont plusieurs lignes d'entrée. Chaque ligne est cryptée comme décrit ci-dessus.

     

Il n'y a pas plus de 1000 mots dans le dictionnaire. Aucun mot dépasse 16   des lettres. Les lignes cryptées contiennent des lettres seulement des minuscules et des espaces et   ne pas dépasser 80 caractères.

     

Sortie
  Décrypter chaque ligne et l'imprimer sur la sortie standard. S'il y a plusieurs solutions, une fera.
  S'il n'y a pas de solution, remplacer chaque lettre de l'alphabet par un astérisque.

     

Entrée de l'échantillon 6
    et
    bite
    jane
    bouffée
    repérer
    Yertle

     

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

     

Exemple de sortie    Dick et jane et feuilletée et place et Yertle ...

Qu'est-ce que Stratégie dois-je prendre pour résoudre cet exercice? Je pensais à une solution classique et retours en arrière bestiale, mais je suis en train d'éviter que jusqu'à ce que je trouve quelque chose de plus intelligent.

PS: Ce n'est pas lié devoirs, je suis juste essayer d'améliorer mes compétences générales

.
Était-ce utile?

La solution

KeyArray tiendra la table de remplacement.

  • Démarrer avec un vide KeyArray, ceci est une version 0

  • mot le plus long match chiffré à plus long mot du dictionnaire et ajouter à KeyArray (S'il y a deux plus longs, prendre tout), c'est une version 1.

  • Décrypter quelques lettres du mot le plus long suivant encrypté.

  • Vérifiez si les lettres déchiffrés correspondent à la lettre dans le même position dans un mot dictionnaire de la même longueur.
  • Si aucune correspond, revenez à la version 0 et essayer un autre mot.

  • Si certaines lettres correspondent, ajoutez le reste des lettres à KeyArray, c'est la version 2.

  • Décrypter quelques lettres du mot le plus long suivant encrypté.

  • Vérifiez si les lettres déchiffrés correspondent à la lettre dans le même position dans un mot dictionnaire.
  • Si aucune correspond, revenez à la version 1 et essayer un autre mot
  • Si certaines lettres correspondent, ajoutez le reste des lettres à KeyArray, ceci est la version 3.

Répéter jusqu'à ce que tous les mots sont décryptées.

Si à la version 0 aucun des mots les plus longs crée une Décrypter partielle mots plus courts, très probablement il n'y a pas de solution.

Autres conseils

Une optimisation mineure pourrait être fait en dénombrant les possibilités avant la course de retours en arrière. 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))

Sortie: 

{'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 vous avez des possibilités d'un seul élément, vous pouvez les éliminer de l'entrée et exécutez à nouveau l'algorithme.

EDIT:. Switched pour définir la place de la liste et le code d'impression ajouté

J'ai essayé une approche assez différente. J'ai construit une structure arborescente des mots du dictionnaire. Ensuite, je marche dans la structure arborescente et la phrase ensemble récursive (traversant la structure arborescente dans un DFS).

A chaque espace je fais que j'atteind la fin d'un mot dans la structure arborescente et si oui, je boucle de retour à la racine. Le long de la façon dont je garde la trace des affectations de lettres que j'ai fait jusqu'à présent. Si jamais j'ai une mission qui contredit une cession antérieure et je ne dénouer la récursion au point que je peux faire la prochaine assigment possible.

Il semble difficile, mais il semble fonctionner assez bien. Et il est vraiment pas difficile à coder!

Une autre optimisation possible, si vous avez un texte « assez » pour traiter et vous connaissez la langue du texte, vous pouvez utiliser des fréquences de lettre (voir: http://en.wikipedia.org/wiki/Letter_frequency). Ceci est bien sûr une approche très approximative lorsqu'il s'agit de 6/7 mots, mais sera le moyen le plus rapide si vous avez quelques pages à décoder.

EDIT: sur la solution de Max, vous pouvez essayer d'extraire certaines caractéristiques du mot, aussi, comme des lettres de répétition. De toute évidence, en remarquant que souffle dans le dictionnaire et qymm dans le texte crypté sont les seuls mots de quatre lettres se terminant par une double lettre donne une réponse directe pour 3 des lettres. Dans les scénarios plus complexes, vous devriez être en mesure de réduire les possibilités pour chaque couple de lettres.

Voici une implémentation Java avec possibilité d'affinement au algorithme proposé par @Carlos Gutiérrez.

Crypt Kicker algorithme et la solution, ce qui a mal tourné?

  • Le raffinement est d'ajouter un modèle de texte pour réduire l'espace de recherche de mots. Par exemple, les mots « abc » et « elle » ont le même schéma en « aac » et « elle » ne pas trois mots de lettres distinctes ne correspondrait pas à une lettre de remorquage mot distinct.

  • De plus, l'algorithme peut être mis en oeuvre de manière récursive qui est plus intuitive et sensible.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top