[Vari] Contest 16: Intervalli

[gugoXX]

Uno facile e non troppo verboso, giusto per pensare e per vedere l'approccio.
Sia dato un lungo elenco di intervalli della retta reale.

-4.5  +3.2
+2.8  +7.15
-7.3  -9.15

Le coordinate di ciascun intervallo possono anche essere "invertite", ovvero non e' assicurato che il primo valore sia sempre inferiore al secondo.

Si noti come ci possano essere delle SOVRAPPOSIZIONI. In questo esempio il primo e il secondo intervallo sono parzialmente sovrapposti.

Si vuole calcolare la lunghezza totale del dominio coperto, contando le sovrapposizioni una e una sola volta.
Si trascurino gli arrotondamenti dovuti a precisione macchina, e dove possibile si lavori con la struttura piu' precisa possibile,
tenendo conto che l'input sara' contenibile senza errori in un IEEE754 da 64bit (in C il double)

In questo esempio il risultato dovrebbe essere 13.5

Primo File, giusto per tastare il terreno.
http://www.usaupload.net/d/ze7gn00x87b

[Vincenzo1968]

E 'ndirindinghete!!!

C'è già un contest 15(Sudoku):

Contest 1

Contest 2

Contest 3

Contest 4

Contest 5

Contest 6

Contest 7

Proposta

Contest 8

Contest 9

Contest 10

Contest 11

Contest 12

Contest 13

Contest 14

Contest 15

[gugoXX]

Fatto fatto
Avevo copiaincollato e non avevo modificato.

[Vincenzo1968]

Senti maaaaaaaaaaaaa

un piccolo chiarimento per chi, come me, ne sa poco e niente di matematica?
Che significa lunghezza totale del dominio coperto? Come viene fuori quel 13.5?

Grazie

[gugoXX]

Dunque.
Sei prendi un intervallo tipo
3.2 --> 7.5
questo e' un intervallo della retta reale, che parte dal punto 3.2 e arriva fino a 7.5
La lunghezza di tale intervallo e' 4.3

Un po' come dire: Ho dipinto di bianco la strada a partire dal Kilometro 3.2 fino al Kilometro 7.5
La domanda sarebbe quindi: Quanti Kilometri di strada ho coperto di bianco? 4.3Km finora, appunto.

Aggiungiamo un altro intervallo, quello
10.4 --> 12.7
e la cui lunghezza e' 2.3

E poi un altro ancora, da
11.9 --> 12.9, la cui lunghezza e' 1.0

Potrebbe venire da dire che la lunghezza totale coperta sia da
4.3 + 2.3 + 1.0 = 7.6

E invece no.
Questo ultimo intervallo e' parzialmente sovrapposto all'intervallo precedente. Per un pezzo di strada ho semplicemente ripittato un pochino, ma era gia' bianca, non conta 2 volte.

Riusciamo a coprire quindi tutto il primo
3.2 --> 7.5
poi il secondo
10.4 --> 12.7
e poi del terzo aggiungiamo solo una piccola fettina
12.7 --> 12.9, perche' la prima parte del terzo era gia' coperta precedentemente.
Abbiamo quindi un totale di 4.3 + 2.3 + 0.2 = 6.8

E' OK?


Nell'esempio abbiamo anche coordinate di partenza negative. Un po' come mettere casa mia al centro di una lunghissima strada diritta, e dire che se vado a sinistra ho coordinate negative e a destra coordinate positive.
Per l'esempio dato abbiamo:
-4.5 --> +3.2 Lunghezza = 7.7
Ovvero sono partito a dipingere 4.5KM a sinistra di casa mia, e ho finito 3.2KM a destra di casa mia.

Poi
+2.8 --> +7.15 E gia' qui sovrappoiniamo, quindi vale solo come se fosse da
+3.2 --> 7.15 = 3.95

E infine
-7.3 --> -9.15, ovvero parto da 7.3KM a sinistra e proseguo fino a 9.15 KM a sinistra, senza sovrapporre niente quindi.
La lunghezza conta tutta, ovvero 1.85KM

Totale 7.7 + 3.95 + 1.85 = 13.5

[banryu79]

Così:
[-4.5 +3.2]
[+2.8 +7.15]
rappresentano due intervalli che si sovvrapongono parzialmente quindi prendiamo l'intervallo ricavato dalla loro "unione":
[-4.5 +7.15]

L'altro intervallo specificato:
[-7.3 -9.15]
non si sovrappone a nessun altro intervallo, quindi lo consideriamo di per se.

Ora la lunghezza totale del dominio sarà data dalla somma delle singole lunghezze degli intervalli, a loro volta date dal valore assoluto del risultato della sottrazione del valore minore dal valore maggiore:
[-4.5 +7.15] -> +7.15 - -4.5 -> 11.65 -> abs -> 11.65
e
[-7.3 -9.15] -> -9.15 - -7.3 -> -1.85 -> abs -> 1.85

Lunghezza dominio coperto dagli intervalli: 11.65 + 1.85 = 13.5

Giusto Gugo?

[gugoXX]

Si, esatto.
Figuratevelo come le istruzioni per pittare di bianco la strada, e la domanda appunto su quanta strada totale avete alla fine pittato di bianco.

[Vincenzo1968]

Grazie mille a entrambi per le spiegazioni. Ora è tutto chiaro

Un'ultima domanda: i tempi di caricamento dal file non vanno conteggiati, giusto?

[gugoXX]

Originariamente inviato da Vincenzo1968

Grazie mille a entrambi per le spiegazioni. Ora è tutto chiaro

Un'ultima domanda: i tempi di caricamento dal file non vanno conteggiati, giusto?

Direi di no.
Certo che se mentre si legge si fa anche altro allora occorre contare, ma se si legge solo il file per poi parsarlo allora va bene tenere i tempi della lettura fuori.

[PGI-Bis]

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?

[banryu79]

Originariamente inviato da PGI-Bis

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?

Sono ancora impelagato in ufficio; questo contest però mi piace e me lo risolverò nel wend, quindi niente soluzione ancora, per fare confronti

Però potresti scriverti uno unit test ( ) dandogli in pasto un file di input "banale" e vedere se i conti tornano

[gugoXX]

Originariamente inviato da PGI-Bis

Per la serie "nutro una grande fiducia in quel che ho scritto", a chi viene

1235792.2454819013


con il file di prova?

a me viene 380404.063114735
Ma potrei avere sbagliato, ho fatto di corsa.
Magari ho semplicemente sbagliato file, dato che da rospo non ho tenuto il seed del generatore... non potro' mai piu' riprodurlo.
Riscarico e controllo.

[^TiGeRShArK^]

minchia siamo messi bene
a me viene 299085,567040739

[Vincenzo1968]

Io ho quest'altro risultato:



Qual è quello giusto?

[^TiGeRShArK^]

miii passerà alla storia come il contest con il maggior numero di risultati diversi

[Vincenzo1968]

Ho provato un piccolo file con i dati dell'esempio iniziale di Gugo:

-4.5 3.2
2.8 7.15
-7.3 -9.15

e il risultato, in questo caso, è corretto: 13.5

Il codice sorgente, in C, si può scaricare da qui.

[^TiGeRShArK^]

quello l'avevo provato pure io ovviamente
cmq ho corretto un potenziale piccolo bug, ma il risultato mi esce sempre quello...
o mi sfugge ancora qualcosa o c'è qualcos'altro che mi sfugge

EDIT: Minchia.. come al solito è sintetico il tuo codice

[Vincenzo1968]

Originariamente inviato da ^TiGeRShArK^

quello l'avevo provato pure io ovviamente
cmq ho corretto un potenziale piccolo bug, ma il risultato mi esce sempre quello...
o mi sfugge ancora qualcosa o c'è qualcos'altro che mi sfugge

E pure io ho corretto un bug potenziale, ma il risultato è sempre quello. Mah
Se Gugo non dà la soluzione entro oggi, sambenito per un anno intero

Originariamente inviato da ^TiGeRShArK^

EDIT: Minchia.. come al solito è sintetico il tuo codice

[gugoXX]

Purtroppo ho il codice in ufficio, e ci tornero' solo lunedi' mattina.
Aspettiamo qualcun altro... se troviamo un altro che da un risultato uguale a qualcuno di noi allora e' piu' probabile che sia quello giusto

Peraltro, giusto per pensare, cosa vi viene fuori da questo, valido?

5 10
16 22
18 9

(E vai di Unit test)

[^TiGeRShArK^]

17....