Skip to content

Instantly share code, notes, and snippets.

@neuroticnerd
Last active September 9, 2016 19:25
Show Gist options
  • Save neuroticnerd/75d8120b43359f615bb5f3cbf4c0c23d to your computer and use it in GitHub Desktop.
Save neuroticnerd/75d8120b43359f615bb5f3cbf4c0c23d to your computer and use it in GitHub Desktop.
Using FizzBuzz as an exercise in coding
#!/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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment