Archive for the ‘golf’ Category
Golf programming: Ritorno al futuro
Se l’ultima volta siamo andati indietro nel tempo fino ad Asterix ed i suoi irriducibili nemici, è tempo di tornare ai giorni nostri, o almeno risalire la catena del tempo fino all’epoca in cui gli arabi conquistarono mezza Europa, introdussero lo zero, e ci insegnarono a contare.
Leggi il seguito di questo post »
Golf programming: Sono Pazzi Questi Romani
E’ passato un mese dall’ultimo contest di golf programming. E’ arrivato il momendo di ricominciare a consumare, il meno possibile, le nostre tastiere per risolvere quello del mese di novembre.
Le Regole
Si tratta delle solite regole, in ossequio al contesto le ho riportare con il copia e incolla 
:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
Il programma da scrivere questa volta riguarda i numeri romani. Quelli che compaiono nelle prefazioni dei libri, per intenderci. O in qualche versione di latino o su centinaia di monumenti.
Questa volta bisogna scrivere un programma che conti, uno per riga, fino a 3999. Partiremo da 1 per arrivare fino a 3999 perché non è possibile, con i caratteri ascii, usare i caratteri romani per esprimere numeri più grandi di 4000. Non mi resta che lasciarvi al vostro compito con un link ad un file di riferimento con tutti la sequenza di numeri da replicare ed aspettare le vostre soluzioni.
La mia, al solito, tra circa una settimana tra i commenti.
Golf Programming: Paroliamo
L’ultima prova della serie anagrammi si è rivelata particolarmente semplice. Complichiamola appena un pò modificando l’algoritmo in modo da costringerci a modificare l’approccio al problema.
Le Regole
Le regole del contest:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
Anche la funzione di questo mese, come quella del mese scorso, prende in input due stringhe ma restituisce/stampa vero se con le lettere che compongono il primo parametro è possibile comporre il secondo. A differenza del programma sugli anagrammi, non è necessario utilizzare tutte le lettere della prima parola per comporre la seconda.
Ad esempio, con la parola MANAGER è possibile (e quindi la funzione deve restituire vero) comporre, tra le altre, le parole RANA, RAME, GARA o GRANE.
L’ordine dei parametri è importante. Con la parola MANAGER non è possibile costruire GERMANIA, mentre è vero il contrario.
La parola OSTE, poi, non può essere usata per comporre TESTO, le lettere ci sono tutte ma manca una T. Di conseguenza la funzione dovrebbe restituire falso.
Al solito posterò la mia soluzione come commento alla fine della settimana entrante, per dare il tempo a chi vuole partecipare di scatenare la propria fantasia.
Golf Programming: Anagrammi
Rientriamo dopo le ferie con un’altra sfida classica, giusto per toglierci di dosso eventuale ruggine. Al solito riporto le regole per chi cominciasse adesso a seguire questa pseudo rubrica.
Le Regole
Ormai le regole dovrebbero essere familiari, le riporto per scrupolo:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
La funzione di questo mese prende in input due stringhe e stampa vero se una delle due è anagramma dell’altra o falso in caso contrario (ovviamente sono consentite anche, per i linguaggi che lo permettono, 0 ed 1 o 0 e ~0).
Al solito posterò la mia soluzione come commento alla fine della settimana entrante, per dare il tempo a chi vuole partecipare di scatenare la propria fantasia.
Golf Programming: Copertura di un segmento
Il pingback di Sandro al post del precedente Golf contest mi ha fatto raggiungere un sito che mi ha dato lo spunto per la prova di Luglio. Ok, uno spunto forse è pretendere troppo, diciamo che l’ho tradotto spudoratamente e adattato al contest togliendo la sommatoria finale.
Ancora una volta si tratta di un classico, dovrete scruvere la versione concisa di un algoritmo per il calcolo della copertura di un segmento.
Le Regole
Ormai le regole dovrebbero essere familiari, le riporto per scrupolo:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
Il problema di questo mese consiste nel calcolare la mappa di copertura di un segmento. In parole povere:
Un segmento è diviso in spezzoni (da 1, non 0, ad n) ed in input arrivano degli intervalli di copertura, gli estremi delle macchie che coprono il segmento.
Le macchie in input possono sovrapporsi, essere completamente contenute in altre macchie e, ovviamente, contenerne altre.
Il pezzo di programma da scrivere deve prendere in input questa sequenza di intervalli e restituire la sequenza di copertura minima,in altre parole deve
ottenere lo stesso risultato della sequenza in input con il minor numero di macchie possibile (fondendo tra di loro quelle che si intersecano o sovrappongono).
Il compito non è troppo difficile e, con un po’ di attenzione si dovrebbe arrivare contemporaneamente al codice più stringato possibile ed all’algoritmo ottimo (o almeno molto vicini a quest’ultimo).
Il formato dell’input
Sul post originale al quale ho attinto l’imput è composto da due array, uno con la coordinata dell’inizio della macchia e, l’altro, nella cella corrispondente, con la coordinata finale della macchia. Ovviamente, trattandosi di un segmento, per coordinata si intende un singolo numero. Per il php, il linguaggio che ho scelto per partecipare ai contest questo formato è preferibile ma se qualcuno ha intenzione di modificarlo per adattarlo meglio al linguaggio che sceglierà può tranquillamante farlo (siamo qui per divertirci, dopo tutto). L’elenco dei segmenti, qualunque esso sia, non è ordinato secondo nessun criterio vi possa venire in mente.
Un formato alternativo potrebbe essere un solo array di coppie di coordinate, inizio fine.
Cercherò di spiegarmi meglio con un esempio, anche questo preso dal post in questione.
[17,85,57], [33,86,84] che diventa [17, 57], [33 86]
un’alternativa potrebbe essere
[[17,33], [85,86], [57,84]] che a sua volta diventa [[17,33], [57,86]]
Il formato dell’output
Una volta scelto il formato in input il formato in output dovrà corrispondere il più possibile a quello dei dati di ingresso. Scrivo il più possibile perché quasi mai è possibile restituire in output entità multiple senza almeno incapsularle in una struttura che le contenga. Non è possibile creare side-effect, modificare i parametri in input come risultato della computazione.
Vi lascio alla soluzione del quesito con un paio di esempi di input:
[ 15, 30, 40, 6, 15, 11, 23, 26, 39 ]
[ 21, 37, 42, 8, 15, 17, 25, 32, 43 ]o, in alternativa, [[15,21], [30,37], [40,42], [6,8], [15,15], [11,17], [23,25], [26,32], [39,43]]
[45, 100, 125, 10, 15, 35, 30, 9]
[46, 200, 175, 20, 25, 45, 40, 10]alias [[45,46], [100,200], [125,175], [10,20], [15,25], [35,45], [30,40], [9,10]]
Il resto sta a voi. Scrivete il meno possibile 
Golf Programming: permutazioni
Proseguiamo con il golf programming con un nuovo problema da risolvere.
Anche questa volta si tratta di un classico (anche se programmarlo secondo le regole del golf me lo ha fatto vedere sotto una nuova luce).
Le Regole
Per che non le ricordasse, e per chi comincia da questa puntata a seguire la rubrica, riporto le regole:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
L’algoritmo da implementare deve, data una stringa, calcolare tutte le sue possibili permutazioni.
Al solito, un esempio servirà a chiarire tutto meglio di una descrizione formale:
data in input la stringa abc, il programma deve stampare, le stringhe abc, acb, bac, bca, cab e cba.
Ovviamente l’ordine delle stringhe restituite non è importante mentre lo è non riportare ripetizioni: la stringa aba, ad esempio, deve dare come risultato solamente aba, aab e baa.
A parte i soliti rubysti che avranno sicuramente un costrutto nel linguaggio tipo .permuta secondo me si tratta di una sfida stimolante, specie per chi volesse risolverla in ricorsione. Come le altre volte, posterò la mia soluzione nel prossimo fine settimana. Buona sfida.
Golf programming: veni vidi dixi
Se le mie reminiscenze di latino non mi ingannano veni, vidi, dixi dovrebbe essere la parafrasi del ben più famoso detto di Giulio Cesare.
Proseguiamo con il golf programming con un nuovo problema da risolvere. Le regole sono uguali a quelle dell’altra volta:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno di caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
L’algoritmo da implementare deve, dato un numero, calcolare il successivo termine della sequenza look and say, una particolare successione matematica costruita descrivendo i diversi termini. Un esempio servirà a chiarire tutto meglio di una descrizione formale; scriviamo i primi cinque membri della successione che comincia con 1:
1, 11, 21, 1211, 111221, …
il primo termine è il seme della sequenza ed è scelto senza nessun vincolo. Il secondo termine descrive il primo, in questo caso abbiamo un numero uno e quindi otteniamo 11. Il terzo termine descrive (si tratta di due cifre 1) il secondo ottenendo 21, il quarto 1211 “legge” il terzo che contiene un due ed un uno e, seguitando, il quinto termine, è 111221. Il sesto, ovviamente, corrisponde a 312211.
Partenza
La sfida consiste nello scrivere una funzione che preso in input un termine qualunque della sequenza, ne restituisca il successivo.
Come al solito aspetterò fino alla fine della settimana per postare la mia versione. Chi volesse cimentarsi non ha altro da fare che postare la propria soluzione tra i commenti.
Eineki
Golf programming: Venerdi 13.
Siete capaci di scrivere un programma, nel linguaggio che più padroneggiate, per calcolare e stampare, dato un anno, quali venerdì tredici ci sono dentro? Se pensate di rispondere si, potreste provare a scriverlo come se giocaste a golf (e poi, magari, potreste postare la vostra soluzione in un commento qui sotto).
Il golf programming è una disciplina per programmatori, consiste nello scrivere il programma più breve possibile per risolvere un determinato problema. Ho visto qualche prova a riguardo nel sito stackoverflow.com, in inglese, ed ho pensato di riproporla su queste pagine, giusto per sciogliere un po’ i muscoli delle dita e scrostare qualche ingranaggio del cervello.
Le regole sono semplicissime:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno di caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
La sfida di oggi, come anticipato consiste nello scrivere un programma che, dato un anno di questo secolo (e quindi dal 2000 al 2099), stampi a video, o mostri su una pagina web, quali sono i venerdi 13, se ne esistono, che cadono in quell’anno. Non c’è bisogno di validare l’input (si assume che il dato in ingresso sia sempre valido) e l’elenco dei diversi giorni può essere separato dal carattere che ritenete più opportuno.L’anno deve essere nel formato a quattro cifre. Ovviamente non vale utilizzare funzioni predefinite che restiuiscono il giorno della settimana a partire da una data.
Ad esempio, per il 2009 bisogna stampare 13 Febbraio 2009, 13 Marzo 2009 o 13 Feb 2009, 13 Mar 2009 oppure, ancora 13/02/2009 , 13/03/2009
Se vi state chiedendo cosa ho fumato stasera per venirmene fuori con un problema del genere, sappiate che non fumo e che non ho visto, causa bidone, il remake dell’omonimo film.
Aggiungeteci che il protagonista del film si chiama J(a)son e capirete perché la mia versione sarà scritta in javascript.
Per ora è tutto, domenica mattina, tra i commenti troverete la mia soluzione.
Uno spunto sugli algoritmi da utilizzare potete trovarlo in questa pagina in inglese sull’algoritmo del giorno del giudizio. E’ in inglese, ma un inglese talmente elementare che anche google riesce a tradurlo quasi decentemente Se qualcuno avesse riferimenti in italiano allo stesso algoritmo e volesse indicarli tra i commenti è sicuramente il benvenuto.
