Skip to content

Instantly share code, notes, and snippets.

@jim3ccc

jim3ccc/fizz.rb

Forked from ggilder/fizz.rb
Created January 23, 2018 23:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jim3ccc/3e8b06e7c3f4509cd960938e6bfa2aaf to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jim3ccc/3e8b06e7c3f4509cd960938e6bfa2aaf to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @ggilder ggilder revised this gist Jun 8, 2012. 1 changed file with 30 additions and 18 deletions.
    48 changes: 30 additions & 18 deletions fizz.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -8,7 +8,8 @@

    # Explanation
    #
    # "810092048" appears to be a magic number, but if we display it as binary pairs it starts to make sense:
    # "810092048" appears to be a magic number, but if we display it as binary
    # pairs it starts to make sense:
    pairs = 810092048.to_s(2).scan(/.{2}/)
    #=> ["11", "00", "00", "01", "00", "10", "01", "00", "00", "01", "10", "00", "01", "00", "00"]
    # Now display each pair of binary digits as decimal:
    @@ -17,52 +18,63 @@
    # Now map those to messages:
    pairs.map {|x| messages[x]}
    #=> ["FizzBuzz", nil, nil, "Fizz", nil, "Buzz", "Fizz", nil, nil, "Fizz", "Buzz", nil, "Fizz", nil, nil]
    # Notice that this is a reversed version of the first 15 messages (where nil stands for "pass through the integer") in the FizzBuzz sequence.
    # Notice that this is a reversed version of the first 15 messages (where nil
    # stands for "pass through the integer") in the FizzBuzz sequence.

    # Now for the binary math. `acc & 3` is the same as taking the last binary pair of the number, because 3 == "11" in binary.
    # So `c = acc & 3` just grabs the last binary pair of acc.
    # `c` must be 0, 1, 2, or 3, so we print messages[c] or pass through the integer if the message is nil (c == 0).
    # Then we perform some shifting on acc. Notice that acc is 30 binary digits long:
    # Now for the binary math. `acc & 3` is the same as taking the last binary pair
    # of the number, because 3 == "11" in binary. So `c = acc & 3` just grabs the
    # last binary pair of acc. `c` must be 0, 1, 2, or 3, so we print messages[c]
    # or pass through the integer if the message is nil (c == 0). Then we perform
    # some shifting on acc. Notice that acc is 30 binary digits long:
    810092048.to_s(2).length
    #=> 30
    # So if we shift acc to the right 2 digits, we "pop off" the last (rightmost) binary pair. That's `acc >> 2`.
    # However, if we want to keep the sequence going past the first 15 integers, we really need to push the binary pair we just used back onto the end of the stack.
    # So, we use a binary OR of the shifted acc with c (the last index we used) shifted to the right 28 binary digits. That way the sequence can go on forever!

    # Let's see what that looks like for one of the iterations, to make it more clear.
    # First let's make a helper function to print out these binary numbers.
    # So if we shift acc to the right 2 digits, we "pop off" the last (rightmost)
    # binary pair. That's `acc >> 2`. However, if we want to keep the sequence
    # going past the first 15 integers, we really need to push the binary pair we
    # just used back onto the end of the stack. So, we use a binary OR of the
    # shifted acc with c (the last index we used) shifted to the right 28 binary
    # digits. That way the sequence can go on forever!

    # Let's see what that looks like for one of the iterations, to make it more
    # clear. First let's make a helper function to print out these binary numbers.
    def pp_binary(n)
    # pad up to 30 binary digits for consistency
    (("0" * 30) + n.to_s(2))[-30..-1].scan(/.{2}/).join(' ')
    end

    # Here's our magic number...
    acc = 810092048
    # But let's start by shifting off the first two pairs (4 digits), since we know those are both zero, so those iterations don't show us much.
    # But let's start by shifting off the first two pairs (4 digits), since we know
    # those are both zero, so those iterations don't show us much.
    acc = acc >> 4
    #=> 50630753
    # Let's see that in binary for reference:
    pp_binary(acc)
    #=> "00 00 11 00 00 01 00 10 01 00 00 01 10 00 01"

    # Now let's see what our index is. We're on the iteration for 3, so we should have the index for "Fizz", which is 1.
    # Now let's see what our index is. We're on the iteration for 3, so we should
    # have the index for "Fizz", which is 1.
    c = acc & 3
    pp_binary(c)
    #=> "00 00 00 00 00 00 00 00 00 00 00 00 00 00 01"

    # Looks good. Now let's see what acc looks like when we shift it over 2 digits...
    # Looks good. Now let's see what acc looks like when we shift it over 2
    # digits...
    pp_binary(acc >> 2)
    #=> "00 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
    # Notice that the last pair has been shifted off, and the leftmost pair is now zero.
    #
    # Notice that the last pair has been shifted off, and the leftmost pair is now
    # zero.

    # To get that last pair back, we take c and shift it back 28 digits:
    pp_binary(c << 28)
    #=> "01 00 00 00 00 00 00 00 00 00 00 00 00 00 00"

    # Great! Now we just combine those with a binary OR.
    acc = acc >> 2 | c << 28
    # The binary OR sets each digit to 1 if it is 1 in either of the operands.
    pp_binary(acc)
    #=> "01 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
    # So now we've pushed our last pair back onto acc, and we're ready to run the process again!
    # Whew!
    # So now we've pushed our last pair back onto acc, and we're ready to run the
    # process again! Whew!

  2. @ggilder ggilder revised this gist Jun 8, 2012. 1 changed file with 61 additions and 0 deletions.
    61 changes: 61 additions & 0 deletions fizz.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -5,3 +5,64 @@
    puts messages[c] || i
    acc = acc >> 2 | c << 28
    end

    # Explanation
    #
    # "810092048" appears to be a magic number, but if we display it as binary pairs it starts to make sense:
    pairs = 810092048.to_s(2).scan(/.{2}/)
    #=> ["11", "00", "00", "01", "00", "10", "01", "00", "00", "01", "10", "00", "01", "00", "00"]
    # Now display each pair of binary digits as decimal:
    pairs = pairs.map {|x| x.to_i(2)}
    #=> [3, 0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0]
    # Now map those to messages:
    pairs.map {|x| messages[x]}
    #=> ["FizzBuzz", nil, nil, "Fizz", nil, "Buzz", "Fizz", nil, nil, "Fizz", "Buzz", nil, "Fizz", nil, nil]
    # Notice that this is a reversed version of the first 15 messages (where nil stands for "pass through the integer") in the FizzBuzz sequence.

    # Now for the binary math. `acc & 3` is the same as taking the last binary pair of the number, because 3 == "11" in binary.
    # So `c = acc & 3` just grabs the last binary pair of acc.
    # `c` must be 0, 1, 2, or 3, so we print messages[c] or pass through the integer if the message is nil (c == 0).
    # Then we perform some shifting on acc. Notice that acc is 30 binary digits long:
    810092048.to_s(2).length
    #=> 30
    # So if we shift acc to the right 2 digits, we "pop off" the last (rightmost) binary pair. That's `acc >> 2`.
    # However, if we want to keep the sequence going past the first 15 integers, we really need to push the binary pair we just used back onto the end of the stack.
    # So, we use a binary OR of the shifted acc with c (the last index we used) shifted to the right 28 binary digits. That way the sequence can go on forever!

    # Let's see what that looks like for one of the iterations, to make it more clear.
    # First let's make a helper function to print out these binary numbers.
    def pp_binary(n)
    # pad up to 30 binary digits for consistency
    (("0" * 30) + n.to_s(2))[-30..-1].scan(/.{2}/).join(' ')
    end

    # Here's our magic number...
    acc = 810092048
    # But let's start by shifting off the first two pairs (4 digits), since we know those are both zero, so those iterations don't show us much.
    acc = acc >> 4
    #=> 50630753
    # Let's see that in binary for reference:
    pp_binary(acc)
    #=> "00 00 11 00 00 01 00 10 01 00 00 01 10 00 01"

    # Now let's see what our index is. We're on the iteration for 3, so we should have the index for "Fizz", which is 1.
    c = acc & 3
    pp_binary(c)
    #=> "00 00 00 00 00 00 00 00 00 00 00 00 00 00 01"

    # Looks good. Now let's see what acc looks like when we shift it over 2 digits...
    pp_binary(acc >> 2)
    #=> "00 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
    # Notice that the last pair has been shifted off, and the leftmost pair is now zero.
    #
    # To get that last pair back, we take c and shift it back 28 digits:
    pp_binary(c << 28)
    #=> "01 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    # Great! Now we just combine those with a binary OR.
    acc = acc >> 2 | c << 28
    # The binary OR sets each digit to 1 if it is 1 in either of the operands.
    pp_binary(acc)
    #=> "01 00 00 11 00 00 01 00 10 01 00 00 01 10 00"
    # So now we've pushed our last pair back onto acc, and we're ready to run the process again!
    # Whew!

  3. @ggilder ggilder revised this gist Jun 8, 2012. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions fizz.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -2,5 +2,6 @@
    acc = 810092048
    (1..100).each do |i|
    c = acc & 3
    puts messages[c] || i
    acc = acc >> 2 | c << 28
    end
  4. @ggilder ggilder created this gist Jun 8, 2012.
    6 changes: 6 additions & 0 deletions fizz.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,6 @@
    messages = [nil, "Fizz", "Buzz", "FizzBuzz"]
    acc = 810092048
    (1..100).each do |i|
    c = acc & 3
    acc = acc >> 2 | c << 28
    end