field-theory.org
the blog of wolfram schroers

Unorthodox Solutions for Fizzbuzz

This post discusses several approaches to the Fizzbuzz group wording game. Starting out from the standard approach, a couple of restrictions are introduced which require more creative and unorthodox solutions.

Table of contents:

What is Fizzbuzz and why should we care?
The straightforward solution
Step 1: No nested if blocks
Step 2: No explicit if statements
Step 3: Only loops, but no branches
Step 4: Step 3 with constant space consumption
Step 5: No conditional branching at all, anywhere!
Conclusions

What is Fizzbuzz and why should we care?

Fizzbuzz is a group wording game, see the Wikipedia entry. It is easy to implement as a software program and can thus be useful to familiarize oneself with a new programming language and a new set of tools pretty quickly — this type of exercise is often called “Kata”, similar to the Katas of prearranged moves in martial arts. Quite frequently it is also used as a screening tool in job interviews.

The rules we will use in the following are:

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

In the following I will show a series of distinct solutions to the Fizzbuzz problem in the Python language. Starting from the straightforward solution I introduce a series of restrictions that prevent the usage of certain language constructs. This way it becomes necessar to find unorthodox and creative ways to solve the (originally) very simple problem. Although the steps are in theory independent of each other, it is advisable to try to find solutions in the given order. And even if you found a solution to the final step, you can still try out the other solutions 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 straightforward solution

The straightforward solution is simply the translation of the rules to imperative Python instructions. This is done by nested if-blocks:

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

class FizzBuzz(object):
    """Class doing FizzBuzz."""

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

    def print_table(self, n):
        """Print the FizzBuzz table up to n."""
        for i in xrange(1, n):
            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 will be checked in a particular order.

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

The branch that is used most often – returning the number – will be accessed only after all other tests have been run and have failed.

Step 1: No nested if blocks

Now let's introduce one restriction:

No nested if-blocks anymore!

Rewrite the above code and come up with a method do_fizzbuzz that has no explicitly nested if-statements anymore. I.e., there should be no more ifs in an else-block. It is no problem if you find alternative constructs that result in implicit branches, but try not to replace ifs by flags that are used to refactor the nested blocks. Just 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 just need to find alternative language constructs that implement conditions and conditional branching.

My solution for this step can be found here.

Step 3: Only loops, but no branches

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

No conditional code anymore! That includes explicit and implicit branches and all alternative code paths.

Before you ask: Yes, it is possible! Although it needs to be done a little bit differently than you originally thought. At this point I give you a hint: My solution changes the interface of the FizzBuzz-class. Specifically, there is some bit of initialization code and an explicit __init__ method involved.

If you have no idea where to start, you can click on this hint which will point you in the right direction, but does not tell you the full solution just yet.

Once you are done my solution is here.

Step 4: Step 3 with constant space consumption

The previous solution has solved all performance issues listed above in step 1. But it introduced another problem: an order O(N) memory consumption. So the next step resolves this issue:

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

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

As usual, my solution can be found here.

Step 5: No conditional branching at all, anywhere!

This is the final step and the final restriction:

Refactor do_fizzbuzz such 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 class FizzBuzz has the same interface as in the straightforward solution and has constant memory consumption.

They key ideas have all been given in step 3 and step4 already. This is just a minor additional restriction which generally requires some code-cleanup which you may have done yourself already. Note that the method is now purely functional-style and also easier to understand than the straightforward solution which used an imperative programming style.

The solution can be found here.

Conclusions

This post has shown a couple of 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 involved different techniques and concepts.

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

I hope you have enjoyed this post. Please drop me a mail if you know of other, unorthodox solutions that I have not presented here.