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.
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:
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 is simply the translation of the rules to imperative Python instructions. This is done by nested
# 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
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.
Now let's introduce one restriction:
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!
For the next iteration of code refactoring there is one more restriction:
This one is a little easier because we just need to find alternative language constructs that implement conditions and conditional branching.
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.
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!
This is the final step and the final restriction:
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
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.
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.
Imprint / Impressum
© 1997-2013 Dr. Wolfram Schroers. This site is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
Additional permissions available at http://www.field-theory.org/editorial/index.html.
Wolfram is a leading software engineer focused on Enterprise and B2B apps on iOS. His clients rank from small independent studios to companies in the German DAX index.
He has worked at top Universities on three continents in the past decade and is a popular speaker at conferences. He is currently working in Berlin, Germany, and can be reached at his company website.