Wie löse ich die Übung "Crypt Kicker", die in "Programming Challenges (The Programming Contest Training Manual)" vorgeschlagen wird?

Question

"Programming Challenges (The Programming Contest Training Manual)" ist wahrscheinlich eines der schönsten Übungsbücher über Algorithmen. Ich habe die ersten 11 Aufgaben gelöst, aber jetzt stecke ich beim "Crypt Kicker" Problem fest:

Krypto-Kicker
Eine gängige, aber unsichere Methode zur Verschlüsselung von Text besteht darin, die Buchstaben des Alphabets zu vertauschen. Mit anderen Worten: Jeder Buchstabe des Alphabets wird im Text konsequent durch einen anderen ersetzt. Um sicherzustellen, dass die Verschlüsselung umkehrbar ist, werden keine zwei Buchstaben durch denselben Buchstaben ersetzt.

Ihre Aufgabe besteht darin, mehrere verschlüsselte Textzeilen zu entschlüsseln, wobei davon ausgegangen wird, dass jede Zeile einen anderen Satz von Ersetzungen verwendet und dass alle Wörter im entschlüsselten Text aus einem Wörterbuch mit bekannten Wörtern stammen.

Eingabe
Die Eingabe besteht aus einer Zeile mit einer ganzen Zahl n, gefolgt von n Wörtern in Kleinbuchstaben, eines pro Zeile, in alphabetischer Reihenfolge. Diese n Wörter bilden das Wörterbuch der Wörter, die in dem entschlüsselten Text vorkommen können.
Nach dem Wörterbuch folgen mehrere Zeilen mit Eingaben. Jede Zeile wird wie oben beschrieben verschlüsselt.

Es gibt nicht mehr als 1.000 Wörter im Wörterbuch. Kein Wort besteht aus mehr als 16 Buchstaben. Die verschlüsselten Zeilen enthalten nur Kleinbuchstaben und Leerzeichen und dürfen nicht länger als 80 Zeichen sein.

Ausgabe
Entschlüsseln Sie jede Zeile und geben Sie sie auf der Standardausgabe aus. Wenn es mehrere Lösungen gibt, ist jede Lösung geeignet.
Wenn es keine Lösung gibt, ersetzen Sie jeden Buchstaben des Alphabets durch ein Sternchen.

Beispielhafte Eingabe 6
y
dick
jane
puff
Punkt
yertle

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

Beispielhafte Ausgabe
Dick und Jane und Puff und Spot und Yertle ...

Was Strategie Was sollte ich tun, um diese Aufgabe zu lösen? Ich dachte an eine klassische und brutale Backtracking-Lösung, aber ich versuche das zu vermeiden, bis ich etwas Intelligenteres finde.

PS: Dies hat nichts mit den Hausaufgaben zu tun, ich versuche nur, meine allgemeinen Fähigkeiten zu verbessern.

Answer 1

KeyArray wird die Ersetzungstabelle enthalten.

• Beginnen Sie mit einem leeren KeyArray, dies ist Version 0

• Längstes verschlüsseltes Wort mit längstem Wörterbuchwort vergleichen und zu KeyArray hinzufügen (wenn es zwei längste Wörter gibt, wähle eines), dies ist Version 1.

• Entschlüsseln Sie einige Buchstaben des nächstlängsten verschlüsselten Wortes.

• Prüfen Sie, ob die entschlüsselten Buchstaben mit dem Buchstaben an der gleichen Position in einem beliebigen Wörterbuchwort der gleichen Länge übereinstimmen.

• Wenn kein Wort passt, gehen Sie zurück zu Version 0 und versuchen Sie ein anderes Wort.

• Wenn einige Buchstaben übereinstimmen, fügen Sie den Rest der Buchstaben zu KeyArray hinzu, dies ist Version 2.

• Entschlüsseln Sie einige Buchstaben des nächstlängsten verschlüsselten Wortes.

• Prüfen Sie, ob die entschlüsselten Buchstaben mit den Buchstaben in derselben Position in einem beliebigen Wörterbuchwort übereinstimmen.

• Wenn kein Wort passt, gehen Sie zurück zu Version 1 und versuchen Sie ein anderes Wort

• Wenn einige Buchstaben übereinstimmen, fügen Sie den Rest der Buchstaben zu KeyArray hinzu, dies ist Version 3.

Wiederholen Sie diesen Vorgang, bis alle Wörter entschlüsselt sind.

Wenn bei Version 0 keines der längsten Wörter eine teilweise Entschlüsselung in kürzeren Wörtern, gibt es sehr wahrscheinlich keine Lösung.

Answer 2

Eine geringfügige Optimierung könnte durch die Aufzählung von Möglichkeiten vor dem Backtracking-Lauf erreicht werden. In 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))

Ausgabe:

{'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'])}

Wenn Sie einige Einzelelementmöglichkeiten haben, können Sie diese aus der Eingabe eliminieren und den Algorithmus erneut ausführen.

EDIT : Umstellung auf Set anstelle von List und Hinzufügen von Druckcode.

Answer 3

Ich habe eigentlich einen etwas anderen Ansatz versucht. Ich habe ein Trie aus den Wörtern des Wörterbuchs erstellt. Dann gehe ich den Trie und den Satz zusammen rekursiv durch (ich durchlaufe den Trie in einem DFS).

Bei jeder Leerstelle vergewissere ich mich, dass ich das Ende eines Wortes im Versuch treffe, und wenn dies der Fall ist, fahre ich in einer Schleife zurück zur Wurzel. Auf dem Weg dorthin notiere ich mir die bisherigen Buchstabenzuordnungen. Wenn ich eine Zuweisung habe, die einer früheren Zuweisung widerspricht, scheitere ich und löse die Rekursion bis zu dem Punkt auf, an dem ich die nächste mögliche Zuweisung vornehmen kann.

Das hört sich kompliziert an, scheint aber recht gut zu funktionieren. Und es ist wirklich nicht so schwer, es zu programmieren!

Answer 4

Eine weitere Optimierungsmöglichkeit, wenn Sie "genug" Text haben und die Sprache des Textes kennen, ist die Verwendung von Buchstabenhäufigkeiten (siehe : http://en.wikipedia.org/wiki/Letter_frequency ). Dies ist natürlich eine sehr ungefähre Vorgehensweise, wenn es sich um 6/7 Wörter handelt, aber es ist der schnellste Weg, wenn Sie einige Seiten zu entschlüsseln haben.

EDIT: Zu Max' Lösung: Sie könnten auch versuchen, einige Merkmale des Wortes zu extrahieren, z. B. sich wiederholende Buchstaben. Der Hinweis, dass puff im Wörterbuch und qymm im verschlüsselten Text die einzigen Wörter mit vier Buchstaben sind, die mit einem Doppelbuchstaben enden, gibt eine direkte Antwort für 3 der Buchstaben. In komplexeren Szenarien sollten Sie in der Lage sein, die Möglichkeiten für jedes Buchstabenpaar einzugrenzen.

Answer 5

Hier ist eine Java-Implementierung mit weiteren Verfeinerungen der Algorithmus vorgeschlagen von @Carlos Gutiérrez.

Crypt Kicker Algorithmus und Lösung, was lief schief?

• Die Verfeinerung besteht darin, ein Wortmuster hinzuzufügen, um den Suchraum für Wörter zu reduzieren. Zum Beispiel haben die Wörter "abc" und "her" das gleiche Muster, "aac" und "her" hingegen nicht, da ein Wort mit drei verschiedenen Buchstaben nicht mit einem Wort mit zwei verschiedenen Buchstaben übereinstimmen würde.

• Außerdem kann der Algorithmus rekursiv implementiert werden, was intuitiver und sinnvoller ist.