Unorthodox Solutions for Fizzbuzz

This post discusses several approaches to the Fizzbuzz group word game. Starting with the standard approach, I introduce a couple of restrictions that require more creative and unorthodox solutions.

What Is Fizzbuzz and Why Should We Care?

Fizzbuzz is a group word game; see the Wikipedia entry. It is easy to implement as a software program and can therefore be useful for familiarizing yourself with a new programming language and a new set of tools quite quickly. This type of exercise is often called a “kata,” similar to the katas of prearranged moves in martial arts. It is also frequently used as a screening tool in job interviews.

There is a deeper reason for approaching the problem this way: it is the programmer’s equivalent of the “10-to-3-to-1” design process, described by former Apple engineering manager Michael Lopp after an SXSW presentation. There is an interesting psychological aspect — The first two to four ideas usually come easily because they are the obvious solutions. By the sixth, seventh, and eighth ideas, you have exhausted the clichés. The ninth and tenth ideas force you to rethink the problem from a completely different angle, often leading to much more original solutions.

This is exactly what this post is about — unusual and creative solutions that force us to rethink how many ways there are to solve a seemingly simple problem.

I introduce a series of restrictions that prevent the use of certain language constructs. This makes it necessary to find unorthodox and creative ways to solve the originally very simple problem. Although the steps are theoretically independent of one another, it is advisable to try the solutions in the given order. Even if you find a solution to the final step, you can still try the other steps because each one employs different concepts and techniques.

The goal is to realize that there are often very different solutions to a given problem. Please enjoy!

The rules we will use are:

• Print a table with 100 entries.
• For every row that is a multiple of fifteen, print fizzbuzz.
• Otherwise, for every row that is a multiple of three, print fizz.
• Otherwise, for every row that is a multiple of five, print buzz.
• For every row that is neither a multiple of three nor five, print the row number.

The Straightforward Solution

The straightforward solution is simply a translation of the rules into imperative Python instructions. This is done with nested if blocks. The original article used Python 2; all examples have since been updated to Python 3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Fizzbuzz in Python.
#
# This is the straightforward, traditional version with nested
# if-statements.
#

class FizzBuzz:
    """Class doing FizzBuzz."""

    def do_fizzbuzz(self, m):
        """Return m, fizz, buzz or fizzbuzz as appropriate."""
        if (m % 15) == 0:
            return 'fizzbuzz'
        else:
            if (m % 3) == 0:
                return 'fizz'
            else:
                if (m % 5) == 0:
                    return 'buzz'
                else:
                    return str(m)

    def print_table(self, n):
        """Print the FizzBuzz table up to n."""
        for i in range(1, n + 1):
            print(self.do_fizzbuzz(i))

# Main program section.
fb = FizzBuzz()
fb.print_table(100)

Notice how this solution features nested if statements in the do_fizzbuzz method that contains the main business logic. Several conditions are checked in a particular order.

There are a couple of problems here. First, the order of the tests matters. We cannot test for either fizz or buzz before we have tested for fizzbuzz. The latter test always needs to come first, although it is actually the least likely to succeed because it occurs least frequently. There are only six occurrences of fizzbuzz in the entire table of 100 rows!

The branch used most often—returning the number—is accessed only after all other tests have run and failed.

Step 1: No Nested if Blocks

Now let us introduce one restriction:

No nested if blocks anymore!

Rewrite the code above and create a do_fizzbuzz method that has no explicitly nested if statements. In other words, there should be no more if statements inside an else block. It is no problem if you find alternative constructs that result in implicit branches, but try not to replace the if statements with flags used merely to refactor the nested blocks. Try to get rid of the nesting altogether!

My solution can be found here.

Step 2: No Explicit if Statements

For the next iteration of code refactoring, there is one more restriction:

No explicit if statements anymore!

This one is a little easier because we only need to find alternative language constructs that implement conditions and conditional branching.

My solution for this step can be found here.

Step 3: Loops, but No Data-Dependent Branches

This one is particularly interesting, although it sounds very tough at first:

No data-dependent conditional branches anymore! Loops are still allowed.

Before you ask: Yes, it is possible! However, it needs to be done a little differently than you may initially expect. Here is a hint: My solution changes the interface of the FizzBuzz class. Specifically, it involves some initialization code and an explicit __init__ method.

If you have no idea where to start, you can click this hint. It will point you in the right direction without revealing the full solution just yet.

Once you are done, my solution is here.

Step 4: Step 3 With Constant Space Consumption

The previous solution avoids data-dependent conditional branches in do_fizzbuzz. However, it introduces another problem: O(n) memory consumption. The next step addresses this issue:

Modify the solution from step 3 so that it uses only constant memory!

Whereas the previous solution modified the initializer and required the user to specify the maximum number of Fizzbuzz entries needed, this modification restores the previous interface and resolves the memory-consumption issue at the same time!

As usual, my solution can be found here.

Step 5: No Conditional Branching at All!

This is the final step and the final restriction:

Refactor do_fizzbuzz so that it does not use any conditional branching at all. This includes looping constructs—the end-of-loop condition is an implicit conditional branch—and all other min, or, and similar statements. The FizzBuzz class has the same interface as in the straightforward solution above and has constant memory consumption.

The key ideas have already been introduced in step 3 and step 4. This is only a minor additional restriction that generally requires some code cleanup, which you may already have done. The resulting method is a simple table lookup followed by a function call. To my eyes, it is also easier to understand than the nested conditionals in the straightforward solution.

The solution can be found here.

Conclusions

This post has shown several different solutions to the Fizzbuzz problem. Some of them have been quite unorthodox. Even though some solutions are inferior to the original straightforward solution, they all involve different techniques and concepts.

I have noticed that many people initially react with disbelief when I present the rules for the final step. However, discovering how an entirely unorthodox approach does the trick can be a source of immense satisfaction.

I hope you have enjoyed this post. Please send me an email if you know of other unorthodox solutions that I have not presented here.