import math

def get_parity_groups(code):
    parity_bits_am = len(code).bit_length()

    groups = {}

    for group in range(parity_bits_am):
        bit = 2 ** group
        for pos in range(len(code)):
            if (pos + 1) & bit:
                if len(groups) >= group + 1:
                    groups[bit].append(pos)
                else:
                    groups[bit] = [pos]

    return groups

def get_parity(to_encode, group):
    gr_str = ""
    for el in group:
        gr_str += to_encode[el]
    return str(str.count(gr_str, "1") % 2)

def hammington_encode(to_encode):
    def get_code(to_encode, groups):
        parity_bits_am = len(to_encode).bit_length()

        code = []
        for i in range(len(to_encode) + parity_bits_am):
            code.append("0")

        for parity_bit in range(parity_bits_am):
            parity_val = 2 ** parity_bit

            group = groups[parity_val]

            code[parity_val - 1] = get_parity(to_encode, group)



        to_fill_with = list(to_encode)
        i = 1
        while(len(to_fill_with) > 0):
            i += 1
            if math.log2(i).is_integer():
                continue
            el = to_fill_with.pop()
            code[i - 1] = el

        return "".join(code)


    groups = get_parity_groups(to_encode)
    code = get_code(to_encode, groups)
    return code

def hammington_decode(to_decode):
    def get_stripped(to_decode):
        stripped = ""
        parity_bits_am = len(to_decode).bit_length()

        for i in range(len(to_decode)):
            if math.log2(i + 1).is_integer():
                continue
            stripped += to_decode[i]
        return stripped

    def code_check(to_decode, stripped, groups):
        wrong_bit = 0

        parity_bits_am = len(to_decode).bit_length()
        for parity_bit in range(parity_bits_am):
            parity_val = 2 ** parity_bit

            group = groups[parity_val]

            check_val = to_decode[parity_val - 1]
            true_val = get_parity(stripped, group)

            if check_val != true_val:
                wrong_bit |= parity_val
        return wrong_bit

    stripped = get_stripped(to_decode)
    groups = get_parity_groups(stripped)
    wrong_bit = code_check(to_decode, stripped, groups)
    if wrong_bit != 0:
        new_code = list(to_decode)
        print("Wrong bit was", wrong_bit, "inversing it.")
        if new_code[wrong_bit - 1] == "1":
            new_code[wrong_bit - 1] = "0"
        else:
            new_code[wrong_bit - 1] = "1"
        to_decode = "".join(new_code)
    return get_stripped(to_decode)

c = hammington_encode("1001")
print(c)
print(hammington_decode(c))