cipher.py

#!/usr/bin/env python3

import re
import itertools


def main():
    phrase = input("")
    numknown = int(input(""))
    known = {}
    for i in range(numknown):
        c = input("")
        known[c[1]] = c[0]

    # Sort wordlist by length
    wordlist = []
    f = open("words", "r")
    words = f.read().split("\n")
    f.close()
    for w in words:
        while len(wordlist) <= len(w):
            wordlist.append([])
        wordlist[len(w)].append(w)

    # Create list of possible alternatives for each word
    words = re.split(r"\W+", phrase)
    alternatives = []
    for w in words:
        if len(w) >= len(wordlist):
            return 1
        possible = []
        for a in wordlist[len(w)]:
            for c in range(len(a)):
                if w[c] in known.keys() and known[w[c]] != a[c]:
                    break
            else:
                possible.append(a)
        alternatives.append(possible)

    # Check for combinations of alternatives that do not contradict
    ref = "".join(words)
    for a in itertools.product(*alternatives):
        cipher = {}
        comb = "".join(list(a))
        for c in range(len(comb)):
            if ref[c] in known.keys() and known[ref[c]] != comb[c]:
                break
            elif ref[c] in cipher.keys() and cipher[ref[c]] != comb[c]:
                break
            cipher[ref[c]] = comb[c]
        else:
            # SUCCESS
            output = phrase
            for i in range(len(words)):
                output = output.replace(words[i], list(a)[i])
            print(output)


if __name__ == "__main__":
    main()