Esercizio 17multicoda e agenda con priorità

Esame

In questa pagina 4

Testo (due prove di programmazione di "appello simulato" di Fondamenti di Informatica, Ingegneria dell'Informazione UniPD, anni accademici non indicati nei testi, sul tipo di dato astratto coda; adattato da un tema d'esame in Java, qui in Python). In entrambe l'ADT va realizzato e poi collaudato con un programma che esegue comandi letti dallo standard input.

Parte A: biglietteria con $N$ sportelli (multicoda). Presso ogni sportello si forma una coda di persone; una persona che arriva si accoda allo sportello con la coda più breve; ogni sportello serve la prima persona della propria coda. Scrivere la classe MultiCoda (costruttore con $N > 0$ , altrimenti errore; aggiungi, rimuovi(i), __str__: per ciascuna coda la riga CODA i: seguita dalle persone, una per riga) e un programma che riceve $N$ dalla riga di comando ed esegue i comandi:

comando	significato
`A`	aggiunge una persona: legge il nome dalla riga successiva e lo inserisce nella coda più breve
`R`	rimuove una persona: legge un indice di coda dalla riga successiva, toglie il primo di quella coda e ne stampa il nome
`P`	stampa il contenuto della multicoda
`Q`	termina

Parte B: agenda con priorità. Un'agenda memorizza impegni "priorità promemoria", con priorità intera da 0 a 3 (0 = massima). Scrivere Agenda (coda con priorità: insert, remove, first, __str__ con un impegno per riga nel formato priorità promemoria) e un programma che esegue ripetutamente i comandi I (legge una riga "priorità promemoria" e inserisce), R (rimuove il primo impegno di priorità massima e ne stampa il promemoria), L (stampa il promemoria del primo impegno senza rimuoverlo), Q (termina), stampando l'agenda aggiornata dopo ogni comando. Se l'agenda è vuota R e L segnalano un errore.

Teoria: Pila e coda, Realizzare contenitori su array e liste, Classi ed ereditarietà in Python, File di record e controllo degli errori riga per riga.

Parte A: multicoda

Struttura. Una lista di $N$ code (deque: inserimento in fondo e estrazione dall'inizio in $O(1)$ ). È una struttura composta da ADT già pronti (Realizzare contenitori su array e liste).

aggiungi(persona): indice della coda più corta con min(range(N), key=lambda k: len(code[k])). In caso di parità min restituisce il primo minimo, cioè l'indice più basso: è una regola da dichiarare, il testo non la fissa. Costo $O(N)$ .
rimuovi(i): popleft della coda i; se è vuota si segnala l'errore (IndexError) invece di fallire in silenzio.
__str__: CODA i: e le persone, una per riga.

Il programma di prova legge i comandi riga per riga. A e R consumano anche la riga successiva: per questo le righe si leggono con un unico iteratore e il comando chiama next(righe).

python

import io
from collections import deque

class MultiCoda:
    """N code; chi arriva si accoda alla più corta (a parità, quella di indice minore)."""

    def __init__(self, n):
        if n <= 0:
            raise ValueError("servono N > 0 code")
        self._code = [deque() for _ in range(n)]

    def aggiungi(self, persona):
        i = min(range(len(self._code)), key=lambda k: len(self._code[k]))
        self._code[i].append(persona)
        return i

    def rimuovi(self, i):
        if not self._code[i]:
            raise IndexError(f"la coda {i} è vuota")
        return self._code[i].popleft()

    def __str__(self):
        return "\n".join(f"CODA {i}:\n" + "".join(p + "\n" for p in q)
                         for i, q in enumerate(self._code)).rstrip("\n")


def biglietteria(righe, n, out):
    righe = (r.rstrip("\n") for r in righe)            # un solo iteratore: next() consuma l'argomento
    m = MultiCoda(n)
    for cmd in righe:
        if cmd == "A":
            m.aggiungi(next(righe))
        elif cmd == "R":
            i = int(next(righe))
            try:
                print(m.rimuovi(i), file=out)
            except IndexError as e:
                print("errore:", e, file=out)
        elif cmd == "P":
            print(m, file=out)
        elif cmd == "Q":
            break


righe = ["A", "Topolino", "A", "Qui", "A", "Ciccio", "A", "Rockerduck", "A", "Minnie", "A", "Quo",
         "A", "Gastone", "A", "Gambadilegno", "A", "Pippo", "A", "Qua", "A", "Paperino", "A", "Bassotto",
         "R", "2", "R", "2", "A", "Paperina", "A", "Paperone", "P", "Q"]
out = io.StringIO()
biglietteria(righe, 4, out)                             # con la tastiera: biglietteria(sys.stdin, int(sys.argv[1]), sys.stdout)
print(out.getvalue())

Traccia. Con $N = 4$ i primi dodici arrivi si distribuiscono a giro (0, 1, 2, 3, 0, 1, ...): ogni coda ha 3 persone. R 2 toglie il primo della coda 2 (Ciccio), il secondo R 2 toglie Gastone: la coda 2 ha ora solo Paperino ed è la più corta, quindi Paperina e Paperone si accodano lì. Uscita:

Ciccio
Gastone
CODA 0:
Topolino
Minnie
Pippo

CODA 1:
Qui
Quo
Qua

CODA 2:
Paperino
Paperina
Paperone

CODA 3:
Rockerduck
Gambadilegno
Bassotto

Parte B: coda con priorità

Struttura. Quattro livelli fissi → una coda FIFO per livello (Realizzare contenitori su array e liste):

insert(impegno) accoda nella coda del suo livello: $O(1)$ ;
first() e remove() cercano la prima coda non vuota partendo dal livello 0: $O(\text{livelli}) = O(1)$ qui, e a pari priorità vale l'ordine di arrivo (FIFO); se sono tutte vuote si solleva EmptyQueueException;
__str__ scorre i livelli in ordine: l'elenco è ordinato per priorità.

Impegno controlla la priorità nel costruttore (ValueError fuori da $[0, 3]$ ). Il programma legge i comandi con lo stesso schema dell'iteratore unico; I prende la riga seguente e la divide una sola volta con split(None, 1): il promemoria può contenere spazi.

python

class EmptyQueueException(Exception):
    pass


class Impegno:
    def __init__(self, priorita, memo):
        if not 0 <= priorita <= 3:
            raise ValueError("priorità da 0 a 3")
        self.priorita, self.memo = priorita, memo

    def __str__(self):
        return f"{self.priorita} {self.memo}"


class Agenda:
    """Coda con priorità a 4 livelli (0 = massima): una coda FIFO per livello."""
    LIVELLI = 4

    def __init__(self):
        self._code = [deque() for _ in range(self.LIVELLI)]

    def insert(self, impegno):
        self._code[impegno.priorita].append(impegno)

    def _primo(self):
        for q in self._code:
            if q:
                return q
        raise EmptyQueueException("agenda vuota")

    def remove(self):
        return self._primo().popleft()

    def first(self):
        return self._primo()[0]

    def is_empty(self):
        return not any(self._code)

    def __str__(self):
        return "\n".join(str(i) for q in self._code for i in q)


def agenda_tester(righe, out):
    righe = (r.rstrip("\n") for r in righe)
    ag = Agenda()
    for cmd in righe:
        if cmd == "Q":
            break
        try:
            if cmd == "I":
                p, memo = next(righe).split(None, 1)       # una sola divisione
                ag.insert(Impegno(int(p), memo.strip()))
            elif cmd == "R":
                print("rimosso:", ag.remove().memo, file=out)
            elif cmd == "L":
                print("primo:", ag.first().memo, file=out)
        except EmptyQueueException as e:
            print("errore:", e, file=out)
        print(ag, file=out)                                # agenda aggiornata dopo ogni comando
        print(file=out)


impegni = ["I", "0 Studiare polimorfismo!", "I", "3 Restituire prestito a Gigi", "I", "2 Email a coso",
           "L", "R", "I", "1 Comprare Aperol x spritz", "I", "0 Iscrizione esame! ", "L", "R", "Q"]
out = io.StringIO()
agenda_tester(impegni, out)
print(out.getvalue())

Traccia dei primi comandi. Dopo i tre I l'agenda è (per priorità) 0 Studiare polimorfismo!, 2 Email a coso, 3 Restituire prestito a Gigi. L stampa primo: Studiare polimorfismo! senza modificare. R lo rimuove (rimosso: Studiare polimorfismo!) e restano 2 Email a coso, 3 Restituire prestito a Gigi. Poi 1 Comprare Aperol x spritz va in testa (priorità 1 < 2) e 0 Iscrizione esame! le passa davanti: i successivi L e R agiscono su quest'ultimo. Alla fine restano:

1 Comprare Aperol x spritz
2 Email a coso
3 Restituire prestito a Gigi

Verifica

python

out = io.StringIO()
agenda_tester(["R", "L", "Q"], out)                        # su agenda vuota
assert out.getvalue().count("errore: agenda vuota") == 2

a = Agenda()
for p, m in [(2, "x"), (0, "a"), (0, "b"), (3, "z"), (1, "y")]:
    a.insert(Impegno(p, m))
usciti = []
while not a.is_empty():
    usciti.append(a.remove().memo)
assert usciti == ["a", "b", "y", "x", "z"]                 # per priorità; a pari priorità FIFO

try:
    Impegno(4, "troppo")
except ValueError:
    pass

m = MultiCoda(3)
assert [m.aggiungi(c) for c in "abcdefg"] == [0, 1, 2, 0, 1, 2, 0]
assert m.rimuovi(0) == "a" and m.aggiungi("h") == 0        # la coda 0 è tornata la più corta
try:
    MultiCoda(0)
except ValueError:
    pass
print("ok")

Errori comuni

In A e R leggere l'argomento con un secondo iteratore (o ricominciare a leggere il file): l'argomento deve essere la riga successiva dello stesso flusso.
Cercare la coda più corta con max o con len della lista di code (numero di code, non di persone).
Dividere il promemoria con split() semplice: perde gli spazi interni; serve split(None, 1).
Nella coda con priorità estrarre l'ultimo inserito (comportamento da pila) invece del primo della coda di livello minore.
Rimuovere da una coda vuota senza segnalarlo; non stampare l'agenda dopo ogni comando.

Versione ripasso

Prove di "appello simulato" di Fondamenti di Informatica (UniPD, in Java; adattato a Python). Teoria: Pila e coda, Realizzare contenitori su array e liste.

A. Multicoda ( $N$ sportelli). Lista di $N$ deque; aggiungi: min(range(N), key=lambda k: len(code[k])) (a parità, indice minore); rimuovi(i): popleft, errore se vuota; __str__: CODA i: + persone. Comandi A (nome nella riga dopo), R (indice nella riga dopo), P, Q: un solo iteratore e next(righe) per l'argomento. Con $N = 4$ e dodici arrivi ogni coda ha 3 persone; dopo R 2 due volte (Ciccio, Gastone) la coda 2 è la più corta e riceve Paperina e Paperone.

B. Agenda (coda con priorità a 4 livelli, 0 = massima). Una deque per livello: insert $O(1)$ ; first/remove sulla prima coda non vuota (EmptyQueueException se tutte vuote), FIFO a pari priorità; __str__ per livelli. I: p, memo = next(righe).split(None, 1); R stampa il promemoria del primo e lo toglie; L lo stampa soltanto; si stampa l'agenda dopo ogni comando. Priorità fuori da $[0, 3]$ → ValueError.

Errori comuni: secondo iteratore per l'argomento; split() che perde gli spazi interni; estrazione da pila invece che da coda; coda vuota non segnalata; agenda non stampata dopo ogni comando.

Esercizio 17multicoda e agenda con priorità

Parte A: multicoda

Parte B: coda con priorità

Verifica

Errori comuni

Teoria collegata