12
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ Please relax your >input< constraints to something that is applicable for each language. For example a lot of languages will hate, and not appreciate that the format starts with a 6. I'd suggest leaving the format totally unspecified, and only say that the input is a list of words and a list of lines to encrypt. \$\endgroup\$ – orlp Aug 8 '15 at 11:56
  • \$\begingroup\$ Okay, There you go! \$\endgroup\$ – Dhruv Ramani Aug 8 '15 at 11:56
  • 1
    \$\begingroup\$ Are there runtime constraints to this? Can I simply iterate through every possible replacement combination, until one works (which would likely take years to finish)? \$\endgroup\$ – Nathan Merrill Aug 8 '15 at 14:27
  • \$\begingroup\$ @NathanMerrill Do that, and if it's gonna take years, just print it in the star form. Vihan, It's not a duplicate, please read the question properly. \$\endgroup\$ – Dhruv Ramani Aug 8 '15 at 17:33
  • \$\begingroup\$ Can we just output the words or do we have to join them? \$\endgroup\$ – Downgoat Aug 9 '15 at 0:21
3
+25
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.