Wie behebe ich die „Crypt Kicker“ Übung vorgeschlagen in „Programmieren Herausforderungen (Der Programmierwettbewerb Training Manual)“?

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

  •  24-09-2019
  •  | 
  •  

Frage

„Programmierung Herausforderungen (Der Programmierwettbewerb Training Manual)“ ist wohl eines der schönsten Übungen auf Algorithmen buchen. Ich habe die ersten 11 Übungen gelöst, aber jetzt bin ich mit „Crypt Kicker“ Problem stecken:

  

Crypt Kicker
  Eine gemeinsame, aber unsicher Methode Text zu verschlüsseln ist, die Buchstaben des Alphabets permutieren.   Mit anderen Worten, jeder Buchstabe des Alphabets konsequent im Text durch einen anderen Buchstaben ersetzt. Um sicherzustellen, dass die Verschlüsselung reversibel ist, werden keine zwei Buchstaben mit dem gleichen Buchstaben ersetzt.

     

Ihre Aufgabe ist es mehrere codierten Textzeilen zu entschlüsseln, unter der Annahme, dass jede Zeile einen anderen Satz von Ersatz verwendet, und dass alle Worte im entschlüsselten Text aus einem Wörterbuch von bekannten Worten sind.

     

Eingabe
  Die Eingabe besteht aus einer Zeile mit n einer ganzen Zahl, gefolgt von n Klein Worten, einem pro Zeile, in alphabetischer Reihenfolge. Diese n Wörter bilden das Wörterbuch von Wörtern, die im entschlüsselten Text erscheinen.
  Nach dem Wörterbuch sind mehrere Linien der Eingabe. Jede Zeile wird verschlüsselt, wie oben beschrieben.

     

Es gibt nicht mehr als 1.000 Wörter im Wörterbuch. Kein Wort mehr als 16   Briefe. Die verschlüsselten Zeilen enthalten nur Kleinbuchstaben und Räume und   nicht mehr als 80 Zeichen lang ist.

     

Ausgang |   Entschlüsseln Sie jede Zeile und drucken Sie es auf die Standardausgabe. Wenn es mehrere Lösungen gibt, tun irgendeine.
  Wenn es keine Lösung gibt, durch ein Sternchen jeden Buchstaben des Alphabets ersetzt werden.

     

Probeneingang 6
    und
    dick
    jane
    puff
    beschmutzen
    Yertle

     

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

     

Beispielausgabe
   Dick und Jane und puff und Stelle und Yertle ...

Was Strategie sollte ich zu ergreifen, um diese Übung zu lösen? Ich wurde zu einem klassischen und viehisch Rückzieher Lösung zu denken, aber ich versuche zu vermeiden, dass bis ich etwas intelligentere finden.

PS:. Diese nicht Hausaufgaben im Zusammenhang ist, ich versuche nur meine allgemeinen Fähigkeiten zu verbessern

War es hilfreich?

Lösung

KeyArray die Ersetzungstabelle halten.

  • Starten Sie mit einem leeren KeyArray, dies ist die Version 0

  • Match längst verschlüsseltes Wort längstes Wort aus dem Wörterbuch und in dem KeyArray (Wenn es zwei längsten ist, holt vorhanden), das ist Version 1.

  • Entschlüsseln einige Buchstaben des nächsten längsten crypted Wort.

  • Überprüfen Sie, ob die entschlüsselten Buchstaben, die Buchstaben in der gleichen passen Position in jedem Wort aus dem Wörterbuch der gleichen Länge.
  • Falls keine Streichhölzer, gehen Sie zurück auf die Version 0 und ein weiteres Wort versuchen.

  • Wenn einige Buchstaben übereinstimmen, den Rest der Briefe an KeyArray hinzufügen, das ist Version 2

  • Entschlüsseln einige Buchstaben des nächsten längsten crypted Wort.

  • Überprüfen Sie, ob die entschlüsselten Buchstaben, die Buchstaben in der gleichen passen Position in jedem Wort aus dem Wörterbuch.
  • Falls keine Streichhölzer, gehen Sie zurück auf die Version 1 und versuchen Sie ein anderes Wort
  • Wenn einige Buchstaben übereinstimmen, den Rest der Briefe an KeyArray hinzufügen, das ist Version 3

Wiederholen, bis alle Wörter entschlüsselt werden.

Wenn in der Version 0 keine der längsten Worte erzeugt eine partielle decrypt in kürzere Worte, sehr wahrscheinlich ist es keine Lösung.

Andere Tipps

Eine geringfügige Optimierung kann durch Aufzählen Möglichkeiten vor dem Rückzieher Laufe durchgeführt 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 Einzelelemente Möglichkeiten haben, können Sie sie von der Eingabe beseitigen und den Algorithmus erneut aus.

EDIT:. Switched-Set statt Liste und hinzugefügt Drucke Code

Ich habe versucht, eigentlich eine ganz andere Herangehensweise. Ich baute einen Trie aus dem Wörterbuch Wort. Dann laufe ich durch den Trie und der Satz zusammen rekursiv (die Trie in einer DFS durchqueren).

An jeden Raum stelle ich sicher, traf ich das Ende eines Wortes in der Trie und wenn ja, ich Schleife zurück in die Wurzel. Auf dem Weg verfolge ich den Brief Zuweisungen ich bisher gemacht habe. Wenn überhaupt habe ich einen Auftrag, dass im Widerspruch zu einer vorherigen Zuteilung ich versage und löse die Rekursion auf den Punkt kann ich die nächste mögliche assigment machen.

Es klingt schwierig, aber es scheint ganz gut zu funktionieren. Und es ist wirklich nicht so schwer zu Code auf!

Eine weitere mögliche Optimierung, wenn Sie „genug“ Text haben, zu beschäftigen und Sie wissen, die Sprache des Textes, können Sie Buchstaben Frequenzen verwenden (siehe: http://en.wikipedia.org/wiki/Letter_frequency). Dies ist natürlich eine sehr approximative Ansatz, wenn sie mit 07.06 Worte tun, sondern wird der schnellste Weg sein, wenn Sie ein paar Seiten zu dekodieren haben.

EDIT: über Max-Lösung, könnten Sie versuchen, einige Eigenschaften des Wortes zu extrahieren, zu, wie sich wiederholende Buchstaben. Offensichtlich bemerkte, dass puff im Wörterbuch und qymm im verschlüsselten Text sind die einzigen vier Buchstaben-Wörter mit einem Doppelbuchstaben enden gibt eine klare Antwort für drei der Buchstaben. In komplexeren Szenarien, sollten Sie in der Lage sein, die Möglichkeiten für jeden Buchstaben Paar zu verengen.

Hier ist eine Java-Implementierung mit mehr Verfeinerungen der Algorithmus Vorschlag @Carlos Gutiérrez.

Crypt Kicker-Algorithmus und Lösung, was schief gelaufen ist?

  • Die Verfeinerung ist ein Wortmuster hinzuzufügen, um den Suchraum für Worte zu reduzieren. Zum Beispiel Worte „abc“ und „sie“ das gleiche Muster aufweist, während „aac“ und „sie“ nicht als drei verschiedene Buchstaben Wort nicht ein Abschlepp Buchstaben deutliches Wort entsprechen würde.

  • Darüber hinaus kann der Algorithmus rekursiv implementiert werden, das intuitiven und sinnvoll ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top