How do I resolve the "Crypt Kicker" exercise proposed in "Programming Challenges (The Programming Contest Training Manual)"?

Question

"Programming Challenges (The Programming Contest Training Manual)" is probably one of the nicest exercises book on algorithms. I've resolved the first 11 exercises, but now I am stuck with "Crypt Kicker" problem:

Crypt 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 a line containing an integer n, followed by n lowercase words, one per line, in alphabetical order. These n 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 6
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 ...

What strategy should I to take in order to resolve this exercise? I was thinking to a classic and brutish backtracking solution, but I am trying avoid that until I find something more intelligent.

PS: This is not homework related, I am just trying to improve my overall skills.

Answer 1

KeyArray will hold the replacement table.

• Start with an empty KeyArray, this is version 0

• Match longest encrypted word to longest dictionary word and add to KeyArray (if there are two longest, pick any), this is version 1.

• Decrypt some letters of the next longest crypted word.

• Check if the decrypted letters match the letter in the same position in any dictionary word of the same length.
• If none matches, go back to version 0 and try another word.

• If some letters match, add the rest of the letters to KeyArray, this is version 2.

• Decrypt some letters of the next longest crypted word.

• Check if the decrypted letters match the letter in the same position in any dictionary word.
• If none matches, go back to version 1 and try another word
• If some letters match, add the rest of the letters to KeyArray, this is version 3.

Repeat until all words are decrypted.

If at version 0 none of the longest words creates a partial decrypt in shorter words, very probably there is no solution.

Answer 2

A minor optimization could be done by enumerating possibilities before the backtracking run. 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))

Output:

{'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'])}

If you have some single-element possibilities, you can eliminate them from the input and rerun the algorithm.

EDIT: Switched to set instead of list and added printing code.