Salta al contenuto
Note per Studenti Esercizio 14 · dizionario invertibile e squadra

Esercizio 14dizionario invertibile e squadra

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

  1. Completare la classe Archivio, che realizza l'interfaccia.
  2. Una squadra è un insieme di al massimo 18 giocatori, e la somma dei costi non può superare 300 milioni. Creare la classe Squadra, che estende Archivio imponendo i due vincoli; ha inoltre il metodo soldi() che restituisce i milioni ancora disponibili.
  3. Programma di prova: leggere il file e salvare tutte le righe in un Archivio; stamparlo; creare una Squadra vuota; 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 O(1)O(1) in media. cerca_per_attributo deve guardare tutte le coppie: O(n)O(n). (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 - vecchio se il giocatore c'era già (sostituzione), altrimenti attributo; se supera i soldi() 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).

python
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 Archivio

Per 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

python
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

python
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())                                            # 10

Errori 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 cancella o dopo una sostituzione; calcolarlo dai dati evita il problema.
  • Dimenticare super().inserisci(...): la squadra non conterrebbe niente. Duplicare invece il codice di Archivio.
  • 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 O(n)O(n) → 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);
  • inserisci ridefinito: chiave nuova e già 18 giocatori → rifiuta; costo aggiuntivo attributo - (vecchio or 0) oltre soldi() → rifiuta; altrimenti super().inserisci(...). Ritorna True/False come Archivio.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.

Teoria collegata