python 3.9 Archivi - Petar Karan

8 Maggio 2021 Nessun commento

[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:

class Nodo:
    def __init__(s,v = None):
        s.valore = v
        s.sx = s.dx = None

def aggiungi(nodo,v):
    if nodo.valore is None:
        nodo.valore = v
        nodo.sx = Nodo()
        nodo.dx = Nodo()
    elif v < nodo.valore:
        aggiungi(nodo.sx,v)
    else:
        aggiungi(nodo.dx,v)

def stampa(nodo):
    if nodo.valore is not None:
        stampa(nodo.sx)
        print(nodo.valore)
        stampa(nodo.dx)

radice = Nodo()


numeri = [3,2,7,4,6,5,9,10]
for n in numeri:
    aggiungi(radice,n)

stampa(radice)

class Nodo:

def __init__(s,v = None):

s.valore = v

s.sx = s.dx = None

def aggiungi(nodo,v):

if nodo.valore is None:

nodo.valore = v

nodo.sx = Nodo()

nodo.dx = Nodo()

elif v < nodo.valore:

aggiungi(nodo.sx,v)

else:

aggiungi(nodo.dx,v)

def stampa(nodo):

if nodo.valore is not None:

stampa(nodo.sx)

print(nodo.valore)

stampa(nodo.dx)

radice = Nodo()

numeri = [3,2,7,4,6,5,9,10]

for n in numeri:

aggiungi(radice,n)

stampa(radice)

Vedi articolo

23 Aprile 2021 Nessun commento

[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.

import pygame as pg
from pygame.locals import *

from OpenGL.GL import *
from OpenGL.GLU import *

import math
from copy import copy
import random

import matplotlib.pyplot as plt

dati = [
    {"infetto":False,"velocita":10,"numero":200},
    {"infetto":False,"velocita":0,"numero":10},
    {"infetto":True,"velocita":10,"numero":1}
    ]

class Simulazione:

    def __init__(s, w = 1200, h = 800, dati = []):

        s.posizioni = []

        s.ratio = w / h
        s.w = w
        s.h = h

        pg.init()
        schermo = (w,h)
        pg.display.set_mode(schermo, DOUBLEBUF|OPENGL)

        # in movimento
        for d in dati:
            for i in range(d["numero"]):
                x = random.randint(-w/2+10,w/2-10)
                y = random.randint(-h/2+10,h/2-10)
                a = 2*math.pi*random.random()
                s.posizioni.append(Punto(x,y,d["velocita"],a,infetto=d["infetto"]))

        infezioni = []

        while True:
            for event in pg.event.get():
                if event.type == pg.QUIT:
                    pg.quit()
                    quit()
        
            glClearColor(1.0, 1.0, 1.0, 1.0)
            glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)

            tot_infetti = 0

            for p in s.posizioni:
                p.muovi()
                s.disegnaPunto(p.x,p.y,raggio=p.raggio,colore=p.colore)
                if p.infetto and not p.guarito: tot_infetti += 1

            infezioni.append(tot_infetti)

            s.controllaUrti()

            pg.display.flip()
            pg.time.wait(10)

            if tot_infetti == 0:
                pg.quit()
                break

        plt.plot(range(len(infezioni)),infezioni)
        plt.title("curva contagi")
        plt.xlabel("periodo")
        plt.ylabel("contagi")
        plt.show()
        

    def controllaUrti(s):
        for p in s.posizioni:
            if copy(p) in s.posizioni:
                pass

    def disegnaPunto(s,x,y,lati=10,raggio=20,colore=(0.0, 0.0, 1.0)):
        raggio = 2 * raggio / s.w
        x = 2 * x / s.w
        y = 2 * y / s.h
        r,g,b = colore
        glColor3f(r,g,b)
        glBegin(GL_POLYGON)
        for v in range(lati):
            angolo = float(v) * 2.0 * math.pi / lati
            glVertex2f(math.cos(angolo)*raggio + x,math.sin(angolo)*raggio*s.ratio + y)
        glEnd()

class Punto:

    def __init__(s,x,y,v=3,alfa=0,colore=(0.0, 0.0, 1.0),raggio=5,infetto=False):
        s.x = x
        s.y = y
        s.v = v
        s.alfa = alfa
        s.id = id(s)
        s.colore = colore
        s.raggio = raggio
        s.urtato = False
        s.guarito = False
        s.infetto = infetto
        s.durata_infezione = 120 # cicli

    def __eq__(s,o):
        if math.sqrt((s.x - o.x)**2+(s.y - o.y)**2) < s.raggio * 2 and s.id != o.id:
            salfa = s.alfa
            oalfa = o.alfa
            if (s.infetto and not s.guarito) or (o.infetto and not o.guarito):
                s.infetto = o.infetto = True
            if not s.urtato: s.urto(oalfa)
            if not o.urtato: o.urto(salfa)
            return True
        else:
            return False

    def muovi(s):

        s.urtato = False

        if s.infetto: s.durata_infezione -= 1
        if s.durata_infezione < 0:
            s.guarito = True
            s.colore=(0.0, 1.0, 0.0)
        if s.infetto and not s.guarito: s.colore=(1.0, 0.0, 0.0)
        
        dx = s.v * math.cos(s.alfa)
        dy = s.v * math.sin(s.alfa)

        if s.x+dx >= 600 or s.x+dx <= -600:
            s.alfa = math.pi-s.alfa
            dx = s.v * math.cos(s.alfa)
            dy = s.v * math.sin(s.alfa)

        if s.y+dy >= 400 or s.y+dy <= -400:
            s.alfa = -s.alfa
            dx = s.v * math.cos(s.alfa)
            dy = s.v * math.sin(s.alfa)

        s.x += dx
        s.y += dy

        if s.x >= 600 or s.x <= -600 or s.y >= 400 or s.y <= -400:
            s.v = -s.v

    def urto(s,theta):
        s.alfa = s.alfa+theta
        s.urtato = True


Simulazione(dati=dati)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

import pygame as pg

from pygame.locals import *

from OpenGL.GL import *

from OpenGL.GLU import *

import math

from copy import copy

import random

import matplotlib.pyplot as plt

dati = [

{"infetto":False,"velocita":10,"numero":200},

{"infetto":False,"velocita":0,"numero":10},

{"infetto":True,"velocita":10,"numero":1}

]

class Simulazione:

def __init__(s, w = 1200, h = 800, dati = []):

s.posizioni = []

s.ratio = w / h

s.w = w

s.h = h

pg.init()

schermo = (w,h)

pg.display.set_mode(schermo, DOUBLEBUF|OPENGL)

# in movimento

for d in dati:

for i in range(d["numero"]):

x = random.randint(-w/2+10,w/2-10)

y = random.randint(-h/2+10,h/2-10)

a = 2*math.pi*random.random()

s.posizioni.append(Punto(x,y,d["velocita"],a,infetto=d["infetto"]))

infezioni = []

while True:

for event in pg.event.get():

if event.type == pg.QUIT:

pg.quit()

quit()

glClearColor(1.0, 1.0, 1.0, 1.0)

glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT)

tot_infetti = 0

for p in s.posizioni:

p.muovi()

s.disegnaPunto(p.x,p.y,raggio=p.raggio,colore=p.colore)

if p.infetto and not p.guarito: tot_infetti += 1

infezioni.append(tot_infetti)

s.controllaUrti()

pg.display.flip()

pg.time.wait(10)

if tot_infetti == 0:

pg.quit()

break

plt.plot(range(len(infezioni)),infezioni)

plt.title("curva contagi")

plt.xlabel("periodo")

plt.ylabel("contagi")

plt.show()

def controllaUrti(s):

for p in s.posizioni:

if copy(p) in s.posizioni:

pass

def disegnaPunto(s,x,y,lati=10,raggio=20,colore=(0.0, 0.0, 1.0)):

raggio = 2 * raggio / s.w

x = 2 * x / s.w

y = 2 * y / s.h

r,g,b = colore

glColor3f(r,g,b)

glBegin(GL_POLYGON)

for v in range(lati):

angolo = float(v) * 2.0 * math.pi / lati

glVertex2f(math.cos(angolo)*raggio + x,math.sin(angolo)*raggio*s.ratio + y)

glEnd()

class Punto:

def __init__(s,x,y,v=3,alfa=0,colore=(0.0, 0.0, 1.0),raggio=5,infetto=False):

s.x = x

s.y = y

s.v = v

s.alfa = alfa

s.id = id(s)

s.colore = colore

s.raggio = raggio

s.urtato = False

s.guarito = False

s.infetto = infetto

s.durata_infezione = 120 # cicli

def __eq__(s,o):

if math.sqrt((s.x - o.x)**2+(s.y - o.y)**2) < s.raggio * 2 and s.id != o.id:

salfa = s.alfa

oalfa = o.alfa

if (s.infetto and not s.guarito) or (o.infetto and not o.guarito):

s.infetto = o.infetto = True

if not s.urtato: s.urto(oalfa)

if not o.urtato: o.urto(salfa)

return True

else:

return False

def muovi(s):

s.urtato = False

if s.infetto: s.durata_infezione -= 1

if s.durata_infezione < 0:

s.guarito = True

s.colore=(0.0, 1.0, 0.0)

if s.infetto and not s.guarito: s.colore=(1.0, 0.0, 0.0)

dx = s.v * math.cos(s.alfa)

dy = s.v * math.sin(s.alfa)

if s.x+dx >= 600 or s.x+dx <= -600:

s.alfa = math.pi-s.alfa

dx = s.v * math.cos(s.alfa)

dy = s.v * math.sin(s.alfa)

if s.y+dy >= 400 or s.y+dy <= -400:

s.alfa = -s.alfa

dx = s.v * math.cos(s.alfa)

dy = s.v * math.sin(s.alfa)

s.x += dx

s.y += dy

if s.x >= 600 or s.x <= -600 or s.y >= 400 or s.y <= -400:

s.v = -s.v

def urto(s,theta):

s.alfa = s.alfa+theta

s.urtato = True

Simulazione(dati=dati)

Il risultato produrrà qualcosa di simile a questo:

Vedi articolo

23 Aprile 2021 Nessun commento

[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.

import os
import math

class CalcolaDimensione:

    def __init__(s):
        s.cartelle = []

    def leggi_cartella(s,path):
        try:
            dim = 0
            for file in os.listdir(path):
                tmp = path + "\\" + file
                if os.path.isdir(tmp):
                    dim += s.leggi_cartella(tmp)
                else:
                    dim += os.path.getsize(tmp)
            s.cartelle.append({
                "path": path,
                "bytes": dim,
                "size": s.dimensione(dim)
                })
            return dim
        except:
            print("Errore: %s" % path)
            return 0

    def ordina(s):
        s.cartelle.sort(key=lambda e: e["bytes"],reverse=True)

    def dimensione(s,dim):
        if dim == 0: return "0B"
        nomi = ("B","KB","MB","GB","TB")
        i = int(math.floor(math.log(dim,1024)))
        p = math.pow(1024,i)
        s = round(dim / p,2)
        return "%s %s" % (s,nomi[i])

cd = CalcolaDimensione()
cd.leggi_cartella("C:\\")
cd.ordina()
for c in cd.cartelle:
    if c["bytes"] > 1024*1024*200:
        print(c["size"],c["path"])

import os

import math

class CalcolaDimensione:

def __init__(s):

s.cartelle = []

def leggi_cartella(s,path):

try:

dim = 0

for file in os.listdir(path):

tmp = path + "\\" + file

if os.path.isdir(tmp):

dim += s.leggi_cartella(tmp)

else:

dim += os.path.getsize(tmp)

s.cartelle.append({

"path": path,

"bytes": dim,

"size": s.dimensione(dim)

})

return dim

except:

print("Errore: %s" % path)

return 0

def ordina(s):

s.cartelle.sort(key=lambda e: e["bytes"],reverse=True)

def dimensione(s,dim):

if dim == 0: return "0B"

nomi = ("B","KB","MB","GB","TB")

i = int(math.floor(math.log(dim,1024)))

p = math.pow(1024,i)

s = round(dim / p,2)

return "%s %s" % (s,nomi[i])

cd = CalcolaDimensione()

cd.leggi_cartella("C:\\")

cd.ordina()

for c in cd.cartelle:

if c["bytes"] > 1024*1024*200:

print(c["size"],c["path"])

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

25 Gennaio 2021 Nessun commento

[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:

class Casella:

    def __init__(s, mina = False):
        s.mina = mina
        s.aperta = False
        s.conteggio = 0

class Casella:

def __init__(s, mina = False):

s.mina = mina

s.aperta = False

s.conteggio = 0

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

campo = [[Casella(True if random.randint(0,difficolta)==0 else False) for j in range(n)] for i in range(n)]

1	campo = [[Casella(True if random.randint(0,difficolta)==0 else False) for j in range(n)] for i in range(n)]

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:

import random

class Casella:

    def __init__(s, mina = False):
        s.mina = mina
        s.aperta = False
        s.conteggio = 0

def conteggio(i,j):

    global n,campo

    # se nella cella non c'è una mina allora procedi
    if campo[i][j].mina == False:
        # controlliamo le celle tutto intorno
        for di in range(-1,2):
            for dj in range(-1,2):
                # se la posizione è compresa nell'intervallo della matrice
                if (i+di > -1 and j+dj > -1) and (i+di < n and j+dj < n):
                    # se la cella è una mina
                    if campo[i+di][j+dj].mina == True:
                        # incrementiamo il contatore
                        campo[i][j].conteggio += 1
        # sfruttiamo il contatore per conteggiare il numero di mine nel gioco
        # se non abbiamo una mina restituiamo 0
        return 0
    else:
        #se abbiamo invece una mina restituiamo 1
        return 1

def controlla(i,j):

    global n,campo

    # se la cella è aperta non facciamo altro
    #restituiamo True per dire che il gioco continua
    if campo[i][j].aperta: return True

    # impostiamo la cella come aperta
    campo[i][j].aperta = True

    # se non abbiamo una mina e il conteggio è a 0, allora procediamo
    # questo perché, cliccando su una cella, vogliamo aprire tutte le celle vuote
    #che non hanno alcuna mina accanto
    if campo[i][j].mina == False and campo[i][j].conteggio == 0:
        for di in range(-1,2):
            for dj in range(-1,2):
                if (i+di > -1 and j+dj > -1) and (i+di < n and j+dj < n):
                    # se non abbiamo una mina e non siamo sulle celle diagonali
                    # l'apertura avviene solo in orizzontale e verticale
                    if not campo[i+di][j+dj].mina:
                        controlla(i+di,j+dj)
    # altrimenti se abbiamo una mina, restituiamo False
    elif campo[i][j].mina:
        return False
    # in tutti gli altri casi True
    return True

# difficoltà come probabilità di trovare mine, 1 / difficolta
difficolta = 10

while True:

    # stampiamo il menu
    print("-- MENU --")
    print("1. gioca")
    print("2. imposta difficoltà")
    print("0. esci")
    s = int(input("> "))

    # usciamo dal gioco
    if s == 0: break

    # giochiamo
    if s == 1:

        #dimensione del campo
        n = 10
        # disegniamo il campo
        campo = [[Casella(True if random.randint(0,difficolta)==0 else False) for j in range(n)] for i in range(n)]
        # true = continua il gioco, false = si ferma
        risultato = True
        totale_mine = 0

        # conteggiamo le mine rispetto alle caselle e le mine totali
        for i in range(n):
            for j in range(n):
                totale_mine += conteggio(i,j)

        # comincia l'inserimento
        while True:

            # numeri in cima
            print(end=" "*3)
            for i in range(n): print(i+1,end=" ")
            print()

            # conteggio chiuse
            ancora_chiuse = 0
            for nr, r in enumerate(campo):
                # numeri accanto
                print(nr,end=" "*2)
                for c in r:
                    # stampa a video
                    if c.aperta:
                        if c.mina: print("X",end=" ")
                        elif c.conteggio > 0: print(c.conteggio,end=" ")
                        else: print(" ",end=" ")
                    else:
                        if c.mina and not risultato: print("X",end=" ")
                        else:
                            print("-",end=" ")
                            ancora_chiuse += 1
                print()
                
            if not risultato:
                print("hai perso")
                break

            if ancora_chiuse <= totale_mine:
                print("hai vinto!")
                break

            # leggiamo l'input e trasformiamolo nella posizione i,j
            pos = int(input("posizione [1-%d]: " % (n**2)))
            i = int((pos-1)/n)
            j = pos - i*n - 1

            # controlliamo la cella corrente
            risultato = controlla(i,j)

    if s == 2:

        # impostiamo la difficoltà
        d = int(input("seleziona difficoltà (1 = facile, 2 = medio, 3 = difficile): "))
        if d == 1: difficolta = 10
        if d == 2: difficolta = 6
        if d == 3: difficolta = 4

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

import random

class Casella:

def __init__(s, mina = False):

s.mina = mina

s.aperta = False

s.conteggio = 0

def conteggio(i,j):

global n,campo

# se nella cella non c'è una mina allora procedi

if campo[i][j].mina == False:

# controlliamo le celle tutto intorno

for di in range(-1,2):

for dj in range(-1,2):

# se la posizione è compresa nell'intervallo della matrice

if (i+di > -1 and j+dj > -1) and (i+di < n and j+dj < n):

# se la cella è una mina

if campo[i+di][j+dj].mina == True:

# incrementiamo il contatore

campo[i][j].conteggio += 1

# sfruttiamo il contatore per conteggiare il numero di mine nel gioco

# se non abbiamo una mina restituiamo 0

return 0

else:

#se abbiamo invece una mina restituiamo 1

return 1

def controlla(i,j):

global n,campo

# se la cella è aperta non facciamo altro

#restituiamo True per dire che il gioco continua

if campo[i][j].aperta: return True

# impostiamo la cella come aperta

campo[i][j].aperta = True

# se non abbiamo una mina e il conteggio è a 0, allora procediamo

# questo perché, cliccando su una cella, vogliamo aprire tutte le celle vuote

#che non hanno alcuna mina accanto

if campo[i][j].mina == False and campo[i][j].conteggio == 0:

for di in range(-1,2):

for dj in range(-1,2):

if (i+di > -1 and j+dj > -1) and (i+di < n and j+dj < n):

# se non abbiamo una mina e non siamo sulle celle diagonali

# l'apertura avviene solo in orizzontale e verticale

if not campo[i+di][j+dj].mina:

controlla(i+di,j+dj)

# altrimenti se abbiamo una mina, restituiamo False

elif campo[i][j].mina:

return False

# in tutti gli altri casi True

return True

# difficoltà come probabilità di trovare mine, 1 / difficolta

difficolta = 10

while True:

# stampiamo il menu

print("-- MENU --")

print("1. gioca")

print("2. imposta difficoltà")

print("0. esci")

s = int(input("> "))

# usciamo dal gioco

if s == 0: break

# giochiamo

if s == 1:

#dimensione del campo

n = 10

# disegniamo il campo

campo = [[Casella(True if random.randint(0,difficolta)==0 else False) for j in range(n)] for i in range(n)]

# true = continua il gioco, false = si ferma

risultato = True

totale_mine = 0

# conteggiamo le mine rispetto alle caselle e le mine totali

for i in range(n):

for j in range(n):

totale_mine += conteggio(i,j)

# comincia l'inserimento

while True:

# numeri in cima

print(end=" "*3)

for i in range(n): print(i+1,end=" ")

print()

# conteggio chiuse

ancora_chiuse = 0

for nr, r in enumerate(campo):

# numeri accanto

print(nr,end=" "*2)

for c in r:

# stampa a video

if c.aperta:

if c.mina: print("X",end=" ")

elif c.conteggio > 0: print(c.conteggio,end=" ")

else: print(" ",end=" ")

else:

if c.mina and not risultato: print("X",end=" ")

else:

print("-",end=" ")

ancora_chiuse += 1

print()

if not risultato:

print("hai perso")

break

if ancora_chiuse <= totale_mine:

print("hai vinto!")

break

# leggiamo l'input e trasformiamolo nella posizione i,j

pos = int(input("posizione [1-%d]: " % (n**2)))

i = int((pos-1)/n)

j = pos - i*n - 1

# controlliamo la cella corrente

risultato = controlla(i,j)

if s == 2:

# impostiamo la difficoltà

d = int(input("seleziona difficoltà (1 = facile, 2 = medio, 3 = difficile): "))

if d == 1: difficolta = 10

if d == 2: difficolta = 6

if d == 3: difficolta = 4

Vedi articolo