Recently, I stumbled over Project Euler. It’s basically a list of mathematical problems that are solvable by a computer. Your task is to solve as many problems as you can.

The most used language for this is by far Python. So I took the chance to learn Python while solving some interesting little problems. I got hooked and the first day (or rather night) I solved about 30 of them.

Find the sum of all even Fibonacci numbers below 4’000’000:

sum = 0
f1 = f2 = 1
while f1 <= 4000000:
    if f1 % 2 == 0: sum += f1
    f1, f2 = f1 + f2, f1

print sum

Looks just like pseudo code, but is executable. Swapping two variables is just a, b = b, a. Maybe this is even more pythonic (I don’t have the feeling yet to tell):

def fib(max):
    f1 = f2 = 1
    while f1 < max:
        yield f1
        f1, f2 = f1 + f2, f1

sum = 0
for f in fib(4000000):
    if f % 2 == 0: sum += f

print sum

yield is like return but it saves the state of the function. The next call to fib will restore the value of the local variables f1 and f2 and execution continues at the point after yield. Who ever implemented a non trivial iterator in java will like this feature.

Print the sum of the digits of 100!

def factorial_func(n): return reduce(lambda accu, v: acc * v, xrange(2, n + 1), 1)

def factorial_imp(n):
    f = 1
    for i in xrange(2, n + 1): f *= i
    return f

def to_digit(s, zero='0'): return ord(s) - ord(zero)

def sum_digits(s): return reduce(lambda accu, v: accu + to_digit(v), s, 0)

print sum_digits(str(factorial(100)))

Arbitrary long integers are supported out of the box. Use functional style with reduce or imperative style with for.

For this kind of problems, I think Python really hits the sweet spot. No ceremony and the standard lib just has the functions you need. So it’s definitely a new hammer in my toolkit.

The first 50 problems are relatively easy and most time is used to implement the algorithm. But slowly the problems get harder and finding out how to solve them needs more time. But I’m confident that Python will still help me in implementing them.