Ecco cosa accade quando alla passione per la programmazione si unisce la sfida per trovare una soluzione elettronica a quesiti di matematica.
Accade che non si riesce più a smettere, e si entra nel tunnel del Progetto Eulero, liberamente tradotto in italiano.

Project Euler è un sito, nato nel 2001, il cui obiettivo è quello di proporre questiti matematici (più di 200, 246 per l’esattezza, e il 247imo è schedulato per venerdì 29 maggio 2009 alle 9.00 PM [GMT]) di diversa complessità, da quelli risolvibili con un foglio e una matita a quelli richiedenti un buon linguaggio di programmazione, un programmatore attento e una forte dose di ottimizzazione.

Già, perchè pur non essendoci un limite di tempo per la scrittura del programma, questo ultimo deve essere in grado di trovare la soluzione al problema nel tempo massimo di 60 secondi! Questo vincolo richiede una particolare attenzione nella scrittura dell’algoritmo risolutivo, e spesso ci si rende conto che un approccio brute-force non è quello più efficace.

Ho cominciato a risolvere i quesiti da poco più di una settimana partendo dall’inizio, e ora sono alle prese con il dodicesimo:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?


Come previsto e predetto, l’approccio a forza bruta non sta funzionando bene; considerando i numeri primi, e non i numeri triangolari come richiesto, il calcolo del numero di divisori di 70000000 (settanta milioni), il quale risulta averne 128, di divisori, richiede 56,5″.
Sono troppo vicino ai 60″, e troppo lontano dai 500 divisori richiesti.

A parte il piacere della programmazione e la soddisfazione per la scrittura di un algoritmo particolarmente efficiente, la risoluzione di alcuni problemi mi ha portato a qualche considerazione:

* il linguaggio Python è estremamente facile da utilizzare, e piuttosto efficiente;
* il linguaggio C è stramaledettamente veloce;
* purtroppo è passato troppo tempo dall’ultima volta che ho scritto del codice Assembler (dalle superiori) per paragonarlo al C;
* il decorator memoize è una figata unica, trovo questo approccio semplicemente geniale;

Una ottima fonte di riferimento al progetto è Stacktrace: qui e qui due post molto belli.

Che dire? Se c’è dell’interesse verso la programmazione e la matematica, il progetto è veramente interessante. Una unica annotazione, come tutte le droghe, CREA DIPENDENZA! Programmatore avvisato…

Alla prox

[tags]projecteuler, python, ottimizzaizone, algoritmi[/tags]