Project Euler: Problemas 1 y 2 con Clojure

Para aprender un lenguaje viene bien comparar la forma en que se resuelven las cosas en ese lenguaje con otros que ya conoces y, casualidades de la vida, he encontrado una manera muy cómoda de comparar Clojure con otros lenguajes.

Eduard Tomás me lo ha puesto en bandeja avisándome de una especie de competición en la que están tratando de resolver problemas del Proyecto Euler usando distintos lenguajes. De momento el propio Eduard está usando Scala, Quique Martínez C#, Alex Casquete F#, Toni Recio Javascript y Nicolás Herrera Python.

Obviamente todo el mundo estaba deseando ver un lenguaje tan bonito como Clojure, así que allá vamos.

OJO: No es la primera vez que intento resolver problemas del Proyecto Euler, y tengo que reconocer que llega un momento en que no recuerdo suficientes matemáticas para seguir avanzando, así que no sé cuan lejos llegaré. De todas formas, siempre me puedo aprovechar del trabajo de otros y traducirlo a Clojure.

Problema 1: múltiplos de 3 y 5

El primer problema del Proyecto Euler es:

Calcular la suma de todos los múltiplos de 3 o 5 menores que 1000.

Una posible solución en Clojure podría ser ésta:

(reduce + 
  (filter #(or (zero? (mod % 3)) 
               (zero? (mod % 5))) 
          (range 1000)))

Se utiliza la función range para obtener una lazy sequence (¿secuencia perezosa?) con los enteros menores que 1000. Las lazy sequences funcionan de forma parecida a los IEnumerable de .NET en el sentido de que sus elementos se van calculando según son necesarios (creando potencialmente secuencias infinitas).

Una vez que tenemos la secuencia, usamos filter con una función anónima para quedarnos con los elementos divisibles entre 3 o 5 y aplicamos reduce con la función + (suma) sobre el resultado para obtener el valor pedido.

Fácil, sencillo y cabe en un tweet ;-)

Problema 2: números de Fibonacci pares

El segundo problema del Proyecto Euler es:

Cada nuevo término de la sucesión de Fibonacci se construye sumando los dos términos anteriores. Empezando con el 1 y el 2, los 10 primeros términos serían:

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

Calcular la suma de los términos con valor par de la sucesión de Fibonacci menores que cuatro millones.

Declarando algunas funciones intermedias este problema se puede resolver de forma más clara, pero he preferido resolverlo en una única expresión (que también cabe en un tweet ;-)):

(reduce + 
  (filter even? 
    (take-while (partial > 4000000) 
      (map first 
	    (iterate #(vector (second %) (reduce + %)) [1 1])))))

La primera duda que salta a la vista es ¿dónde está la función para calcular los números de Fibonacci? El cálculo se realiza con la siguiente expresión:

(iterate #(vector (second %) (reduce + %)) [1 1])

La función iterate nos permite generar una lazy sequence a partir de aplicar repetidas veces una función sobre un valor inicial, es decir, (iterate f x) generaría una secuencia con los valores:

f(x) → f(f(x)) → f(f(f(x))) → ....

La función que estamos iterando es la que genera los números de Fibonacci, pero de una forma un poco especial. Recibe un vector en el que aparecen los elementos n-2 y n-1 y calcula a partir de ellos un nuevo vector con los elementos n-1 y n.

[1 1] → [1 2] → [2 3] → [3 5] → [5 8] ...

A partir de ahí vamos aplicando funciones para quedarnos con el primer elemento de cada vector, tomar sólo los elementos menores de cuatro millones, quedarnos con los que son pares y sumarlos.

A veces se puede hacer complicado comprender este tipo de código porque hay que empezar a analizarlo “de dentro a fuera”. Para solucionar esto, podemos reescribirlo y dejarlo con un aspecto más familiar:

(->> 
  (iterate #(vector (second %) (reduce + %)) [1 1])
  (map first) 
  (take-while (partial > 4000000))
  (filter even?) 
  (reduce +))

Este código aprovecha la macro ->> para encadenar las llamadas a las funciones de una manera más legible (dentro de lo legible que resulta Clojure). La macro ->> recibe cómo parámetros un valor inicial y una serie de funciones, invoca la primera función pasando el valor inicial como último parámetro de la función, pasa el resultado de la función como último parámetro a la función siguiente, y así sucesivamente.

Existe una macro similar, ->, que en lugar de pasar el valor como último parámetro a cada función, lo pasa como primer parámetro. Utilizar una u otra depende de la forma de las funciones empleadas.

Resumen

No sé hasta donde llegaré con esto del proyecto Euler, pero de momento es una forma entretenida de ir practicando con Clojure. Posiblemente en las próximas semanas aparezcan por aquí más posts sobre los siguientes problemas. Por supuesto, si alguien se anima a corregir algo, los comentarios están abiertos.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

*

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>