Project Euler - Problema 2

Definizione

Il problema numero due ha la seguente definizione:

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.

In italiano:

Ciascun nuovo termine della serie di Fibonacci è generato aggiungendo i due precedenti termini. Iniziando con i 1 e 2, i primi 10 termini saranno:

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

Considerando i termini della serie di Fibinacci non superiori a quattro milioni, trovare la somma dei termini pari.

Funzioni base

L’idea è quella di definire una funzione che dati una serie di N numeri di Fibonacci, restituisca una nuova serie formata dai precedenti N numeri con l’aggiunta di un nuovo termine; il nuovo termine sarà calcolato sommando gli ultimi due.

La funzione clojure, quindi, sarà:

(defn fibonacci-step [xs]
  (let [prossimo-termine (+ (first xs) (second xs))]
    (conj xs prossimo-termine)))

La funzione appena definita avrà in input una lista di termini e restituirà una nuova lista formata dalla vecchia più il prossimo termine.

La funzione let utilizzata ha la seguente forma: (let [bindings*] exprs*). Il suo scopo è quello di valutare le espressioni in un contesto nel quale è stato definito un insieme di bindings.

In questo caso, quindi, abbiamo creato un binding di nome prossimo-termine con valore la somma del primo e del secondo elemento della lista.

Proviamo ad applicare la funziona appena definita:

user => (fibonacci-step '(2 1))
(3 2 1)
user => (fibonacci-step (fibonacci-step '(2 1))))
(5 3 2 1)

Come possiamo vedere la nostra lista cresce a sinistra con i nuovi termini calcolati.

Ricorsione

A questo punto possiamo pensare di creare una sequenza di applicazioni di funzione così fatta:

x, f(x), f(f(x)), ...

Per questo ci viene in aiuto la funzione iterate. La sua definizione è la seguente:

(iterate f x)

Il ritorno è una sequenza lazy (letteralmente pigra), cioè una lista in cui i singoli elementi non vengono calcolati subito ma solo se e quando servono veramente. La lista lazy ritornata ha una sequenza infinita di termini. Possiamo concretizzare la lista prendendo un certo numero di elementi; le funzioni utilizzate a tale scopo sono take e take-while.

Ad esempio:

user => (take 2 (iterate fibonacci-step '(2 1)))
((2 1) (3 2 1))

La funzione take-while prende in input un predicato (il predicato è una funzione che torna un booleano). Ad esempio:

user => (take-while #(<= (count %) 6) (iterate fibonacci-step '(2 1)))
((2 1) (3 2 1) (5 3 2 1) (8 5 3 2 1) (13 8 5 3 2 1))

Nell’esempio il predicato torna true solo se il numero dei termini della i-esima applicazione è <= 6. Se il predicato fosse sempre true l’esecuzione non avrebbe mai fine.

Finalizzazione

Gli ingredienti per la finalizzazione sono i seguenti:

1. La funzione fibonacci-step
2. La funzione iterate
3. La funzione take-while

e possiamo utilizzarli all’interno della funzione peuler2:

(defn peuler2 []
  (let [mf (fn [xs] (<= (first xs) 4000000))]
    (->> (iterate fibonacci-step '(2 1))
         (take-while mf)
         (last)
         (filter even?)
         (reduce +))))

Note

Vorrei evidenziare l’uso della funzione ->>. La sua definizione formale è la seguente: (->> x & forms). Il suo scopo è quello di appendere il parametro x alla fine della prima forma. Successivamente, il risultato sarà appeso alla fine delle altre forme.

Con un esempio:

user => (->> (range)
              (filter even?)
              (take 6)
              (reduce +))
30

Il risultato è la somma dei primi 6 numeri pari (0 2 4 6 8 10).

La forma ->> è molto utile per semplificare la lettura del codice; per ottenere lo stesso risultato senza ->> avremmo dovuto scrivere:

user => (reduce + (take 6 (filter even? (range))))
30