August 7, 2018 · intermediate python kata

Kata #3: FizzBuzz

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:

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.

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

Things to note:

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]
In [4]: string = 'a'
In [5]: string += 'bcd'
In [6]: string
Out[6]: 'abcd'
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

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket