HW8: Come faccio quando ho sia a destra che sotto la stessa sequenza di caratteri che sto cercando?

Heretic (460 points)
3 5 7
asked Dec 11, 2019 in HW8 obbligatorio by Heretic (460 points)
recategorized Jan 6, 2020 by andrea.sterbini
Ho impostato una funzione ricorsiva che richiama sé stessa per vedere se a destra o sotto è presente un carattere della parola che sto cercando.

Al fine di decidere quale direzione prendere nel caso in cui io abbia lo stesso carattere sia sopra che sotto, vado a vedere cosa c'è al carattere successivo a quello uguale. Ad esempio se prima ho controllato n +1, dopo vado a controllare n + 2.

Il problema sorge quando dopo n + 2 c'è un ulteriore carattere uguale! A quel punto il mio algoritmo va a destra perché è la prima condizione che soddisfa, quando magari dovrebbe andare giù.

Come posso controllare anche questa casistica?

PS: quando controllo n + 1 e n + 2 lo faccio sempre nella stessa direzione, quindi controllare n + 3 non mi sarebbe di grosso aiuto.
1,236 views

4 Answers

Best answer
a
andreaamici (1740 points)
9 12 21
answered Dec 12, 2019 by andreaamici (1,740 points)
selected Dec 12, 2019 by Heretic
avevo lo stesso problema,l'ho risolto creando due funzioni uguali ma una che va prima a destra e poi giù e l'altra che va prima giù e poi a destra cosi returno due 'strade' e le confronto,se hanno la stessa lunghezza e sono entrambe giuste prendo la prima....però mi si pone un altro problema per una parola di due test(praticamente mi da tutta la sequenza giusta tranne una parola..)so qual'è il problema ma non riesco a risolverlo..
a
a.pietroluongo (11250 points)
15 38 131
commented Dec 12, 2019 by a.pietroluongo (11,250 points)
Ok ma non è corretto perché così sceglierai sempre la cella a destra (se va prima a dx ) o in basso  (se va prima in basso)
a
andreaamici (1740 points)
9 12 21
commented Dec 12, 2019 by andreaamici (1,740 points)
no naturalmente mettendo sempre il controllo se è giusta la lettera a destra o giù,semplicemente fai due starde parallele una che cerca prima a destra e poi giù e una che cerca giù e poi a destra,alla fine otterai quindi due percorsi e devi scegliere(di cui uno quasi sempre errato) e dovrai scegliere su quei due
a
a.pietroluongo (11250 points)
15 38 131
commented Dec 12, 2019 by a.pietroluongo (11,250 points)
edited Dec 12, 2019 by a.pietroluongo

Ad esempio in questa matrice:

ANTANTOER
LNONTRNIQ
EIOTOOIQO
SSUONLOIC

'ANTONIO' e' individuata da (0,3) e 'DDDGGG'

Il tuo programma restituirebbe -1 perché la funzione che cerca prima a dx trova ANTONIQ  , quella che cerca prima in basso ANTON
Ti trovi?

fc-dev (16450 points)
12 20 34
answered Dec 11, 2019 by fc-dev (16,450 points)
Potresti andare sia a destra, sia giù, chiamando la tua funzione 2 volte all'interno di se stessa.
Heretic (460 points)
3 5 7
commented Dec 12, 2019 by Heretic (460 points)
Ci provo. Devo ristrutturare tutta la funzione.
M
Michelangelo00 (1050 points)
2 3 8
answered Dec 11, 2019 by Michelangelo00 (1,050 points)
Il testo dell'HW dice, che se la lettera a destra è uguale a quella in basso, di prendere la lettera a destra, perché bisogna dare la precedenza alla lettera che viene prima lessicograficamente.
Heretic (460 points)
3 5 7
commented Dec 12, 2019 by Heretic (460 points)
Non è corretto, con questo ragionamento prova a superare il test esempio4, vedrai che avrai qualche problema.
edoardottt (8210 points)
1 3 37
commented Dec 12, 2019 by edoardottt (8,210 points)
La sequenza che viene prima in ordine lessicografico. Può capitare che scegli la cella destra ma da lì non trovi la parola che stai cercando.
M
Michelangelo00 (1050 points)
2 3 8
commented Dec 12, 2019 by Michelangelo00 (1,050 points)
Mi manca da superare solo il test 100x40, ma penso di aver capito come fare, un'ottima idea sarebbe quella di cercare le lettere di una parola se ci sono, all'interno della matrice, così da evitare di controllare se queste non ci sono
edoardottt (8210 points)
1 3 37
answered Dec 12, 2019 by edoardottt (8,210 points)
Io chiamo la ricorsione su entrambi. Poi in base a cosa restituiscono le due chiamate scelgo il risultato. Una delle due può essere None, oppure entrambe possono avere un risultato valido. In quest'ultimo caso devi restituire la prima in ordine lessicografico
Heretic (460 points)
3 5 7
commented Dec 12, 2019 by Heretic (460 points)

Ciao, e con questa metodica tu riesci a passare tutti quanti i test?

Ti spiego con un esempio:

se stai cercando la stringa 51567 nella matrice

475163477859

891588789631

476799448752

Dovresti prendere la strada GGD, non DD perché se segui la via lessicografica non trovi nessuna stringa, mentre in realtà esiste.

edoardottt (8210 points)
1 3 37
commented Dec 12, 2019 by edoardottt (8,210 points)
Sì. Ma non devi per forza fare una ricorsione unica. Puoi inserire il risultato delle due chiamate in due variabili e poi agire di conseguenza. Potrebbero essere entrambe vuote(None), una None e una no, oppure entrambi con risultati validi. Ed é qui che scegli quella con stringa che precede in ordine lessicografico. Spero di esserti stato d'aiuto.