#!/usr/bin/python

import glob
import os
import sys

def cmp (a, b):
    la = len (a)
    lb = len (b)
    if la < lb:
        return -1
    elif la == lb:
        return 0
    else:
        return 1

def frequencyHash (word):
    ret = []
    found = dict ()
    code = 0
    for char in word:
        try:
            ret.append (found [char])
        except KeyError:
            ret.append (str (code))
            found [char] = str (code)
            code += 1

    return "".join (ret)

class DescramblerWalker (object):
    def __init__ (self, dictionary, scrambled_words, scrambled_hashes):
        self.dictionary = dictionary
        self.scrambled_hashes = scrambled_hashes
        self.scrambled_words = scrambled_words
        self.table = {" ": " "}
        self.inverted_table = {" ": " "}
        self.stack = list ()

    def advance (self, word, scrambled_word, dictionary_index):
        # state e' una tabella che mappa i caratteri encodati a quelli decodati
        state = dict ()
        # inverted_state e' il contrario di state, mappa caratteri decodati a
        # quelli encodati. viene usata perche' un carattere encodato puo
        # matchare piu caratteri non encodati. 
        inverted_state = dict ()
        for i in range (0, len (word)):
            # carattere ennesimo della parola non encodata
            char = word [i]
            # carattere ennesimo della parola encodata
            scrambled_char = scrambled_word [i]
            try:
                # se il carattere encodato e' presente nella tabella (lo abbiamo
                # incontrato prima) il valore decodato deve essere uguale a
                # quello che abbiamo stabilito precedentemente
                translated_char = self.table [scrambled_char]
                if translated_char != char:
                    return False
            except KeyError:
                # il carattere encodato e' stato incontrato ora per la prima
                # volta, lo memorizziamo nel dizionario dei caratteri matchati
                # in questo stato
                state [scrambled_char] = char

            try:
                inverted_char = self.inverted_table [char]
                if inverted_char != scrambled_char:
                    return False
            except KeyError:
                inverted_state [char] = scrambled_char

        self.stack.append ((state, inverted_state, dictionary_index))
        self.table.update (state)
        self.inverted_table.update (inverted_state)

        return True

    def backtrack (self):
        last_state, last_inverted, last_index = self.stack.pop ()
        for scrambled_char in last_state:
            del self.table [scrambled_char]

        for char in last_inverted:
            del self.inverted_table [char]

        return last_index

    def getCandidateDictionary (self, scrambled_word):
        hash = self.scrambled_hashes [scrambled_word]
        ret = self.dictionary [hash]
        if len (hash) > 1:
            try:
                ret = ret + self.dictionary [hash [:-1]]
            except KeyError:
                pass

        return ret

    def walk (self):
        input_index = 0
        input_len = len (self.scrambled_words)

        scrambled_word = self.scrambled_words [input_index] 
        candidate_dictionary = self.getCandidateDictionary (scrambled_word)
        dictionary_index = 0
        dictionary_len = len (candidate_dictionary)
        word = candidate_dictionary [dictionary_index]

        # run until the whole input has been parsed
        while True:
            if self.advance (word, scrambled_word, dictionary_index):
                input_index += 1
                if input_index == input_len:
                    return True

                scrambled_word = self.scrambled_words [input_index]
                candidate_dictionary = \
                    self.getCandidateDictionary (scrambled_word)
                dictionary_index = 0
                dictionary_len = len (candidate_dictionary)
                word = candidate_dictionary [dictionary_index]
            else:
                dictionary_index += 1
                if dictionary_index == dictionary_len:
                    # we need to backtrack
                    while True:
                        # go back one input symbol
                        if input_index == 0:
                            return False

                        input_index -= 1
                        # clear the chars entered during the backtraced state
                        scrambled_word = self.scrambled_words [input_index]
                        candidate_dictionary = \
                            self.getCandidateDictionary (scrambled_word)
                        dictionary_len = len (candidate_dictionary)
                        dictionary_index = self.backtrack () + 1
                        if dictionary_index < dictionary_len:
                            break

                word = candidate_dictionary [dictionary_index]

class Descrambler (object):
    def __init__ (self):
        words = list ()

    def loadDictionaryFile (self, filename):
        fi = file (filename)
        for word in fi.readlines ():
            word = word.rstrip ()
            if not word:
                continue

            try:
                self.codes [frequencyHash (word)].append (word)
            except KeyError:
                continue

    def loadFile (self, filename):
        fi = file (filename)
        self.loadText (fi.read ().rstrip ())
        fi.close ()

    def loadText (self, text):
        self.text = text
        self.scrambled_hashes = dict ()
        self.scrambled_words = text.split (" ")
        self.scrambled_words.sort (cmp, reverse=True)

        self.codes = dict ()
        for word in self.scrambled_words:
            hash = frequencyHash (word)
            self.scrambled_hashes [word] = hash
            self.codes.setdefault (hash, [])
            self.codes.setdefault (hash[:-1], [])


    def decodeText (self):
        walker = DescramblerWalker (self.codes, self.scrambled_words, self.scrambled_hashes)
        ret = []
        if walker.walk ():
            for char in self.text:
                ret.append (walker.table.get (char, "UNKNOWN"))

            return "".join (ret)
        else:
            return "miserably failed"
        

def main ():
    inputfile = sys.argv[2]
    dict_files = glob.glob (os.path.join (sys.argv[1], "ITALIANO.?"))
    descrambler = Descrambler ()
    descrambler.loadFile (inputfile)
    for filename in dict_files:
        descrambler.loadDictionaryFile (filename)

    print descrambler.decodeText ()

if __name__ == '__main__':
    sys.exit (main ())