computer science goes bonk / all posts / rss / about

fizzbuzz madness

FizzBuzz Cola

Whew it is hot outside.

You know a great way to cool off? An ice-cold bottle of FizzBuzz.

A FizzBuzz problem is an easy programming problem that can be used to screen potential candidates for a job before bringing them in for a full interview. The idea is that an alarming number of applicants don't really grok basic programming concepts, and you can avoid wasting everybody's time by starting with the bar low.

And I mean really low. The most well-known FizzBuzz problem goes something like this:

  • Print the numbers from 1 to 100.
  • If the number is divisible by 3, also print "Fizz".
  • If the number is divisible by 5, also print "Buzz".

In other words, you should see something like this:

1
2
3 Fizz
4
5 Buzz
6 Fizz
7
8
9 Fizz
10 Buzz
11
12 Fizz
13
14
15 FizzBuzz

...and so on. A good programmer should be able to bang a solution to this problem out in a few minutes.

#include <iostream>

int main() {
   for (int i = 1; i <= 100; ++i) {
      std::cout << i << " ";
      if (i % 3 == 0) std::cout << "Fizz";
      if (i % 5 == 0) std::cout << "Buzz";
      std::cout << std::endl;
   }
}

But FizzBuzz might pop up elsewhere, too. Over in the comments to one of Stephan Lavavej's awesome "Advanced STL" videos, STL challenges a commenter who doesn't understand template metaprogramming to write FizzBuzz without runtime loops or runtime conditionals.

#include <iostream>

template <size_t N>
void fizzBuzzHelper(const char*) {}

template <>
void fizzBuzzHelper<0>(const char *str) {
   std::cout << str;
}

template <size_t N>
void fizzBuzz() {     // general case for N > 0
  fizzBuzz<N-1>();
  std::cout << N << " ";
  fizzBuzzHelper<N % 3>("Fizz");
  fizzBuzzHelper<N % 5>("Buzz");
  std::cout << std::endl;
}

template <>
void fizzBuzz<0>() {}  // base case for N == 0

int main() {
   fizzBuzz<100>();
}

Ahh, metaprogramming with FizzBuzz. I feel cooler already.


worth 1000 lines of code

While heading into work earlier this week, I became convinced that the classic recursive solution to the "Towers of Hanoi" problem couldn't possibly work.

Turns out I had the algorithm upside-down, a fact I realized once I got to work and drew a picture of the algorithm on a whiteboard.

Now I happen to like pictures. Being able to actually see a problem helps me organize my thoughts and figure out what should happen next. But as people drifted by and saw this piece of dry-erase resistance, it became clear that this approach doesn't work for everyone.

Refresher

In case you've forgotten, the Towers of Hanoi problems consists of N discs on three pegs:

start of game

The goal of the problem is to move all N discs from one peg to another (for example, from peg 0 to peg 2):

the goal of the game

There are only two rules:

  • You can only move one disc at a time
  • You can't put a bigger disc on top of a smaller disc

A Picture of a Photograph

There are iterative ways to solve this problem. Since my brain's stack pointer is easily corrupted, my usual style of play involves making random moves until I accidentally win. However, if you have more reliable storage, Towers of Hanoi practically begs to be solved recursively.

But first, go and see if you can remember how to do it. I'll wait here. Srsly. The internet isn't going anywhere.

Done?

Okay. Remember that thinking recursively involves breaking a problem into smaller versions of the same problem. For Towers of Hanoi, let's assume that we know how to solve the smaller problem that only involves N-1 discs:

  • Use the power of recursion to move the top N-1 discs to a temporary peg:

step one: get a box

  • Move the bottom disc to its final position:

step2

  • Harness once more the power of recursion to move the N-1 discs to their final position on top of the bottom disc:

step3

That's pretty much it. (Of course with any recursive algorithm, you have to know when to stop -- for Towers of Hanoi, the base case is 1 disc, which you can easily move.)


making COUNTOF suck less

If you've played around with C++ enough, you've probably run across something like this:

#define COUNTOF(arr) (sizeof(arr) / sizeof(arr[0]))

It's our good friend COUNTOF, a cute little macro that helps us figure out how big arrays are:

int primes[] = {2, 3, 5, 7, 11, 13};

for (int i = 0; i < COUNTOF(primes); ++i) {
   std::cout << primes[i] << std::endl;
}

At first glance, this is great: COUNTOF is like a magic incantation that lets us avoid the highly error-prone world of C-style arrays.

The Problem

Unfortunately, COUNTOF can fail in a pretty spectacular way.   It's kind of ridiculous, really:

#define COUNTOF(arr) (sizeof(arr) / sizeof(arr[0]))

void foo(int *primes) {
   // someone said that arrays and pointers are pretty much the same,
   // so this should work, right?
   std::cout << COUNTOF(primes) << std::endl;
}

void bar(int primes[]) {
   // okay, maybe that last one won't be right, but this one has got to work!
   std::cout << COUNTOF(primes) << std::endl;
}

int main() {
   int primes[] = {2, 3, 5, 7, 11, 13};
   std::cout << COUNTOF(primes) << std::endl; // fine, displays "6"
   foo(primes);  // displays e.g. "4", aka sizeof(int*)
   bar(primes);  // also "4"
}

The problem is that C++ allows arrays to decay into pointers at the drop of a hat.  This is useful behavior, because it allows us to do fun things with pointers without having to do a lot of casting, but it also allows for some pretty unexpected behavior.

One Solution

Wouldn't it be nice if the compiler would warn us when we try to pass the wrong type of data to COUNTOF? Check this out: 

template <typename T, size_t N>
inline size_t countof(const T (&arr)[N]) {
   return N;
}

void foo(int primes[]) {
   // compiler error: primes is not an array
   std::cout << countof(primes) << std::endl;
}

int main() {
   int primes[] = {2, 3, 5, 7, 11, 13};
   std::cout << countof(primes) << std::endl; // fine, displays "6"
   foo(primes);
}

This approach uses some template trickery to define a free function that takes a reference to an array of N elements of type T.  Since we're using an array explicitly, the compiler will error out if we try to pass a pointer into this function.  And that's good: the compiler is our friend, and we should be happy when it tells us that we're doing something wrong.

But I like macros!

Maybe you're worried about performance. Maybe you just don't trust the inline keyword.  Is there a way we can do all of this at compile time?

template <typename T, size_t N>
char (&ArraySizeHelper( T (&arr)[N] ))[N];
#define COUNTOF(arr) ( sizeof(ArraySizeHelper(arr)) )

void foo(int primes[]) {
   // compiler error: primes is not an array
   std::cout << COUNTOF(primes) << std::endl;
}

int main() {
   int primes[] = {2, 3, 5, 7, 11, 13};
   std::cout << COUNTOF(primes) << std::endl; // fine, displays "6"
   foo(primes);
}

What the heck is that?

This version of COUNTOF uses a free helper function called ArraySizeHelper that is declared, but not defined.  Like the inline function from our first solution, this helper function takes a reference to an array of N objects of type T.  This function, however, returns a reference to an array of N objects of type char.  (What?!  You can return raw arrays from functions in C++?  Sure, as long as you return them by reference.)

We don't need to define ArraySizeHelper, because we never call it: arguments to the sizeof operator are not evaluated.  The only thing that sizeof uses is type information, which in this case is the return type of ArraySizeHelper.

We could define COUNTOF like so:

...
#define COUNTOF(arr) ( sizeof(ArraySizeHelper(arr)) / sizeof(char) )

...but since sizeof(char) is defined as 1, we can omit it.

This version of COUNTOF won't accidentally compile when passed pointers and runs completely at compile-time. This is good. In fact, this is how the _countof macro in Visual Studio (VC9) is defined.

But Wait, There's More!

This template tomfoolery is all well and good, but there are places where templates won't work well.  Locally-defined types are useful when you want to define a "throwaway" type that won't be used outside of the current function, but like that old joke goes, local types and templates don't mix. Or maybe I'm thinking of a different joke.

...
void foo() {
   struct {int i; bool b;} arr[10];
   // compiler error: template argument uses local type
   std::cout << COUNTOF(arr) << std::endl;
}

(Update: this problem was fixed in C++11.)

Ivan Johnson solved this problem with a clever COUNTOF macro that wins on all accounts: it's typesafe, compile-time, and works with local types:

#define COUNTOF(arr) ( \
   0 * sizeof(reinterpret_cast<const ::Bad_arg_to_COUNTOF*>(arr)) + \
   0 * sizeof(::Bad_arg_to_COUNTOF::check_type((arr), &(arr))) + \
   sizeof(arr) / sizeof((arr)[0]) )

struct Bad_arg_to_COUNTOF {
   class Is_pointer; // incomplete
   class Is_array {};
   template <typename T>
   static Is_pointer check_type(const T*, const T* const*);
   static Is_array check_type(const void*, const void*);
};

And I'll bet you thought that last version was cryptic.

This version isn't as bad as it first looks.  It works by inserting two "tests" before the standard sizeof-based array-size macro. Those tests don't impact the final calculation, but are designed to generate compile errors for non-array types:

  1. The first test fails unless arr is integral, enum, pointer, or array.  reinterpret_cast should fail for any other types.
  2. The second test fails for integral, enum, or pointer types. Integral and enum types will fail because there's no version of check_type that they match, since check_type expects pointers. Pointer types will fail because they'll match the templated version of check_type, but the return type (Is_pointer) for the templated check_type is incomplete, which will produce an error. Array types will pass because taking the address of an array of type T will give you T (*)[], aka a pointer-to-an-array, not a pointer-to-a-pointer. That means that the templated version of check_type won't match. Thanks to SFINAE, the compiler will move on to the non-templated version of check_type, which should accept any pair of pointers. Since the return type for the non-templated version is defined completely, no error will be produced. And since we're not dealing with templates now, local types work fine.

So there you have it: a COUNTOF macro that is fast, safe, and helps you avoid those pernicious pointer problems.


« Previous Page