Задача: Расстояние Хэмминга

категория: Python
Еще одна интересная задача по питону - вычислить расстояние Хэмминга между двумя целыми числами в бинарном представлении. Как раньше я не надыбал этот ресурс http://www.checkio.org/, все задачки оттуда. Получаем два целых положительных числа в десятичной форме (n, m). Нужно посчитать дистанцию Хэмминга между ними в бинарной форме:
117 = 0 1 1 1 0 1 0 1
17 = 0 0 0 1 0 0 0 1
H = 0+1+1+0+0+1+0+0 = 3
Сразу на ум пришло перевести из десятичной формы в двоичную и засунуть в список, при этом отрезать "0b". Дальше узнать какой список меньше и набить его нулями в начале. Ну а потом сравнить и подсчитать сколько несовпадений по одинаковым индексам двух списков.
def checkio(n, m):
    # Преобразование в список
    def get_list(el):
        bin_el = list(bin(el))
        el = bin_el[2:]
        return el
    # Добавление нулей в начало меньшего списка    
    def add_0(n, m):
        len_insert = len(n) - len(m)
        for i in range(len_insert):
            m.insert(0, '0')
#    
    n = get_list(n)
    m = get_list(m)
    res = 0
#    
    if len(n) > len(m):
        add_0(n, m)
    elif len(n) < len(m):
        add_0(m, n)
#
    for i in range(len(n)):
        if n[i] != m[i]:
            res += 1
#            
    return res
#
if __name__ == '__main__':
    #Тесты
    assert checkio(117, 17) == 3, "First example"
    assert checkio(1, 2) == 2, "Second example"
    assert checkio(16, 15) == 5, "Third example"


blog comments powered by Disqus