Salta al contenuto
Note per Studenti Esercizio 16 · oracolo di Delfi

Esercizio 16oracolo di Delfi

Esame
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'è)
  1. Scrivere la classe D che realizza Dictionary.
  2. Scrivere la classe eseguibile Oracolo che eredita da D, con la costante RISPOSTA (un elenco di risposte, per esempio "Naturalmente.", "Forse.", "Ne dubito.", "Assolutamente no.", "Certamente.", "Puoi scommetterci.", "Probabilmente no.", "Poco ma sicuro.") e il metodo rispondi(domanda): cerca la domanda nel dizionario; se c'è, restituisce l'attributo (la risposta già data); altrimenti sceglie a caso una risposta tra quelle di RISPOSTA, inserisce la coppia (domanda, risposta) nel dizionario e la restituisce.
  3. Il metodo main istanzia un Oracolo, legge le domande finché non trova una riga vuota, risponde con rispondi e 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 [A,B][A, B]; 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

python
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

python
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 in e poi leggere (due ricerche) o catturare Exception invece di KeyError.
  • Dimenticare super().__init__() in Oracolo: 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() solleva TypeError.
  • D(Dictionary): dict interno; insert sostituisce, find/remove sollevano KeyError se la chiave manca.
  • Oracolo(D): rispondi(domanda): try: return self.find(domanda); except KeyError: scegli con random.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.

Teoria collegata