Progetto Eulero: Problema 1

Primo problema. Livello: Facile.Project Euler è un sito che propone più di un centinaio di problemi a carattere matematico. Alcuni di questi possono essere affrontati con carta, penna e un pizzico di astuzia matematica, ma di base si tratta di una sfida algoritmica pensata per programmatori e appassionati di programmazione. C’è da chiedersi se la sfida sia più tra le migliaia di programmatori (con tanto di classifica) o contro se stessi. Infatti Project Euler è ideale per rinfrescarsi la memoria in materia di algoritmi e matematica, oltre ad essere un valido ausilio per misurare i propri progressi nello studio di un nuovo linguaggio di programmazione.

Benché in costante espansione, esistono attualmente 174 problemi che vanno dal quasi ovvio al piuttosto complesso, in grado di stuzzicare quindi l’intelletto di programmatori a tutti i livelli. Non c’è limite di tempo per la scrittura di codice funzionante, ma il tempo di esecuzione del programma che risolve un dato problema non può eccedere i 60 secondi. La parte più interessante è cercare di trovare euristiche e algoritmi efficienti per affrontare problemi NP-completi, dove (con un input sufficientemente grande) un approccio brute-force non solo richiederebbe più di un minuto, ma in alcuni casi non terminerebbe affatto.

Con una cadenza grosso modo settimanale (siamo un aperiodico in fondo) pubblicheremo e discuteremo insieme un problema alla volta in una serie di articoli. Partiamo subito col primo che è, bisogna ammetterlo, piuttosto banale:

Se elenchiamo tutti numeri naturali minori di 10 che sono multipli di 3 o 5, otteniamo 3, 5, 6 e 9. La somma di questi multipli è 23. Trova la somma di tutti i multipli di 3 o 5 inferiori a 1000.

La semplicità del problema permette alla descrizione dello stesso di fornirci già la soluzione che stiamo cercando. Ad esempio, in Python potremmo scrivere:

print sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)

Leggendo quasi letteralmente il one-liner otteniamo a grandi linee la stessa descrizione del problema di cui sopra. Una lista di numeri naturali viene creata, includendo solamente gli elementi nell’intervallo chiuso tra 0 e 999, il cui resto della divisione con 3 o 5 sia nullo. Infine, la funzione sum si occupa di calcolare la somma di tutti questi elementi, per essere poi stampata dall’istruzione print.

A qualche lettore potrebbe venire in mente di sostituire i tre confronti logici richiesti da i % 3 == 0 or i % 5 == 0 con il solo confronto necessario per i % 3 * i % 5 == 0. In quest’ultimo caso, moltiplichiamo i resti (della divisione per 3 e per 5) e se uno dei due è nullo, il prodotto sarà nullo anch’esso. La differenza tra i due algoritmi è quasi impercettibile per numeri inferiori a mille, ma cosa accadrebbe se volessimo ripetere lo stesso esercizio per numeri inferiori ai dieci milioni? D’ora in poi, per comodità, il codice mostrato risolverà il problema nei vari linguaggi ma mostrerà i tempi non per la somma dei numeri minori di 1000, ma per quelli minori di 10 milioni. Sul mio MacBook Pro Core 2 Duo 2.2 GHz, il primo script richiede 5.160 secondi, mentre il secondo 6.257. Moltiplicare i resti “costa” evidentemente di più, rispetto ad effettuare due confronti extra. Volendo applicare lo stesso principio ma evitando accuratamente di introdurre moltiplicazioni non necessarie, potremmo risolvere il problema con il seguente codice che si basa sul fatto che in Python, qualsiasi numero non-nullo viene valutato come True.

print sum(i for i in range(1000) if not (i % 3 and i % 5))

In questo caso, il tempo medio di esecuzione sul mio laptop (per valori inferiori a 10 milioni) è di 5.384 secondi. Più lento del primo, ma migliore del secondo. La soluzione naïve iniziale sembra avere la meglio per ora. Volendo guadagnare in velocità ma soprattutto risparmiare memoria, possiamo utilizzare la funzione xrange che è un generatore. In questo caso, il tempo di esecuzione per numeri minori di 107 è 4.895 secondi.

print sum(i for i in xrange(1000) if i % 3 == 0 or i % 5 == 0)

Si noti che l’operatore or in Python è a valutazione minima, per cui mettendo i % 3 (che varrà True più spesso) prima di i % 5 riusciamo a ridurre il numero di confronti richiesti (rispetto alla configurazione opposta).

L’equivalente in Haskell è pressoché identico, facendo uso della funzione sum e delle list comprehension.

print $ sum [i | i <- [1..999], i `mod` 5 == 0 || i `mod` 3 == 0]

Haskell è un linguaggio che può essere compilato ed è notoriamente veloce, eseguendo il compito esteso allo stesso intervallo di dieci milioni di numeri, in soli 1.516 secondi.

In Ruby, non c’è un equivalente così diretto, come in Haskell, ma possiamo seguire un approccio simile che comunque verifica ogni numero nell’intervallo. Con Ruby 1.9, l’equivalente da 10 milioni di numeri esegue in 4.095 secondi.

sum = 0
(1..999).each { |i| sum+=i if i % 3 == 0 || i % 5 == 0 }
puts sum

Volendo scrivere un one-liner, un po’ più elaborato, possiamo utilizzare il seguente che rimane però decisamente troppo lento per grandi numeri a causa dell’inject.

puts (1..999).inject { |sum, n| (n % 3 == 0 || n % 5 == 0) ? sum += n : sum }

Giovanni Intini, nella mailing list del team di Stacktrace, ha proposto anche una soluzione piuttosto elegante in Erlang:

sum_mul([H|T]) -> valid(H) + sum_mul(T);
sum_mul([]) -> 0.
valid(H) when H rem 3 =:= 0; H rem 5 =:= 0 -> H;
valid(H) -> 0.
sum_mul(lists:seq(1,999))

Questa invece è la versione in Lisp di Valentino Volonghi:

(loop for n from 1 to 1000
when (= (* (mod n 5) (mod n 3)) 0)
summing n)

Ci sono però due problemi con l’approccio utilizzato finora. Il primo deriva dalla verifica, non necessaria, di ogni singolo numero nell’intervallo per controllare se è un multiplo di 3 o 5. La seconda riguarda invece il modus operandi: stiamo cercando di effettuare micro-ottimizzazioni. Quest’ultime sono utili solo quando la velocità di esecuzione è assolutamente necessaria e soprattutto quando l’algoritmo in uso è già il migliore possibile. Nel nostro caso, stiamo migliorando una soluzione di base che è piuttosto ingenua e sub-ottimale.

Un modo più efficiente sarebbe quello di generare i multipli di 3 e i multipli di 5, sommarli per poi sottrarre i multipli di 15 che verrebbero contati due volte perché multipli sia di 3 sia di 5. Il vantaggio di questo metodo è che non bisogna verificare ogni singolo numero nel range indicato e il codice risultante è piuttosto pulito e chiaro da comprendere.

In Python:

print sum(xrange(3,1000,3)) + sum(xrange(5,1000,5)) - sum(xrange(15,1000,15))

In Haskell:

print $ sum [3,6..999] + sum [5,10..999] - sum [15,30..999]

In Ruby:

sum = 0
3.step(999, 3) {|n| sum += n}
5.step(999, 5) {|n| sum += n}
15.step(999, 15) {|n| sum -= n}
puts sum

I tre impiegano sul mio portatile (sempre per x < 107) rispettivamente 1.434 secondi (Python 2.5.1), 0.828 secondi (ghc-6.8.1) e 4.937 secondi (Ruby 1.9). Nonostante la complessità algoritmica sia di gran lunga migliorata, come dimostrano Python ed Haskell, lo snippet in Ruby è più lento di quello (semplice) precedente.

sum = 0
3.step(999, 3) {|n| sum += n}
5.step(999, 5) {|n| sum += n}
15.step(999, 15) {|n| sum -= n}
puts sum

I rubisti non disperino, Ruby può risolvere il problema (esteso a 107) in 4 millisecondi. Ciò che conta davvero è trovare l’algoritmo giusto. Sempre sulla falsa riga del codice precedente, notiamo che la somma dei multipli inferiori a un dato numero può essere calcolata aritmicamente sfruttando le proprietà delle progressioni aritmetiche. Può essere provato (esercizio per il lettore) che la somma è pari a step * n * (n + 1) / 2 dove step nel nostro caso è 3 o 5 , mentre n è il quoziente della divisione intera tra il valore massimo (999) e step:

class Integer
def sum_mult(step)
n = self / step
step*n*(n + 1)/2
end
end

n = 999
puts n.sum_mult(3) + n.sum_mult(5) - n.sum_mult(15)

Nonostante il problema originale possa essere considerato banale, se ne potrebbe comunque parlare per ore ma è meglio fermarci qui. Usate pure la sezione commenti per indicare soluzioni nel linguaggio di vostra scelta e fateci sapere cosa ne pensate di questa serie. Vi diamo appuntamento al prossimo problema.

About Antonio Cangiano

Antonio lavora come Software Engineer & Technical Evangelist presso la IBM in Canada. È inoltre il direttore di Stacktrace.it, un internet marketing strategist, imprenditore del web, serial blogger, e autore di un paio di libri in inglese (recentemente Technical Blogging.) Puoi dare un'occhiata ai suoi progetti sulla sua homepage e seguendolo su Twitter.

Comments

  1. bellissima idea questo progetto eulero… ci proverò 🙂

  2. Un’idea davvero molto molto carina!!!
    Sia mai che mi torni la simpatia per la matematica 😛
    Lo segnalerò ai miei amici all’università…piu’ che altro per vedere se riesco a farli avvicinare al Python 😉

  3. Ottima iniziativa, discutere le soluzioni a problemi del genere migliorerà sicuramente il nostro stile, specialmente per chi sta imparando un nuovo linguaggio!

    Ne approfitto per segnalare http://www.pythonchallenge.com/, che è più orientato al Python ed è anch’esso pensato per aiutare chi si sta addentrando per la prima volta nei meandri del linguaggio.

    Continuate così! 😀

  4. credo che una soluzione con “intelligenza adattativa” sia:
    * calcola un intervallo multiplo dei numeri(intervallo=3*5=15)
    * una sola volta, calcola quali & quanti divisori ci sono in quell’intervallo (divs=3,6,9,12,5,10)
    * esegui la somma usando un paso pari all’intervallo e sommando ad ogni iterazione intervallo*numero di divisori+1+somma divisori, in pratica riscrivere come base+divisore e raccogliere base, considerando lo 0.

    Si può spostare il calcolo della somma dei divisori in un passo di setup he viene seguito una sola volta, e quindi ridurre arbitrariamente il tempo di calcolo(usando un passo da 30,60,150) mettendo più intelligenza nel setup (ovviamente non troppo, sennò finisce finisce per diventare quello il collo di bottiglia)

    Dovrebbe funzionare 🙂

  5. Articolo *fantastico*! da quanto non vedo un articolo così hardcore….e su un blog italiano sembrava un’utopia!
    Inoltre la discussione delle soluzione è assolutamente interessante e mette in luce l’eleganza di alcuni linguaggi

  6. Grande, trovo interessante oltre ogni misura questo genere di articoli. Giusto per avere un altro linguaggio ho replicato gli stessi esempi con Lua. Il primo snippet replica il comportamento del primo in Python (sperando che la formattazione venga tenuta):

    local sum = 0
    for i = 0, 9999999 do 
        if i % 3 == 0 or i % 5 == 0 then sum = sum + i end 
    end
    print(sum)
    

    Tanto per offrire un paragone, sul mio computer con Python 5.2.1 ottengo il risultato in 5.478s contro i 2.610s necessari con Lua 5.1. In seguito ho riprodotto anche lo script che effettua il calcolo dei multipli di 3 e 5 e li somma per poi sottrarre la somma dei multipli di 15, usando prima un approccio simile a xrange con step di Python (vedi meth_a) sia con la formula step * n * (n + 1) / 2 (vedi meth_b):

    function meth_a(f, t)
        local sum = 0
        for i = f, t, f do sum = sum + i end
        return sum
    end
    
    function meth_b(f, t)
        local q = math.floor(t / f)
        return f * q * (q + 1) / 2
    end
    
    function multsum(f, t, func)
        return func(f, t)
    end
    
    -- ************************************ --
    
    local up_to = 9999999
    local sum_meth = meth_a   -- oppure meth_b :-)
    
    print(multsum(3, up_to, sum_meth)  + 
          multsum(5, up_to, sum_meth)  - 
          multsum(15, up_to, sum_meth) )
    

    Il risultato usando meth_a è di 0.234s contro i 1.320s dell’equivalente in Python, usando meth_b invece non vale nemmeno la pena mettersi a misurare i tempi.

  7. Dude, you rock!

    Complimenti, gran bell’articolo.

    Sulle cose algoritmiche e/o a sfondo matematico non svegliate il Cangiano che dorme! 😉

    L.

  8. Fico. Sicuramente utilissimo, specie la parte di confronto tra varie tecniche / approcci.

    Io leggendo mentre leggevo l’articolo mi sono ritrovato a pensare ad una soluzione “sporca”, ma (suppongo) abbastanza rapida.
    Vi prego perdonatemi, non ho fatto benchmark né verifiche di sorta, ma dovrebbe funzionare 😉

    in Ruby:

    sum=0
    0.step(999,15) { |n| sum += 7*n + 45 }
    puts sum – (2*n + 22)

    P.S.: manca la parte iniziale per settare i parametri, e leggendo i commenti direi che è lo stesso approccio proposto da riffraff

  9. ops… dimenticato il “pre” per formattare il codice nel commento qui sopra 😉

  10. @ Daniele Alessandri

    > Tanto per offrire un paragone, sul mio computer con Python 5.2.1 […]

    spero che tu intenda Python 2.5.1, e non 1.5.2 (che purtroppo e’ ancora diffusissimo) =D

    Detto questo, grazie del contributo. Lua rocks!

  11. @C8E: ovviamente intendevo la prima, dev’essere stato solo un misto tra lapsus (Python 2.5.1 e Lua 5.1), errore di battitura e cervello sconnesso 🙂

  12. Provo con GW-Basic 3.23 e senza usare il Mod perche’ gestisce solo interi fino a +32767.

    10 INPUT "INSERISCI IL RANGE MAX:", RANGEMAX
    20 START=TIMER
    30 FOR I=1 TO RANGEMAX
    40 IF (I - (3 * FIX(I/3))=0 OR I-(5* FIX(I/5))=0) THEN SOMMA=SOMMA+I
    50 NEXT I
    60 PRINT "TEMPO STIMATO (Sec.):", TIMER - START
    70 PRINT "RISULTATO:", SOMMA
    80 END
    

    con input 9999999 arrivo a 54,62 sec su un pentium 4 a 3Ghz.Ciao :D.

  13. Bello!
    Ma al momento il sito sembra essere un po’ carico di connessioni… a volte non é accessibile.

    Per rimediare io sto perdendo tempo sul vecchio pythonchallenge.com

  14. Affascinante! Complimenti a voi e grazie per questi post settimanali perchè sono davvero stupendi e il progetto è interessantissimo, anche solo da leggere è davvero affascinante!
    Segnalo il vostro sito anche sul mio blog sperando che questo progetto venga conosciuto anche dai miei colleghi in università.
    Bravi! Continuate così! 😉

  15. Sono contento di essere venuto a conoscenza di un progetto del genere. Project Euler invita gli utenti a sviluppare algoritmi efficaci e veloci, questo è un punto molto importante nella programmazione di un software. Mi iscrivo appena possibile.

  16. Io ho semplificato il problema basandomi sul fatto che “la somma di tutti i numeri multipli di 3 o di 5” equivale a “la somma di tutti i multipli di 3” più “la somma di tutti i multipli di 5” meno “la somma di tutti i multipli di 3*5” (perchè sono stati sommati due volte, una per i multipli di 3 e una per quelli di 5).
    In C è venuto semplicemente

    main() {
    int i, sum;
    sum = 0;
    for (i = 3; i < 1000; i += 3) sum += i; for (i = 5; i < 1000; i += 5) sum += i; for (i = 15; i < 1000; i += 15) sum -= i; printf("%d\n", sum); }

  17. @T.A.: forse non hai visto bene la riga di python dell’articolo che fa la stessa cosa (5*3=15):

    print sum(xrange(3,1000,3)) + sum(xrange(5,1000,5)) - sum(xrange(15,1000,15))

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.


Trackbacks

  1. Merry Christmas everyone!

    It’s been a long time since I wrote a post, but I’ve been very busy coding, and I could only muster some posts for Stacktrace, so express all your Christmas-y goodness and pardon me

    On Stacktrace we just starte…