Cryptic Kicker //

Question

Cryptic Kicker

A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same letter. Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input

The input consists of lowercase words, in alphabetical order. These words compose the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.

There are no more than 1,000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

Output

Decrypt each line and print it to standard output. If there are multiple solutions, any one will do. If there is no solution, replace every letter of the alphabet by an asterisk.

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

Sample Output

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

Here's the solution. Please note that I am not a horse running in the race for the shortest bytes / Competitive programmer. I just like puzzles!

(Source)

Answer 1

Python 3, 423 bytes

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))

Reads input from STDIN and writes output to STDOUT, using the same format as the sample input/output.

Explanation

For each line of ciphertext, we perform the following procedure:

We keep a map, M, of all the letter transformations we've already established (which is initially empty). We do it in such a way that the source letters are all lowercase and the destination letters are all uppercase.

We process the words in the ciphertext in order. For each word, we find all the words in the dictionary it might match, as follows:

Suppose that our word, w, is glpplppljjl and that M contain the rule j -> P. We first transform w using the existing rules in M, getting glpplpplPPl. We then transform w into the following python-flavored regex:

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

The rules of the transformation are as follows:

• The first occurrence of each lowercase letter, x, is replaced with (?P<x>.). This defines a named capture group, called x, that matches a single cahracter.
• Every subsequent occurrence each lowercase letter, x, is replaced with (?P=x). This is a backreference to the character previsouly captured by the named group x.

We perform this transformation by reversing w, then applying the two following regex substitutions:

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

and then reversing the result. Note that the characters previously transformed by M appear as uppercase, and therefore remain unchanged.

We match the resulting regex against each of the dictionary words, where the dictionary words appear as uppercase. For example, the above regex would match the word MISSISSIPPI. If we find a match, we extract the new transformation rules from it, and add them to M. The new transformation rules are simply the characters captured by each of the capture groups. In the above regex, the group g matches M, the group l match I, and the group p matches S, giving us the rules g -> M, l -> I, p -> S. We have to make sure that the resulting rules are consistent, that is, that no two source letters map to the same destination letter; otherwise, we reject the match.

We then proceed to the next word, using the augmented transformation rules. If we can match all the ciphertext words using this process, we have decrypted the text. If we can't match a word against any of the dictionary words, we backtrack and try to match the previous words against different dictionary words. If this process fails, there is no solution, and we print a row of asterisks.

Answer 2

CJam, 62 56 bytes

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

Quite slow and memory hungry, but works for the test case with the Java interpreter.

Example run

$ 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