A breakdown of my condensed, obfuscated fizzbuzz for educational purposes

fizzbuzz_explained.py

#!/usr/bin/env python

__author__ = 'Adam R. Smith (adam@adamia.com)'

# Loop from 0 through 99. Need zero-based for the later cyclic bit-shifting.
for x in xrange(100):
    # There are 4 possible outputs on each iteration of the loop.
    # 4 possibilities requires 2 bits to store (0, 1, 2, 3):
    # 0 == 00b == the number (x + 1)
    # 1 == 01b == 'Fizz' when a multiple of just 3
    # 2 == 10b == 'Buzz' when a multiple of just 5
    # 3 == 11b == 'FizzBuzz' when a multiple of 15
    output_candidates = [x + 1, 'Fizz', 'Buzz', 'FizzBuzz']

    # Mathematically, the output must repeat itself in sets of 15.
    # So fizzbuzz from 1-15 is the same as 16-30, and 31-45, etc.
    # We can encode all possible outputs as a sequence of 15 2-bit numbers, and
    # store the entire sequence in a 32-bit integer (15*2 == 30).
    # The output for "1" is "1", "2" is "2", and "3" is "Fizz".
    # Mapping these to indexes into the output_candidates list above gives:
    # 1 -> 0 -> 00b
    # 2 -> 0 -> 00b
    # 3 -> 1 -> 01b
    # So a binary string representing the first 3 outputs, in order of least
    # significant digit to most significant, would be:
    # 010000 (00b, then 00b to its left, then 01b to its left.)
    # Encoding the whole sequence of 15 gives us:
    output_indexes = 0b110000010010010000011000010000
    # A shorter way to represent this number is in hexadecimal: 0x30490610

    # Now, we want to repeat this pattern by retrieving 2 bits at a time 15x.
    # The easy way to do that, is to take the remainder of x/15, "x mod 15":
    sequence_num = x % 15
    # This will produce the numbers 0-14 over and over.

    # Next we need to extract the 2-bit code from the index sequence.
    # This involves 2 steps:
    # 1. Shift/rotate the bits in output_indexes so the 2 on the right (the
    #     "least significant" bits mathematically) are the 2 corresponding to
    #     this output in the sequence.
    # 2. Extract just the last 2 bits that we just shifted to the end.

    # Since each code is 2-bits, we need to shift by double our sequence #.
    shift_by = 2*sequence_num
    shifted_indexes = output_indexes >> shift_by
    # Example: if x is 18, then sequence_num is 3 (18%15 == 3). So we shift
    # right by 6 bits, giving (compare to output_indexes above):
    # 0b110000010010010000011000

    # Now extract just the last 2 bits by doing a bitwise AND with 3 (11b).
    output_index = shifted_indexes & 0b11

    # Finally we can retrieve the output from the list based on the code.
    output = output_candidates[output_index]
    print output

fizzbuzz_magic.py

for x in xrange(100): print [x + 1, 'Fizz', 'Buzz', 'FizzBuzz'][0x30490610>>x%15*2&3]

insert about 30 minutes of me staring silently at the screen, occasionally swearing quietly under my breath

Well, I have tried very hard to comprehend this, and so far, I've had little success. I understand the concept of the four "on off" positions of the two bits (shave and a haircut...), and I see what you're saying about the numbers 1 - 15 and 16 - 30 etc being the same in terms of the on off positions of the aforementioned two bits, in other words 1 - 15 in this context creates the same binary bit formation as 16 - 30.

I assume from your explanation that binary reads from right to left rather than from left to right. Is hexadecimal the same? Why is there a "b" in the binary sequence? Aside from those questions, I understand everything above this line: "# A shorter way to represent this number is in hexadecimal: 0x30490610"

Here, insert about 20 minutes of me staring silently at the screen

Okay, how does "sequence_num = x%15" produce the numbers 0-14? Shouldn't it produce, if we start from zero and work toward 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, etc?

The part I'm having by far the most trouble with is lines 31-34. I think I could understand the rest if I could figure out why that works the way it does.

edit: neat! I didn't realize that markdown would make ">>" into a special kind of text.

To understand how the remainder/modulo operator works, open a python interpreter:

>>> for x in xrange(10): print x % 3
...
0
1
2
0
1
2
0
1
2
0
>>> for x in xrange(10): print x % 5
...
0
1
2
3
4
0
1
2
3
4
>>> for x in xrange(100): print x % 15

For more of the math, see http://mathworld.wolfram.com/Congruence.html

Wow, that math website was almost entirely opaque to me. Like someone who speaks "Math" fluently came along and rattled off a series of words in his language that, to someone like me who has at best taken a couple of "conversational math" classes in high school, are gibberish.

Basically it would be like me writing the above sentence and expecting someone who understands 1000 words of English to get it.

I need to learn this stuff to the point of really understanding it just so I can turn around and explain it in print form in a way that someone who hasn't read the previous 200 pages of the math textbook will understand or at least be able to vaguely follow.

My understanding of the modulo operator is that 15%4 is the same as the remainder of 15/4, ie, 3. Since 15/4 = 3, and 3x4 = 12, and 15-12 is 3, 15%4 = 3. Am I even close there?

So, since we're talking strictly integers here for the most part, let's switch it around: 4/15, if we grab the answer in just a whole number, is 0. So 4%15 would also be 0. Right? What am I missing here?

Based on the blob of annoyingly abstract variables and math terminology on the wolfram site, if we have two numbers (b and c in this case), let's say that b = 15 and c = 5, then we have another number, m, which in our little example m = 2, then their formula, (b - c)/m comes to (15-5)/2 = 5 (which is an integer). So is it then correct to say that 15 "insert little congruence sign here" 5 (mod 2)? If so, what the fuck does that mean and why is it useful?

How does it play into the mod operator in Python?

I am deeply indignant with math for not revealing its secrets to me more easily.

Sorry if this is all coming off as a little hostile. I'm certainly not upset with you at all, I'm just frustrated because this is the same shit I went through in high school, where people who write math textbooks and "learning aids" (I refer here specifically to the wolfram site) generally have NO concept of how to make sense to actual humans.

You don't seem to have that same problem, which is why I am asking you this stuff instead of digging for it myself online. I did search for "congruence" and this: http://www.mathsisfun.com/geometry/congruent.html is what I found... not useful. Ha. Anyway, going to bed now! Goodnight.