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:

  1. Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
  2. per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
  3. l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
  4. si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
  5. 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:

  1. Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
  2. per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
  3. l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
  4. si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
  5. 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:

  1. Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
  2. per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno di caratteri;
  3. l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
  4. si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
  5. 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:

  1. Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
  2. per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno di caratteri;
  3. l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
  4. si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
  5. 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.