.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- progetto Hitori (http://www.dsy.it/forum/showthread.php?threadid=38459)

progetto Hitori

Ciao ragazzi apro un thread per il progetto hitori.
Cosa pensate per la struttura di dati che va utilizzata per memorizzare la griglia ?

Re: progetto Hitori

nessuna idea???

boh, io sto guardando le hash map penso che siano quelle giuste ,anke se nn lo so come andra dopo con le coordinate e altre richeieste del progetto.

Siete già a corto di idee?

scusate, ma la proprietà 3, è spiegata male:
"le caselle non annerite devono formare una sola componente connessa verticalmente e orizzontalmente,
ovvero non devono esserci caselle o gruppi di caselle isolate dal resto dello schema."
però nell'esempio che c'è subito dopo, la soluzione al centro è corretta, allora non devono essere sia orizzontali che verticali, devono essere orizzontali O verticali.
voi che ne pensate?

__________________
Se non credi in te stesso, chi ci crederà?

si...nel senso che le caselle bianche non devono essere isolate, quindi una casella è connessa con quella sopra verticalmente oppure con quella di fianco orizzontalmente e quindi in qualche modo collegate..ma per la struttura dati a cosa ti affidi?

La prima proprietà l'avete già implementata ?

consiglio vivamente di provare a risolvere qualche hitori per gioco.

solo così si capisce bene cosa fare e quando farlo per rislverlo.

io lo sto facendo e sto prendendo degli ottimi spunti...

__________________
L'ignoranza è il pane dei poveri

io ho implementato struttra dati(hash table), una conversione della struttura per lavorare con piu semplicita, le proprieta 1 e 2, mi metto a fare la 3, ma le euristiche non so se riusciro a farle, perche devo testare tutto quanto, senno non mi serve a nulla tutto questo...
francamente a me non è piaciuto che si rifacesse come febbraio, preferisco 2 appelli distinti, non e giusto secondo me fare cosi...

__________________
Se non credi in te stesso, chi ci crederà?

ma l'implementazione l'hai presa da Algo team?

l'implementazione di cosa?comunque, ho usato la hash table, nella miriade di esempi c'era questa struttura bell'e pronta. Per le 3 proprietà, le ho fatte 2 da solo, la terza veramente devo rivedermi la teoria, in ogni caso, ho provato a giocare sul link che viene dato, ma non riesco a vincere nemmeno una volta...mi chiedo come diavolo farò a verificare tutto sto casino...e ancora non mi sono messo sulle euristiche!

__________________
Se non credi in te stesso, chi ci crederà?

Originally posted by Benny
io ho implementato struttra dati(hash table), una conversione della struttura per lavorare con piu semplicita, le proprieta 1 e 2, mi metto a fare la 3, ma le euristiche non so se riusciro a farle, perche devo testare tutto quanto, senno non mi serve a nulla tutto questo...
francamente a me non è piaciuto che si rifacesse come febbraio, preferisco 2 appelli distinti, non e giusto secondo me fare cosi...

__________________
L'ignoranza è il pane dei poveri

Ragazzi attenzione:

il prof non ha previsto un caso (almeno IMHO):

1 1 1 1 1
1 1 0 1 1
1 a 1 0 1
1 1 0 1 1
1 1 1 1 1

anche in questo tipo di configurazione, stando alle regole, la casella con la a non può essere annerita.

Eppure la regola angolo vale solo sugli angoli delle griglie, non su tutto l'hitori...

__________________
L'ignoranza è il pane dei poveri

Io userei l'albero rosso nero per la griglia,
ma non ho capito una cosa,
da quale casella si parte e con quale principio si sceglie la tecnica di risoluzione con cui cominciare per risolvere l'hitori?
Nell'esempio parte dalla tecnica PI casella 0,1 non avrebbe potuto cominciare con qualcos'altro?

pau, non saprei..per ora mi sto ammazzando il cervello per implementare la proprietà 3 con una bella visita in ampiezza, tutta da riscrivere (grande inutilità in rete)...però non si rischia di violare una di queste proprietà se si seguono troppo le euristiche?boh, tanto manco riesco a vincere una partita senza le euristiche, figuriamoci con tutte quelle che ci sono...

__________________
Se non credi in te stesso, chi ci crederà?

beh ma se implementi le euristiche correttamente, le proprietà sono rispettate.

alla fine se la griglia rispetta le proprietà, le euristiche sono fatte giuste, altrimenti qualcosa non va...

__________________
L'ignoranza è il pane dei poveri

Originally posted by marcio
Io userei l'albero rosso nero per la griglia,
ma non ho capito una cosa,
da quale casella si parte e con quale principio si sceglie la tecnica di risoluzione con cui cominciare per risolvere l'hitori?
Nell'esempio parte dalla tecnica PI casella 0,1 non avrebbe potuto cominciare con qualcos'altro?

__________________
L'ignoranza è il pane dei poveri

ma non basta secondo voi implementare solo le euristiche? alla fine rispettano le 3 proprietà!

Ma per implementare tutte le euristiche, le si applica in un ordine particolare o le si fa a caso?

Originally posted by marcio
Ma per implementare tutte le euristiche, le si applica in un ordine particolare o le si fa a caso?

__________________
L'ignoranza è il pane dei poveri

Per la proprietà 3 (della componente connessa) usate una visita di un grafo vero?

Anche io penso di scegliere un albero Rb..
Benny perchè hai usato proprio l'hash table?

perchè è la struttura che uso da diversi progetti, e cambiarla vuol dire ripartire da zero...so che per la stragrande maggioranza dei progetti sarebbe più indicato usare un bel grafo e tanti saluti, come del resto anche in questo è la diretta soluzione migliore...però in sintesi sono tutte molto simili, adottano una forma molto diversa ma sempre di puntatori alla fine si tratta...si riesce anche con difficoltà a piegare al proprio volere la struttura che si preferisce..e poi non si ha sufficiente tempo per provare più di una soluzione di struttura dati per lo stesso progetto, quindi meglio non arrovellarsi troppo e darci dentro con la scelta più facile

__________________
Se non credi in te stesso, chi ci crederà?

Domandina:
quando finisce il gioco? O meglio, quante volte devo utilizzare le diverse tecniche ?Cosa mi dice "basta"?

quando finisce il gioco? O meglio, quante volte devo utilizzare le diverse tecniche ?Cosa mi dice "basta"?

Il gioco termina al ennesimo battito di clock dove n è ceil log del numero di celle non bianche della tabella hash da voi precedentemente implementata.
Per la proprietà B e garantire una mutua esclusione nel caso di sconfitta per proprietà 2 ( ovvero quando rimani incastrato) io consiglierei un risto orientato

Perchè nei progetti sono richieste strutture che durante il corso di laboratorio non sono nemmeno contemplate? Mi riferisco ad esempio alla gestione di insiemi disgiunti con rappresentazione mediante alberi?E' possibile che per implementare una union-find si debba aspettare il progetto e non una sana e profiqua discussione e implementazione durante le ore di laboratorio?

Bello oggi guardo se è uscito il progetto visto che era per ieri/oggi la data d'uscita segnata anche sul calendario degli appelli e me lo trovo fuori già da una settimana, andiamo bene -__-'

A sto punto mi sono iscritto pure all'esame di luglio perchè dubito di farcela per il 22 giugno -__-'

Per il progetto a un primo sguardo mi sembra uno dei soliti progetti complicati usciti ultimamente, speriamo in bene...

garet concordo pienamente con te, e da un po c'e sto sistema della consegna doppia...

__________________
Se non credi in te stesso, chi ci crederà?

Come state procedendo col pogetto?

Scusate, sono io che mi sono perso qualche pezzo del testo, oppure si possono utilizzare le matrici? In altri progetti era espressamente scritto che non potevano essere utilizzate, ma in questo caso o ho letto male, oppure possiamo utilizzarle.
Guardando gli input, il primo numero passato è proprio la grandezza della griglia, quindi è facile costruirci una matrice, in più in questo caso non ci sono piani infiniti o cose del genere, la griglia è per definizione finita... Non so, magari sono io che ho letto male...

Ciau
Ivan

__________________
Tecum sunt, quae fugis... Seneca

ivanbag hai perfettamente ragione, infatti io le uso..il problema è che nonostante ho implementato quasi tutto, ho problemi con la memoria..ste maledette cose mi fanno perdere sempre un sacco di tempo..non so neanche come risolverlo sto problema dei passaggi di matrici qua e la..

__________________
Se non credi in te stesso, chi ci crederà?

ciao!
Credo che basta usarne due matrici!
Una in input e l'altra sfrutarla per l'output
In teoria,e anche in pratica funzionano!
Per quanto riguarda il loro uttilizo, il prof mi ha confermato che si possono uttilizare le matrici,quando sono andato a chiedere!

ma i valori li inserisco nella matrice ma per implementare le euristiche bisogna basarsi su un albero o è sufficiente la matrice!!!!
perchè io mi sono bloccato nell'inserimento dei valori letti da matrice nell'albero!!

no no niente albero...
le euristiche li implementi con i soliti cicli for per strapolare le coordinate e controllare tutte le celle della matrice, e dei if qua e la per gli appositi controlli

e le solite strutture dati utilizzate nei progetti vecchi si vanno a far benedire!!!?
ma così forse ha un senso tutto quanto...

ma quindi tu [Alien] sei a buon punto....?

ho trovato delle dificolta sulle due tecniche NI e BI
che sono per la consegna di luglio,visto che io a giugnio devo partire il 20,e non posso consegnarlo!

Nel progetto non lo dice specificatamente ma immagino, anche dagli esempi visti e dal fatto che venga data solo una dimensione in input, che la griglia dell'hitori sarà sempre un quadrato (indi 4x4, 5x5, 200x200, ecc...), giusto?

up

__________________
Saluti - Davide

esato...la dimensione sara n*n

ho un dubbio..
lo schema dell'hitori deve essere passato al programma da file (es. txt) oppure deve essere scritto dall'utente su richiesta del programma?

marcodili, l'input è nella forma:
3
1 2 3
1 2 3
1 2 3
ma io le ho trovate chiare le specifiche, certo sono un po lunghette, ma perche ci sono degli esempi..il difficile per me è vincere anche un solo hitori..

__________________
Se non credi in te stesso, chi ci crederà?

si.. ma questo input... deve essere contenuto in un file di testo?

è indifferente...sia che arrivi da standard input (console) o da file di testo è la stessa cosa per il programma.
Non è necessario considerare "da dove arrivi" in quanto la redirezione dell'input / output è una funzionalità che offre il SO stesso.

__________________
Saluti - Davide

Originally posted by alien
no no niente albero...
le euristiche li implementi con i soliti cicli for per strapolare le coordinate e controllare tutte le celle della matrice, e dei if qua e la per gli appositi controlli

__________________
Tecum sunt, quae fugis... Seneca

scusate ma usando le matrici, come fate a tener traccia di quali celle devono per forza essere bianche o quali sono già nere? Avete costruito una seconda matrice che ne tiene conto? Perchè la tecnica suggerita dal prof con -3-, *3*, non credo sia applicabile con le matrici o sbaglio?

Io sto usando una matrice di struct, il problema è la ricorsione per effettuare le varie chiamate e il fatto di determinare se la chiamata a non_annerire() viene da PI o da NV
e lo stesso per annerisci()!!!
potete suggerirmi qualcosa...

Ciao a tutti!
Sono pienamente d'accordo con voi che è comodissimo usare le matrici...ma come si implementa la regola 3 per la quale le caselle bianche devono essere una componente connessa????
Certo che è un bel casino questo progetto!!!

anche io sono in difficoltà sulla proprietà 3. voi come avete fatto?

quando sono andato a parlare al prof dopo il progetto di gennaio, mi aveva detto che in generale per ogni progetto vengono chieste:
gestione input(e con faccialibro ci ho perso praticamente settimane)
struttura dati
un algoritmo sui grafi, ovvero una visita in ampiezza o in profondita
la mia proprieta 3 fa qualche cavolata, ma se la cava in qualche modo, quindi non penso possa dare un esempio valido...
ma qualcuno di voi e riuscito a consegnarlo per il 22?come e andata?

__________________
Se non credi in te stesso, chi ci crederà?

ho dovuto utilizzare un hash come struttura di supporto, altrimenti la uno solo con matrici è abbastanza difficile da implementare.

per la componente connessa penso che si dovranno collegare i nodi in una struttura da albero...vedrò...

__________________
L'ignoranza è il pane dei poveri

io per la 1 e la 2 sono riuscito solo con le matrici. è la terza che è problematica. non avete idee?

ciao a tutti domanda....
la terza regola , premetto che ho implementato l'hitori con una tabella, e se per testare la componente connessa creassi un grafo di appoggio solo con le celle bianche, cioè con contenuto diverso da zero?
a me sembra una cosa un pò onerosa ma per ora è l'unica idea che mi è venuta in mente.....avete altre idee?
buona giornata e buon lavoro!!

secondo me la cosa migliore è fare tipo una "visita in ampiezza" adattata ad una matrice... e quindi verificare la componente connessa.

Come avete fatto BI e NI?
Nell'esempio il prof usa NI nel (4,2). Però non sarebbe identico il risultato se avesse usato BI in (4,0)? I Altrimenti perchè il professore decide di utilizzare NI in (4,2)?

non sarebbe meglio una union find per vedere la componente connessa?

Ho un dubbio sulle euristiche..
Non ho capito ma devo usarle per risolvere l'hitori nel senso inserito l'hitori chiamare le euristiche oppure deve esserci una funzione che avuto in ingresso l'hitori lo risolva in autonomia?
proprio non riesco a capire!

per la NI e BI come si può fare?...io il resto l'ho fatto con le matrici,ma andrà bene?!!

scusate stavo ragionando su NI e BI e mi è venuto un dubbio... da quanto mi sembra di aver capito leggendo il progetto.. BI e NI vengono applicate per ultime se sono presenti due numeri uguali sulle righe o sulle colonne... Però ci sono dei casi in cui forzando la casella e applicando ricorsivamente le regole, non si arriva a una soluzione definitiva perchè rimangono altri numeri uguali sulle righe o sulle colonne...
In questo caso la proprietà 1 non verrebbe rispettata e quindi verrebbe annerita/non annerita una casella che non dovrebbe essere annerita/non annerita.
Quindi se bisogna applicare più volte BI o NI la soluzione dell'hitori non è mai giusta. Mentre se si applicano una sola volta BI o NI la soluzione è sempre giusta.
Qualcuno ha riscontrato questo stesso problema?

ma per la tecnica trapezio come avete fatto?

non ho capito una cosa...ma per verificare il metodo NI nell' esempio, si fa l'ipotesi che (4,2) sia nero e poi si trova che questo non può avvenire perchè altrimenti le celle nell'angolo rimarebbero chiuse, ma per verificare questa condizione bisogna fare un grafo con una visita per vedere che le celle siano connesse o basta applicare le regole, magari implementandone qualcuna aggiuntiva come ad esempio CLOSE EDGE sul sito http://www.menneske.no/hitori/methods/eng/methodce.html ????????????

Ho un paio o più di domande, magari qualcuno mi sa dare un suggerimento...

1) Con che ordine si possono applicare le euristiche? Le ho implementate tutte, tranne BI e NI che per il momento trascuro, prese singolarmento funzionano bene, in più se faccio piccole "catene" vanno bene, ma non trovo la "catena" unica per farle coesistere tutte... Avete idee in proposito?

2) E' possibile implementare ulteriori euristiche? Da quello che ho letto dalle specifiche quelle indicate sono le minime ed indispensabili, però, come suggerito da garfa84, ci sono regole ulteriori come il closed edge (molto utile per fare in modo che venga rispettata la terza proprietà...)

3) La terza proprietà... Io stavo pensando ad un grafo, ma non vorrei farmi del male... Come la verificate?

Saluti
un Ivan... che finalmente poterci dedicare tempo...

__________________
Tecum sunt, quae fugis... Seneca

Sono nella tua stessa situazione...
Hai rappresentato in modo completo e chiaro il problema

Scusate domandona: Come avete implementato la regola trapezio? sono bloccata li per ora, anche perchè non riesco a capire bene la specifica sul progetto...qualcuno può aiutarmi?

Io l'ordine delle euristiche le ho applicate nel main a partire da [PI], poi questa richiama una funzione non_annerire che mi chiama [SB] che mi richiama annerisci e così ricorsivamente. Quando non è più applicabile niente richiama trapezio , coppia , angolo che come prima richiamano SB e NV se c'è qualcosa da annerire o no.
In questo modo prendendo l'esempio dato, arrivo fino all' applicazione della regola no (4,3) : A
Rimane da fare NI e BI che devono fare una supposizione su un valore per trovare una contraddizione , pensavo a una pila o una coda per memorizzare la supposizione. E per la terza regola mi viene in mente anche a me un grafo ma è un bel casino.
Anch' io chiedo , ma c'è bisogno di fare un grafo o si può tramite l'implementazione di altre tecniche di evitarlo???

io pensavo di andare dal prof a chiedere dei chiarimenti....
qualcuno va in Silab o è già lì a impazzire sul progetto?? magari ci si chiarisce le idee insieme!!!

per trapezio io ho controllatto tramite dei cicli for , se ci sono elementi sulla prima colonna uguali a distanza 1 o più e sulla colonna dopo a distanza 2 o + se si richiamo la funzione per annerire il primo elemento in diagonale e poi quell'altro elemento , lo stesso ho fatto per verificare l'uguaglianza sulle righe!!!
Non so se si è capito bene!!!

Quello che non capisco di Trapezio è cosa devo cercare. Cioè cerco di spiegarmi: devo cercare se su una riga i c'è un numero ripetuto a distanza di una cella e nella riga i+1 un altro numero ripetuto a distanza 2?

Garfa purtroppo non riesco a passare in Silab, non sono di Milano, e non riesco con il lavoro a scendere apposta...

Quello che non capisco di Trapezio è cosa devo cercare. Cioè cerco di spiegarmi: devo cercare se su una riga i c'è un numero ripetuto a distanza di una cella e nella riga i+1 un altro numero ripetuto a distanza 2?

Giusto ma lo devi fare non solo a distanza di una cella, ma anche a distanza 2 , 3 ...n-2 e nella riga i+1 a distanza 2 ,3 ... n-1

ma così è da impazzire!!!!!!

Sono passato dal prof e quello che ne ho ricavato è che:
le euristiche da implementare sono quelle scritte, se uno vuole aggiungerne altre tipo quelle del sito suggerito, può tranquillamente.

Mi ha spiegato come dovrei fare con [NI]
cioè supporre sui valori che rimangono, bisogna memorizzare la supposizione da qualche parte(coda,pila,variabili addirittura).
cioè suppongo 1 (4,2) annerito allora dico 1 (4,0) può essere nero o bianco.
Nero non può essere perchè se no rimane chiuso 2. e cancello nero. vado avanti con la supposizione di 1(4,0) bianco e poi sarà 1(2,0) bianco o nero, non può essere ne bianco ne nero allora 1(4,2) non può essere nero e sarà bianco.

Quello che mi chiedo come faccio a memorizzare la supposizione?
e per la verifica che il 2 non rimanga chiuso bisogna applicare la regola 3 non close_edge, perchè nel caso specifico vabe ma in altri casi potrebbe non andare bene!!!quindi come faccio a verificarlo???

quindi stai dicendo che annerisci e non_annerisci non sono obbligatorie come implementazione....
ma allora come faccio a risolvere l'hitori.....qualcosa mi dice che questo progetto non lo consegnerò.....ufffff

io annerisci e non_annerire le ho implementate...adesso provo a guardare come implementare il backtracking per fare la supposizione..mi ha parlato di esempi fatti a lezione (mosse del cavallo, o regina)....io devo consegnarlo perchè non ho voglia di sbattere la testa su un altro progetto!! quindi uniamo le forze!!

si se è per quello nemmeno io ma qui è un bel pò incasinato

Si nelle slide mi ricordo l'esempio della scacchiera con il cavallo.
Nella quinta lezione se non ricordo male
Ora mi riguardo un pò tutto.
Grazie Garfa!

Immaginavo che BI e NI fossero da applicare alle celle non ancora controllate, mi mancano solo loro e poi ho implementato tutto. Devo solo farlo funzionare... ahahaha

Io T l'ho implementata più o meno così:
se mat[0][0].num == mat[2][0].num && mat[0][1].num == mat[3][1].num ... ovviamente questo è solo uno dei tanti if (all'interno dei for) del trapezio, per esempio devo controllare che che gli indici durante i for di controllo non escano dalla matrice, oppure "il senso" del trapezio, perché, per come l'ho interpretato io, può essere "girato" in modi diversi... E adesso che ci penso non ho provato a farlo con i due vicini in basso ed i diagonali in alto O_O , corro ssssubito ad aggiungere quella parte!

annerire e non_annerire io le ho implementate per comodità, ma effettivamente possono non essere obbligatorie. Le ho trovate comode perché le implementi una volta sola e le riusi spesso, in più al loro interno è facile inserire le chiamate alle euristiche che applichi solo quando annerisci o non annerisci una cella... In questo modo con una funzione le chiami tutte

Originally posted by garfa84

Quello che mi chiedo come faccio a memorizzare la supposizione?
e per la verifica che il 2 non rimanga chiuso bisogna applicare la regola 3 non close_edge, perchè nel caso specifico vabe ma in altri casi potrebbe non andare bene!!!quindi come faccio a verificarlo???

__________________
Tecum sunt, quae fugis... Seneca

in pratica annerisci e non_annerire richiamano rispettivamente:
NV A e non_annerire, mentre non annerire richiama SB e annerisci.
Il mio dubbio resta su come gli passo le coordinate su cui eseguire annerisci e non annerire quando non è la prima chiamata? Oppure devo inserire nelle euristiche le chiamate alle due funzioni ricorsive?
a me mancano queste due e NI BI poi ovviamente farlo funzionare

__________________
Tecum sunt, quae fugis... Seneca

si ok ora mi sorge un'altra domanda....la chiamata ricorsiva a annerisci o non annerisci avrà dei parametri che saranno la matrice e le due coordinate o x e y come le hai chiamate tu su cui eseguire le euristiche.... per quello che mi chiedevo se le chiamate ricorsive devono essere all'interno delle euristiche....è questo il mio problema! o almeno uno dei tanti

Ok...

Allora, ti porto il mio esempio per CS. Al suo interno, una volta eseguiti i controlli, passo ad annerire la matrice e le coordinate della cella. Da annerire chiamo:

- NV che a sua volta chiama non_annerire passando matrice e cella e con gli stessi parametri chiama anche SB. SB a sua volta chiama annerire. Qui ho avuto il primo problema, perché come noterai rischia di continuare il giro all'inifinito, per fare questo ho fatto in modo che nv controlli con un if le celle vicine, se sono già state "toccate" non fa partire SB, al contrario, se non sono state "toccate" SB parte. Ovvio che al primo giro parte e al secondo no.
- A che, come dicevo prima, controlla tutti gli angoli, quindi gli passo solo la matrice. Al suo interno richiama solo non_annerire. Non ho ancora deciso se far partire SB anche all'interno di A, questo mi creerebbe qualche casino con l'impostazione che ho dato.

E' importante mettere uno "stop" forzato alle continua chiamate o ti perdi in un bel loop... Ieri mattina ho cristato parecchio perché non capivo come fare... Spero di essere stato chiaro, è abbastanza un casino a parole, parla meglio il codice, ma non posso metterlo

Ciau
Ivan

EDIT: per BI e NV mi è venuto in mente che posso sfruttare l'impostazione che ho dato. All'interno della matrice di strutture che ho creato ho un int che contiene il numero e ho un int che fa da "tag" per le celle già controllate. Quelle ancora non controllate hanno un determinato "tag". Una volta terminate le euristiche è facile scorrere la matrice alla ricerca delle celle non visitate. Da qui si può scegliere se lavorarci direttamente oppure crearsi una struttura esterna ed applicare BI e NV ed eventuali altri controlli...

__________________
Tecum sunt, quae fugis... Seneca

ok quindi tu per ogni euristica richiami rispettivamente o annerire o non annerire giusto? non voglio vedere il tuo codice ma cercare di capirne un pò di più

Originally posted by Lallac10
ok quindi tu per ogni euristica richiami rispettivamente o annerire o non annerire giusto? non voglio vedere il tuo codice ma cercare di capirne un pò di più

__________________
Tecum sunt, quae fugis... Seneca

Originally posted by ivanbag

EDIT: per BI e NV mi è venuto in mente che posso sfruttare l'impostazione che ho dato. All'interno della matrice di strutture che ho creato ho un int che contiene il numero e ho un int che fa da "tag" per le celle già controllate. Quelle ancora non controllate hanno un determinato "tag". Una volta terminate le euristiche è facile scorrere la matrice alla ricerca delle celle non visitate. Da qui si può scegliere se lavorarci direttamente oppure crearsi una struttura esterna ed applicare BI e NV ed eventuali altri controlli...

Originally posted by ivanbag
Esatto, per ogni euristica richiamo annerire e/o non_annerire. Come dicevo annerire a sua volta richiama euristiche... Un bel macello ^^

Ivan

si perchè non annerire lo eseguo fin tanto che può essere applicato e siccome nell'esempio quelle chiamate a PI richiamo non_annerire che a sua volta richiama solo una bianco, ma questo non trova niente a annerire, riesegue PI fin quando trova valori che soddisfano l'euristica!!

Originally posted by garfa84
Ok , anch'io avevo pensato di usare l'int della struct per vedere i numeri che mi rimangono da decidere, i e j che sono gli indici della matrice[ i ][ j ] li ho per identificare il numero in questione...in base a questo devo fare la supposizione che sia nero, ma dove la metto sta supposizione????....

Originally posted by garfa84
e non ho ancora capito come fare x la componente connessa, cioè il prof mi ha detto che andrebbe verificata ogni volta che devo decidere se annerire o no una cella.....

__________________
Tecum sunt, quae fugis... Seneca

io per la regola 3 ho trattato la matrice come se fosse un grafo testando le prime 2 celle se sono nere e per la prima che non lo è guardo gli adiacenti a croce cioè dx sx su giù e metto le coordinate in una coda poi fino a quando la coda non è vuota faccio lo stesso per tutti gli adiacenti. per capire se ho toccato tutti i nodi ho 2 contatori che mi contano le celle nere e le celle bianche che ho visitato se la loro somma è diversa dal numero di celle totali della griglia allora la griglia non è connessa


EDIT: ho provato a eseguire manualmente la catena di euristiche e arrivati al punto no (2,3)PI li dovrebbe poi applicare SB non di nuovo PI.....se non è così allora non ci ho ancora capito molto

si lo esegue SB ma non ci sono valori per cui stampa il messaggio no (x,x) : SB...l'esecuzione avviene sempre dopo non_annerire ma non sempre trova valori!!!

io per la regola 3 ho trattato la matrice come se fosse un grafo testando le prime 2 celle se sono nere e per la prima che non lo è guardo gli adiacenti a croce cioè dx sx su giù e metto le coordinate in una coda poi fino a quando la coda non è vuota faccio lo stesso per tutti gli adiacenti. per capire se ho toccato tutti i nodi ho 2 contatori che mi contano le celle nere e le celle bianche che ho visitato se la loro somma è diversa dal numero di celle totali della griglia allora la griglia non è connessa

il primo passo è il controllo di 00 se è nero incremento il contatore nero, e setto 1 il visitato di 00, poi passo a 01 e quello se è bianco controllo a croce e metto quelli non neri nella coda
e così via incrementando per ogni bianco il contatore bianco

non capisco la tua risposta però.....ci sono due numeri uguali su quella riga....eppure la considera dopo molto....boh

si ma il PI non_annerisce il 4 e non ci sono 4 sulla stessa riga o colonna..no?!

scusa un'altra domanda...ma il controllo sulla regola 3 al momtento di eseguire nero_impossibile , cioè alterzultimo passo o anche nei passaggi precedenti???

già......perchè tiene in considerazione la casella che non viene annerita.....ok

non ho ancora implementato e pensato a NI e BI

ma per bianca intendi che non si sa ancora o che è già stato determinato che sarà bianca???

no beh prima di tutto la regola 3 viene applicata su una griglia risolta quindi sai già che se è nera o bianca, e nel caso di BI o NI tu presupponi che sia nero consideri nera la cella e vice versa la consideri bianca

Lallac10 ma la regola 3 l'hai implementata con un grafo vero e proprio, cioè creando il grafo e facendo una visita o solo con controlli per i valori della matrice?

niente grafo, solo prendendo in considerazione le celle con coordinate (i-1, j)(i+1,j)(i,j-1)(i,j+1) e basta solo quello ma ovviamente controllando che gli indici non escano dai limiti della matrice

Tralasciando la regola 3 che mi sta dando ancora qualche grattacapo...
Ora mi sorge un problema, sto mettendo giu la gestione dell'input... Voi come avete fatto? Per il momento utilizzavo una matrice dichiarata all'interno, ma ora vorrei iniziare a passargliela di volta in volta... Avete qualche idea? Io sinceramente sulla gestione degli input non sono molto sveglio
Ho provato con gets, ma se compilo con --ansi mi dice che è è pericolosa:

/tmp/cceIIiNg.o: In function `main':
input.c: (.text+0x39): warning: the `gets' function is dangerous and should not be used.

__________________
Tecum sunt, quae fugis... Seneca

Bene, ho la verifica di tutte e tre le regole funzionante, almeno, per tutti gli input provati fin'ora sembrano funzionare.
Il tutto senza BI e NI che mi danno problemi seri... Se riesco a sistemare anche queste due mi manca *solo* il rendere le matrici dinamiche e poi sono a posto... Dico solo perché prevedo parecchi fault tra malloc e puntatori...

Che ragionamento avete fatto per BI e NI? A me è un po' poco chiaro quel che devono fare... Almeno, come le ho interpretate io non funzionano O.o

Ciau
Ivan

__________________
Tecum sunt, quae fugis... Seneca

anch'io ci sono con le tre regole...x la terza con 2 funzioni che finalmente funziona!!!
Devo fare BI e NI!!!
Ho 2 domande:
1)la regola 3 bisogna verificarla sempre o solo quando si applica NI e BI e nel caso dell' input con zeri, perchè nell'esecuzione delle euristiche non mi pare vada mai a contraddire la regola 3

2)l' input con zeri come fate a diferenziarlo da quello senza, cioè non fargli stampare i passaggi che svolge, perchè io stampo il messaggio del passo eseguito appena lo esegue

Ragazzi ma com'è che a me NI funziona se la struttura è un albero rosso nero
e se è una matrice dinamica allocata con calloc invece si interrompe a un certo punto senza motivo?

Originally posted by marcio
Ragazzi ma com'è che a me NI funziona se la struttura è un albero rosso nero
e se è una matrice dinamica allocata con calloc invece si interrompe a un certo punto senza motivo?

Originally posted by garfa84
1)la regola 3 bisogna verificarla sempre o solo quando si applica NI e BI e nel caso dell' input con zeri, perchè nell'esecuzione delle euristiche non mi pare vada mai a contraddire la regola 3

Originally posted by garfa84
2)l' input con zeri come fate a diferenziarlo da quello senza, cioè non fargli stampare i passaggi che svolge, perchè io stampo il messaggio del passo eseguito appena lo esegue

__________________
Tecum sunt, quae fugis... Seneca

scusate io una volta arrivato ad applicare la regola A (4,3)..poi sò le celle ancora da decidere , sulla base di queste applico NI...come l'avete pensata???
sono un po impatanato su questo?

Ops... Da ieri mattina non mi sono più collegato e non ho visto la tua richiesta... Sei riuscito a sistemare?

Ni e BI alla fine non mi vanno come dovrebbero e le ho lasciate stare... Ho dato ora l'ultima compilazione e fatto gli ultimi test, funziona... Più o meno, ma funziona... Alcuni schemi me lo fanno andare in pappa, ma purtroppo il tempo rimasto per debuggarlo come si deve è finito... E devo ancora fare la relazione O_O Non so nemmeno da che parte cominciarla...

Mi sa che mi toccherà farla domani mattina in silab, ora sono ko e non ne ho proprio voglia... Uff...

Ciau
Ivan

__________________
Tecum sunt, quae fugis... Seneca

a me NI E BI andrrebbero pure , ho un problema con la regola 3 per controllare se quando faccio la supposizione la regola vale o no..adesso provo a vedere di fare qualcosa...sto impazzendo!!anch'io domattina faccio la relazione, ci si becca in silab mattina o pomeriggio

sperem bene!!

Per fortuna a me la regola 3 va... O almeno, sembra andare ^_^
Sono arrivato ora in Silab, passaggio di rito alle macchinette e poi mi piazzo a fare la relazione... Speriamo bene davvero!
Ciau
Ivan

__________________
Tecum sunt, quae fugis... Seneca

ma per i tempi di calcolo che gli scrivo...io ho utilizzato una matrice allocata dinamicamente e faccio vari controlli su questa..come faccio a sapere che tempi mettere...O(n)..O(logn)..O(nlogn)..teta di n teta di quant'altro esista..

Originally posted by garfa84
ma per i tempi di calcolo che gli scrivo...io ho utilizzato una matrice allocata dinamicamente e faccio vari controlli su questa..come faccio a sapere che tempi mettere...O(n)..O(logn)..O(nlogn)..teta di n teta di quant'altro esista..

__________________
Tecum sunt, quae fugis... Seneca

relazioni ce ne sono ma cavolo sono tutte fatte con alberi grafi alberi rb e chissà cos'altro...bhoooo!!!

Originally posted by garfa84
relazioni ce ne sono ma cavolo sono tutte fatte con alberi grafi alberi rb e chissà cos'altro...bhoooo!!!

__________________
Tecum sunt, quae fugis... Seneca

C'è qualcuno che ha terminato il progetto e lo vuole postare ???

Originally posted by marchinkus
C'è qualcuno che ha terminato il progetto e lo vuole postare ???

__________________
Tecum sunt, quae fugis... Seneca

cos'hanno chiesto oggi all'orale Aguzzoli e Torelli?com'è?

Potete anche non studiare,passano tutti

Originally posted by Microke
Potete anche non studiare,passano tutti

__________________
Tecum sunt, quae fugis... Seneca

Originally posted by Microke
Potete anche non studiare,passano tutti

Con torelli ?
Come è possibile ?
Io ho visto gente fare scena muta e farsi confermare il voto del progetto..

Originally posted by Microke
Con torelli ?
Come è possibile ?
Io ho visto gente fare scena muta e farsi confermare il voto del progetto..