[C] progetto vasca pesci

[matteo.pata]

Ragazzi avrei bisogno di una mano per il progetto di algoritmi vi posto un po' di specifiche.Mi servirebbe una mano per l'utilizzo di una struttura dati adeguata.

La vasca è rettangolare e, al momento della partenza del De Pescis, contiene solo uova. Ogni uovo si
trova in una posizione x; y sul fondo della vasca (la x rappresenta la distanza dal bordo Est della vasca
e la y quella dal bordo Nord). Ogni notte se ne schiudono un certo numero. Il pesciolino pesa di solito
assai poco all'inizio della propria vita; ci sono comunque alcune variazioni casuali in questo peso iniziale.
Appena nato, il pesciolino elegge a propria tana il punto dove è nato. Da questo punto si guarda intorno,
e per lui ogni cosa che si muova (non le uova, dunque, ma solo altri pesci) è una potenziale preda.
Di giorno avvengono un certo numero di attacchi fra barracuda. Gli attacchi sono rapidissimi: pratica-
mente istantanei. Il pesce attaccante, scelta una vittima, gli si precipita addosso, divorandola o venendone
divorato. Se sopravvive, torna subito alla propria tana. L'esito dello scontro è determinato dalla più anti-
ca regola del mare: il pesce più grande (cioè il più pesante) mangia quello più piccolo. Attaccare fornisce
tuttavia un vantaggio: quando attacca, un pesce combatte come se avesse un peso maggiorato del 50%.
Nel raro caso di parità, vince comunque l'attaccante.
Dopo ogni pasto fratricida, un pesce incrementa il proprio peso di un decimo di quello della vittima che
ha appena divorato.
Gli attacchi avvengono prevalentemente fra pesci vicini di casa. I barracuda sono infatti creature molto
prevedibili: infallibilmente, sono sempre i due pesci più vicini ad attaccarsi per primi. Fra questi, è
sempre l'individuo più giovane, cioè il più irruento, ad attaccare l'altro (per più giovane si intende quello
nato dopo, fosse pure di pochi minuti). Fra diversi pesci potenzialmente attaccanti con prede altrettanto
distanti, si muoverà per primo il più giovane. Se lo stesso pesce deve scegliere fra prede altrettanto vicine,
si muoverà prima verso quella più giovane.
Le vacanze del professore
Il professore si assenta per un gran numero di giornate. Come sappiamo, ogni notte di assenza si possono
schiudere alcune uova, e ogni giorno avvengono alcuni attacchi. L'ordine e il numero delle nascite, i dati
relativi, il numero degli attacchi che avvengono durante ogni giorno, eccetera sono tutti descritti in un
le che il programma prende in input, no alla notte in cui si schiude l'ultimo uovo. Anche dopo questa
notte, cioè anche quando tutte le uova inizialmente presenti si sono schiuse, l'assenza del professore si
prolunga e i pesci continuano a divorarsi reciprocamente, giorno dopo giorno, no a che non ne rimane
uno solo.

Si vuole sapere la posizione e il peso dell'ultimo pesce rimasto cos come lo ritrova il distratto De Pescis
al ritorno dalle sue troppo prolungate vacanze.
Inoltre si vuole tener traccia del susseguirsi delle fortune dei vari barracuda. In particolare, si vuole
sapere in ogni momento quale sia il pesce dominante, cioè quello di peso massimo. Per fare questo, ogni
volta che emerge un nuovo pesce dominante, si vuole sapere la sua posizione (cioè quella della sua tana)
e il suo peso, al momento del \sorpasso".
Nota: ci sono tre casi in cui ciò può accadere.
A) quando un pesce, dopo un pasto, supera nel peso (i pareggi non contano) il pesce precedentemente
più grande;
B) quando nasce un pesce particolarmente vigoroso, già in partenza più grosso del precedente pesce di
peso massimo; notare che questo succede anche quando nasce il primo pesce.
C) quando il pesce attualmente più grosso viene pappato, e un altro gli subentra.

INPUT

L'input è un le di testo che descrive una serie di notti alternate a giorni, iniziata e terminata da una
notte. Nella prima riga compare il numero di notti presenti nel le.
Una notte è segnalata da una riga contenente la lettera N seguita dal numero di uova che si schiuderanno
quella notte. Ogni lieto evento è descritto, in ordine di tempo, da una riga successiva dove vengono
specicati tre numeri: le posizioni x e y dell'uovo che si schiude, in metri (precise al millimetro), e il peso
iniziale del pesciolino w in decine di grammi (con una precisione del centesimo di grammo).
Un giorno è segnalato da una riga contenente la lettera G seguita dal numero di attacchi che si manifestano,
al massimo, quel giorno. Il numero eettivo potrebbe essere inferiore perchè, quando rimane un solo pesce,
non sono possibili ulteriori attacchi prima della notte successiva.

OUTPUT

L'output deve consistere in una o più righe. Ogni riga corrisponde all'emergere di un nuovo pesce di
dimensione massima, oppure al ritorno del prof. De Pescis (che avviene troppo tardi, quando ormai è
rimasto un solo pesce, probabilmente aamatissimo). La riga deve cominciare dalla lettera che identica
il tipo di evento: A, B o C, col signicato descritto sopra, oppure D, che corrisponde al ritorno del
professore.
Dopo la lettera che identica l'evento, deve comparire nella stessa riga: il numero di pesci presenti
attualmente nell'acquario, e la posizione (sia x che y) e il peso attuale del pesce dominante.

Suggerimenti

Dati due punti A e B nel piano aventi coordinate, rispettivamente, (xA; yA) e (xB; yB), la distanza
che li separa si trova banalmente col teorema di Pitagora:

rad((xA + xB)2 + (yA + yB)).


Ragazzi io avevo pensato a uno HEAP però volevo sentire un po' anche i vostri pareri....grazie mille

Ripeto non chiedo la risoluzione del progetto ma una mano nel trovare la struttura dati da utilizzare.

[lupoxxx87]

un heap non è totalmente ordinato, quindi non va bene

[tuccio`]

Originariamente inviato da lupoxxx87

un heap non è totalmente ordinato, quindi non va bene

infatti, anche perché se vuoi controllare quale sia il massimo in O(1) ti basta salvarlo in una variabile a parte (oltre a tenerlo nella tua struttura dati) da aggiornare quando il pesce viene mangiato o viene "superato"

uno heap non è molto adatto a search e delete, operazioni fondamentali nel tuo caso.. molto meglio un avl

[matteo.pata]

Originariamente inviato da tuccio`

infatti, anche perché se vuoi controllare quale sia il massimo in O(1) ti basta salvarlo in una variabile a parte (oltre a tenerlo nella tua struttura dati) da aggiornare quando il pesce viene mangiato o viene "superato"

uno heap non è molto adatto a search e delete, operazioni fondamentali nel tuo caso.. molto meglio un avl

un albero binario bilanciato in altezza ma ordinato su cosa però....distanza tra un uovo e l'altro oppure altro??

[tuccio`]

Originariamente inviato da matteo.pata

un albero binario bilanciato in altezza ma ordinato su cosa però....distanza tra un uovo e l'altro oppure altro??

no be', pensavo alla dimensione a dire il vero, ma i pesci non si muovono se non per attaccare? in tal caso decisamente meglio lo heap

nel senso, se va aggiornato poco, e ogni aggiornamento avviene a seguito di un estrazione di minimo, va bene lo heap

[matteo.pata]

dai ragazzi una mano......

[wingman87]

Io partirei facendo un po' di ordine nelle specifiche:

Un pesce ha le seguenti caratteristiche:
posizione x,y
peso
data_nascita

Quando avviene un attacco, questo avviene sempre tra i 2 pesci (se ce ne sono) più vicini ed è sempre il più giovane ad attaccare la preda più vicina più giovane. Il pesce vincente è determinato dal peso dei contendenti, ma l'attaccante ha un bonus del 50% ed inoltre vince in caso di parità. Il pesce vincente aumenta il proprio peso del 10% del peso del perdente. Il pesce vincente rimane nella propria posizione (l'attacco è istantaneo), l'altro scompare.

Il file di input:
per ogni notte ci dice dove nascono i pesci, in quale ordine, e ci dice il peso con uno scarto di +-5cg (se ho capito bene);
per ogni giorno invece ci dice quanti attacchi al più avvengono (se resta un solo pesce non possono più esserci attacchi ma se ci sono pesci a sufficienza gli attacchi avvengono tutti).


Ora devo andare a mangiare.

EDIT: eccomi, edito sopra alcune cose che mi sono accorto di aver dimenticato.

Il file di output:
Ogni qualvolta che nell'acquario si presenta un nuovo "peso massimo" (pesce più pesante), questo va annotato sul file, scrivendo:
- da cosa deriva questo "sorpasso"
A - Un pesce, mangiandone un altro ha superato il "peso massimo"
B - E' nato un nuovo pesce più grande del "peso massimo"
C - Il "peso massimo" è stato mangiato
- il numero di pesci presenti nell'acquario
- la posizione e il peso del "peso massimo"

[wingman87]

Hai delle restrizioni sulla complessità dell'algoritmo?
Provo a esporti quello che stavo pensando:
Potresti tenere uno heap per ogni pesce. Per ogni pesce avrai quindi disponibile il più giovane e vicino a quel pesce.
Quando deve avvenire un attacco scorri tutti i pesci per determinare la coppia designata, poi simuli l'attacco ed elimini da ogni heap il pesce perdente ed aggiorni il peso del pesce vincente (non è necessario farlo in ogni heap se metti i collegamenti giusti).
Quando nasce un nuovo pesce scorri tutti i pesci aggiungendo agli heap associati il nuovo pesce ed aggiungendo allo heap del nuovo pesce ogni pesce.

In questo modo se non erro la complessità in spazio sarà n^2 ma quella in tempo sarà nlog(n)

[lupoxxx87]

mah... io non sono così convinto sullo heap.

ricordati che ogni cancellazione e ogni inserimento necessitano di un riordinamento dello heap, il che sarebbe notevolmente costoso avendo un heap per ogni pesce.

e il fatto che tu hai continui inserimenti e cancellazioni mi fa pensare a qualcosa simile a un albero binario (o rb, o b+) in cui tenere ordinate le distanze (come struttura da-a) e una hash table in cui tenere i pesci.

bisognerebbe valutare se, a seconda delle istanze, è necessario fare inserimenti alla radice negli alberi.

comunque opererei facendo

n inserimenti nell'albero e nella hash table in corrispondenza dei giorni
ogni notte:
cancellare il nodo più a sx
attaccare il pesce "a" con il pesce "da"
a seconda dell'esito, variare i dati di una riga hash e cancellare l'altra.


eviterei l'hash per le distanze perchè andrebbe riordinato in seguito ad ogni cancellazione, un bst non necessita di questo

[wingman87]

Originariamente inviato da lupoxxx87

mah... io non sono così convinto sullo heap.

ricordati che ogni cancellazione e ogni inserimento necessitano di un riordinamento dello heap, il che sarebbe notevolmente costoso avendo un heap per ogni pesce.

L'inserimento in uno heap richiede un tempo O(log(n)), dovendolo fare per ogni pesce otterresti un tempo O(nlog(n)). Il problema sarebbe la cancellazione ma si potrebbe postporre finché un pesce mangiato non arriva alla cima dello heap (quindi dovrà esserci un controllo da espletare con una semplice ricerca binaria ad esempio).

Originariamente inviato da lupoxxx87

e il fatto che tu hai continui inserimenti e cancellazioni mi fa pensare a qualcosa simile a un albero binario (o rb, o b+) in cui tenere ordinate le distanze (come struttura da-a) e una hash table in cui tenere i pesci.

bisognerebbe valutare se, a seconda delle istanze, è necessario fare inserimenti alla radice negli alberi.

comunque opererei facendo

n inserimenti nell'albero e nella hash table in corrispondenza dei giorni
ogni notte:
cancellare il nodo più a sx
attaccare il pesce "a" con il pesce "da"
a seconda dell'esito, variare i dati di una riga hash e cancellare l'altra.


eviterei l'hash per le distanze perchè andrebbe riordinato in seguito ad ogni cancellazione, un bst non necessita di questo

Anch'io avevo pensato altre soluzioni, sono rimasto però bloccato quando ho pensato al fatto che quando un pesce muore, se era il più vicino ad altri pesci andrebbe aggiornato il pesce più vicino a questi e non ho trovato un modo efficiente di farlo.
Es:
Abbiamo i pesci 1,2,3 e 4
Mettiamo che 2,3,4 hanno come pesce più vicino 1. 2 è il più vicino e lo attacca e vince. Ora dovrò ricalcolare il pesce più vicino per tutti i pesci.
In verità basterebbe calcolare la coppia di pesci più vicini, però anche così non mi è venuto in mente un modo efficiente per farlo (solo con complessità quadratica).
A meno che non tieni in memoria tutte le distanze tra ogni pesce... che è quello che facevo con gli heap.

Mi rendo conto comunque che la mia soluzione non è quel granché (credo).

[tuccio`]

in fin dei conti la soluzione più stupida potrebbe essere la migliore: un array

ti permette di trovare la coppia di pesci con distanza minima in O(nlogn), la cancellazione è O(1) e l'inserimento ti può costare una realloc, ma diciamo che comunque mediamente ti costa O(1) se fai crescere con un fattore di crescita decente l'array

ovviamente il pesce di peso massimo lo tieni in una variabile a parte e via

ps: l'algoritmo O(nlogn) per i punti con distanza minima è il numero 3 discusso in queste dispense: http://twiki.di.uniroma1.it/pub/Algo...ISP_divide.pdf

non so se ce ne siano di migliori, io conosco questo :X

[lupoxxx87]

Originariamente inviato da wingman87

Anch'io avevo pensato altre soluzioni, sono rimasto però bloccato quando ho pensato al fatto che quando un pesce muore, se era il più vicino ad altri pesci andrebbe aggiornato il pesce più vicino a questi e non ho trovato un modo efficiente di farlo.

...forse una matrice di adiacenza dinamica...
però il fatto che coordinate x,y siano continue rende il piano infinito, e non discretizzabile, non è facilmente utilizzabile.

forse, a questo punto, l'heap è il più veloce

[tuccio`]

Originariamente inviato da lupoxxx87

...forse una matrice di adiacenza dinamica...
però il fatto che coordinate x,y siano continue rende il piano infinito, e non discretizzabile, non è facilmente utilizzabile.

forse, a questo punto, l'heap è il più veloce

usare un heap per distanza minima vuol dire avere tutte le coppie nello heap, quindi se hai n pesci, nello heap ci sono n(n-1)/2 = O(n²) nodi e come dicevi prima eliminare 1 nodo vuol dire eliminarne n-1

[matteo.pata]

Originariamente inviato da tuccio`

in fin dei conti la soluzione più stupida potrebbe essere la migliore: un array

ti permette di trovare la coppia di pesci con distanza minima in O(nlogn), la cancellazione è O(1) e l'inserimento ti può costare una realloc, ma diciamo che comunque mediamente ti costa O(1) se fai crescere con un fattore di crescita decente l'array

ovviamente il pesce di peso massimo lo tieni in una variabile a parte e via

ps: l'algoritmo O(nlogn) per i punti con distanza minima è il numero 3 discusso in queste dispense: http://twiki.di.uniroma1.it/pub/Algo...ISP_divide.pdf

non so se ce ne siano di migliori, io conosco questo :X

Stavo dando un occhio interessante la cosa quindi dici di utilizzare quel tipo di algoritmo usando un array per trovare la distanza minima e di tenere a parte una variabile per il pesce + grande che ogni volta sostituisco.nella struttura del pesce quindi dovre tenere
posizione x
posizione y
peso pesce
creazione ??? in quanto devo vedere per il fatto di chi attacca per primo...

L'inserimento poi dici di farlo all'inizio dell'array oppure alla fine.
L'array lo tengo ordinato oppure no.

vi ringrazio intanto molto e se riusciete a darmi qualche altra dritta ve ne sarei molto grato....

[tuccio`]

Originariamente inviato da matteo.pata

Stavo dando un occhio interessante la cosa quindi dici di utilizzare quel tipo di algoritmo usando un array per trovare la distanza minima e di tenere a parte una variabile per il pesce + grande che ogni volta sostituisco.nella struttura del pesce quindi dovre tenere
posizione x
posizione y
peso pesce
creazione ??? in quanto devo vedere per il fatto di chi attacca per primo...

L'inserimento poi dici di farlo all'inizio dell'array oppure alla fine.
L'array lo tengo ordinato oppure no.

vi ringrazio intanto molto e se riusciete a darmi qualche altra dritta ve ne sarei molto grato....

se vedi come funziona quell'algoritmo tenerlo ordinato è un po' dura perché va ordinato prima per x e poi per y, in compenso ordinare prima di eseguirlo per x ti costa O(nlogn) quindi la complessità rimane O(nlogn)

per la creazione dico: allochi inizialmente un array di una certa dimensione, e inserisci sempre in fondo e incrementi una variabile che ti indica il numero di elementi effettivamente in uso dell'array, appena lo riempi fai una realloc facendolo crescere di un 50% ad esempio.. così non devi fare realloc ogni volta, ma hai un po' di margine, chiaramente per eliminare scambi l'ultimo elemento dell'array con quello che devi cancellare e decrementi la variabile che indica il numero di elementi dell'array utilizzati

[Furla]

Originariamente inviato da tuccio`

usare un heap per distanza minima vuol dire avere tutte le coppie nello heap, quindi se hai n pesci, nello heap ci sono n(n-1)/2 = O(n²) nodi e come dicevi prima eliminare 1 nodo vuol dire eliminarne n-1

questo si può risolvere usando un flag per ogni pesce, che dice se è vivo o se è già stato mangiato. quando si estrae dallo heap si verifica che entrambi i pesci coinvolti siano ancora vivi.

[tuccio`]

il che vuol dire avere come spazio occupato qualcosa che non è neanche limitato da O(n^k) per qualsiasi k intero :P

quello dell'array mi sembra un buon compromesso tra spazio e complessità onestamente

[matteo.pata]

ok ragazzi grazie della mano da domani mi metto sotto con l'implementazione di quell'algoritmo se qualcuno mi vuole dare una mano è sempre ben accetta visto che lavoro e il mio tempo a disposizione è veramente poco........Grazie intanto a tuttie dell'aiuto che mi state dando....

[matteo.pata]

up ragazzi qualche manima nella stesura della funzione....

[wingman87]

Originariamente inviato da matteo.pata

up ragazzi qualche manima nella stesura della funzione....

Che metodo hai scelto di usare? Quali problemi hai incontrato?