9
\$\begingroup\$

Just starting out in Python, coming from a C/C++ background. Any comments on style, how its solved, unseen redundancies, is it 'Pythonic' enough or am I lacking in the general syntax structure?

#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Created on Jan 12, 2018

@author: Anonymous3.1415
'''

#is test number divisable by divisor
def divisable_by(divisor,test_num):
    if not test_num % divisor:
        return True
    else:
        return False
'''
FUNCTION DEF: nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end)
PURPOSE: Find list of natural numbers that are divisable by either divisor1 or divisor2
@ var: (nat_nums_list) list of numbers that satisfy conditon
@ var: (nat_num_iterator) used to iterate through the natural numbers withing a given range

'''
def nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end):
    nat_nums_list = [] 
    for nat_num_iterator in range(range_start, range_end):
        if divisable_by(divisor1, nat_num_iterator) or divisable_by(divisor2, nat_num_iterator):
            nat_nums_list.append(nat_num_iterator)
        nat_num_iterator += 1
    return nat_nums_list


nat_nums_div_3_5 = [] # Natural numbers divisable by either 3 or 5
divisor_3, divisor_5 = 3, 5
range_start, range_end = 1, 1000

nat_nums_div_3_5 = nat_nums_divisors_1_or_2(divisor_3, divisor_5, range_start, range_end)

nat_nums_div_3_5_sum = sum(nat_nums_div_3_5)
print ("The sum of Natural Numbers in range: [%d, %d]; divisable by either 3 or 5 is: %d") % (range_start, range_end, nat_nums_div_3_5_sum)
\$\endgroup\$
  • \$\begingroup\$ made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward. \$\endgroup\$ – Anonymous3.1415 Jan 13 '18 at 6:52
  • 1
    \$\begingroup\$ In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u \$\endgroup\$ – Chris G Jan 13 '18 at 15:13
  • \$\begingroup\$ @Chris-G, Awesome, I appreciate it! \$\endgroup\$ – Anonymous3.1415 Jan 13 '18 at 19:26
  • \$\begingroup\$ The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which is set(A) + set(B) - interaction(A, B). That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do. \$\endgroup\$ – Reti43 Jan 14 '18 at 13:30
10
\$\begingroup\$

Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for loops into the list constructor:

def sum_of_divisors():
    return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])

Here we could also use a generator expression, which would mean simply replacing the [] with () However this would look ugly (we would have sum((...))), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be

def sum_of_divisors():
    """
    Find sum of natural numbers between 1 and 1000,
    that are divisible by either 3 or 5.
    """
    return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)

I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors) in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__,.

Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:

def sum_of_divisors(start, end, divisors):
    """
    Find sum of natural numbers between `start` and `end`,
    that are divisible by any of the `divisors`.
    """
    return sum(i for i in range(start, end + 1)
               if any(i % k == 0 for k in divisors))

Call it with:

sum_of_divisors(1, 1000, {3, 5})

to get the base answer. Here the {} is a set but it can be any iterable. The any function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True (And so does all, as soon as it finds a False).

\$\endgroup\$
  • \$\begingroup\$ Upvoted for list comprehensions. \$\endgroup\$ – Oleg Lobachev Jan 13 '18 at 23:47
  • \$\begingroup\$ @MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes... \$\endgroup\$ – Graipher Jan 15 '18 at 14:31
11
\$\begingroup\$

Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.

  • The construct

        if condition:
            return True
        else
            return False
    

    is a long way to say

        return condition
    
  • The in range loop which modifies its loop variable, as in

    for nat_num_iterator in range(range_start, range_end):
        ....
        nat_num_iterator += 1
    

    gives me shivers. Here you increment nat_num_iterator twice per iteration. If it is an intent, use range(range_start, range_end, 2).

\$\endgroup\$
  • \$\begingroup\$ what does constant time mean? \$\endgroup\$ – Anonymous3.1415 Jan 13 '18 at 4:52
  • \$\begingroup\$ @Anonymous3.1415 Loosely speaking, it means no loops. \$\endgroup\$ – vnp Jan 13 '18 at 4:52
  • \$\begingroup\$ so there's probably an equation to find the sum that I was unaware? \$\endgroup\$ – Anonymous3.1415 Jan 13 '18 at 4:55
  • \$\begingroup\$ @vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment. \$\endgroup\$ – Anonymous3.1415 Jan 13 '18 at 4:57
  • 4
    \$\begingroup\$ @vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty \$\endgroup\$ – WorldSEnder Jan 13 '18 at 10:29
6
\$\begingroup\$

Your code is bloated. You could have written it like this:

def sum_of_divisors():
    sum = 0
    for i in range(1, 1001):
        if i % 3 == 0 or i % 5 == 0:
            sum += i
    return sum

This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.

Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.

\$\endgroup\$
2
\$\begingroup\$

Simpler (Didn't look up the formula yet), but much simpler:

#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Created on Jan 12, 2018

@author: Anonymous3.1415
'''

sum_multiples = 0
for i in range(1,1000): 
    if i % 3 == 0 or i % 5 == 0:
        sum_multiples += i
print(sum_multiples)
\$\endgroup\$
2
\$\begingroup\$

I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.

limit = 1000

threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]

allnums = set(threes) | set(fives)

print(sum(allnums))

a very similar approach, not using sets:

limit = 1000

threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))

print(threes + fives - fifteen)

and a generalized version that again uses a set and works for any and any number of divisors:

from functools import reduce

def numsums(limit=1000, divisors=None):
    if divisors is None:
        divisors = []
    nums = []
    for ind in range(len(divisors)):
        nums.append( [i for i in range(0,limit,divisors[ind])])
    allnums = set(nums[0])
    allnums = reduce(allnums.union, nums[1:], allnums)
    return sum(allnums)

print(numsums(1000,[3,5]))

This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.

\$\endgroup\$
  • \$\begingroup\$ I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance. \$\endgroup\$ – Alan Hoover Jan 14 '18 at 1:59
  • \$\begingroup\$ Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time. \$\endgroup\$ – Alan Hoover Jan 14 '18 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.