Do you need any help?

Come impostare la ricorsione avendo usato un dizionario

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

Salve, ho provato a leggere e a rileggere i vari thread nel forum ma non riesco a capire che ragionamento usare per la mia ricorsione avendo utilizzando un dizionario.

Il mio dizionario è strutturato così: 

{('ROMA', 'la'): [('PARIGI', 'vendita'), ('CAIRO', 'furto'), ('MOSCA', 'mata')], 
    ('PARIGI', 'bocca'): [('BERLINO', 'diamanti'), ('CANCUN', 'cannoni')], 
    ('CAIRO', 'bocca'): [('MILANO', 'di')], 
    ('MOSCA', 'bocca'): [('PECHINO', 'hari')], ...

ecc.ecc.

Per trovare il primo segreto (vendita diamanti rubati stanotte ad anversa)  all'interno della mia ricorsione, scorro tutte le chiavi del dizionario finché non trovo (ROMA, la)
Poi uso un for per i valori di (ROMA, la) quindi prendo il primo valore e mi creo (PARIGI, bocca), rimuovo l'indizio 'bocca' e rimando la mia funzione con i dati aggiornati

Man mano la mia funzione mi crea il segreto in modo giusto, ma non so come andare avanti.
Il for che scorre i dati all'interno di (ROMA, la) giustamente, ogni volta che la funzione viene richiamata si riazzera quindi partirà sempre dal primo valore, ma oltre a questo, secondo quale logica la mia funzione dovrebbe andare avanti di valori?

Mi spiego meglio, nel primo caso la mia funzione deve prendere due volte PARIGIA, bocca, perché questa key ha due valori all'interno 

3 Answers

Best answer
twgever (14740 points)
7 26 105
answered Dec 13, 2020 by twgever (14,740 points)
selected Dec 16, 2020 by CiZ
Se lo deve prendere due volte Parigi, bocca, allora deve fare due chiamate diverse, una per ogni valore. Una volta finita la prima chiamata, ti salvi risultati e può fare la chiamata. La chiamata sarà dentro un ciclo for chiaramente
CiZ (3810 points)
4 11 20
commented Dec 16, 2020 by CiZ (3,810 points)
Ma facendo così non trovo l'ordine dei segreti, inoltre dovrei prendere ogni città facendo così mi carica nella chiamata ricorsiva solo l'ultima città del ciclo, nel caso di PAIRIGIbocca scorrerebbe BERLINO,diamanti, CANCUN, cannoni e quindi ora che il ciclo è finito i dati da caricare nella funzione sarebbero CANCUN, sollevò.

Io per capire al meglio come impostare la ricorsione ho creato una versione di codice per risolvere il file esempio.txt in modo iterativo, con tanti cicli for annidati per ogni indizio, quindi quando finisce l'ultimo ciclo for (quindi arriva al mio caso base possiamo dire, perché è l'ultimo indizio) giustamente ricomincia dal ciclo for che ancora non aveva finito di scorrere, quindi prende il secondo valore di PARIGI, bocca e ricomincia, finito questo ritorna al primo ciclo for che sarebbe ROMA,la e va al secondo valore (CANCUN, furto) e ripete il processo, trovandomi ogni volta che arrivo all'ultimo for (quello con l'ultimo indizio) tutta la frase. Il risultato è esatto, e cercando le analogie tra i cicli ho creato un ciclo esterno alla mia funzione ricorsiva che sarebbe il ciclo iniziale, e poi visto che tutti gli altri cicli erano al 99% identici ho creato una funzione ricorsiva adattando tutti quei cicli, per questo la richiamo nel return, però la funzione ricorsiva quando arriva al caso base finisce, non torna mica indietro a scorrere tutti i cicli.

Sono convinto di perdermi in qualche sciocchezza da poco
twgever (14740 points)
7 26 105
commented Dec 16, 2020 by twgever (14,740 points)
solo il return fuori dal ciclo, non la chiamata ricorsiva. Alla chiamata ricorsiva passerai la singola parola, al return passi tutti segreti che hai trovato, come ho scritto. quindi alla funzione ricorsiva non passi solo CANCUN,sollevò, ma prima BERLINO,sollevò, e poi dopo che è finita la ricorsione con BERLINO,sollevò, passerai CANCUN,sollevò

ancora non capisco cosa intendi con "ordine dei segreti".Se intendi l'ordine delle parole all'interno della frase, non credo che venga influenzato.

Non credo sia il massimo ragionare sulla ricorsione partendo dall'iterazioe, credo sia come tradurre dall'italiano all'inglese traducendo le singole parole da una frase italiana, poi vabbè, è una mia opinione non so quanto affidabile.

"però la funzione ricorsiva quando arriva al caso base finisce, non torna mica indietro a scorrere tutti i cicli." sempre perchè il return sta dentro al ciclo for. Deve assolutamente stare fuori.
CiZ (3810 points)
4 11 20
commented Dec 16, 2020 by CiZ (3,810 points)
Era da una settimana che cercavo di fare questo :( grazie mille per l'aiuto finalmente ho risolto ahaha
twgever (14740 points)
7 26 105
commented Dec 16, 2020 by twgever (14,740 points)
grazie al cielo :)

Quindi il problema era dove stava il return?
CiZ (3810 points)
4 11 20
commented Dec 16, 2020 by CiZ (3,810 points)

Si era solo quello ahaha ora teoricamente ho il problema che la prima frase è giusta ma nelle biforcazioni si sbaglia tipo:

vendita diamanti rubati stanotte ad anversa
vendita diamanti cannoni

Ma ci sono vari thread nel forum che sto cercando di capire per risolvere il mio problema, grazie ancora laugh

O
Oakandrew (6400 points)
4 26 63
answered Dec 13, 2020 by Oakandrew (6,400 points)
Salve.

Per curiosità, ma perche scorri tutte le chiavi del dizionario? Se tu avessi dizionario , potresti restituire subito il valore, o mi sbaglio?
CiZ (3810 points)
4 11 20
commented Dec 13, 2020 by CiZ (3,810 points)
Per trovare la città giusta, come valori ho le altre città dove deve andare Nikita raccolte in tuple con il loro relativo segreto.

Tu hai in mente qualcos'altro?
O
Oakandrew (6400 points)
4 26 63
commented Dec 13, 2020 by Oakandrew (6,400 points)
si, ma credo che debba iterare sulle citta successive associate alla tua chiave
CiZ (3810 points)
4 11 20
commented Dec 13, 2020 by CiZ (3,810 points)
Ho provato a spiegare cosa ho in mente nel commento del post più recente
O
Oakandrew (6400 points)
4 26 63
commented Dec 13, 2020 by Oakandrew (6,400 points)
non capisco perche devi tornare indietro
CiZ (3810 points)
4 11 20
commented Dec 14, 2020 by CiZ (3,810 points)
Per trovare gli altri segreti che usano gli stessi valori, per esempio: ROMAla per PARIGIbocca va chiamata due volte perché ci sono 2 PARIGIbocca
O
Oakandrew (6400 points)
4 26 63
commented Dec 14, 2020 by Oakandrew (6,400 points)
A questo punto o non ti serve ciclo for e tu ritorni indietro, o lasci il ciclo ma non ritorni
f
fabrizio_ancaiani (1790 points)
0 0 9
answered Dec 13, 2020 by fabrizio_ancaiani (1,790 points)
>scorro tutte le chiavi del dizionario finché non trovo (ROMA, la)

il dizionario è fatto apposta per non scorrere tutte le chiavi, ma accedere direttamente all'elemento ricercato (tramite la tecnica dell'hashing). Perciò si preleva l'elemento cercato indicandone la chiave e, se esso è una lista, ci si può fare un ciclo. Se ho ben capito la domanda, sennò chiedo scusa.
CiZ (3810 points)
4 11 20
commented Dec 13, 2020 by CiZ (3,810 points)
Ah perfetto, grave errore mio, ma il punto è come hai detto tu e gli altri colleghi, faccio un ciclo for per i valori del dizionario, che sono appunto le città dove deve andare però questo ciclo for deve andare avanti solo quando ho finito di trovare tutti i segreti di quella città

Prendi come esempio: ('ROMA', 'la'): [('PARIGI', 'vendita'), ('CAIRO', 'furto'), ('MOSCA', 'mata')]

Dovrò prendere due volte il primo valore perché in ('PARIGI', 'bocca'): [('BERLINO', 'diamanti'), ('CANCUN', 'cannoni') ci sono due valori. Mentre in (PARIGI, bocca) devo prendere ogni valore una sola volta perché dopo non mi serve più, quindi quando ho finito di ciclare i valori di questa key posso tornare 'indietro' e andare avanti con i valori della key (ROMA, la) e prendere (CAIRO, bocca) ecc.ecc.
È il ragionamento che vorrei applicare a tutto è questo, parti dal primo valore di tutte le keys, seguendo il percorso esatto, poi finché non hai ciclato tutte i valori delle keys successive a un'altra non puoi andare avanti con quella precendente.

Esempio: cicli tutti i valori di C e vai al valore successivo di B, ma mantieni il valore di A. Ripeti il passaggio, cicli tutti i valori di C con B[1], se B è finito vai al valore successivo di A e via dicendo così. Penso sia questo il metodo di trovare i segreti no?
f
fabrizio_ancaiani (1790 points)
0 0 9
commented Dec 13, 2020 by fabrizio_ancaiani (1,790 points)
Mi sa che c'è un equivoco di fondo. La soluzione non deve essere iterativa: è richiesto che il problema sia risolto ricorsivamente (cioè con una funzione che invoca se stessa), quindi si deve trovare una relazione induttiva che permetta di ramificare il problema idealmente come se fosse un albero. Il tornare "indietro" in realtà è semplicemente la fine di un ramo dell'albero ricorsivo. Dentro il ciclo bisogna scomporre il problema in sottoproblemi che convergono verso i casi base e che messi insieme danno la soluzione. Per il resto ci sono diversi spunti nel forum. Spero che questa risposta sia più utile di quella di prima!
CiZ (3810 points)
4 11 20
commented Dec 14, 2020 by CiZ (3,810 points)
No ma io infatti avevo basato l'esempio sopra in modo ricorsivo, come se fosse un albero appunto, calcola tutti i nodi e  quando sono finiti torna al nodo precedente, finito il nodo torna al nodo radice e via dicendo così per tutti i nodi. Ma ricorsivamente non capisco come impostarla perché trovo spiegazioni con le classi e io non ho usato le classi nel mio codice.
f
fabrizio_ancaiani (1790 points)
0 0 9
commented Dec 14, 2020 by fabrizio_ancaiani (1,790 points)

Ok. Per avere un ottimo indizio (appunto...) su come impostare la procedure ricorsiva, un consiglio potrebbe essere quello di vedere le lezioni sulla ricorsione del prof. Sterbini (sul wiki ci sono anche le sessioni iPython del 24/11), ci sono esempi ben spiegati usando le funzioni, senza classi. Per esempio la funzione "dimensioni_file". Da lì si capisce che in pratica si devono seguire sempre alcune regole basilari: si parte impostando per bene i casi base all'inizio, per uscire e evitare i loop infiniti, e poi mettere la chiamata ricorsiva con la riduzione del problema essendo sicuri che ci porterà al caso base. Bisogna stare attenti al "key error" nei dizionari e ai parametri della funzione (per esempio le liste vengono create appena l'interprete le "vede", e quindi potrebbe essere che ci si ritrova a lavorare sempre sulla stessa lista, anche se no lo si voleva).