Come impostare la ricorsione avendo usato un dizionario

CiZ (3810 points)
4 12 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 (15190 points)
7 27 105
answered Dec 13, 2020 by twgever (15,190 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 12 20
commented Dec 13, 2020 by CiZ (3,810 points)
Non credo di aver capito bene, perché da come ho capito io facendo così non saprei farlo per tutti i casi possibili di chiavi che hanno più valori.

Non so come calcolare tutti i percorsi possibili, tipo con (PARIGI, bocca) li calcolo tutti, poi con CAIRO,bocca pure
twgever (15190 points)
7 27 105
commented Dec 13, 2020 by twgever (15,190 points)
perchè devi scorrere tutti i segreti di cairobocca? se la città iniziale è parigi e l'indizio è bocca, cairobocca non ti servirà mai
CiZ (3810 points)
4 12 20
commented Dec 14, 2020 by CiZ (3,810 points)
Nono era per dire, il punto è che non so come far scorrere tutti i valori della key PARIGI, bocca
twgever (15190 points)
7 27 105
commented Dec 14, 2020 by twgever (15,190 points)
for elemento in valore

non ti va bene così?
twgever (15190 points)
7 27 105
commented Dec 14, 2020 by twgever (15,190 points)
Mi sembra molto confuso il tuo ragionamento. Se ti costruisci ROMAla, l'hai costruito con la città iniziale e con il primo indizio, allora per chiamare i valori basta che fai diz[ROMAla], e questa sarà la lista di valori associati a ROMAla. una volta fatto questo, per ogni elemento di questa lista, dovrai richiamare la funzione (teoricamente) costruendo la parola successiva con la città che hai trovato in quell'informazione. Se la seconda città del primo elemento della lista diz[ROMAla] è parigi, allora la prossima parola sarà PARIGIbocca, e nella chiamata successiva ti scorrerà tutti gli elementi dentro diz[PARIGIbocca]. una volta uscito dalla chiamata che scorre diz[PARIGIbocca], visto che la chiamata sta dentro un for, la prossima parola sarà CAIRObocca, e la prossima chiamata di funzione scorrerà diz[CAIRObocca] ecc.

(mi sono confuso effettivamente, CAIRObocca serve, chiedo perdono)
CiZ (3810 points)
4 12 20
commented Dec 14, 2020 by CiZ (3,810 points)
Sì ma facendo così non posso trovare trovare l'ordine dei segreti, ma tutti i segreti in disordine, scusa se ti domando, ma tu alla tua funzione ricorsiva hai usato per trovare tutti i segreti un'altra funzione no? Con la funzione ricorsiva trovati una singola parola del segreto, o tutta la frase? Perché io con la mia vecchia funzione ricorsiva mi calcolavo tutte le frasi dei segreti scorrendo ogni volta il dizionario però eliminavo le istruzioni che trovavo ogni volta e quindi questo non funzionava per altri test.
twgever (15190 points)
7 27 105
commented Dec 14, 2020 by twgever (15,190 points)
sì, sono riuscito a costruirmi un dizionario che mi associa ad ogni coppia, le possibili città + segreto, proprio come l'hai costruito te. Poi la funzione ricorsiva mi aggiunge le parole, non la frase. ogni chiamata trova tutte le possibili frasi con quell'inizio però.

L'ordine dei segreti nell'insieme che devi restituire non è importante, la cosa importante è che le frasi siano ordinate. E se fai in questa maniera, le frasi saranno ordinate, perchè vai di città in città, e mano mano aggiungi le parole.
CiZ (3810 points)
4 12 20
commented Dec 15, 2020 by CiZ (3,810 points)
Per ogni chiamata intendi dire ogni volta che la funzione richiama se stessa? Quindi tu chiami la prima volta la tua funzione con ROMAlaPARIGIvendita, fa la ricorsione e ti trova la prima frase, poi continua a chiamarsi? Finché per esempio  il valore non è nullo?
twgever (15190 points)
7 27 105
commented Dec 15, 2020 by twgever (15,190 points)
Esattamente, e poi visto che la chiamata ricorsiva sta dentro il ciclo, passa direttamente alla parola successiva quando necessario.
CiZ (3810 points)
4 12 20
commented Dec 15, 2020 by CiZ (3,810 points)
Ma come fa a capire quando è necessario?
twgever (15190 points)
7 27 105
commented Dec 15, 2020 by twgever (15,190 points)
quando finiscono le chiamate ricorsive dentro al ciclo, finiscono le istruzioni dentro all'iterazione e passa alla parola successiva
CiZ (3810 points)
4 12 20
commented Dec 16, 2020 by CiZ (3,810 points)
Ed era quello che avevo in mente, però la mia funzione ricorsiva non scorre tutto il ciclo,
All'interno della mia funzione ricorsiva, se la lunghezza della lista segreti è uguale alla lunghezza della lista indizi allora caso base

Sennò
ho un for per tutti i valori della key (la partenza la calcolo fuori dalla ricorsiva ma forse sbaglio)
calcolo quello che devo calcolare
Quindi aggiorno i valori per cui devo cercare i segreti, cioè mi calcolo la nuova città e il nuovo indizio e richiamo la funzione ricorsiva.
Quando richiamo la funzione il return è dentro al ciclo for
twgever (15190 points)
7 27 105
commented Dec 16, 2020 by twgever (15,190 points)
forse il problema è perchè il return sta dentro al ciclo for. Puoi provare a non fare return del singolo segreto nei casi non base, ma a fare return, piuttosto, di tutti i segreti che ha trovato il ciclo. è un po' complessa forse come idea, ma una volta realizzata anche solo parzialmente, dovrebbe risolvere il problema.
CiZ (3810 points)
4 12 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 (15190 points)
7 27 105
commented Dec 16, 2020 by twgever (15,190 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 12 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 (15190 points)
7 27 105
commented Dec 16, 2020 by twgever (15,190 points)
grazie al cielo :)

Quindi il problema era dove stava il return?
CiZ (3810 points)
4 12 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 12 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 12 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 12 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 12 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 12 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).