import string

A = ord('A')
Z = ord('Z')

DICTFILE = 'words.txt'

def encode(text, key):
    """ Encode text by shifting each letter key times """
    encodedText = ""
    for letter in text.upper():

        # only alter letters
        if letter not in string.uppercase:
            encodedText += letter
            continue

        # find ordinal of current letter and add key to it
        # if new value is out of range adjust until back in range
        value = ord(letter)
        value += key
        while value > Z:
            value = A + value - Z - 1
        while value < A:
            value = Z - (A - value) + 1
        encodedText += chr(value)
        
    return encodedText

def crack(message):
    """ Decode a message by trying all possible keys and determining
        which key results in the most words in the dictionary """

    # Open file containing a list of words and store them in a dictionary
    words = open(DICTFILE, 'r')
    dictionary = {}
    for line in words:
        dictionary[line.lower().strip()] = 0  # convert all to lowercase

    # convert all words to lowercase so they match those in the dictionary
    encodedWords = message.lower().split()
    results = []

    # try all possible keys
    for key in range(26):
        numberFound = 0
        for word in encodedWords:
            testWord = encode(word, -key).lower()  # decode current word
            if dictionary.has_key(testWord):
                numberFound += 1
        results.append(numberFound)

    # find maximum number of valid words and then find the index with that value
    mostFound = max(results)
    bestKey = results.index(mostFound)
    return bestKey, encode(message, -bestKey)

if __name__ == '__main__':
    ENCODE = '0'
    DECODE = '1'
    CRACK  = '2'

    operation = None
    operation = raw_input("Encode, Decode, or Crack? (%s=encode,%s=decode, %s=crack)\n?"%(ENCODE,DECODE, CRACK))
    text = raw_input("Enter text\n?")
    if operation == ENCODE:
        key = int(raw_input("Enter key\n?"))
        print encode(text, key)
    elif operation == DECODE:
        key = int(raw_input("Enter key\n?"))
        print encode(text, -key)
    elif operation == CRACK:
        key, msg = crack(text)
        print 'Cracked message:\n%s'%msg
        print 'Key = %i'%key
    else:
        print "Error"