Fizz-Buzz in Haskell



It’s a simple FizzBuzz riddle implementation written in Haskell.

Here is what FizzBuzz is: > Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Solution:

fizzbuzz :: [Int] -> IO ()
fizzbuzz [] = return ()
fizzbuzz (x:xs) = do
  let
    l = [show $ x + 1, "Fizz", "Buzz", "FizzBuzz"]
    n = ((0x30490610 `shiftR` ((x `mod` 15) * 2)) .&. 3)
  putStrLn $ show $ l !! n
  fizzbuzz xs

Use: fizzbuzz [0..99]

Explanation:

  • There are four possible outputs: the number, “Fizz”, “Buzz”, “FizzBuzz”; each output need two bits to store: 00, 01, 10, 11 respectively.
  • After playing with numbers, we you might spot that the output repeats itself in sets of 15. Meaning that fizzbuzz for 1-15 is exactly the same as for 16-30, etc.
  • Now, the basic idea is to encode all possible outputs as a binary sequence of 15 2-bit values: 110000010010010000011000010000 (in hex it is 0x30490610).
  • Then, we are going to repeat this pattern by getting 2 bits at a time 15x, taking the remainder of x/15, (x 'mod' 15) - this will produce the numbers from 0 to 14.
  • Next we need to extract the 2-bit value from the initial index sequence (the 0x30490610): firstly, we do right shift on the bits in the sequence so the two on the right (the “least significant” bits) are the two corresponding to this output in the sequence; secondly, we extract just the last two bits that we just shifted to the end.
  • Since each code is two-bits, we need to shift by double our sequence: ``(0x30490610shiftR((xmod` 15) * 2)```
  • Now extract just the last two bits by doing a bitwise AND with 3 (11): .&. 3
  • Finally, we can get the output from the list based on the code: l !! n (where l is our list and n is the calculated index).

Source of inspiration: FizzBuzz in Python