Esercizio 16oracolo di Delfi
In questa pagina 4
Testo (appello del 25 gennaio 2018 di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD; adattato da un tema d'esame in Java, qui in Python).
Si vuole un programma che risponda alle domande dell'utente come l'Oracolo di Delfi. Le domande sono lette dallo standard input, una riga alla volta, e per ciascuna si stampa una risposta. Le domande ammettono una risposta affermativa o negativa. Il programma termina quando si inserisce una riga vuota. Domande identiche devono avere risposte identiche.
L'ADT dizionario è definito da un'interfaccia che estende Container:
Container: is_empty() -> bool, make_empty(), size() -> int
Dictionary: insert(key, attribute), find(key) -> attribute, remove(key) -> attribute
(find e remove sollevano un'eccezione se la chiave non c'è)- Scrivere la classe
Dche realizzaDictionary. - Scrivere la classe eseguibile
Oracoloche eredita daD, con la costanteRISPOSTA(un elenco di risposte, per esempio "Naturalmente.", "Forse.", "Ne dubito.", "Assolutamente no.", "Certamente.", "Puoi scommetterci.", "Probabilmente no.", "Poco ma sicuro.") e il metodorispondi(domanda): cerca la domanda nel dizionario; se c'è, restituisce l'attributo (la risposta già data); altrimenti sceglie a caso una risposta tra quelle diRISPOSTA, inserisce la coppia(domanda, risposta)nel dizionario e la restituisce. - Il metodo
mainistanzia unOracolo, legge le domande finché non trova una riga vuota, risponde conrispondie stampa domanda e risposta.
Nel testo originale per il numero casuale si usava (int)(A + (1 + B - A) * Math.random()), che dà un intero in ; in Python si usa direttamente random.choice (o random.randint(A, B)).
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 →, Eccezioni in PythonEccezioni e traceback, eccezioni predefinite più comuni, try/except/else/finally, raise per segnalare errori, propagazione lungo le chiamate.Eccezioni in Python →.
Progetto
Interfacce come classi astratte. Container e Dictionary si scrivono con abc (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 →): i metodi sono @abstractmethod, quindi non si può istanziare un Dictionary ma solo una sua realizzazione concreta. Dictionary estende Container: eredita le tre operazioni e ne aggiunge altre tre.
D realizza il dizionario. Un dict interno fa da deposito: insert sostituisce se la chiave c'è già; find e remove sollevano KeyError se manca (l'eccezione che il testo chiama NoSuchElementException).
Oracolo è un D. L'oracolo è un dizionario (domanda → risposta) con un comportamento in più: eredita insert e find senza riscriverli e aggiunge rispondi. La coerenza richiesta ("domande identiche, risposte identiche") si ottiene ricordando la prima risposta: è una memoizzazione.
rispondi usa try/except KeyError invece di controllare con in e poi leggere: una sola ricerca invece di due, ed è lo stile "chiedi scusa" (EAFP) tipico di Python (Eccezioni in PythonEccezioni e traceback, eccezioni predefinite più comuni, try/except/else/finally, raise per segnalare errori, propagazione lungo le chiamate.Eccezioni in Python →).
main legge righe: la riga vuota (dopo aver tolto il '\n') termina il ciclo con break. Per rendere il programma verificabile il generatore casuale si passa dall'esterno (random.Random(seme)): con lo stesso seme la sequenza è sempre uguale; senza argomento ne viene creato uno ordinario.
Codice
import io
import random
from abc import ABC, abstractmethod
class Container(ABC):
@abstractmethod
def is_empty(self): ...
@abstractmethod
def make_empty(self): ...
@abstractmethod
def size(self): ...
class Dictionary(Container):
@abstractmethod
def insert(self, key, attribute): ...
@abstractmethod
def find(self, key): ...
@abstractmethod
def remove(self, key): ...
class D(Dictionary):
def __init__(self):
self._d = {}
def is_empty(self):
return not self._d
def make_empty(self):
self._d.clear()
def size(self):
return len(self._d)
def insert(self, key, attribute):
self._d[key] = attribute # chiave presente: sostituisce
def find(self, key):
return self._d[key] # KeyError se manca
def remove(self, key):
return self._d.pop(key) # restituisce l'attributo; KeyError se manca
class Oracolo(D):
RISPOSTA = ["Naturalmente.", "Forse.", "Ne dubito.", "Assolutamente no.",
"Certamente.", "Puoi scommetterci.", "Probabilmente no.", "Poco ma sicuro."]
def __init__(self, rng=None):
super().__init__()
self._rng = rng or random.Random()
def rispondi(self, domanda):
try:
return self.find(domanda) # già vista: stessa risposta
except KeyError:
vaticinio = self._rng.choice(self.RISPOSTA) # nuova: scelta a caso...
self.insert(domanda, vaticinio) # ...e ricordata
return vaticinio
def main(f, out, rng=None):
magico = Oracolo(rng)
for domanda in f:
domanda = domanda.rstrip("\n")
if domanda == "": # riga vuota: fine
break
print(f"Oracolo di Delfi, {domanda}\n Risposta: {magico.rispondi(domanda)}", file=out)
domande = ("supererò questo esame?\navrò successo nella vita?\nvincerà lo scudetto il Chievo?\n"
"avrò successo nella vita?\nvincerà lo scudetto il Chievo?\nsupererò questo esame?\n"
"\nnon letta?\n")
out = io.StringIO()
main(io.StringIO(domande), out, random.Random(7)) # con la tastiera: main(sys.stdin, sys.stdout)
print(out.getvalue())Con il seme 7 (Python 3.12) l'uscita è:
Oracolo di Delfi, supererò questo esame?
Risposta: Puoi scommetterci.
Oracolo di Delfi, avrò successo nella vita?
Risposta: Ne dubito.
Oracolo di Delfi, vincerà lo scudetto il Chievo?
Risposta: Probabilmente no.
Oracolo di Delfi, avrò successo nella vita?
Risposta: Ne dubito.
Oracolo di Delfi, vincerà lo scudetto il Chievo?
Risposta: Probabilmente no.
Oracolo di Delfi, supererò questo esame?
Risposta: Puoi scommetterci.Le risposte cambiano con il seme, ma le coppie uguali restano uguali: la 1ª e la 6ª riga di risposta coincidono, come la 2ª e la 4ª, e la 3ª e la 5ª. La riga vuota ferma la lettura: non letta? non viene elaborata.
Verifica
righe = [r for r in out.getvalue().split("\n") if r.startswith(" ")]
print(len(righe), righe[0] == righe[5], righe[1] == righe[3], righe[2] == righe[4]) # 6 True True True
try:
Dictionary() # classe astratta: non istanziabile
except TypeError:
print("TypeError: Dictionary è astratta")
for seme in range(200): # per ogni sequenza casuale vale la coerenza
o = Oracolo(random.Random(seme))
r1 = o.rispondi("q")
assert o.rispondi("q") == r1 and r1 in Oracolo.RISPOSTA
print("ok")Errori comuni
- Generare a ogni chiamata una nuova risposta e dimenticare
insert: la stessa domanda riceverebbe risposte diverse. - Controllare con
ine poi leggere (due ricerche) o catturareExceptioninvece diKeyError. - Dimenticare
super().__init__()inOracolo: il dizionario interno non esisterebbe. - Creare un generatore casuale a ogni domanda con lo stesso seme: le risposte sarebbero sempre le stesse per ogni domanda nuova.
- Non togliere il
'\n': la riga vuota è"\n", non"", e il ciclo non terminerebbe.
Versione ripasso
Appello del 25 gennaio 2018 (UniPD, in Java; adattato a Python). 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 →.
- Interfacce con
abc:Container(is_empty,make_empty,size),Dictionary(Container)(insert,find,remove), metodi@abstractmethod;Dictionary()sollevaTypeError. D(Dictionary):dictinterno;insertsostituisce,find/removesollevanoKeyErrorse la chiave manca.Oracolo(D):rispondi(domanda):try: return self.find(domanda);except KeyError:scegli conrandom.choice(RISPOSTA),self.insert(domanda, risposta), restituiscila (memoizzazione: stessa domanda → stessa risposta).main: righe senza'\n'; la riga vuota termina (break); stampa domanda e risposta. Il generatore si passa dall'esterno (random.Random(seme)) per poter verificare.
Errori comuni: insert dimenticato; in + lettura (due ricerche); super().__init__() omesso; generatore ricreato a ogni domanda; '\n' non tolto.