Using FizzBuzz as an exercise in coding

fizzbuzz.py

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
Sure, I had been aware that FizzBuzz existed, and had heard about it in
passing, but never had it actually been used in any interview I had been a
part of. Until now. The actual premise of the question is just as simple as
it was designed to be, but what if you wanted to improve upon it? This is
just a random exercise in improving the algorithm. For science.

FIZZBUZZ:
Write a program that prints the numbers from 1 to 100. But for multiples
of three print “Fizz” instead of the number and for the multiples of five
print “Buzz”. For numbers which are multiples of both three and five
print “FizzBuzz”.

NOTE: the functions below create an array and return the array instead of
printing the numbers in-place; this is for demonstration purposes and partly
because string formatting and writing output are far more expensive operations.

Sample Timings:
$ ./fizzbuzz.py
<... normal fizzbuzz output ...>
100000 repetitions each
  3.2291s = fizz_buzz_basic()
  3.0338s = fizz_buzz_dry()
  2.6494s = fizz_buzz_tracked()
  3.2943s = fizz_buzz_single()
  6.1235s = fizz_buzz_slow_params()
  3.7059s = fizz_buzz_params()
  7.4557s = fizz_buzz_slow_params(6, 7)
  4.9164s = fizz_buzz_params(6, 7)
  2.7081s = fizz_buzz_tracked_params()
  2.5694s = fizz_buzz_tracked_params(6, 7)
"""
from __future__ import absolute_import, unicode_literals

import timeit

fizzbuzz = 'FizzBuzz'
fizz = 'Fizz'
buzz = 'Buzz'


def fizz_buzz_basic(stop=100):
    """ quintessential implementation of FizzBuzz """
    result = []
    for num in range(1, stop + 1):
        if num % 3 == 0 and num % 5 == 0:
            result.append(fizzbuzz)
        elif num % 3 == 0:
            result.append(fizz)
        elif num % 5 == 0:
            result.append(buzz)
        else:
            result.append(num)

    return result


def fizz_buzz_dry(stop=100):
    """ DRY-er FizzBuzz """
    result = []
    for num in range(1, stop + 1):
        divthree = num % 3 == 0
        divfive = num % 5 == 0
        if divthree and divfive:
            output = fizzbuzz
        elif divthree:
            output = fizz
        elif divfive:
            output = buzz
        else:
            output = num
        result.append(output)

    return result


def fizz_buzz_tracked(stop=100):
    """ keep track of multiples of 3 and 5 to avoid modulo """
    result = []
    three = 3
    five = 5
    for num in range(1, stop + 1):
        if num == three and num == five:
            output = fizzbuzz
        elif num == three:
            output = fizz
        elif num == five:
            output = buzz
        else:
            output = num
        result.append(output)
        if num == three:
            three = three + 3
        if num == five:
            five = five + 5

    return result


def fizz_buzz_single(stop=100):
    """
    Utilize the Least Common Multiple to map to responses.

    With a little bit of math, we can reduce it to just a single modulo
    operation and use the result to determine the appropriate response.

    The LCM for 3 and 5 is 15, so we use 15 for the modulo. If the result is
    0, then we know it is divisible by both numbers and the output should be
    'FizzBuzz'. If the result is 5, or 10, then we know it is divisible by 5,
    but not by 3 so the output should be 'Buzz'. If the result is 3, 6, 9, or
    12, then we know the number is divisible by 3, but not by 5 thus the
    output should be 'Fizz'.
    """
    result = []
    for num in range(1, stop + 1):
        val = num % 15
        if val == 0:
            output = fizzbuzz
        elif val in [3, 6, 9, 12]:
            output = fizz
        elif val in [5, 10]:
            output = buzz
        else:
            output = num
        result.append(output)

    return result


def _findlcm(first, second):
    greater, lower = (first, second) if first > second else (second, first)
    worst_case = greater * lower
    for num in range(greater, worst_case + 1, greater):
        if num % lower == 0:
            return num


def fizz_buzz_slow_params(fizznum=3, buzznum=5, stop=100):
    """
    This parameterizes the previous approach and generalizes it.

    The 'Fizz' and 'Buzz' numbers are now parameters allowing essentially any
    positive integers to be passed, and will automatically assign 'FizzBuzz'
    to the LCM of the two numbers. Once the LCM is found, each divisor is
    assigned to the appropriate response.

    It is also important to note that I used a dict for the mapping on purpose
    to demonstrate that while it is logically an easy way to map responses, it
    adds significant overhead as shown by the profiling.
    """
    result = []
    lcm = _findlcm(fizznum, buzznum)
    mapping = {0: fizzbuzz}
    for num in range(fizznum, lcm + 1, fizznum):
        mapping[num] = fizz
    for num in range(buzznum, lcm + 1, buzznum):
        mapping[num] = buzz

    for num in range(1, stop + 1):
        try:
            result.append(mapping[num % lcm])
        except KeyError:
            result.append(num)

    return result


def fizz_buzz_params(fizznum=3, buzznum=5, stop=100):
    """
    This uses lists instead of a dict for comparisons, but is otherwise
    identical to the previous approach.
    """
    result = []
    lcm = _findlcm(fizznum, buzznum)
    fizzlist = range(fizznum, lcm + 1, fizznum)
    buzzlist = range(buzznum, lcm + 1, buzznum)
    for num in range(1, stop + 1):
        val = num % lcm
        if val == 0:
            result.append(fizzbuzz)
        elif val in fizzlist:
            result.append(fizz)
        elif val in buzzlist:
            result.append(buzz)
        else:
            result.append(num)

    return result


def fizz_buzz_tracked_params(fizznum=3, buzznum=5, stop=100):
    """
    Parameterized tracking approach.

    By now the empirical evidence shows that while the LCM approach might be
    more creative or unique, so far the tracked approach has been the most
    efficient. So here we make the original allow for dynamic parameters.
    While this approach may not be flashy or pretty, the fact that it only
    uses simple operations and comparisons allows it to be significantly
    faster than many of the other approaches yet offer the same flexibility.
    """
    result = []
    currentfizz = fizznum
    currentbuzz = buzznum
    for num in range(1, stop + 1):
        if num == currentfizz and num == currentbuzz:
            output = fizzbuzz
        elif num == currentfizz:
            output = fizz
        elif num == currentbuzz:
            output = buzz
        else:
            output = num
        result.append(output)
        if num == currentfizz:
            currentfizz = currentfizz + fizznum
        if num == currentbuzz:
            currentbuzz = currentbuzz + buzznum

    return result


if __name__ == '__main__':
    fbparams = (
        (3, 5),
        (3, 5),
        (3, 5),
        (3, 5),
        (3, 5),
        (3, 5),
        (6, 7),
        (6, 7),
        (6, 7),
    )
    header = ' | '.join(['  {0}, {1}  '.format(x, y) for x, y in fbparams])
    trials = (
        fizz_buzz_basic(),
        fizz_buzz_dry(),
        fizz_buzz_tracked(),
        fizz_buzz_single(),
        fizz_buzz_slow_params(),
        fizz_buzz_params(),
        fizz_buzz_slow_params(6, 7),
        fizz_buzz_params(6, 7),
        fizz_buzz_tracked_params(6, 7),
    )
    num_trials = len(trials)
    linebreak = '=*='.join(['========' for i in range(num_trials)])
    repetitions = 100000

    print('generating output...')
    output = (
        linebreak,
        header,
        linebreak,
        '\n'.join([' | '.join(
            ['{0:<8}'.format(x) for x in item]
        ) for item in zip(*trials)]),
        linebreak,
        header,
        linebreak,
        '{0} repetitions each'.format(repetitions),
        '\n'.join([
            '{time:>8.4f}s = {func}({params})'.format(
                func=func, params=p, time=timeit.timeit(
                    stmt='{0}({1})'.format(func, p),
                    setup='from __main__ import {0}'.format(func),
                    number=repetitions
                )
            ) for func, p in (
                ('fizz_buzz_basic', ''),
                ('fizz_buzz_dry', ''),
                ('fizz_buzz_tracked', ''),
                ('fizz_buzz_single', ''),
                ('fizz_buzz_slow_params', ''),
                ('fizz_buzz_params', ''),
                ('fizz_buzz_slow_params', '6, 7'),
                ('fizz_buzz_params', '6, 7'),
                ('fizz_buzz_tracked_params', ''),
                ('fizz_buzz_tracked_params', '6, 7'),
            )
        ]),
        linebreak,
    )

    print('\n'.join(output))