Experimentalia

Appunti raminghi

Golf Programming: Copertura di un segmento

with 2 comments

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😉

Written by Eineki

luglio 17, 2009 a 4:42 am

Pubblicato su golf

2 Risposte

Subscribe to comments with RSS.

  1. Di seguito una prima approssimazione della mia soluzione. 206 caratteri utili

    /*
    $s= array degli estremi sinistri dei segmenti
    $e= array degli estremi destri dei segmenti
    $k= estremo sinistro attuale
    $z= estremo destro attuale
    $p= accumulatore risultati
    */
    function R($s,$e,$k,$z,$p) {
    array_multisort($s, $e);
    $f='array_slice';
    $x=!$e||$z<$s[0];
    if($x){$p[0][]=$k;$p[1][]=$z;
    if(!$e) return $p;
    if($x) $k=$s[0];
    if($z<$e[0])$z=$e[0];
    return R($f($s,1), $f($e,1),$k, $z,$p);
    }

    eineki

    luglio 24, 2009 at 9:20 am

  2. Ciao

    Questa volta ho provato a farlo in Erlang, sono 330 caratteri ma sono convinto che un coder più skillato sappia fare meglio; anyway… questo è il link, grazie ancora ad Eineki per questa bella iniziativa🙂

    Il codice su github

    Sandro

    luglio 29, 2009 at 23:20 pm


Lascia un commento

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 cliccano Mi Piace per questo: