[python] Albero binario in Python

Riporto qui un classico dell’informatica di base: la realizzazione di un albero binario per l’ordinamento.

Quello dell’albero binario è un algoritmo che consente di ordinare dei valori in base al criterio di inserimento e successivamente di lettura.

Per far capire meglio il procedimento vediamo anzitutto come funziona.

Immaginiamo di avere la sequenza di numeri 3, 4, 1, 7, 6, 5, 8, 11, 9. L’algoritmo prevede la creazione di una struttura ad albero, composta di nodi, dove ogni nodo contiene un valore e un ramo di sinistra e uno di destra, che puntano rispettivamente al valore minore e maggiore, rispetto al valore nel nodo. La creazione dell’albero procederà quindi come nel video soprastante.

La lettura avverrà invece a partire dal primo nodo, procedendo anzitutto sul nodo di sinistra, poi stampando il valore del nodo corrente e poi procedendo sul nodo di destra. Come illustrato nella seguente animazione:

 

Procedendo in questo modo otterremo tutti i valori ordinati.

Questo algoritmo può essere scritto in Python nel modo seguente:

 

Vedi articolo

[python] Semplice simulazione dell’espansione di un contagio tipo COVID19 con PyGame e OpenGL

Ripropongo un esercizio in Python simile a quello svolto in JavaScript in Simulazione sull’espansione del contagio da Coronavirus (COVID-19)

Questa volta utilizzeremo PyGame e OpenGL per costruire la simulazione, similmente a quanto fatto nel precedente articolo. Il programma è stato svolto in Python 3.9.

Il risultato produrrà qualcosa di simile a questo:

Vedi articolo

[python] Calcolare la dimensione delle cartelle sul computer e trovare quelle più grandi

Ecco un veloce script in python per ricavare la dimensione delle cartelle sul computer (vale sia per Windows che Mac e Linux) e stampare l’elenco ordinato (dalla più grande alla più piccola) di tutte quelle trovate sopra una certa dimensione.

A me è stato molto utile per svuotare C: che si era riempito di cartelle temporanee, di cache e cose totalmente dimenticate.

Lo script è stato scritto per Python 3.9

L’ouput finale genera qualcosa di simile (nel mio caso vedo che le macchine virtuali di Android occupano da sole 24GB!)

Faccio notare che nella stampa finale ho ridotto l’elenco a cartelle maggiori di 200MB.

Vedi articolo

[python] Semplice esercizio per creare il gioco del campo minato in Python (da console)

In questo semplice esercizio vogliamo riprodurre in Python, in modo un po’ rudimentale, quello che era il gioco del campo minato (poi campo fiorito) per Windows.

Quello che vogliamo ottenere assomiglierà a questo all’avvio:

Mentre alla vittoria otterremo qualcosa di simile:

Il gioco sarà costruito su una griglia 10×10, di 100 caselle in totale, che faremo selezionare all’utente con un numero da 1 a 100.

Anzitutto costruiamo la griglia fatta di oggetti di tipo Casella, definiti nel modo seguente:

Per costruire il campo useremo la funzione random.randint() per distribuire le mine in modo casuale, nel modo seguente:

In questo caso la variabile difficolta viene usata per bilanciare la distribuzione casuale. Se impostiamo difficolta su 2, avremo in media il 50% di caselle con mine (1/2). Se impostiamo difficolta su 10 allora avremo circa il 10% di mine (1/10), ecc.

Fatto questo dobbiamo costruire due metodi che si occuperanno rispettivamente di conteggiare le mine e aprire le celle. All’interno di entrambi i metodi useremo due cicli for ricordandoci che rispetto alla posizione attuale quelle intorno partiranno da [-1,-1] fino a [1,1]

Riporto di seguito il codice, commentato, dell’intero giochino realizzato a partire da queste idee:

 

Vedi articolo