Cryptic Kicker

Une méthode courante mais peu sûre de chiffrement du texte consiste à permuter les lettres de l'alphabet. En d'autres termes, chaque lettre de l'alphabet est systématiquement remplacée dans le texte par une autre lettre. Pour garantir que le cryptage est réversible, deux lettres ne sont pas remplacées par la même lettre. Votre tâche consiste à décrypter plusieurs lignes de texte codées, en supposant que chaque ligne utilise un ensemble différent de remplacements et que tous les mots du texte décrypté proviennent d'un dictionnaire de mots connus.

Contribution

L'entrée se compose de mots en minuscules, par ordre alphabétique. Ces mots composent le dictionnaire des mots qui peuvent apparaître dans le texte décrypté. Après le dictionnaire se trouvent plusieurs lignes d'entrée. Chaque ligne est cryptée comme décrit ci-dessus.

Le dictionnaire ne contient pas plus de 1 000 mots. Aucun mot ne dépasse 16 lettres. Les lignes cryptées ne contiennent que des lettres minuscules et des espaces et ne dépassent pas 80 caractères.

Production

Déchiffrez chaque ligne et imprimez-la sur une sortie standard. S'il y a plusieurs solutions, n'importe qui fera l'affaire. S'il n'y a pas de solution, remplacez chaque lettre de l'alphabet par un astérisque.

Exemple d'entrée

and dick jane puff spot yertle

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

Exemple de sortie

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

Voici la solution. Veuillez noter que je ne suis pas un cheval courant dans la course pour les octets les plus courts / Programmeur compétitif. J'aime juste les puzzles!

( Source )

Python 3, 423 octets

import sys,re
S=re.sub
D,*L=sys.stdin.read().split('\n')
def f(W,M=[],V="",r=0):
 if len({d for(s,d)in M})==len(M):
  if[]==W:return V.lower()
  for d in D.split():p='([a-z])(?%s.*\\1)';m=re.match(S(p%'=',')\\1=P?(',S(p%'!',').>\\1<P?(',W[0].translate(dict(M))[::-1]))[::-1]+'$',d.upper());r=r or m and f(W[1:],M+[(ord(s),m.group(s))for s in m.groupdict()],V+d+" ")
  return r
for l in L:print(f(l.split())or S('\w','*',l))

Lit l'entrée de STDIN et écrit la sortie dans STDOUT, en utilisant le même format que l'échantillon d'entrée / sortie.

Explication

Pour chaque ligne de texte chiffré, nous effectuons la procédure suivante:

Nous gardons une carte, M , de toutes les transformations de lettres que nous avons déjà établies (qui est initialement vide). Nous le faisons de telle manière que les lettres source sont toutes en minuscules et les lettres de destination sont toutes en majuscules.

Nous traitons les mots dans le texte chiffré dans l'ordre. Pour chaque mot, nous trouvons tous les mots du dictionnaire auxquels il peut correspondre, comme suit:

Supposons que notre mot, w , soit glpplppljjlet que M contienne la règle j -> P. Nous transformons d'abord w en utilisant les règles existantes dans M , en obtenant glpplpplPPl. Nous transformons ensuite w en l'expression rationnelle de type python suivante:

(?P<g>.)(?P<l>.)(?P<p>.)(?P=p)(?P=l)(?P=p)(?P=p)(?P=l)PP(?P=l)

Les règles de la transformation sont les suivantes:

• La première occurrence de chaque lettre minuscule,, xest remplacée par . Cela définit un groupe de capture nommé, appelé , qui correspond à un seul cahracter.(?P<x>.)x
• Chaque occurrence suivante, chaque lettre minuscule,, xest remplacée par . Il s'agit d'une référence au personnage précédemment capturé par le groupe nommé .(?P=x)x

Nous effectuons cette transformation en inversant w , puis en appliquant les deux substitutions d'expression régulière suivantes:

s/([a-z])(?!.*\1)/)>\1<P?(/
s/([a-z])(?=.*\1)/)\1=P?(/

puis inverser le résultat. Notez que les caractères précédemment transformés par M apparaissent en majuscules et restent donc inchangés.

Nous comparons l'expression régulière résultante à chacun des mots du dictionnaire, où les mots du dictionnaire apparaissent en majuscules. Par exemple, l'expression régulière ci-dessus correspondrait au mot MISSISSIPPI. Si nous trouvons un match, on extrait les nouvelles règles de transformation de celui - ci, et les ajoute à M . Les nouvelles règles de transformation sont simplement les caractères capturés par chacun des groupes de capture. Dans l'expression régulière ci-dessus, les gcorrespondances de groupe M, la lcorrespondance de groupe Iet les pcorrespondances de groupe S, nous donnant les règles g -> M, l -> I, p -> S. Nous devons nous assurer que les règles résultantes sont cohérentes, c'est-à-dire qu'aucune lettre source ne correspond à la même lettre de destination; sinon, nous rejetons le match.

Nous passons ensuite au mot suivant, en utilisant les règles de transformation augmentées. Si nous pouvons faire correspondre tous les mots chiffrés en utilisant ce processus, nous avons déchiffré le texte. Si nous ne pouvons pas faire correspondre un mot avec l'un des mots du dictionnaire, nous revenons en arrière et essayons de faire correspondre les mots précédents avec différents mots du dictionnaire. Si ce processus échoue, il n'y a pas de solution et nous imprimons une ligne d'astérisques.

CJam, 62 56 octets

qN%Sf/(f{\:C,m*{C..+`Sa`m2/Q|z_''f-Qf|=},C:,'*f*a+0=S*N}

Assez lent et gourmand en mémoire, mais fonctionne pour le cas de test avec l'interpréteur Java.

Exemple d'exécution

$ cat input; echo
and dick jane puff spot yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
$ time cjam kicker.cjam < input
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

real    5m19.817s
user    6m41.740s
sys     0m1.611s