Esercizio 9codice cliente che si incrementa
In questa pagina 4
Testo (appello del 31 gennaio 2023, esercizio 2 "Tour operator", 20 punti, di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java, qui in Python).
Un'agenzia di viaggi tiene un dizionario dei propri clienti: codice identificativo (chiave), nome e destinazione del viaggio (attributi). Il codice è di quattro caratteri nel formato Lnnn: L è una lettera maiuscola da A a Z, n una cifra da 0 a 9 (esempio valido: A199).
Scrivere, nella classe TourOperator:
add(nome, dest): inserisce nel dizionario (codice corrente, nome, destinazione) e poi incrementa il codice corrente;_incrementa(): se il numeronnnè minore di 999 lo si incrementa; altrimenti le cifre diventano000e si passa alla lettera successiva. Esempio: daC998si passa aC999; daC999aD000.
Il costruttore riceve il codice iniziale. Il programma di prova legge da standard input le righe nome:destinazione (file viaggi.txt) e, partendo da A998, stampa il dizionario:
Ironman:Malibu
Spider man:New York
Thor:Asgard
Batman:Gotham
Superman:MetropolisTeoria: Stringhe in Pythonstr come sequenza immutabile di caratteri Unicode; indici e slicing; operatori; metodi principali (split, join, strip, find, replace...); f-string e formattazione; confronto lessicografico.Stringhe 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 →, 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 →.
Analisi
- Dizionario. I codici sono chiavi uniche generate in ordine crescente. In Python basta un
dict(codice → (nome, destinazione)): conserva l'ordine di inserimento efindcosta in media. Nel tema originale il dizionario si realizzava con un array (le chiavi, crescenti per costruzione, permettono la ricerca binaria): vedi Realizzare contenitori su array e listeCome si realizza un ADT contenitore partendo da un array: lunghezza logica e capacità con raddoppio (costo ammortizzato), dizionario su array ordinato con ricerca binaria, coda doppia su array circolare, coda con priorità a livelli, ADT costruiti sopra altri ADT (pila di code, pila reversibile); tabella dei costi.Realizzare contenitori su array e liste →. - Il codice è una stringa con due parti:
codice[0](lettera) ecodice[1:](le tre cifre). Per incrementare si converte la parte numerica inint, si somma 1 e si riformatta con zeri a sinistra:f"{n:03d}". - Lettera successiva:
chr(ord(lettera) + 1)(orddà il codice numerico del carattere,chrlo riconverte). - Casi limite. Il formato
Lnnnha un numero finito di codici: l'ultimo èZ999. Dopo averlo assegnato non esiste un codice successivo: lo stato deve restare coerente e un ulterioreadddeve segnalare l'errore (si usaNoneper "codici esauriti" eOverflowError). Il codice iniziale va validato con un'espressione regolare[A-Z][0-9]{3}.
Codice
import io
import re
class TourOperator:
def __init__(self, codice_iniziale):
if not re.fullmatch(r"[A-Z][0-9]{3}", codice_iniziale): # formato Lnnn
raise ValueError("codice non valido: " + codice_iniziale)
self._prossimo = codice_iniziale # None quando i codici sono finiti
self._clienti = {} # codice -> (nome, destinazione)
def add(self, nome, dest):
if self._prossimo is None:
raise OverflowError("codici esauriti")
self._clienti[self._prossimo] = (nome, dest)
self._incrementa()
def _incrementa(self):
lettera, numero = self._prossimo[0], int(self._prossimo[1:])
if numero < 999: # basta incrementare il numero
self._prossimo = f"{lettera}{numero + 1:03d}"
elif lettera < "Z": # nnn -> 000 e lettera successiva
self._prossimo = f"{chr(ord(lettera) + 1)}000"
else: # Z999 era l'ultimo codice
self._prossimo = None
def find(self, codice):
return self._clienti[codice] # KeyError se assente
def __str__(self):
return "\n".join(f"{c} : {n} : {d}" for c, (n, d) in self._clienti.items())
def main(codice, f):
t = TourOperator(codice)
for riga in f:
riga = riga.strip()
if riga:
nome, dest = riga.split(":")
t.add(nome, dest)
print(t)
viaggi = "Ironman:Malibu\nSpider man:New York\nThor:Asgard\nBatman:Gotham\nSuperman:Metropolis\n"
main("A998", io.StringIO(viaggi)) # con la tastiera: main(sys.argv[1], sys.stdin)Stampa:
A998 : Ironman : Malibu
A999 : Spider man : New York
B000 : Thor : Asgard
B001 : Batman : Gotham
B002 : Superman : MetropolisTraccia degli incrementi (il codice dopo ogni add): A998 → A999 (numero < 999) → B000 (numero = 999, lettera A → B) → B001 → B002.
Verifica
for iniziale, atteso in [("C998", "C999"), ("C999", "D000"), ("A000", "A001"), ("Y999", "Z000")]:
t = TourOperator(iniziale)
t.add("x", "y")
assert t._prossimo == atteso, (iniziale, t._prossimo)
t = TourOperator("Z999")
t.add("a", "b")
print(t._prossimo, t.find("Z999")) # None ('a', 'b')
try:
t.add("c", "d")
except OverflowError as e:
print("OverflowError:", e) # OverflowError: codici esauriti
for cattivo in ("a123", "A12", "AB12", "12AB", "A1x3"):
try:
TourOperator(cattivo)
except ValueError:
pass
else:
print("accettato?", cattivo)
print("ok")Errori comuni
- Dimenticare gli zeri a sinistra:
"B" + str(1)dàB1, nonB001(serve:03d). - Incrementare la lettera quando il numero è ancora minore di 999, o non azzerare le cifre.
- Non gestire
Z999: la lettera successiva aZnon è una lettera. - Incrementare prima di inserire: il primo cliente avrebbe il codice successivo a quello iniziale invece del codice iniziale.
- Confondere la chiave (codice) con gli attributi (nome, destinazione) nel dizionario.
Versione ripasso
Appello del 31 gennaio 2023, esercizio 2 (UniPD, in Java; adattato a Python). Teoria: Stringhe in Pythonstr come sequenza immutabile di caratteri Unicode; indici e slicing; operatori; metodi principali (split, join, strip, find, replace...); f-string e formattazione; confronto lessicografico.Stringhe 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 →.
Problema. Dizionario codice → (nome, destinazione); codice Lnnn (L in A–Z, nnn 3 cifre). add(nome, dest) inserisce con il codice corrente e poi lo incrementa.
Incremento: numero < 999 → f"{lettera}{numero + 1:03d}"; altrimenti f"{chr(ord(lettera) + 1)}000"; da Z999 non esiste un successivo (None, OverflowError al successivo add). Costruttore: validare con re.fullmatch(r"[A-Z][0-9]{3}", codice).
Esempi: C998 → C999 → D000; con A998 e 5 clienti: A998, A999, B000, B001, B002.
Errori comuni: zeri a sinistra persi (B1); lettera incrementata troppo presto; Z999 non gestito; incremento prima dell'inserimento.