Project Euler e bash: un passatempo matematico

Nel mio solito girovagare in Rete mi ero imbattuto tempo fa nel Project Euler, una collezione di problemini/problemoni di matematica da risolvere con l’aiuto di qualche riga di codice: “Oh che bello!” esclamò Cappuccetto Geek, e ben presto, raffazzonati un paio di script, si dimenticò della faccenda (o non ebbe più la testa di dedicarcisi). Ma lasciamo senz’altro perdere le favolette, già ci ho giocato abbastanza in passato

Dopo un po’ pure Stefania (co-autrice sul blog del buon Juhan) si è imbattuta nelle stesse pagine e, più prontamente di me, ha tele{p,m}aticamente (chi l’ha capita rifletta sulla propria vita) scritto le sue impressioni in proposito (leggitevìllo, così mi risparmio qualche chiacchiera), ricordandomi il vecchio proposito di… boh!?… fare qualcosa con questi problemini di numerini.

Dicevo, problemi in ordine crescente di difficoltà benché, dopo un certo livello, si entri decisamente nel campo del “Machecca§§è?!?!?“. I primi però sono più che abbordabili, quasi da Settimana Enigmistica, e soprattutto si sposano bene con quelle quattro righe in croce di shell scripting con bash che conosco.

Un’ultima (lo giuro) nota personale: i problemi, secondo le indicazioni del Progetto Eulero, devono essere risolti nel modo più efficace ed elegante possibile. Ora, visto il basso livello di difficoltà dei primi problemi, non so quanto si possano migliorare le procedure che ho trovato (e che comunque sono, dal mio punto di vista, già il meglio che posso offrire).

D’altro canto sì, mi sto auto-maltrattando e sminuendo ma è pur vero che gli script mi sono riusciti (sia come sintassi che come risultato) praticamente al primo tentativo: bravo bravissimo a me! Ho preso quindi i problemi del Progetto come spunti per riprendere a “fare esercizio” con lo shell scripting, senza preoccuparmi di dove riuscirò ad arrivare con le soluzioni. Basta così, si passa agli scriptini (la descrizione è riportata direttamente dal sito).


Problema 1 [link]

Multiples of 3 and 5: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

#!/bin/bash
sum=0
printf "%4s\t%8s\n" "Num" "Sum"
for i in {1..999}
do
if [[ $((i%3)) -eq 0 ]] || [[ $((i%5)) -eq 0 ]]
then sum=$((sum+i))
# One line for each found number and sum progress
printf "%4s\t%8s\n" $i $sum
# Single line, overwritten at each found number
#printf "\r%4s\t%8s" $i $sum
# Makes sense in combination with
# single line output to show progress
#sleep 0.02
fi
done
#echo $sum #final result
exit

Output:

 Num         Sum
   3           3
   5           8
   6          14
[...]      [...]
 996      232169
 999      233168

Et voilà, il risultato richiesto, 233168, ottenuto dalla somma di 466 numeri (999/3=333 divisibili per 3, 999/5=200 divisibili per 5 a cui se ne sottraggono 999/15=66, cioè quelli divisibili per entrambi) che rispettano le condizioni richieste, come conferma wc (la prima riga contata è l’intestazione).

$ ./euler1.sh | wc -l
467

Appurato che il codice funziona, si può pasticciare un po’ con le istruzioni commentate per misurare il tempo di esecuzione dello script in diverse condizioni:

                        sleep | 0,02s |   no  | 
+------------+----------------+-------+-------+
| Tempo di   | Solo risultato |   -   |  0,01 |
|            +----------------+-------+-------|
| esecuzione |  Linea singola | 10,19 |  0,02 |
|            +----------------+-------+-------|
| (secondi)  |   Multilinea   | 10,25 |  0,03 |
+------------+----------------+-------+-------+

Tempo di esecuzione – solo risultato finale

 

I tempi sono misurati alla meglio con il comando /usr/bin/time -f %e ./euler1.sh (“-f %e” è il formato dell’output, ovvero il solo tempo di esecuzione in secondi).

euler1_type_time

time – builtin

Attenzione a distinguere l’eseguibile vero e proprio (vedere “man time” per ulteriori dettagli) dal time che è uno dei comandi “builtin” della shell (come cd e echo): quest’ultimo però non offre opzioni per modificare il formato dell’output.

E visto che di sicuro non vi fidate dei risultati che ho messo in tabella, tié, beccatevi un altro paio di screenshot!

Tempo di esecuzione – linea singola, nessuna pausa

 

Facendo due conticini, ho notato una cosa curiosa: la differenza tra i tempi di esecuzione “linea singola” con e senza pausa è di circa 10,17s (10,19 – 0,02), a causa appunto dell’istruzione sleep 0.02. I conti però non mi tornano del tutto, poiché 466 pause da 0,02s totalizzerebbero 9,32s: i rimanenti 0,85s mi danno quindi un’indicazione di quanto tempo è necessario ad elaborare quelle stesse 466 istruzioni. Facendo un ultimo conticino, sono necessari dunque 0,85s/466=0,0018240343s affinché l’ammasso di ferraglia acquisisca l’istruzione da eseguire, prima di metterla effettivamente in atto.

Tempo di esecuzione – linea singola, pausa 0,02s

 

E se ancora non ne avete abbastanza, vi ho fatto pure la GIF animata (che pare sia tornata di moda)!

script_run

Come al solito ho divagato un po’, come al solito ho curiosato in giro tra la ferraglia ed il Pinguino che la abita, come al solito mi sono divertito con robe che la gente normale guarda come minimo con sospetto, e sicuramente da una certa distanza: continuerò così.

Annunci

Informazioni su Man from Mars

https://extendedreality.wordpress.com/

  1. Ho capito la battuta tra graffe… Vado a riflettere?!?! 🙂

    Mi piace

  2. Vai, di corsa, e rifletti a lungo, 30 min{uti,imo}! 😀

    Mi piace

  3. juhan

    Una piccolissima correzione: è tutto di Stefania. Una che rockz!

    Mi piace

  4. Corretto, grazie. Diamo a Cesare quel che è di Cesare, a Stefania quel che è di Stefania, a Juhan quel che è di Juhan.

    Mi piace

  5. Pingback: Visto nel Web – 173 | Ok, panico

  6. Una volta la maestra, alle elementari, ci disse di ricordarle, tra le altre cose, di parlarci di un problema con i verbi. Si alza un mio compagno di classe e fa “Maestra, io non capisco neppure i problemi coi numeri figuriamoci quelli coi verbi!”
    Ecco. Di fronte a questo post mi sento come lui.

    Mi piace

  7. Ma dai, lo so che non è così. Il fatto che un computer faccia la parte noiosa dei calcoli può essere tranquillamente ignorato, una volta che hai capito cosa chiede il problema: puoi risolverlo anche con carta e penna (e calcolatrice) se preferisci.

    Mi piace

  8. Il problema è che io non la trovo noiosa. Per questo non mi riesce ignorarla. E no, non sono normale.

    Mi piace

  9. Pingback: Project Euler and bash: maths for fun! | Extended Reality

Comments are disabled. Please comment and share on Twitter, G+, Facebook.

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: