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; qui in 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: un dict chiave → attributo. inserisci sostituisce se la chiave c'è (d[chiave] = attributo); cerca e cancella restituiscono una Coppia o None, in O(1)O(1) medio. cerca_per_attributo scorre tutte le coppie, O(n)O(n), e restituisce un elenco anche vuoto o con più coppie. Per renderlo veloce si può tenere un indice inverso attributo → chiavi.
  • Squadra(Archivio): costanti MAX_GIOCATORI = 18 e BUDGET = 300.
    • soldi() = BUDGET - sum(valori): ricavato dai dati, senza un contatore da tenere allineato.
    • inserisci ridefinito: se la chiave è nuova e ci sono già 1818 giocatori, rifiuta; il costo aggiuntivo è attributo - (vecchio or 0), che se supera soldi() fa rifiutare; altrimenti chiama super().inserisci(...). Restituisce True o False come Archivio.inserisci, così una squadra si usa ovunque serva un archivio.
  • Prova: righe nome:costo lette con rsplit(":", 1), archivio stampato, squadra riempita dall'archivio. Sul file d'esempio ROSSI A. viene sostituito (costo 2121), GRIGI A.:301 è rifiutato, la squadra ha 88 giocatori e soldi = 125 (300−175300-175).
  • Principio di sostituzione: una Squadra si usa dove serve un Archivio: inserisci restituisce True o False in entrambe le classi.
  • Verifica dei vincoli: 2525 giocatori da 11 milione danno taglia = 18 e soldi = 282. Con x a 290290, y a 1111 viene rifiutato (restano 1010 milioni), y a 1010 passa e soldi diventa 00.
  • Sostituzione: riportare x da 290290 a 280280 libera 1010 milioni, perché il costo aggiuntivo è 280 - 290 < 0; il budget residuo diventa 1010.
  • Errori tipici: controllare i vincoli dopo l'inserimento; ignorare la sostituzione, che non occupa un posto in più e libera il vecchio costo; contatore dei soldi non aggiornato dopo cancella; super() omesso; ereditare senza una relazione is-a.

Teoria collegata