Do you need any help?

Consigli su come trovare i segreti

CiZ (3810 points)
4 11 20
asked Dec 11, 2020 in HW8 obbligatorio by CiZ (3,810 points)

Salve, sto cercando di creare la mia funzione ricorsiva per la ricerca dei segreti ma incappo in un grosso problema: 
Come faccio a gestire: ROMAlaPARIGIvendita ---> PARIGIboccaBERLINOdiamanti
                                                                             --->PARIGIboccaCANCUNcannoni

Dovrei calcolare tutte le possibili combinazioni?  E come posso fare senza sapere effettivamente il percorso che devo percorrere?
Ho riordinato tutte le istruzioni in una lista di tuple [(ROMA, la, PARIGI, vendita), (ROMA, la, CAIRO, furto )]

Accetto qualsiasi consiglio  :(

EDIT: come caso base uso un contatore che mi dice a quale indizio sono, quando il contatore == numero indizi:  allora finisce la ricorsione

594 views

6 Answers

Fabioerpini (7970 points)
5 9 27
answered Dec 11, 2020 by Fabioerpini (7,970 points)
Mi aggrego anche io nella ricerca di qualche consiglio...

P.S.: non sto utilizzando classi (al momento)
g
gullisa (1170 points)
7 24 31
answered Dec 11, 2020 by gullisa (1,170 points)
Ciao, premetto che anche io sto risolvendo la ricorsione e mi accodo alla tua richiesta di consigli.

Allora io ho creato un dizionario che ha come chiavi città+indizio ('ROMAla') e per valori tutte le coppie destinazione+segreto (['PARIGI','vendita']).

Quindi costruisco la stringa del segreto cercando la chiave nel dizionario e poi per tutti i valori della chiave riapplico la logica della ricorsione con la nuova città ed utilizzando il nuovo indizio (anche io come te uso un contatore che ad ogni passata mi restringe la lista degli indizi): quindi ricerco la nuova città+indizio e così via...

Il segreto lo costruisco ad ogni chiamata passando la stringa creata fino all'istante precedente e aggiungendo il nuovo segreto.

Tuttavia, così facendo, sto riscontrando il problema che la funzione mi ritorna tutti i segreti costruiti ad ogni passata (compreso anche quello finale...) cosa che sto cercando di evitare, ma con difficoltà.
CiZ (3810 points)
4 11 20
commented Dec 11, 2020 by CiZ (3,810 points)
Ma controlli tutte le possibilità per coprirei vari casi?
g
gullisa (1170 points)
7 24 31
commented Dec 11, 2020 by gullisa (1,170 points)
In che senso? Ad ogni chiamata restringo i clues. Alla fine ottengo una lista di coppie tipo [('vendita','MILANO'), ('vendita diamanti', ROMA), ('vendita diamanti rubati', 'CANCUN') etc...]
CiZ (3810 points)
4 11 20
commented Dec 11, 2020 by CiZ (3,810 points)
Ah tu usi la ricorsione per creare il dizionario?
g
gullisa (1170 points)
7 24 31
commented Dec 11, 2020 by gullisa (1,170 points)
Sì, mi trovo più comodo e mi sembra più intuitivo usando un dizionario
g
giacomo_venturini (6680 points)
2 5 39
answered Dec 11, 2020 by giacomo_venturini (6,680 points)
Conviene utilizzare i primi due valori come parametri di ricerca, mentre i secondi due servono per continuare o interrompere la ricerca, averli tutti allo stesso livello (come per esempio in una tupla), comporta la necessità di effettuare operazioni più complesse per passare da una coppia città-indizio all'altra.
CiZ (3810 points)
4 11 20
commented Dec 11, 2020 by CiZ (3,810 points)

Io controllo solo che istruzione[:2] sia uguale a un parametro che ricorsivamente cambio, questo parametro è composto dalla seconda città all'interno dell'istruzione che sto studiando, e dall' indizio successivo a quello controllato in precedenza.

[ROMA, la, PARIGI, vendita] ---> [ROMA, la]
E da qui creo [PARIGI, bocca]

Quindi ricomincio a controllare tutte le istruzioni finché non trovo quella che mi interessa 

g
giacomo_venturini (6680 points)
2 5 39
commented Dec 11, 2020 by giacomo_venturini (6,680 points)
Ti complica un po' la vita quando hai più istruzioni che partono dalla stessa coppia città-indizio

Io ho messo in un dizionario con chiave (città, indizio) le liste di coppie (prossima città, segreto) corrispondenti

Così posso accedervi e scorrerle facilmente
CiZ (3810 points)
4 11 20
commented Dec 11, 2020 by CiZ (3,810 points)
Quindi diciamo che facendo così il percorso lo sai già in linea di massima, fai la ricorsione solo per unire i segreti? Perché un'idea del genere ce l'avevo ma non ero sicuro come implementarla.
R
Raffaele (3850 points)
10 23 48
answered Dec 11, 2020 by Raffaele (3,850 points)
Ho lo stesso problema
AdSum (16290 points)
9 20 134
answered Dec 11, 2020 by AdSum (16,290 points)
Buonasera, non sono sicuro di aver capito il problema. Tu sai benissimo quali percorsi devi percorrere. Il percorso ti viene dato dall'accoppiatta (citta,indizio) che è univocamente collegata ad una lista di città (che può avere n elementi con n>=0).
Quindi tu non devi far altro che scorrere queste associazioni fin quando non scorri tutti gli indizi o trovi una pista falsa (non esiste un'associazione lunga quanto gli indizi). Nell'ultimo caso abbandoni quella specifica strada.

Se non ho centrato il problema chiedo gentilmente delucidazioni riguardo il problema, perchè ho l'impressione che non è in questo che ti stai incartando.
R
Raffaele (3850 points)
10 23 48
commented Dec 11, 2020 by Raffaele (3,850 points)

Il problema è che durante la ricorsione si perdono N volte i nodi che hanno N-1 figli.

Nel caso di vendita che ha come figli "cannone" e "diamanti", ergo vendita ha 2 figli, perdi una volta la parola vendita.

Per cui ottiene una cosa simile a:

vendita diamanti rubati stanotte ad anversa 

(parte mancante) cannoni mercato nero del cairo

furto di diamanti a buckingham palace

mata hari ha sedotto ambasciatore zambia

g
giacomo_venturini (6680 points)
2 5 39
commented Dec 12, 2020 by giacomo_venturini (6,680 points)
puoi risolvere passando delle copie delle sequenze in modo da non sovrascrivere eventuali informazioni usate in altri percorsi
AdSum (16290 points)
9 20 134
commented Dec 12, 2020 by AdSum (16,290 points)
Avevo questo problema anche io all'inizio. Devo calcolare i casi in cui effettivamente hai più figli, quindi ottieni più risultati. Non puoi applicare i controlli e le varie righe una sola volta, ma N volte a seconda degli N figli
CiZ (3810 points)
4 11 20
commented Dec 12, 2020 by CiZ (3,810 points)
Quindi così si va a creare una struttura ad albero? Perché io pensavo a una permutazione, ma non avevo idea su come farla senza conoscere i vari percorsi. Quindi pensavo di calcolarmi i possibili percorsi cioè [ROMAla] ---> [PARIIGbocca],[PARIGIbocca]---> e via dicendo, ma non ho idea su come calcolare la permutazione
R
Raffaele (3850 points)
10 23 48
commented Dec 12, 2020 by Raffaele (3,850 points)

@AdSum puoi spiegarti meglio? Grazie in anticipo. 

AdSum (16290 points)
9 20 134
commented Dec 14, 2020 by AdSum (16,290 points)

@CiZ noi stiamo effettivamente lavorando su una struttura ad albero.

AdSum (16290 points)
9 20 134
commented Dec 14, 2020 by AdSum (16,290 points)

@Raffaele allora, prendiamo ad esempio un caso in cui il nodo A ha tre figli, B,C e D. Alla fine della festa tu non devi avere A che si applica a tutto il gruppo di figli insieme, quindi A(B,C,D), ma devi applicarlo ad ogni suo figlio, quindi AB, AC, AD.
Nel primo caso ti esce qualcosa del tipo (VENDITA)([diamanti rubati stanotte...][cannoni mercato...]) e quindi ti risulta solo al primo. Nel secondo caso ti risulta giusto.

CiZ (3810 points)
4 11 20
commented Dec 14, 2020 by CiZ (3,810 points)

@AdSum ora è quello che sto cercando di implementare, ma proprio non so come fare, anche perché online trovo solo esempi con le classi e io non ho usato le classi per il mio codice.

nick98 (700 points)
3 11 14
answered Dec 12, 2020 by nick98 (700 points)

io anche avevo questo problema ho risolto con una stringa che teneva conto sempre dei segreti a cui ero arrivato.

mi spiego, se sono arrivato a PARIGIpasto allora sono al caso base perchè non ho più figli e la mia stringa sarà ' vendita diamanti rubati stanotte ad anversa, ' che poi appenderò ad una lista assieme alla città in cui ho trovato il segreto, man mano che torno indietro sullo stack ricorsivo elimino l ultima parola in modo che quando torno a ROMAlaPARIGI e sto per andare al secondo ramo ovvero PARIGIboccaCANCUNcannoni la mia stringa manterrà "vendita" e quindi potrà completare il secondo segreto 'vendita cannoni mercato nero del cairo' . E' più facile di quello che pensi non fare cose astruse

R
Raffaele (3850 points)
10 23 48
commented Dec 12, 2020 by Raffaele (3,850 points)
Facendo come dici tu io mi ritrovo senza 'vendita'.
nick98 (700 points)
3 11 14
commented Dec 12, 2020 by nick98 (700 points)
probabilmente elimini  l ultima parola anche nel caso base.

tu devi eliminare l ultima parola solo quando ritorni dallo stack ricorsivo. nel caso base non devi elminare l ultima parola.
CiZ (3810 points)
4 11 20
commented Dec 12, 2020 by CiZ (3,810 points)
Ho capito molto bene il tuo consiglio, e mi sembra davvero utile per come ho impostato il mio programma, mi manca solo capire cosa intendi per tornare indietro nello stack ricorsivo, ho seguito le lezioni sulla ricorsione, e ho letto anche qualcosa online ma ancora non capisco appunto questa importante parte. Sicuramente avrò saltato qualche cosa dalle lezioni, mi consigli di rivedere qualcosa? O sai dove posso leggere qualcosa online?
nick98 (700 points)
3 11 14
commented Dec 13, 2020 by nick98 (700 points)
edited Dec 13, 2020 by nick98
per tornare indietro nello stack, intendo quando torni alla chiamata ricorsiva precedente seguendo la regola last in first out, per intenderci quando tu sei al caso base hai appena aggiunto l ultima chiamata allo stack prima di cominciare a "consumare lo stack". ma comunque è una cosa che avviene in automatico con la ricorsione.
CiZ (3810 points)
4 11 20
commented Dec 13, 2020 by CiZ (3,810 points)
Quindi tu parti nella funziona ricorsiva con vendita nella tua stringa giusto? Il mio problema è capire come scorrere tutti i valori della chiave del dizionario, ma penso che ora proverò a farlo nella ricorsione, e quando mi da valore None vado avanti, e penso di doverlo fare con un'altra funzione esterna