Generadores, funciones lambda y el problema 2 del proyecto Euler

En el problema 2 del proyecto Euler hay que hallar la suma de los números pares en la secuencia de Fibonacci:

Even Fibonacci numbers

Problem 2

Published on 19 October 2001 at 06:00 pm [Server Time]

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Con las funciones lambda y filter podemos extraer los números pares de una secuencia:

1. secuencia_par = filter(lambda x: x%2 == 0, [1,2,3,4,5,6])
3. print secuencia_par
4. Out[1]: [2, 4, 6]

Los generadores son como funciones pero en vez de la sentencia return tienen sentencias yield que generan una sola salida y detienen la ejecución del código hasta que vuelven a ser llamadas. Por ejemplo, el siguiente código genera valores por encima del parámetro ingresado que pueden ser llamados con el método next():

1. def contador(x):
2.     while True:
3.         yield x
4.         x += 1
5.        
7. c = contador(3)
9. c.next()
10. Out[2]: 3
12. c.next()
13. Out[3]: 4
15. c.next()
16. Out[4]: 5
18. c.next()
19. Out[5]: 6

La secuencia de fibonacci se puede obtener con un generador lo que es ventajoso en términos de manejo de memoria:

1. def fibonacci(num):
2.         x,y = 0,1
3.         while x < num:
4.                 yield x
5.                 x, y = y, x + y

Combinando la función sum() con filter y lambda podemos resolver el problema 2 del proyecto Euler:

1. lista = fibonacci(4000000) #un generador
2. pares = lambda x: x%2 == 0 #selecciona los números pares
3. print sum(filter(pares, lista))

El resultado es 4613732.