FizzBuzz is one of the most well-known katas. It originated as a game to teach children about division, and is now sometimes used in programming job interviews as a minimum standard.


Definition

Iterating through the numbers between 1 and n:

  • If the number divisible by three, print "Fizz"
  • If the number is divisible by five, print "Buzz"
  • If the number is divisible by both three and five, print "FizzBuzz"
  • If the number is not divisible by three or five, print the number

E.g. fizzbuzz(10) would print:

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz

For our solution, we are going to return a newline-separated string, rather than printing individual values

Attempt 1: iterate

The most simple solution is what interviewers are looking for, as it demonstrates coding ability at the minimum standard.

  • Iterate through numbers 1 to n
  • For each number, check what it is divisible by, create a string accordingly
  • Return all the strings

For our first method, we're going to use some python features (but not many, this approach is almost pseudo-code)

Things to note:

  • range(0, 10) will print all the numbers from 0-9, but not 10.We need to add a wee +1 to make sure we're iterating through all numbers
In [1]: list(range(1, 10))
Out[1]: [1, 2, 3, 4, 5, 6, 7, 8, 9]

In [2]: list(range(1, 10+1))
Out[2]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  • You can append to a string using +=
In [4]: string = 'a'
In [5]: string += 'bcd'
In [6]: string
Out[6]: 'abcd'
  • You can use a boolean expression to return a 'truthy' value, which I though was pretty cool
In [8]: line = ''
In [9]: i = 1
In [10]: (line or i)
Out[10]: 1
class Basic:
    def fizzbuzz(n=100):
        every = []
        for i in range(1, n+1):
            line = ''
            if i % 3 == 0:
                line += 'fizz'
            if i % 5 == 0:
                line += 'buzz'

            every.append(line or str(i))
        return '\n'.join(every)

Let's see if it works!

In [13]: print(fizzbuzz.Basic.fizzbuzz(10))
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz

Noice, we've implemented our basic solution and got a job! But maybe there's a better way?

Attempt 2: Map

This attempt is pretty similar, but it uses map to execute the same function over every number in the sequence.

class Map:
    def fizzbuzz(n=100):
        return '\n'.join(list(map(Map.rep, range(1, n))))

    def rep(n):
        line = ''
        if n % 3 == 0:
            line += 'fizz'
        if n % 5 == 0:
            line += 'buzz'
        return line or str(n)

Attempt 3: Lazy/Functional

After a lot of tinkering, I finally made a functional/lazy solution! I'm not going to go into detail around this solution - I'll save that for a standalone post, as it will get quite involved.

from itertools import cycle, count, islice

class Lazy:
    def fizzbuzz(n=100): 
        return '\n'.join(
            word or str(i) for word, i in Lazy.sequence(n)
        )

    def sequence(n):
        'Return a lazy fizzbuzz sequence of the required size'
        return islice(
            Lazy.cycle_with_count(Lazy.fb_seq()),
            n
        )

    def fb_seq():
        return map(''.join, zip(
            cycle(['', '', 'Fizz']),
            cycle(['', '', '', '', 'Buzz'])
        ))

    def cycle_with_count(seq, start=0):
        return zip(seq, count(start))

Speed

Python 3.6.5 |Anaconda, Inc.| (default, Apr 26 2018, 08:42:37)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.4.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import fizzbuzz

In [2]: %timeit fizzbuzz.Basic.fizzbuzz(100)
32.4 µs ± 1.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [3]: %timeit fizzbuzz.Map.fizzbuzz(100)
34.4 µs ± 1.85 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [4]: %timeit fizzbuzz.Lazy.fizzbuzz(100)
34.6 µs ± 1.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
n method time
100 Basic 34.1 µs
100 Map 36.8 µs
100 Lazy 36.3 µs
10_000 Basic 3.41 ms
10_000 Map 3.48 ms
10_000 Lazy 3.22 ms
1_000_000 Basic 380 ms
1_000_000 Map 396 ms
1_000_000 Lazy 396 ms

Conclusion

The fizzbuzz challenge ended up being more interesting that I initially expected. I haven't encountered another Kata yet where the most basic solution performs neck-and-neck with solutions that require a more in-depth knowledge.

'Til next time