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 😉
Penso che conosciate tutti il gioco Life e quindi non lo descriverò se non per ricordarne le regole. Chi non lo conoscesse ancora potrà rivolgersi all’apposita pagina di wikipedia per approfondirne le potenzialità e la storia.
Experimentalia 