FizzBuzz for CodeEval

Question

I'm a beginner programmer and decided to try some coding challenges. I found CodeEval and attempted the first challenge, FizzBuzz. However upon submitting my code I found that my submission only partially solved the problem.

Link to the challenge

Challenge Description:

Players generally sit in a circle. The first player says the number “1”, and each player says next number in turn. However, any number divisible by X (for example, three) is replaced by the word fizz, and any divisible by Y (for example, five) by the word buzz. Numbers divisible by both become fizz buzz. A player who hesitates, or makes a mistake is eliminated from the game.

Write a program that prints out the final series of numbers where those divisible by X, Y and both are replaced by “F” for fizz, “B” for buzz and “FB” for fizz buzz.

Input Sample:

Your program should accept a file as its first argument. The file contains multiple separated lines; each line contains 3 numbers that are space delimited. The first number is the first divider (X), the second number is the second divider (Y), and the third number is how far you should count (N). You may assume that the input file is formatted correctly and the numbers are valid positive integers.

For Example:

1) 3 5 10

2) 2 7 15

Output Sample:

Print out the series 1 through N replacing numbers divisible by X with “F”, numbers divisible by Y with “B” and numbers divisible by both with “FB”. Since the input file contains multiple sets of values, your output should print out one line per set. Ensure that there are no trailing empty spaces in each line you print.

1) 1 2 F 4 B F 7 8 F B

2) 1 F 3 F 5 F B F 9 F 11 F 13 FB 15

How can I improve my code speed-wise and memory-wise so that I can fully complete this challenge?

The code is working for my test cases.

import sys


def main(name_file):
    _test_cases = open(name_file, 'r')
    for test in _test_cases:
        result = ""
        if len(test) == 0:
            break
        else:
            test = test.split()
            first_div = int(test[0])
            second_div = int(test[1])
            lim = int(test[2])
            for i in range(1, lim+1):
                if i % (first_div*second_div) == 0:
                    result += "FB "
                elif i % first_div == 0:
                    result += "F "
                elif i % second_div == 0:
                    result += "B "
                else:
                    result += "%d " % i
            print(result[:-1])

    _test_cases.close()
if __name__ == '__main__':
    main(sys.argv[1])

Answer 1

There is a bug in your code for those times when the two input values are not prime.

Consider an instance when the input values are 4 and 6. In this case, your code will output F for multiples of 4, and B for multiples of 6, and FB for multiples of 24.... great... but, is it? No, 12 is a multiple of both, but will only print "F ".

If you want to use the optimized cascading-if-else version of FizzBuzz, then you need to ensure the inputs are both prime, or have no common factors.

It would often still be faster to compute the common factors and then after that do the system you have.

Answer 2

First, you have file handling with the FizzBuzz code. You should probably change it so main, handles the file, where a new function say fizz_buzz handles the FizzBuzz part.

You open a file, and thankfully you close it, however it is better to use with. This means that the file will always close even if your program breaks.

with open(name_file, 'r') as _test_cases:
    for test in _test_cases:
        # Rest of code

That way you won't have to _test_cases.close(), and you won't ever forget to close the file.

You should use Pythons empty test rather than len. This is as anything that is empty will result in False otherwise True. Also, you can remove the else, as it will not run.

if not test:
    break
# Rest of code

String concatenation is very poor, always build a list and use ''.join(list) or an alternate way if you need to concatenation a lot of strings. Also this will make it so you don't have to do result[:-1].
This is as internally strings are non-mutable, and so adding even one character means that you have to move the entire string to another place in memory, before adding the new string to it. Leading to horrific performance.

You should not use % to input variables in text, this is as it has some quirks, and str.format is more supported.

You should also put result in the else statement to prevent people misreading it outside the for loop.

If you were to use all the above you should get something like:

def fizz_buzz(constraints):
    FIZZ = int(constraints[0])
    BUZZ = int(constraints[1])
    FIZZ_BUZZ = FIZZ * BUZZ
    result = []
    for number in range(1, int(constraints[2]) + 1):
        if number % FIZZ_BUZZ == 0:
            result.append("FB")
        elif number % FIZZ == 0:
            result.append("F")
        elif number % BUZZ == 0:
            result.append("B")
        else:
            result.append(str(number))
    return result

def main(name_file):
    with open(name_file, 'r') as test_cases:
        for line in test_cases:
            if not test:
                break
            print(' '.join(fizz_buzz(line.split())))

if __name__ == '__main__':
    main(sys.argv[1])

Finally as my review for performance is just don't do str += str. There is still potential speed problems, (three mods) and so say if it's not 'good enough'.

---

As this is tagged performance, I use the test:

def time_it_maker(*input_):
    def time_it(fn, name):
        iterations = 1000
        start = time.time()
        for _ in range(iterations):
            fn(*input_)
        stop = time.time()
        print(name, '=', stop - start)
    return time_it

time_it = time_it_maker('3 5 100000')

And got the result:

Original = 64.22514319419861
fizz_buzz = 54.241493463516235

Answer 3

You asked how to improve your code speed-wise and memory-wise, so to comment on just the speed-speed wise component:

It turns out that the % operation is expensive, and you're also doing a multiplication. So how do you avoid the % operation? Use separate counters for fizz_div_counts and buzz_div_counts, and reset them to zero (or 1) every time they hit their limit. Something like this:

 fizz_div_counts = 0
 buzz_div_counts = 0
 for number in range(1, int(constraints[2]) + 1):
        fizz_div_counts++
        buzz_div_counts++
        append_number = true
        result.append(" ")
        if fizz_div_counts == FIZZ:
            result.append("F")
            fizz_div_counts = 0
            append_number = false
        if buzz_div_counts == BUZZ:
            result.append("B")
            buzz_div_counts = 0
            append_number = false
        if append_number:
            result.append(str(number))
    return result

I'm not a python programmer, so this might not run out of the box, but it's the general idea. Also, the fizz_div_counts and buzz_div_counts might have to be reset to 1 instead of 0.

If you can avoid file IO, that would be your biggest gain, regardless of other optimizations, but the problem specifically asks to read from a file.

You also don't need a special case for fizz_buzz, if you do the if statements separately. The B just gets appended after the F, so you get FB.

It would be great if you could time this on your machine, I'm really curious as to how long this takes. Please just post a comment with the times.