Problema HW4bis esercizio 1

B
Bagaglini (900 points)
1 10 13
asked Jan 18, 2019 in HW4bis by Bagaglini (900 points)
edited Jan 18, 2019 by Bagaglini

Allora, ho appena terminato l'esercizio 1 dell'HW4bis, sulla mia macchina ne passa 7 su 11 perché gli altri 4 a quanto ho capito fanno troppe ricorsioni e quindi si bloccano perché raggiungono il limite massimo consentito. Il problema sta invece nel fatto che quando lo carico sulla VM non ne passa neanche uno e non so perché, qualcuno ha lo stesso problema? Sinceramente non so..

L'errore dei 4 test non passati è sempre lo stesso:
'maximum recursion depth exceeded in comparison'

Mentre la scritta dopo aver lanciato il test è la seguente:
'Ran 11 tests in 0.039s

FAILED (errors=4)
11 test passed, 0 tests failed'

1 Answer

Best answer
_andrea_ (45670 points)
2 40 297
answered Jan 18, 2019 by _andrea_ (45,670 points)
selected Jan 18, 2019 by Bagaglini
ti dovrebbe dire in che funzione ricorsiva eccedi di ricorsioni
B
Bagaglini (900 points)
1 10 13
commented Jan 18, 2019 by Bagaglini (900 points)
Si me lo dice, sono il 7, 8, 9 e 10
_andrea_ (45670 points)
2 40 297
commented Jan 18, 2019 by _andrea_ (45,670 points)
no dico proprio qual è la funzione ricorsiva che supera il limite. senza quella non ti si può aiutare
B
Bagaglini (900 points)
1 10 13
commented Jan 18, 2019 by Bagaglini (900 points)

Ah, all'interno del programma è la funzione combo, è l'unica ricorsiva e quella da dove estrapolo la maggior parte dei dati che servono per i test.

_andrea_ (45670 points)
2 40 297
commented Jan 18, 2019 by _andrea_ (45,670 points)
Che cosa fai di preciso? Usi le classi? Hai pensato di dividerla in funzioni diverse? Anche perché sennò viene difficile capire quale parte ti manda troppo oltre il limite se fai tutto insieme
B
Bagaglini (900 points)
1 10 13
commented Jan 18, 2019 by Bagaglini (900 points)

Allora il programma non ha solo quella funzione, ma da lì viene gran parte dei dati che poi utilizzo per 'risolvere' il test in corso, alla funzione combo passo principalmente la lunghezza della stringa iniziale -1, una variabile booleana per vedere i vincitori successivamente, la stringa iniziale e altre variabili o liste di supporto che servono per calcolare altezza e cose simili.

Tendo a precisare che dentro la funzione ricorsiva c'è un ciclo while che continua fino a che la x non è uguale alla lunghezza della stringa corrente -1, questa cosa sarà spiegata più avanti.

La funzione combo è una funzione che, partendo dalla stringa originale, scende man mano facendo tutte le possibili 'combinazioni' e, una volta arrivata al capolinea, ritorna su facendo poi tutte le altre possibili combinazioni, per tornare su semplicemente rende la stringa corrente uguale alla penultima stringa che ho trovato, mentre per andare avanti negli indici di tutte le combinazioni la situazione è la seguente, quando troviamo una nuova combinazione e quindi 'scendiamo' si aggiunge ad una lista di indici il numero 0 , mentre quando 'risaliamo' la situazione cambia perché prendiamo il penultimo indice che abbiamo trovato e gli aggiungiamo 1, la poi diventerà uguale a questo penultimo indice, ciò porta così a non bloccarsi in un ciclo infinito dove la funzione farebbe su e giù sempre nella stessa combinazione. Nel ciclo while si ha la 'ciccia' di questa funzione, ché molto piccola a vederla, una volta controllato i criteri per fare a - b, lo fa e genera la nuova stringa, qui succede la cosa più importante, si aggiunge ad una lista creata in precedenza una tupla formata da:

( padre, figlio, vincitore, altezza )

Da questa lista di tuple poi estrapolo tutto ciò che mi serve tramite varie altre funzioni.. bene o male questo è tutto.

_andrea_ (45670 points)
2 40 297
commented Jan 18, 2019 by _andrea_ (45,670 points)
prova invece a calcolare altezza e vincitori in seguito, prova ad usare la classe Albero che è definita anche in altri esercizi. la funzione potresti farla così: prende in ingresso la lista di numeri, se non ci sono mosse da fare ritorna l'oggetto nodo che rappresenta quella configurazione e gli mette come figli una lista vuota. se invece ci sono mosse da fare crea il nodo sempre con quel nome e aggiunge ai suoi figli i nodi che si ottengono da ogni mossa possibile. quindi il while lo fai lo stesso, ma dentro fai solo l'aggiunta dei nodi che si formano per ogni mossa. questi nodi ovviamente si formano chiamando ricorsivamente la funzione. alla fine ritorni il nodo principale che hai creato. così la funzione iniziale ti torna un nodo, che sarà la radice, i cui figli saranno i nodi che si ottengono facendo tutte le mosse dalla configurazione iniziale. quei figli avranno anche loro dei figli che si ottengono facendo ogni mossa a partire dalla loro configurazione. così intanto risolvi il maximum recursion depth (in teoria, se la fai bene). poi potresti aggiungere altre funzioni, una che ti calcola l'altezza massima e una la minima. a questo punto sapresti che se l'altezza massima è un numero dispari, la partita è stata vinta dallo stesso giocatore che ha iniziato, altrimenti è stata vinta dal secondo. allo stesso modo anche se l'altezza minima è dispari, avrà vinto il primo altrimenti il secondo. poi un'altra funzione che calcola il numero di partite percorrendo tutto l'albero. così non dovresti mai andare troppo a fondo nella ricorsione
B
Bagaglini (900 points)
1 10 13
commented Jan 18, 2019 by Bagaglini (900 points)
Grazie mille del consiglio, ci proverò allora :')