Cryptic Kicker
Eine übliche, aber unsichere Methode zum Verschlüsseln von Text besteht darin, die Buchstaben des Alphabets zu permutieren. Mit anderen Worten, jeder Buchstabe des Alphabets wird im Text durch einen anderen Buchstaben ersetzt. Um sicherzustellen, dass die Verschlüsselung umkehrbar ist, werden keine zwei Buchstaben durch denselben Buchstaben ersetzt. Ihre Aufgabe ist es, mehrere verschlüsselte Textzeilen zu entschlüsseln, vorausgesetzt, jede Zeile verwendet einen anderen Satz von Ersetzungen und alle Wörter im entschlüsselten Text stammen aus einem Wörterbuch bekannter Wörter.
Eingang
Die Eingabe besteht aus Wörtern in Kleinbuchstaben in alphabetischer Reihenfolge. Diese Wörter bilden das Wörterbuch der Wörter, die im entschlüsselten Text vorkommen können. Nach dem Wörterbuch folgen mehrere Eingabezeilen. Jede Zeile wird wie oben beschrieben verschlüsselt.
Das Wörterbuch enthält nicht mehr als 1.000 Wörter. Kein Wort überschreitet 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 drucken Sie sie auf die Standardausgabe. Wenn es mehrere Lösungen gibt, reicht jede aus. Wenn es keine Lösung gibt, ersetzen Sie jeden Buchstaben des Alphabets durch ein Sternchen.
Sample Input
and dick jane puff spot yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
Beispielausgabe
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******
Hier ist die Lösung. Bitte beachten Sie, dass ich bin kein Pferd im Rennen läuft für das kürzeste Bytes / Competitive - Programmierer. Ich mag nur Rätsel!
( Quelle )
quelle
Antworten:
Python 3, 423 Bytes
Liest die Eingabe von STDIN und schreibt die Ausgabe in STDOUT. Dabei wird dasselbe Format wie für die Beispieleingabe / -ausgabe verwendet.
Erläuterung
Für jede Chiffretextzeile führen wir das folgende Verfahren durch:
Wir behalten eine Karte, M , aller Buchstabenumwandlungen, die wir bereits erstellt haben (die anfangs leer sind). Wir machen das so, dass die Quellbuchstaben alle Kleinbuchstaben und die Zielbuchstaben alle Großbuchstaben sind.
Wir verarbeiten die Wörter im Chiffretext der Reihe nach. Für jedes Wort finden wir alle Wörter im Wörterbuch, die möglicherweise übereinstimmen:
Angenommen, unser Wort w ist
glpplppljjl
und M die Regel enthältj -> P
. Wir transformieren w zuerst unter Verwendung der bestehenden Regeln in M , bekommenglpplpplPPl
. Wir wandeln w dann in folgenden Regex mit Python-Geschmack um:Die Regeln der Transformation lauten wie folgt:
x
wird durch ersetzt . Hiermit wird eine benannte Erfassungsgruppe definiert , die einem einzelnen Zeichen entspricht.(?P<
x
>.)
x
x
, ersetzt . Dies ist ein Rückverweis auf den Charakter, der zuvor von der genannten Gruppe erfasst wurde .(?P=
x
)
x
Wir führen diese Transformation durch, indem wir w umkehren und dann die beiden folgenden regulären Substitutionen anwenden:
und dann das Ergebnis umkehren. Beachten Sie, dass die zuvor von M transformierten Zeichen als Großbuchstaben angezeigt werden und daher unverändert bleiben.
Wir gleichen den resultierenden regulären Ausdruck mit jedem der Wörterbuchwörter ab, wobei die Wörterbuchwörter in Großbuchstaben angezeigt werden. Beispielsweise würde der obige reguläre Ausdruck mit dem Wort übereinstimmen
MISSISSIPPI
. Wenn wir eine Übereinstimmung finden, extrahieren wir die neuen Transformationsregeln daraus und fügen sie zu M hinzu . Die neuen Transformationsregeln sind einfach die Zeichen, die von jeder Erfassungsgruppe erfasst werden. In dem obigen regex, die Gruppeg
übereinstimmtM
, dasl
GruppenspielI
, und die Gruppep
StreichhölzerS
, uns die Regeln zu gebeng -> M, l -> I, p -> S
. Wir müssen sicherstellen, dass die resultierenden Regeln konsistent sind, dh, dass keine zwei Quellbuchstaben demselben Zielbuchstaben zugeordnet sind. Andernfalls lehnen wir das Spiel ab.Wir fahren dann mit dem nächsten Wort fort und verwenden die erweiterten Transformationsregeln. Wenn wir mit diesem Verfahren alle Chiffretextwörter abgleichen können, haben wir den Text entschlüsselt. Wenn wir kein Wort mit einem der Wörterbuchwörter vergleichen können, werden wir zurückverfolgen und versuchen, die vorherigen Wörter mit verschiedenen Wörterbuchwörtern zu vergleichen. Wenn dieser Vorgang fehlschlägt, gibt es keine Lösung und wir drucken eine Reihe von Sternchen.
quelle
CJam,
6256 BytesZiemlich langsam und speicherhungrig, funktioniert aber für den Testfall mit dem Java-Interpreter.
Beispiellauf
quelle