[python] Esercizio su funzioni ricorsive e calcolo tratte dei treni

Facciamo un piccolo programma in Python che ci permetta di gestire le distanze da percorrere tra due stazioni, di partenza ed arrivo.

Abbiamo le seguenti tratte:

Stazione A Stazione B Distanza
Firenze Bologna 100km
Firenze Roma 250km
Roma Napoli 200km
Bologna Milano 220km
Bologna Venezia 150km

Ogni tratta è percorribile sia in andata che in ritorno. Quello che vogliamo è che il programma ci permetta di inserire due città e calcolare la distanza minima da percorrere e le stazioni da attraversare.

Anzitutto vediamo come sono disposti i nodi dell’intero percorso:

Notiamo che in questa configurazione elementare solo Bologna ha 3 rami, mentre tutte le altre città hanno solo 2 rami ciascuna.

Potremmo affrontare l’esercizio lavorando sui nodi oppure sulle tratte. In questa soluzione lavorerò sulle tratte.

Cominciamo quindi creando anzitutto una classe che ci permetta di descrivere ogni tratta come abbiamo visto nel mandato dell’esercizio.

In questo modo dichiariamo 3 variabili private per registrare le due città della tratta e la rispettiva distanza.

Adesso registriamo tutte le tratte in una lista, nel modo seguente:

Ora cominciamo a pensare all’algoritmo che potrebbe permetterci di calcolare il percorso.

Immaginiamo anzitutto la soluzione più semplice, dove io penso di andare da Firenze a Napoli. Su questa tratta non ci sono diramazione e sostanzialmente il percorso che dovrà venire fuori sarà Firenze – Roma – Napoli.

Fase 1:

Faccio un ciclo su ogni elemento della lista tratte[] e cerco anzitutto dove è presente la città di partenza. Siccome la città può essere sia in A che in B, per ogni oggetto Tratta dovrò implementare un metodo all’interno dell’oggetto stesso che mi permetta di valutare se la città sia presente in modo comodo. Implementiamo quindi la classe nel modo seguente:

Il metodo presente(citta) mi permette di valutare se la città sia presente nella tratta.

Fase 2:

Se trovo la città di partenza su una tratta allora controllo se l’altra città della tratta sia quella di arrivo. Allo stesso tempo registro la città di partenza all’interno di una lista percorso[] in modo da metterla come partenza del percorso complessivo.

Quindi se l’altra città è quella di arrivo posso chiudere il percorso, altrimenti passo il controllo sull’altra città.

Quando mi trovo nella riga 10 capisco anche che ho trovato la fine del percorso, quindi posso salvare l’intero percorso da qualche parte. Siccome potrei avere molteplici percorsi possibili decido di salvare il percorso in una lista globale chiamata percorsi = []

Modifichiamo quindi il codice nel modo seguente:

Adesso analizziamo due aspetti dell’ultima istruzione, quella dove richiamo la funzione.

Anzitutto voglio tirare fuori dalla tratta l’altra città, rispetto alla città di partenza. Per farlo implemento la classe principale nel modo seguente:

In questo modo quando mi trovo per esempio sulla tratta Firenze – Roma posso passare all’oggetto tratta Firenze, che conosco essendo il punto di partenza e chiedergli di darmi l’altra città della tratta, in questo caso Roma.

Il secondo aspetto che voglio evidenziare è che passo la lista percorso[] alla funzione medesima in partenza dall’altra città, per farlo utilizzo l’istruzione []+percorso, in caso contrario percorso passerebbe per riferimento e qualora fosse passato su più rami verrebbe elaborato contemporaneamente da più rami. Io invece voglio che resti un oggetto singolo e lineare per ogni percorso.

Arrivati a questo punto del codice la situazione è la seguente:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. LOOP INFINITO!

Fase 3:

Devo evitare il loop infinito in cui il percorso possa tornare indietro. Per farlo modifico la mia funzione aggiungendo il seguente controllo all’inizio:

In questo modo controllo che il punto di partenza DA non sia già presente nel percorso[].

Adesso ricomincio a controllare il mio algoritmo da capo:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  11. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  12. Torno al punto 9
  13. In posizione 3 trovo Bologna – Milano dentro tratte[] dove appartiene il mio DA
  14. Questo pezzo di codice adesso si ripete uguale a quello tra 10 e 12 fino a chiudersi su Milano e Venezia che terminano il percorso
  15. Trono al punto 3
  16. In posizione 1 trovo la tratta Firenze – Roma a cui DA (Firenze) appartiene
  17. Controllo se A (Napoli) appartiene alla tratta
  18. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Roma e la passo come nuovo DA alla funzione medesima
  19. La funzione ricomincia e aggiungendo DA (Roma) al percorso[]
  20. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  21. Trovo che DA nella posizione 1 sulla tratta Firenze – Roma
  22. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  23. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  24. Torno al punto 20
  25. Trovo che DA nella posizione 2 sulla tratta Roma – Napoli
  26. Controllo se A (Napoli) appartiene alla tratta
  27. Napoli appartiene alla tratta nel pezzo di codice if t.presente(a)
  28. A questo punto aggiungo A (Napoli) alla fine di percorso[]
  29. Aggiungo il percorso[] ai percorsi[] con l’istruzione percorsi.append(percorso)

Fase 4:

Apporto ancora un paio di correzioni tecniche alla mia funzione per evitare inutili duplicati.

A questo punto posso scrivere la parte principale del mio programma con:

Per stampare il percorso faccio una join su ogni percorso che trovo dentro a percorsi[]

Fase 5:

Aggiungo soltanto un metodo per calcolare le distanze. Potrei farlo anche in modi più ottimizzato, ma per le finalità di questo esercizio ci accontentiamo di percorrere tutte le stazioni, esclusa l’ultima, e di calcolare la distanza tra la stazione corrente e la successiva sommandole tutte insieme.

A tale proposito aggiunto un metodo che mi permetta di valutare se 2 città appartengono entrambe alla tratta ed un getter per la distanza.

La funzione quindi sarà:

Fatto tutto questo posso completare il mio programma nella sua versione finale nel modo seguente:

Se volessimo complicare un po’ lo schema potremmo aggiungere altre tratte:

Ed ottenere una versione finale del programma in questo modo:

Il nostro nuovo programma genererà un output come questo:

Rispondi

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.