Happy Bear Software

Screencast: Fizzbuzz Four Ways

Trouble viewing the screencast? See it on YouTube or download it for viewing offline.

Hello everyone, todays screencast is about implementing a well-known programming challenge called Fizzbuzz. If you haven't heard of it, it's an extremely simple task designed to weed out programmers who can't code their way out of a paper bag.

The task is to iterate from one to a hundred, and for each number, print out the number then "Fizz" if it's a multiple of three, "Buzz" if it's a multiple of five, or "FizzBuzz" if it's a multiple of both three and five.

Sound easy enough right? But we can use it to illustrate a few different ways of doing things in ruby. We're going to go ahead and do it in plain old C first, then in different styles of ruby using recursion and enumerators.

Modulo Operator

First of all, just in case there's any mystery as to how you do this, the only thing that's perhaps new is how we figure out whether one number is a multiple of another. We do that using the modulo operator. Most programming languages use the % symbol to indicate modulo, and what it does is give you the integer remainder after division.

If you remember when you were young you probably did division like this:

5 / 3 = 1

Because three fits into five once, with a remainder of 2. Modulo gives you the remainder after division:

5 % 3 = 2

In some cases, the modulo is zero:

15 / 5 = 3

15 % 5 = 0

Five fits into fifteen three times with no remainder, so we say that fifteen is a multiple of five. We can generalize this to any number like this:

class Numeric
  def multiple_of?(n)
    0 == self % n
  end
end

15.multiple_of? 3 #=> true
15.multiple_of? 5 #=> true
15.multiple_of? 7 #=> false

We're not going to monkeypatch numeric in our implementations, but we will use the modulo operator to determine if a number is a multiple of three or five.

C implementation

The absolute simplest way we could possibly implement this is in a little C program. Here's what it might look like:

#include <stdio.h>

int main() {
  int i = 1;
  while (i++ < 100) {
    printf("%d: ", i);
    if (0 == i % 3) {
      printf("Fizz");
    }
    if (0 == i % 5) {
      printf("Buzz");
    }
    printf("\n");
  }
}

Imperative Ruby Implentation

We can transplant that code into a ruby file and do more or less the same thing:

#! /usr/bin/env ruby

i = 1
while i < 101
  print "#{i}: "
  print 'Fizz' if 0 == i % 3
  print 'Buzz' if 0 == i % 5
  i += 1
end

No one writes ruby code like this though, or at least they shouldn't. If you're coming from another C-like language this is probably what your code will start out like, but idiomatic Ruby uses other mechanisms for iterations that we'll take a look at later.

Recursive Ruby Implementation

Another way you might do this is by using recursion. Recursion is simply about functions calling themselves in a loop if a certain base case hasn't been met:

#! /usr/bin/env ruby

def fizzbuzzer(n = 1)
  if n < 101
    print "#{i}: "
    print 'Fizz' if 0 == i % 3
    print 'Buzz' if 0 == i % 5
    print "\n"
    fizzbuzzer(n + 1)
  end
end

fizzbuzzer

So here the base case is the same conditional we used for iterating in the previous example, only we're checking the argument that gets passed into fizzbuzzer. We print the output as expected and then call fizbuzzer again if the argument is still under 101, else we do nothing.

Recursion is one of the fundamental building blocks of functional programming. I'm a big fan of functional programming in general and learning a language that supports it like Haskell is very much worth your time.

At the same time, coding in this way goes against the grain in Ruby for a number of reasons. Functional programming languages have all sorts of optimisations in place to make techniques like recursion less performance intensive.

As it stands you're making the ruby interpreter do a hundred nested function calls in this code, and it's simply not designed to work in this way. Whenever you do a function call, the context you're currently in gets pushed onto a stack. When you return from a function, the context is popped off that stack. If you do ten thousand nested function calls, that pushes ten thousand contexts on to the stack.

The size of the system stack is limited. You can see what it is on your system by running the following command:

ali@cassini ~/C/happy-bear-software λ ulimit -a
Maximum size of core files created                           (kB, -c) 0
Maximum size of a process’s data segment                     (kB, -d) unlimited
Maximum size of files created by the shell                   (kB, -f) unlimited
Maximum size that may be locked into memory                  (kB, -l) unlimited
Maximum resident set size                                    (kB, -m) unlimited
Maximum number of open file descriptors                          (-n) 2560
Maximum stack size                                           (kB, -s) 8192
Maximum amount of cpu time in seconds                   (seconds, -t) unlimited
Maximum number of processes available to a single user           (-u) 709
Maximum amount of virtual memory available to the shell      (kB, -v) unlimited

As you can see for me that returns a maximum stack size of 8192kb. Let's say that each stack frame takes up around 1kb of memory. I'm guessing that if we were to do 10000 nested function calls we'd probably exceed that limit and cause a stack too deep error, let's give it a try...

[STACK OVERFLOW]

So that breaks as expected. Languages that support functional programming usually feature something called tail-call optimisation, which basically means that it discards stack frames that it knows for sure it can, so you won't have this problem with say Haskell.

Ruby Enumerator Implementation

Another way you could do this in Ruby is using Enumerators. Here's the easiest possible Enumerator you could create to do fizzbuzz for you:

fizzbuzzerator = Enumerator.new do |yielder|
  1.upto(BigDecimal::INFINITY) do |i|
    line = "#{i}: "
    line += 'Fizz' if 0 == i % 3
    line += 'Buzz' if 0 == i % 5
    yielder << line
  end
end

fizzbuzzerator.take(100).each { |l| puts l }

Here all we're doing is looping from 0 to infinity in our enumerator and yielding the correct fizzbuzz line for each number. This code doesn't loop to infinity because we're only taking a hundred values from it. The line yielder << line blocks if we take no more values from the enumerator.

This is a nice abstraction which is useful if we don't know in advance how many lines we're going to generate fizzbuzz output for. It's a little heavy handed for our use case as a little technical interview programming challenge, but definitely a good technique to have up your sleeve. Abstractions like this are present in most object oriented languages, including iterators in C++, PHP and Java, and an equivalent in Python.

Idiomatic Ruby Implementation

Finally, here's what I'd write in ruby without really thinking:

1.upto(100).each do |i|
  print "#{i}: "
  print 'Fizz' if 0 == i % 3
  print 'Buzz' if 0 == i % 5
  print "\n"
end

each is what we use typically use for iteration in Ruby and the upto method provides a convenient shorthand for iterating up to a known value. There's not much of note going on here apart from that!

Anyway, I hope this screencast has been at least a little interesting and you were able to pick up a trick or two. Until next time!