Esercizio 14dizionario invertibile e squadra
In questa pagina 5
Testo (appello del 31 gennaio 2017, "Fantacalcio", di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java, qui in Python; i nomi dei giocatori sono inventati).
Un dizionario invertibile contiene coppie in cui sia la chiave sia l'attributo sono oggetti confrontabili e realizza l'interfaccia:
| operazione | significato |
|---|---|
inserisci(chiave, attributo) |
inserisce la coppia; non ci sono mai due coppie con la stessa chiave: inserire una chiave già presente sostituisce la coppia |
cerca(chiave) |
restituisce la Coppia della chiave, o None se non c'è |
cancella(chiave) |
elimina la coppia e la restituisce; se la chiave non c'è, non fa nulla e restituisce None |
cerca_per_attributo(attributo) |
restituisce l'elenco delle coppie con quell'attributo (anche nessuna, o più di una) |
taglia() |
numero di coppie |
(Si noti che cerca trova al più una coppia, mentre cerca_per_attributo ne può trovare molte.)
Un appassionato di fantacalcio tiene un archivio dei suoi giocatori preferiti: righe nome:costo, con il costo intero in milioni, nel file fantacalcio.txt.
- Completare la classe
Archivio, che realizza l'interfaccia. - Una squadra è un insieme di al massimo 18 giocatori, e la somma dei costi non può superare 300 milioni. Creare la classe
Squadra, che estendeArchivioimponendo i due vincoli; ha inoltre il metodosoldi()che restituisce i milioni ancora disponibili. - Programma di prova: leggere il file e salvare tutte le righe in un
Archivio; stamparlo; creare unaSquadravuota; riempirla con i giocatori dell'archivio; stamparla.
Teoria: Classi ed ereditarietà in PythonAttributi di istanza e di classe, metodi di istanza, di classe e statici; confronto e ordinamento con eq e lt; proprietà; ereditarietà, super(), override e polimorfismo; classi astratte come interfacce; eccezioni personalizzate; overloading e shadowing in Python.Classi ed ereditarietà in Python →, Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →, File di record e controllo degli errori riga per rigaSchema per leggere un file (o lo standard input) di record, uno per riga: formati con separatore, controllo di ogni riga, messaggi di errore con il numero di riga su standard error, righe da saltare, fine dell'input su riga vuota; versione in Python con split, int, float e eccezioni; versione in C con fgets, sscanf e strtol.File di record e controllo degli errori riga per riga →.
Archivio
La rappresentazione naturale è un dict chiave → attributo: inserisci che sostituisce è l'assegnazione d[chiave] = attributo, cerca e cancella costano in media. cerca_per_attributo deve guardare tutte le coppie: . (Per renderlo veloce si tiene in più un indice inverso attributo → insieme di chiavi, aggiornato a ogni inserimento e cancellazione.)
Coppia è un piccolo oggetto con chiave e attributo; __str__ dà chiave:attributo.
Squadra: ereditarietà con un vincolo in più
La squadra è un archivio ("is-a") con più regole: si eredita e si ridefinisce inserisci, che controlla i vincoli e poi chiama la versione di Archivio con super(). Così il codice dell'archivio non si duplica.
Le regole, da applicare prima di modificare lo stato:
- se la chiave è nuova e la squadra ha già 18 giocatori → rifiutato;
- il costo aggiuntivo è
attributo - vecchiose il giocatore c'era già (sostituzione), altrimentiattributo; se supera isoldi()rimasti → rifiutato.
soldi() si ricava dai dati (300 - somma dei costi): non c'è una variabile in più da tenere allineata dopo cancella o dopo una sostituzione (l'implementazione Java del tema teneva un contatore e doveva ridefinire anche cancella).
import io
class Coppia:
def __init__(self, chiave, attributo):
self.chiave, self.attributo = chiave, attributo
def __str__(self):
return f"{self.chiave}:{self.attributo}"
__repr__ = __str__
def __eq__(self, altra):
return (self.chiave, self.attributo) == (altra.chiave, altra.attributo)
class Archivio:
"""Dizionario invertibile: chiave -> attributo (int)."""
def __init__(self):
self._d = {} # chiave -> attributo
def inserisci(self, chiave, attributo):
self._d[chiave] = attributo # chiave presente: sostituisce
return True
def cerca(self, chiave):
return Coppia(chiave, self._d[chiave]) if chiave in self._d else None
def cancella(self, chiave):
return Coppia(chiave, self._d.pop(chiave)) if chiave in self._d else None
def cerca_per_attributo(self, attributo): # O(n): nessuna, una o più coppie
return [Coppia(k, a) for k, a in self._d.items() if a == attributo]
def taglia(self):
return len(self._d)
def __str__(self):
return "\n".join(str(Coppia(k, a)) for k, a in self._d.items())
class Squadra(Archivio):
MAX_GIOCATORI = 18
BUDGET = 300 # milioni
def soldi(self):
return self.BUDGET - sum(self._d.values())
def inserisci(self, chiave, attributo):
vecchio = self._d.get(chiave) # None se il giocatore non c'è
if vecchio is None and self.taglia() >= self.MAX_GIOCATORI:
return False # squadra al completo
if attributo - (vecchio or 0) > self.soldi():
return False # budget superato
return super().inserisci(chiave, attributo) # vincoli rispettati: si riusa ArchivioPer segnalare il rifiuto inserisci restituisce False (e True se ha inserito): anche Archivio.inserisci restituisce True, così le due versioni sono intercambiabili da chi le usa (principio di sostituzione: una Squadra si può usare ovunque serva un Archivio).
Programma di prova
FILE = """ROSSI A.:19
BIANCHI G.:20
VERDI S.:19
NERI M.:8
GIALLI N.:42
ROSSI A.:21
BLU F.:14
VIOLA F.:27
ARANCI M.:24
GRIGI A.:301
"""
def main(f):
mio_archivio = Archivio()
for riga in f:
riga = riga.strip()
if riga:
nome, costo = riga.rsplit(":", 1) # il costo è dopo l'ultimo ":"
mio_archivio.inserisci(nome, int(costo))
print(mio_archivio)
mia_squadra = Squadra()
for nome, costo in mio_archivio._d.items():
if not mia_squadra.inserisci(nome, costo):
print("rifiutato:", nome, costo)
print(mia_squadra, "\nsoldi:", mia_squadra.soldi(), "taglia:", mia_squadra.taglia())
main(io.StringIO(FILE)) # con il file vero: main(open("fantacalcio.txt"))Risultato: ROSSI A. compare due volte nel file (19 e poi 21): la seconda riga sostituisce la prima, e nell'archivio resta ROSSI A.:21 al suo posto. L'archivio ha 9 giocatori. GRIGI A. costa 301 e supera il budget da solo: viene rifiutato (rifiutato: GRIGI A. 301), la squadra ha 8 giocatori e restano 300 - 175 = 125 milioni (si stampa soldi: 125 taglia: 8).
Verifica dei vincoli
a = Archivio()
for k, v in [("a", 1), ("b", 2), ("c", 1)]:
a.inserisci(k, v)
print(a.cerca_per_attributo(1), a.cerca_per_attributo(9)) # [a:1, c:1] []
print(a.cerca("b"), a.cerca("z"), a.cancella("b"), a.cancella("b"), a.taglia()) # b:2 None b:2 None 2
s = Squadra()
for i in range(25): # 25 giocatori da 1 milione: vale il limite di 18
s.inserisci(f"g{i}", 1)
print(s.taglia(), s.soldi()) # 18 282
s = Squadra()
print(s.inserisci("x", 290), s.inserisci("y", 11), s.inserisci("y", 10), s.soldi()) # True False True 0
print(s.inserisci("x", 295), s.soldi()) # False 0: sostituire x costerebbe 5 in più
s.inserisci("x", 280) # sostituzione che risparmia 10
print(s.soldi()) # 10Errori comuni
- Controllare i vincoli dopo aver inserito (poi bisogna annullare) o confrontare con la somma prima di sommare il nuovo costo.
- Non tener conto della sostituzione: un giocatore già presente non occupa un posto in più, e il suo vecchio costo si libera.
- Tenere un contatore dei soldi che resta sbagliato dopo
cancellao dopo una sostituzione; calcolarlo dai dati evita il problema. - Dimenticare
super().inserisci(...): la squadra non conterrebbe niente. Duplicare invece il codice diArchivio. - Ereditare per riusare codice senza relazione is-a; qui c'è ("una squadra è un archivio con vincoli").
Versione ripasso
Appello del 31 gennaio 2017, "Fantacalcio" (UniPD, in Java; adattato a Python, nomi inventati). Teoria: Classi ed ereditarietà in PythonAttributi di istanza e di classe, metodi di istanza, di classe e statici; confronto e ordinamento con eq e lt; proprietà; ereditarietà, super(), override e polimorfismo; classi astratte come interfacce; eccezioni personalizzate; overloading e shadowing in Python.Classi ed ereditarietà in Python →, Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →.
Archivio (dict chiave → attributo): inserisci sostituisce se la chiave c'è, cerca/cancella → Coppia o None, cerca_per_attributo → elenco (anche vuoto o con più coppie), taglia. Opzionale: indice inverso attributo → chiavi per renderlo veloce.
Squadra(Archivio), MAX_GIOCATORI = 18, BUDGET = 300:
soldi()=BUDGET - sum(valori)(ricavato dai dati: niente contatore da tenere allineato);inserisciridefinito: chiave nuova e già 18 giocatori → rifiuta; costo aggiuntivoattributo - (vecchio or 0)oltresoldi()→ rifiuta; altrimentisuper().inserisci(...). RitornaTrue/FalsecomeArchivio.inserisci(sostituibilità).
Prova: righe nome:costo (rsplit(":", 1)), archivio → stampa → squadra riempita dall'archivio. Sul file d'esempio: ROSSI A. sostituito (21), GRIGI A.:301 rifiutato, squadra di 8 giocatori con soldi = 125.
Errori comuni: vincoli controllati dopo l'inserimento; sostituzione ignorata; contatore dei soldi non allineato; super() omesso; ereditarietà senza is-a.