Шестнадцатеричный FizzBuzz в Python

Question

Я уверен, что для большинства из вас должно быть известно, что такое FizzBuzz.

Для тех, кто не знает, что я здесь заявляю. Вот что FizzBuzz является:

Напишите программу, которая печатает числа от 1 до 100. Но для кратных три печати «Fizz» вместо числа и кратных пяти печати «Buzz». Для чисел, кратных как трех, так и пяти, напечатайте «FizzBuzz».

Для большинства из вас это может быть очень легко создать.

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

Я нашел этот питон код интересное:

m = [None, "Fizz", "Buzz", "FizzBuzz"] 
v = 0x30490610 
for i in range(1, 101): 
    j = v & 3 
    print(m[j] if j else i) 
    v = v >> 2 | j << 28 

Результат:

1 
2 
Fizz 
4 
Buzz 
Fizz 
7 
8 
Fizz 
Buzz 
11 
Fizz 
13 
14 
FizzBuzz 
16 
17 
Fizz 
19 
Buzz 
Fizz 
22 
23 
Fizz 
Buzz 
26 
Fizz 
28 
29 
FizzBuzz 
31 
32 
Fizz 
34 
Buzz 
Fizz 
37 
38 
Fizz 
Buzz 
41 
Fizz 
43 
44 
FizzBuzz 
46 
47 
Fizz 
49 
Buzz 
Fizz 
52 
53 
Fizz 
Buzz 
56 
Fizz 
58 
59 
FizzBuzz 
61 
62 
Fizz 
64 
Buzz 
Fizz 
67 
68 
Fizz 
Buzz 
71 
Fizz 
73 
74 
FizzBuzz 
76 
77 
Fizz 
79 
Buzz 
Fizz 
82 
83 
Fizz 
Buzz 
86 
Fizz 
88 
89 
FizzBuzz 
91 
92 
Fizz 
94 
Buzz 
Fizz 
97 
98 
Fizz 
Buzz 

Мой вопрос заключается в том, как он это делает?

Я понимаю, что переменная 'v' содержит шестнадцатеричное значение.

Как это достигается при создании FizzBuzz? Как бы вы объяснили это новичку?

Answer 1

Во-первых, мы наблюдаем, что шаблон FizzBuzz является циклическим с длиной 15, начиная с n % 3 = (n + 15) % 3 и n % 5 = (n + 15) % 5.

Если n делится на 3 и/или 5 может быть сохранено с двумя битами информации: 00 для них, 01 для деления на 3, 10 для делимых на 5 и 11 для делимых на 3 и 5.

в FizzBuzz "ответы" для чисел от 1 до 15 являются, справа налево:

11 00 00 01 00 10 01 00 00 01 10 00 01 00 00.

Обратите внимание, что каждый третья битовая пара имеет правильный бит, и каждая пятая битовая пара имеет установленный левый бит. Крайняя правая пара соответствует числу 1, а крайняя левая пара соответствует числу 15. Это, возможно, более ясно, чтобы отделить левые биты и правые биты:

v5: 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 
v3: .1 .0 .0 .1 .0 .0 .1 .0 .0 .1 .0 .0 .1 .0 .0 
v5|v3: 11 00 00 01 00 10 01 00 00 01 10 00 01 00 00 

Если преобразовать эту строку битов в hexadecimal, мы получаем магическую константу v из вашего фрагмента: 0x30490610.

Мы можем извлечь нижние два бита v с выражением j = v & 3, так как число 3 имеет нижние два бита, а остальные не установлены. (Это «побитовое И» -оператором из Python.)

Мы можем цикл вокруг 2 * 15 = 30 бит путем сдвига v два бита в правую v >> 2, а затем добавить два бита в другом конце, (v >> 2) | (j << 28). (Это операторы сдвига влево и вправо Python, которые также работают поразмерно.)

Таким образом, v можно рассматривать как «очередь», содержащую 2-битные элементы, каждый элемент, соответствующий «правильному ответу FizzBuzz», на один из следующих 15 номеров, подлежащих обработке. Как только элемент j выталкивается из этой очереди, он выталкивается на другой конец, поэтому он готов снова через 15 итераций.

Один последний момент: Синтаксис print(m[j] if j else i) означает «Если j не falsy значение, таких как 0, а затем распечатать m[j], в противном случае, печать i.» Так как m[1], m[2] и m[3] содержат правильные строки, соответствующие нашему 2-битовому представлению ответов FizzBuzz, а j всегда находится в диапазоне от 0 до 3, выход правильный.

В качестве упражнения попробуйте изменить v на 0x39999999 и посмотреть, сможете ли вы объяснить его поведение. (Подсказка: 9 в шестнадцатеричном формате 10 01 в двоичном формате.)

Обновление: Вот вариант программы. Я заменил шестнадцатеричное значение v на явную очередь q ответов, а страшно выглядящий v = v >> 2 | j << 28 был заменен поп-файлом спереди и с обратной связью, q.append(q.pop(0)).

q = ['', '', 'Fizz', '', 'Buzz', 
    'Fizz', '', '', 'Fizz', 'Buzz', 
    '', 'Fizz', '', '', 'FizzBuzz'] 
for i in range(1, 101): 
    print(q[0] or i) 
    q.append(q.pop(0)) 

Мы можем также добавить отдельный fizz и buzz очереди:

f = ['', '', 'Fizz'] 
b = ['', '', '', '', 'Buzz'] 
for i in range(1, 101): 
    print((f[0] + b[0]) or i) 
    f.append(f.pop(0)) 
    b.append(b.pop(0)) 

Поскольку '' является falsy значение, (f[0] + b[0]) or i напечатает число i всякий раз, как f[0] и b[0] пустая строка.