Инверсия бита. Python

Question

Есть следующая задача:

 Числовые ребусы, решение реализовано на python.
  1. Каждой строчной букве латинского алфавита сопоставляется двоичный разряд, начиная с младшего a - 0-й, b - 1-й, ... z - 25-й.
  2. Чтобы произнести букву производится инверсия соответствующей букве бита в специальной переменной W в новое значение W в десятичной
 системе. Определение: инверсия бита j в числе x - изменение j-го
 разряда числа x в двоичной системе на противоположное (0 становится 1,
 1 становится 0). Пример: число 15 (1111) после инверсии бита 2
 становится равным числу 11 (1011).
  3. Также для пробела используется 26-й разряд. Значение переменной W перед произнесением первого символа равно 0. Напишите программу,
 которая переведет числовой ребус. Примечание: пробел используется
 наравне с буквами латинского алфавита - для пробела не существует
 дополнительных ограничений и условий для его произнесения.
 
 
 Формат ввода. В первой строке содержится единственное число n (1 <= n
 <= 500) - количество сказанных чисел. Во второй строке расположено n
 целых чисел Wi (0 <= Wi < 2**27) - значение переменной W после
 произнесения i-го символа.
 
 Формат вывода. В единственной строке выведите n символов - строчные
 буквы латинского алфавита или пробел в порядке произнесения.
 
 Пример 1
 
 Ввод:
 
 5
 
 1 2049 2305 2309 2325
 
 Вывод:
 
 alice
 
 Пример 2
 
 Ввод:
 
 3
 
 1 3 2
 
 Вывод:
 
 aba
 
 Примечания
 
 Рассмотрим детально первый пример входных данных:
  1. Начальное значение переменной W равно 0 (по условию задачи)
  2. Сначала произносится символ a,поэтому значение переменной W становится равным 2**0 = 1.
  3. Затем произносится символ l, которому соответствует 11-й разряд, поэтому значение переменной W становится равным 2**0 + 2**11 = 2049
  4. Далее следует символ i (8-й разряд), поэтому W = 2**0 + 2**11 + 2**8 = 2305
  5. Предпоследним символом является c (2-й разряд) - W = 2**0 + 2**11 + 2**8 + 2**2 = 2309
  6. Завершает фразу символ e (4-й разряд) - итоговое значение W равно 2**0 + 2**11 + 2**8 + 2**2 +2**4 = 2325
 
 Во втором примере последовательность W следующая:
 
  1. После первого символа a значение W = 2**0 = 1
  2. После символа b значение W = 2**0 + 2**1 = 3
  3. После произнесения второго символа значение W будет равно 2**1 = 2, так как 0-й бит инвертируется из 1 в 0

Мною был написан код, позволяющий решить ребус из первого примера, но неработающий со вторым примером. И из условия мне так и не ясно в каких случаях и каким образом работает инверсия.

from math import log2

n = int(input())
el_list = list(map(int, input().split()))
letter_dict = {
    0:'a', 1:'b', 2:'c', 3:'d', 4:'e', 5:'f', 6:'g', 7:'h',
    8:'i', 9:'j', 10:'k', 11:'l', 12:'m', 13:'n', 14:'o',
    15:'p', 16:'q', 17:'r', 18:'s', 19:'t', 20:'u', 21:'v',
    22:'w', 23:'x', 24:'y', 25:'z', 26:' ',
}
str_result = ''

sum_letter = el_list[0]
first_letter = int(log2(sum_letter))
str_result += letter_dict[first_letter]

for i in range(1, n):
    diff = el_list[i] - sum_letter
    num = int(log2(diff))
    str_result += letter_dict[num]
    sum_letter += 2**num

print(str_result)

Answer 1

Я только учусь, и вчера в Яндекс контекст мне попалась эта же задача. Решил ее так:

from math import log2


n = int(input())
el_list = list(map(int, input().split()))
letter_dict = {
    0:'a', 1:'b', 2:'c', 3:'d', 4:'e', 5:'f', 6:'g', 7:'h',
    8:'i', 9:'j', 10:'k', 11:'l', 12:'m', 13:'n', 14:'o',
    15:'p', 16:'q', 17:'r', 18:'s', 19:'t', 20:'u', 21:'v',
    22:'w', 23:'x', 24:'y', 25:'z', 26:' ',
}
list_result = []
result = ''
sum_letter = 0
list_result.append(letter_dict[int(log2(el_list[0]))])
for i in range(1, n):
    diff = el_list[i] - el_list[sum_letter]
    if diff < 0:
        diff = abs(diff)
    sum_letter += 1
    list_result.append(letter_dict[int(log2(diff))])
for letter in list_result:
    result += letter
print(result)

Примеры:

Ввод

12
4 132 148 262292 262164 262420 393492 393476 67502340 67502336 67502337 68026625

Вывод

cheshire cat

Answer 2

Чтобы заставить работать ваш код достаточно добавить abs:

> num = int(log2(diff))
---
< num = int(log2(abs(diff)))

Получившееся решение опирается на точность вычисления log2, которая не гарантирована. Есть шанс что будет напечатана предыдущая буква.

Операция ^ подходит чтобы выяснить какие биты в двух числах различны. В условиях задачи n ^ prev выделит изменённый (инвертированный) бит между текущим и предыдущим числом. Номер бита указывает на нужную букву. Чтобы не вычислять номер бита пойдём на хитрость: в словаре запомним не номера битов, а степени двоек с этими номерами.

import string


bits = {2 ** i: c for i, c in enumerate(string.ascii_lowercase + ' ')}

input()
prev = 0
for n in map(int, input().split()):
    print(bits[n ^ prev], end='')
    prev = n
print()

БЛОГ НА HUSL

Инверсия бита. Python

Ответы (2 шт):