Public feed
#378567
#!/usr/bin/pythonimport globimport osimport sysdef cmp (a, b): la = len (a) lb = len (b) if la < lb: return -1 elif la == lb: return 0 else: return 1def 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 ())