#
#
#
#Alice Zhang
#Huffman encoding
#HW#9

def main():
    fileName = intro()
    original = read_file(fileName)
    parts = subtractStuff(original)
    text = parts[0]
    listKey = eval(parts[1])
    list2 = eval(parts[2])
    leftOver =parts[3]
    string = decode1(text, leftOver)
    translated = ''
    translated = decode2(string, listKey, list2, translated)
    print "translated is " , translated
    f = open(fileName+ ".DECODED", 'w')
    f.write(translated)
    print "Output written to file: " + fileName + '.DECODED'

def intro():
    fileName = raw_input("Enter name of file to be UNcompressed (must end in .HUFFMAN)")
    return fileName

def read_file(fileName):
    text_file = open(str(fileName))
    original = text_file.read()
    text_file.close()
    return original

def subtractStuff(original):
    leftOver=original[0]
    original = original[1:]
    breakPoint = original.index('\n')
    listKey = original[:breakPoint]
    original = original[breakPoint+1:]
    breakPoint = original.index('\n')
    list2 = original[:breakPoint]
    original = original[breakPoint:]
    return [original, listKey, list2, leftOver]

def decode(original):
    if original == '': return ''
    else: return numToBinary(ord(original[0]))+decode(original[1:])

def decode1(text, leftOver):
    text = text[:-int(leftOver)]
    print text
    return decode(text)


def decode2(string, listKey, list2, translated):
    if string == '': return ''
    else:
        for n in range(1,8):
            list1 = []
            if str(string[:n]) in listKey:
                translated = translated + str(list2[listKey.index(string[:n])])
                print "translated", translated
                list1.append(n)
                print "list1 is ", list1
                break
            print "blah is", list1[0]
        return decode2(string[(list1[0]):], listKey, list2, translated)

def numToBinary(N):
    """convert base-10 N to binary"""
    if N==0: return ''
    elif N%2==1: return numToBinary(N/2) +'1'
    else:
        return numToBinary(N/2) +'0'