On the FizzBuzz Test

Dan Cross, Cambridge, MA

FizzBuzz is a apparently a word game for children, but is also presented as a simple programming problem that is used as a filter in the hiring process. Despite a simple problem statement, a large number of programmers are reportedly unable to produce a program that correctly implements a solution.

The problem statement is as follows:

For each integer between 1 and 100, inclusive:

A trivial solution is:


#include <stdio.h>

int
main(void)
{
        for (int k = 1; k <= 100; k++) {
                if (k%3 == 0 && k%5 == 0)
                        printf("FizzBuzz\n");
                else if (k%3 == 0)
                        printf("Fizz\n");
                else if (k%5 == 0)
                        printf("Buzz\n");
                else
                        printf("%d\n", k);
        }

        return 0;
}

This solution is correct and perfectly adequate. Another correct solution that a possibly more experienced C programmer might write avoids the 'else' clauses by using the 'continue' statement in the loop.


#include <stdio.h>

int
main(void)
{
        for (int k = 1; k <= 100; k++) {
                if (k%3 != 0 && k%5 != 0) {
                        printf("%d\n", k);
                        continue;
                }
                if (k%3 == 0)
                        printf("Fizz");
                if (k%5 == 0)
                        printf("Buzz");
                printf("\n");
        }

        return 0;
}

This is typical of C programs that use the "guard clause" technique: iteratively test for the uninteresting or exceptional case and handle it first and move on. This naturally keeps code indented towards the left, which in turn frees the programmer to focus on a narrowing set of possibilities until nothing remains but the problem at hand.

For FizzBuzz, arguably the interesting thing is when to print the non-numeric "words", so we handle the not-divisible-by-either case first; this also lets us cascade the divisibility conditions so we can avoid 'else' all together.

But going beyond these simple solutions, there are many fancy ways to solve this trivial problem. Russ Cox wrote a lovely solution that he described in a Google+ post (sadly now lost) that models FizzBuzz as a special case of a sieve filtering a subset of the prime numbers; this is wonderful for demonstrating some of the basic capabilities of the Go programming language and is reminiscent of Doug McIllroy's paper, Squinting at Power Series.

However, a quick reminder from abstract algebra leads to an even simpler program: generators of cyclic groups form equivalence classes, and the modulus operator partitions integers into equivalence classes. Thus, we can replace all of the conditionals in our program (save for that checking the loop index) by partitioning into the appropriate subgroup of the cyclic group generated by 3 and 5 (that is, $\mathbb{Z}/15\mathbb{Z}$) and using that to select a formatting string that will produce the output appropriate to the given number. This gives the following program:


#include <stdio.h>

const char *fmts[] = {
        "FizzBuzz", "%d", "%d", "Fizz", "%d", "Buzz", "Fizz",
        "%d", "%d", "Fizz", "Buzz", "%d", "Fizz", "%d", "%d",
};
#define NFMTS (sizeof(fmts) / sizeof(fmts[0]))

int
main(void)
{
        for (int k = 1; k <= 100; ++k) {
                printf(fmts[k % NFMTS], k);
                printf("\n");
        }

        return 0;
}

Note that this program relies on a peculiarity of C: one may present more arguments to printf than will be consumed according to the format string. This is explicitly permitted by section 7.21.6.1 paragraph 2 of the 2011 ISO C standard, so it's perfectly legal if somewhat obscure.

After Russ's post, I decided to see if I could transliterate my program into Go, but Go's formatted output routines are too clever for me: in particular, Go doesn't permit C's trick and will issue a runtime diagnostic (in the form of a warning message printed to the standard error) if a formatted print function receives more arguments than it consumes.

However, this is relatively easy to work around: in the relevant cases one uses a format string that consumes but discards an argument by truncating it to zero width. While there is no format specifier to truncate an integer that way, "%.0s" does for a string and it's trivial to convert the second argument to fmt.Printf to a string using functions from the strconv package. Here is the result:


package main

import "fmt"
import "strconv"

func main() {
        s := func(f string) string { return f + "%.0s" }
        fmts := []string{
                s("FizzBuzz"), "%s", "%s", s("Fizz"), "%s",
                s("Buzz"), s("Fizz"), "%s", "%s", s("Fizz"),
                s("Buzz"), "%s", s("Fizz"), "%s", "%s",
        }

        for k := 1; k <= 100; k++ {
                fmt.Printf(fmts[k%len(fmts)]+"\n", strconv.Itoa(k))
        }
}

Who ever said that abstract mathematics has no bearing on real world programs?