Python - gregorymorrison/euler1 GitHub Wiki
Python happens to be my favorite language. This language, introduced in 1991, is a simple, dynamic, strongly typed, multiparadigm language language known for its small syntax and large library. Although Python's philosophy is that there should only be one way to do something, the multiparadigm nature of the language allows us to write Euler1 in lots of different ways.
Python does straight Procedural - the Missionary Position of paradigms:
#!/usr/bin/python
# Euler1 in Python
def euler1(x):
result = 0
for i in range(x):
if i%3==0 or i%5==0:
result += i
return result
print ("Euler1 =", euler1(1000))
This can be made a little more elegant using Python's built-in support for iterators - generators:
#!/usr/bin/python3
# Euler1 in Python
def euler(n):
i = 0
while i < n:
if i%3==0 or i%5==0:
yield i
i += 1
def euler1(n):
return sum(euler(n))
print ("Euler1 =", euler1(1000))
Python gives you OOP. Here's a somewhat contrived version in which I create a class with a constructor, a member variable, and a method. It's contrived because OOP is way overkill for so simple a problem:
#!/usr/bin/python3
# Euler1 in Python
class Euler1:
def __init__(self, size):
self.size = size
def solve(self):
self.result = 0
for i in range(self.size):
if i%3==0 or i%5==0:
self.result += i
euler1 = Euler1(1000)
euler1.solve()
print ("Euler1 =", euler1.result)
Python fully supports the Functional paradigm. Here's an example where the problem is decomposed into the canonical Lambda, Map, Filter, and Reduce. Obviously myMap() here does nothing - it merely returns what's passed in; it's just included for illustration. Notice one of the hallmarks of the Functional paradigm - no mutable state. There is no variable manipulation here - only declarations:
#!/usr/bin/python3
# Euler1 in Python
from functools import reduce
myMap = lambda size: map(lambda x: x, range(size))
myFilter = lambda ints: filter(lambda x: x%3==0 or x%5==0, ints)
myReduce = lambda filtered: reduce(lambda x,y: x+y, filtered)
print ("Euler1 =", myReduce(myFilter(myMap(1000))))
Here is another Functional construct in Python - List Comprehension - a loop, a condition, and an accumulator, all in one line - very nice! This is probably the most idiomatic Python (Pythonic) example here (even though Guido hates lambdas):
#!/usr/bin/python3
# Euler1 in Python
euler1 = lambda x: sum(i for i in range(x) if i%3==0 or i%5==0)
print ("Euler1 =", euler1(1000))
Here's a version where we generate three ranges - multiples of 3, 5, and 15, and we subtract the multiples of 15 since they're going to be the duplicate values found in the other two sequences:
#!/usr/bin/python3
# Euler1 in Python
def euler1(size):
return sum(range(3, size, 3)) \
+ sum(range(5, size, 5)) \
- sum(range(15, size, 15))
print ("Euler1 =", euler1(1000))
Here's a different version - I simply sum up three collections of ints up to 1000, one step 3, one step 15 starting at 5, and one step 15 starting at 10. This covers all the ints divisible by 3 or 5 with no overlaps. Cool!
#!/usr/bin/python3
# Euler1 in Python
def euler1(size):
return sum(range(3, size, 3)) \
+ sum(range(5, size, 15)) \
+ sum(range(10, size, 15))
print ("Euler1 =", euler1(1000))
Python's extremely flexible nature even supports the Prototype paradigm. Classes are actually containers that are modifiable at runtime. Check this out - our class is nothing more than a dictionary into which we can shove whatever we want:
#!/usr/bin/python3
# Euler1 in Python
class Euler1:
pass
euler1 = Euler1()
euler1.range = 1000
euler1.solver = lambda x: sum(i for i in range(x) if i%3==0 or i%5==0)
euler1.result = euler1.solver(euler1.range)
print ("Euler1 =", euler1.result)
To illustrate this, we can rewrite the last example using Python's built-in dictionary object. One limitation - Python's dictionary requires its objects to be fully resolved before being added, so I have to create temporary variables for solver and result before they get added:
#!/usr/bin/python3
# Euler1 in Python
euler1 = dict()
euler1[range] = 1000
solver = lambda x: sum(i for i in range(x) if i%3==0 or i%5==0)
euler1[solver] = solver
result = euler1[solver] (euler1[range])
euler1[result] = result
print ("Euler1 =", euler1[result])
Python doesn't do tail recursion well, though. Apparently Guido doesn't believe in it. The following, while logically correct, only narrowly misses blowing the stack - Python's stack is only 1000 deep by default:
#!/usr/bin/python3
# Euler1 in Python
import sys
sys.setrecursionlimit(1500) # Set the maximum recursion depth to 1500
def euler1(n, acc=0):
if n==1: return acc
if n%3==0 or n%5==0:
return euler1(n-1, acc+n)
else:
return euler1(n-1, acc)
print ("Euler1 =", euler1(999))
Let's try a variant based on QuickSort! Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we'll filter the pivot value, converting it to 0 if it's not divisible. I was actually able to run this out to 60M places without blowing the stack:
#!/usr/bin/python3
# Euler1 in Python
def euler1(L):
if len(L) == 0: return 0
# calculate the index at which the list should be divided into two sublists
pivot = round(len(L)/2)
# call the function recursively with a sublist of the left half of the original list
pre = euler1(L[:pivot])
# call the function recursively with a sublist of the right half of the original list
post = euler1(L[pivot+1:])
# check if the number at the pivot index is a multiple of 3 or 5
# and save the result in val variable
val = ((L[pivot]%3==0 or L[pivot]%5==0) and L[pivot] or 0)
# return the sum of the left sublist, val and the right sublist.
return pre + val + post
print ("Euler1 =", euler1(range(1,1000)))
One more example - I just found this elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. I tried it with 1 googol (1.0 × 10^100), and not only did Python actually handle this without choking, it took no measurable time to calculate! Don't sweat it if this seems inscrutable; click the blog link above for an explanation. Here is my version:
#!/usr/bin/python3
# Euler1 in Python
from math import floor;
def mySum(n, size):
return n * ((floor(size/n)**2 + floor(size/n)) / 2)
def euler1(size):
return floor(mySum(3,size) + mySum(5,size) - mySum(15,size))
print ("Euler1 =", euler1(999))
Now, to execute our Python script, simply call it:
$ ./euler1.py
Euler1 = 233168