# Huffman Coding Algorithm
import math


def HuffmanEncoding(data):
    assert(round(sum(data.values())) == 1.0)

    if(len(data) == 2):
        return dict(zip(data.keys(), ['0', '1']))

    probabilityList = data.copy()

    a1, a2 = lowestProbabilityPair(data)
    p1, p2 = probabilityList.pop(a1), probabilityList.pop(a2)
    probabilityList[a1+a2] = p1 + p2

    c = HuffmanEncoding(probabilityList)
    combined_a1a2 = c.pop(a1+a2)
    c[a1], c[a2] = combined_a1a2+'0', combined_a1a2+'1'

    return c


def lowestProbabilityPair(data):
    assert(len(data) >= 2)
    sorted_p = sorted(data.items(), key=lambda x: x[1], reverse=True)
    return sorted_p[-2][0], sorted_p[-1][0]


def descendingOrder(data):
    sorted_p = sorted(data.items(), key=lambda x: x[1], reverse=True)
    return sorted_p


def calculateEntropy(data):
    assert(round(sum(data.values())) == 1.0)
    ent = []
    for k, v in data.items():
        data[k] = float(v)
        ent.append(data[k] * math.log2(1/data[k]))
    entropy = sum(ent)
    return round(entropy, 3)


def averageCodeLength(data, probability):
    x = []
    y = []
    z = []
    for k, v in data.items():
        data[k] = len(v)
        x.append(data[k])
    for k, v in probability.items():
        probability[k] = float(v)
        y.append(probability[k])
    for i in range(0, len(data)):
        z.append(x[i]*y[i])
    codeLength = sum(z)
    return round(codeLength, 3)


def codeRate(entropy, codeLength):
    assert(round(sum(data.values())) == 1.0)
    efficiency = (entropy/codeLength)
    return round(efficiency, 3)


data = {}
length = int(input("Enter the number of symbols: "))
print("\n")
for i in range(length):
    symbol = "s" + str(i+1)
    probability = float(input("Enter the probability for " + symbol + ": "))
    data[symbol] = probability

s = dict(descendingOrder(data))
final = HuffmanEncoding(data)
print("The Huffman Encoding for given symbols is: \n", HuffmanEncoding(data))

hauffmanEntropy = calculateEntropy(data)
print("The Entropy is : ", hauffmanEntropy)

hauffmanCodeLength = averageCodeLength(final, s)
print("Average Code Length is : ", hauffmanCodeLength)

hauffmanCodeRate = codeRate(hauffmanEntropy, hauffmanCodeLength)
print("The Code Efficiency is : ", hauffmanCodeRate*100, "%")
print("The Hauffman Code Redundancy is : ",
      round((1-hauffmanCodeRate)*100, 3), "%")