"""
Corso Machine Learning Engineer - Modulo 10, Lezione 02
"Tokenizzazione: come il testo diventa numeri, e perche' il modello non sa
contare le lettere"

OBIETTIVO DI QUESTO FILE
------------------------
Il byte pair encoding dell'articolo e' qui GIA' SCRITTO e funzionante: lo trovi
nella prima parte, con il corpus costruito offline dai docstring della libreria
standard. I tre esercizi stanno su terreni che l'articolo nomina e non
implementa, e ognuno ha un criterio di correttezza esterno con cui confrontarsi:

  1. il criterio di WORDPIECE al posto di quello del BPE. Invece di fondere la
     coppia piu' frequente si fonde quella che massimizza

         punteggio(a, b) = c(ab) / ( c(a) * c(b) )

     cioe' la coppia che ricorre piu' di quanto ricorrerebbe se i due pezzi
     fossero indipendenti. Il controllo e' doppio: le prime fusioni DEVONO
     essere diverse da quelle del BPE (il BPE parte dalle sequenze di spazi,
     WordPiece dagli acronimi), e la compressione finale DEVE essere
     SENSIBILMENTE PEGGIORE, perche' questo criterio non ottimizza la
     compressione. Se ti ritrovi le stesse fusioni del BPE, hai dimenticato
     il denominatore;

  2. la FERTILITA' di un tokenizzatore, cioe' i token per parola, misurata su
     una coppia di testi paralleli italiano/inglese, e il preventivo di quante
     parti serve un documento per entrare in una finestra di contesto. I numeri
     dell'articolo con llama3.1:8b sono 1.5547 token per parola in italiano e
     1.1429 in inglese: il tokenizzatore di questo file e' molto piu' piccolo e
     dara' numeri piu' alti (intorno a 3.4 e 2.6), ma il RAPPORTO fra le due
     lingue deve restare vicino a 1.3;

  3. un TRONCAMENTO che non spezza mai un carattere multibyte. Tagliare una
     lista di identificativi a un numero fisso puo' interrompere una sequenza
     UTF-8 a metà, e la decodifica produce U+FFFD (il carattere di
     sostituzione) senza sollevare nulla. Il controllo e' esatto: la stringa
     troncata non deve contenere U+FFFD, e deve essere la piu' lunga possibile
     entro il limite. Con le 384 fusioni di questo file la parola "perche'"
     accentata diventa CINQUE token, mentre nell'articolo, con 768 fusioni su
     un corpus piu' grande, sono quattro: i numeri cambiano col
     tokenizzatore, l'invariante no.

COME SI USA
-----------
    python3 esercizi.py

Il file gira anche cosi' com'e': stampa quali esercizi mancano ancora, e
risolve i tre in qualunque ordine li completi (ognuno e' indipendente dagli
altri due).

AMBIENTE DICHIARATO
-------------------
Python 3.12+ e la SOLA libreria standard. Nessun pacchetto da installare,
nessuna rete, nessun download. Eseguito e verificato con Python 3.14.4.

I conteggi del corpus dipendono dalla versione di Python, perche' i docstring
della libreria standard cambiano fra una versione e l'altra: il file stampa i
propri numeri invece di darli per noti, quindi i tuoi controlli restano validi
su qualunque versione.
"""

import importlib
import inspect
import re
import unicodedata
from collections import Counter

# ----------------------------------------------------------------------
# PARTE GIA' SCRITTA - il corpus e il BPE dell'articolo
#
# Il corpus e' ridotto a 16 moduli (invece degli 81 dell'articolo) perche'
# l'addestramento deve finire in pochi secondi su qualunque macchina.
# ----------------------------------------------------------------------

MODULI = (
    "argparse", "collections", "csv", "dataclasses", "datetime", "fractions",
    "functools", "heapq", "itertools", "json", "pathlib", "re", "statistics",
    "string", "textwrap", "typing",
)

N_FUSIONI = 384
SOGLIA_WORDPIECE = 20          # frequenza minima perche' una coppia sia candidata

PEZZI = re.compile(r" ?\w+| ?[^\s\w]+|\s+")
PAROLE = re.compile(r"\w+")

TESTO_IT = (
    "La finestra di contesto di un modello si misura in token, non in parole. "
    "Quando carichi un documento lungo dentro una richiesta, quello che conta "
    "non è quante pagine ha, ma quanti token produce il tokenizzatore su quel "
    "testo. Due documenti della stessa lunghezza in caratteri possono costare "
    "un numero di token molto diverso: dipende dalla lingua, dalla presenza di "
    "nomi propri, di codice, di numeri e di sigle. Perciò la prima misura da "
    "fare, prima di stimare una spesa o di decidere una strategia di "
    "suddivisione, è contare i token sul materiale vero e non su un campione "
    "inventato. Chi salta questa misura scopre il problema quando la richiesta "
    "viene rifiutata perché supera la finestra, oppure quando il conto arriva "
    "al doppio di quello che aveva previsto."
)

TESTO_EN = (
    "The context window of a model is measured in tokens, not in words. "
    "When you load a long document into a request, what counts "
    "is not how many pages it has, but how many tokens the tokeniser produces on "
    "that text. Two documents of the same length in characters can cost "
    "a very different number of tokens: it depends on the language, on the presence "
    "of proper nouns, of code, of numbers and of acronyms. So the first measurement "
    "to take, before estimating a cost or deciding a splitting "
    "strategy, is to count the tokens on the real material and not on a made-up "
    "sample. Whoever skips this measurement discovers the problem when the request "
    "is rejected because it exceeds the window, or when the bill arrives "
    "at twice what they had expected."
)


def costruisci_corpus():
    """Concatena i docstring dei moduli elencati e dei loro oggetti pubblici."""
    pezzi = []
    for nome in MODULI:
        try:
            modulo = importlib.import_module(nome)
        except Exception:
            continue
        testo = inspect.getdoc(modulo)
        if testo:
            pezzi.append(testo)
        for attributo in sorted(dir(modulo)):      # sorted: l'ordine deve essere deterministico
            if attributo.startswith("_"):
                continue
            oggetto = getattr(modulo, attributo, None)
            if not (inspect.isfunction(oggetto) or inspect.isclass(oggetto)):
                continue
            testo = inspect.getdoc(oggetto)
            if testo:
                pezzi.append(testo)
    return "\n\n".join(pezzi)


def frequenze_iniziali(testo):
    """Ogni pezzo distinto diventa una tupla di byte, con la sua frequenza."""
    return {tuple(pezzo.encode("utf-8")): quante
            for pezzo, quante in Counter(PEZZI.findall(testo)).items()}


def conta_coppie(frequenze):
    """Quante volte ogni coppia di simboli adiacenti compare nel corpus."""
    coppie = Counter()
    for simboli, quante in frequenze.items():
        for coppia in zip(simboli, simboli[1:]):
            coppie[coppia] += quante
    return coppie


def conta_simboli(frequenze):
    """Quante volte ogni singolo simbolo compare nel corpus."""
    simboli = Counter()
    for sequenza, quante in frequenze.items():
        for simbolo in sequenza:
            simboli[simbolo] += quante
    return simboli


def fondi(simboli, coppia, nuovo):
    """Sostituisce ogni occorrenza di `coppia` con il simbolo `nuovo`."""
    uscita, i = [], 0
    while i < len(simboli):
        if i < len(simboli) - 1 and (simboli[i], simboli[i + 1]) == coppia:
            uscita.append(nuovo)
            i += 2
        else:
            uscita.append(simboli[i])
            i += 1
    return tuple(uscita)


def scegli_coppia_bpe(coppie, simboli):
    """Criterio del BPE: la coppia piu' frequente. I pareggi sono risolti in
    modo stabile sugli identificativi, cosi' due esecuzioni danno lo stesso
    vocabolario."""
    return max(coppie.items(), key=lambda kv: (kv[1], -kv[0][0], -kv[0][1]))[0]


def allena(testo, n_fusioni, criterio=scegli_coppia_bpe, traccia=0, etichetta=""):
    """Impara `n_fusioni` fusioni con il `criterio` dato.

    Ritorna (fusioni, vocabolario), oppure (None, None) se il criterio non e'
    ancora stato implementato (cioe' se ritorna None).
    """
    frequenze = frequenze_iniziali(testo)
    vocabolario = {i: bytes([i]) for i in range(256)}
    fusioni = {}
    for passo in range(n_fusioni):
        coppie = conta_coppie(frequenze)
        if not coppie:
            break
        coppia = criterio(coppie, conta_simboli(frequenze))
        if coppia is None:
            return None, None
        nuovo = 256 + passo
        fusioni[coppia] = nuovo
        vocabolario[nuovo] = vocabolario[coppia[0]] + vocabolario[coppia[1]]
        frequenze = {fondi(s, coppia, nuovo): q for s, q in frequenze.items()}
        if passo < traccia:
            print(f"    {etichetta}fusione {passo + 1:>2}: "
                  f"{vocabolario[nuovo]!r}   ({coppie[coppia]} occorrenze)")
    return fusioni, vocabolario


def codifica_pezzo(simboli, fusioni):
    """Riapplica le fusioni a un singolo pezzo, in ordine di apprendimento."""
    simboli = list(simboli)
    while len(simboli) >= 2:
        candidate = [(fusioni[c], c) for c in zip(simboli, simboli[1:]) if c in fusioni]
        if not candidate:
            break
        _, coppia = min(candidate)                 # min sul rango = la fusione imparata prima
        simboli = list(fondi(tuple(simboli), coppia, fusioni[coppia]))
    return simboli


def codifica(testo, fusioni):
    uscita = []
    for pezzo in PEZZI.findall(testo):
        uscita.extend(codifica_pezzo(tuple(pezzo.encode("utf-8")), fusioni))
    return uscita


def decodifica(identificativi, vocabolario):
    grezzo = b"".join(vocabolario[i] for i in identificativi)
    return grezzo.decode("utf-8", errors="replace")


SOSTITUZIONE = "�"        # il carattere che compare quando l'UTF-8 e' incompleto


# ----------------------------------------------------------------------
# ESERCIZIO 1 - Il criterio di WordPiece
#
# Il BPE fonde la coppia piu' frequente. WordPiece (M. Schuster e
# K. Nakajima, "Japanese and Korean Voice Search", ICASSP 2012) fonde quella
# che fa crescere di piu' la verosimiglianza di un modello unigramma, che in
# pratica equivale a massimizzare
#
#     punteggio(a, b) = c(ab) / ( c(a) * c(b) )
#
# dove c(ab) e' il numero di occorrenze della coppia adiacente e c(a), c(b)
# sono le occorrenze dei due simboli presi da soli. Il numeratore premia le
# coppie frequenti, il denominatore penalizza i pezzi che sono gia' frequenti
# per conto loro: il risultato premia le coppie che "stanno insieme piu' del
# dovuto".
#
# Devi scrivere la funzione che, date le coppie e i conteggi dei simboli,
# ritorna la coppia col punteggio massimo.
#
# DUE TRAPPOLE, ed e' per questo che l'esercizio esiste:
#
#   (a) senza una soglia di frequenza minima il criterio sceglie coppie che
#       compaiono DUE volte in tutto il corpus, perche' se i due simboli
#       compaiono solo in quella coppia il punteggio e' enorme. Il runner
#       filtra le coppie sotto SOGLIA_WORDPIECE (20), e anche cosi' le prime
#       fusioni atterrano esattamente sulla soglia: prova a metterla a 1 e
#       guarda che fusioni vengono fuori;
#   (b) i pareggi vanno risolti in modo deterministico, altrimenti due
#       esecuzioni dello stesso codice danno vocabolari diversi. Usa la stessa
#       chiave di spareggio del BPE: a parita' di punteggio, l'identificativo
#       piu' piccolo.
# ----------------------------------------------------------------------


def scegli_coppia_wordpiece(coppie, simboli):
    """Criterio di WordPiece: la coppia col punteggio c(ab)/(c(a)*c(b)) massimo.

    Parametri
    ---------
    coppie  : dict {(a, b): occorrenze della coppia adiacente}
    simboli : dict {a: occorrenze del simbolo a}

    Ritorna
    -------
    La coppia scelta, cioe' una tupla (a, b); oppure None se non svolto.

    Suggerimento: le coppie sono gia' filtrate per frequenza dal runner, quindi
    qui non devi preoccuparti della soglia. Ti serve una sola riga con `max` e
    una chiave che calcoli il punteggio, piu' lo spareggio deterministico.
    """
    # TODO (esercizio 1): sostituisci `return None` con la scelta della coppia.
    return None


# ----------------------------------------------------------------------
# ESERCIZIO 2 - Fertilita' e preventivo in parti
#
# La "fertilita'" di un tokenizzatore su un testo e' il numero medio di token
# per parola:
#
#     fertilita' = numero di token / numero di parole
#
# E' la grandezza che serve per rispondere alle due domande che si fanno
# davvero: quanto mi costa questo documento, e in quante parti devo tagliarlo
# perche' entri nella finestra di contesto.
#
# Conta le parole con PAROLE.findall (la stessa espressione regolare usata
# nell'articolo), non con split(): la punteggiatura attaccata falserebbe il
# conto in modo diverso nelle due lingue. Il brano inglese risultera' di 134
# parole invece delle 133 dell'articolo, perche' "made-up" per \w+ sono due
# parole e per split() una: e' il genere di differenza che va dichiarata e non
# nascosta, perche' finisce al denominatore di una metrica.
#
# Per il preventivo, la finestra utile e' (finestra - riservati): i token
# riservati sono quelli che lasci alla risposta, e se non li sottrai il conto
# torna finche' il modello non risponde.
#
# Attenzione al caso limite che un test di produzione prima o poi incontra:
# se la finestra utile e' zero o negativa, non esiste nessun numero di parti
# che risolva il problema. La funzione deve dirlo, non dividere per zero.
# ----------------------------------------------------------------------


def fertilita(testo, fusioni):
    """Token per parola del `testo` con il tokenizzatore dato.

    Ritorna
    -------
    float, oppure None se non svolto.
    """
    # TODO (esercizio 2a): sostituisci `return None` con il rapporto token/parole.
    return None


def parti_necessarie(n_parole, token_per_parola, finestra, riservati):
    """Quante parti servono per far entrare `n_parole` nella finestra.

    Ritorna
    -------
    int (>= 1), oppure None se non svolto.
    Solleva ValueError se la finestra utile non e' positiva.

    Nessun import aggiuntivo serve: la divisione intera con arrotondamento per
    eccesso si scrive con -(-a // b), e sapere questo idioma e' metà
    dell'esercizio.
    """
    # TODO (esercizio 2b): sostituisci `return None` con il numero di parti.
    return None


# ----------------------------------------------------------------------
# ESERCIZIO 3 - Troncare senza spezzare un carattere
#
# Un identificativo di un BPE a livello di byte puo' contenere BYTE PARZIALI
# di un carattere multibyte. Nell'articolo la parola "perche'" con l'accento
# diventa quattro token, e gli ultimi due sono i due byte della lettera
# accentata presi separatamente: tagliare a tre token produce una sequenza
# UTF-8 incompleta, che decodificata con errors="replace" diventa U+FFFD.
#
# Scrivi una funzione che tronchi a NON PIU' di n_max token, e che fra tutti i
# prefissi ammessi scelga il PIU' LUNGO la cui decodifica non contiene U+FFFD.
#
# Casi limite da gestire, tutti verificati dal runner:
#   - n_max <= 0            -> lista vuota, stringa vuota;
#   - n_max >= len(ids)     -> tutta la lista, se il testo intero e' valido;
#   - il primo token e' gia' un byte parziale -> l'unico prefisso valido e'
#     quello vuoto, e la funzione deve ritornarlo invece di sollevare.
#
# Nota sulla complessita': la soluzione ovvia prova tutti i prefissi da n_max
# verso il basso e decodifica ogni volta, quindi e' quadratica nella lunghezza.
# Su un prompt di 100.000 token si sente. Una versione lineare esiste e
# guarda i byte: un byte di continuazione UTF-8 ha i due bit alti 10, cioe'
# vale (b & 0xC0) == 0x80. Fai prima quella ovvia e poi, se vuoi, l'altra.
# ----------------------------------------------------------------------


def tronca_senza_rompere(identificativi, n_max, vocabolario):
    """Il prefisso piu' lungo di al massimo `n_max` token che decodifica pulito.

    Ritorna
    -------
    (lista di identificativi, stringa decodificata), oppure None se non svolto.
    """
    # TODO (esercizio 3): sostituisci `return None` con il troncamento sicuro.
    return None


# ----------------------------------------------------------------------
# Runner
# ----------------------------------------------------------------------

def _sezione(titolo):
    print()
    print(titolo)
    print("-" * len(titolo))


def _da_fare(numero):
    print(f"  [ ] Esercizio {numero} non ancora svolto: completa il TODO qui sopra.")


def esegui_esercizio_1(testo, fusioni_bpe, vocabolario_bpe):
    _sezione("Esercizio 1 - il criterio di WordPiece contro quello del BPE")

    def criterio_filtrato(coppie, simboli):
        candidate = {c: q for c, q in coppie.items() if q >= SOGLIA_WORDPIECE}
        if not candidate:
            candidate = coppie
        return scegli_coppia_wordpiece(candidate, simboli)

    if criterio_filtrato(conta_coppie(frequenze_iniziali(testo)),
                         conta_simboli(frequenze_iniziali(testo))) is None:
        _da_fare(1)
        return False

    print("  le prime 8 fusioni del BPE (criterio: la coppia piu' frequente)")
    allena(testo, 8, scegli_coppia_bpe, traccia=8, etichetta="BPE  ")
    print(f"  le prime 8 fusioni di WordPiece (soglia {SOGLIA_WORDPIECE})")
    allena(testo, 8, criterio_filtrato, traccia=8, etichetta="WP   ")

    fusioni_wp, vocabolario_wp = allena(testo, N_FUSIONI, criterio_filtrato)
    byte = len(testo.encode("utf-8"))
    for nome, f in (("BPE      ", fusioni_bpe), ("WordPiece", fusioni_wp)):
        ids = codifica(testo, f)
        print(f"  {nome}  {len(ids):>7} token   byte/token {byte / len(ids):.3f}")
    print("  WordPiece comprime meno, e non e' un difetto dell'esercizio:")
    print("  ottimizza la verosimiglianza, non i byte per token.")
    return True


def esegui_esercizio_2(fusioni):
    _sezione("Esercizio 2 - fertilita' e preventivo in parti")
    f_it = fertilita(TESTO_IT, fusioni)
    f_en = fertilita(TESTO_EN, fusioni)
    if f_it is None or f_en is None:
        _da_fare(2)
        return False
    print(f"  italiano  {len(PAROLE.findall(TESTO_IT)):>4} parole   "
          f"fertilita' {f_it:.4f} token/parola")
    print(f"  inglese   {len(PAROLE.findall(TESTO_EN)):>4} parole   "
          f"fertilita' {f_en:.4f} token/parola")
    print(f"  rapporto italiano/inglese {f_it / f_en:.4f}"
          f"   (con llama3.1:8b l'articolo misura 1.3604)")

    parti = parti_necessarie(12_000, f_it, 8192, 1000)
    if parti is None:
        _da_fare(2)
        return False
    print("  un manuale di 12.000 parole, finestra 8192 token, 1000 riservati:")
    for nome, valore in (("italiano", f_it), ("inglese", f_en)):
        n = parti_necessarie(12_000, valore, 8192, 1000)
        print(f"      {nome:9} {12_000 * valore:>9.0f} token -> {n} parti")
    try:
        parti_necessarie(12_000, f_it, 1000, 1000)
    except ValueError as errore:
        print(f"  finestra utile nulla -> ValueError corretto: {errore}")
    else:
        print("  [!] con finestra utile nulla la funzione non ha sollevato ValueError")
    return True


def esegui_esercizio_3(fusioni, vocabolario):
    _sezione("Esercizio 3 - troncare senza spezzare un carattere")
    casi = ("perché", "città", "la finestra di contesto si misura in token", "🍓🍓🍓")
    esito = tronca_senza_rompere(codifica("perché", fusioni), 3, vocabolario)
    if esito is None:
        _da_fare(3)
        return False
    for caso in casi:
        ids = codifica(caso, fusioni)
        print(f"  {caso!r}  ({len(ids)} token)")
        for n_max in range(0, len(ids) + 1):
            tagliati, stringa = tronca_senza_rompere(ids, n_max, vocabolario)
            grezzo = decodifica(ids[:n_max], vocabolario)
            marchio = "  <- il taglio crudo rompeva un carattere" \
                if SOSTITUZIONE in grezzo else ""
            print(f"      n_max {n_max}: {len(tagliati)} token -> {stringa!r}{marchio}")
            assert SOSTITUZIONE not in stringa, "la stringa troncata contiene U+FFFD"
            assert len(tagliati) <= n_max, "troncamento piu' lungo del limite"
    print("  Nessuna stringa troncata contiene U+FFFD: l'invariante tiene.")
    return True


def main():
    print("Corso MLE - Modulo 10, Lezione 02 - esercizi di codice")
    print(f"Python della libreria standard, Unicode {unicodedata.unidata_version}")
    testo = costruisci_corpus()
    print(f"corpus: {len(MODULI)} moduli, {len(testo)} caratteri, "
          f"{len(testo.encode('utf-8'))} byte")
    print(f"addestramento del BPE di riferimento ({N_FUSIONI} fusioni)...")
    fusioni, vocabolario = allena(testo, N_FUSIONI)
    ids = codifica(testo, fusioni)
    print(f"  vocabolario {len(vocabolario)} voci, "
          f"byte/token {len(testo.encode('utf-8')) / len(ids):.3f}")
    assert decodifica(ids, vocabolario) == testo, "andata e ritorno non identico"
    print("  andata e ritorno sull'intero corpus: identico")

    fatti = 0
    fatti += bool(esegui_esercizio_1(testo, fusioni, vocabolario))
    fatti += bool(esegui_esercizio_2(fusioni))
    fatti += bool(esegui_esercizio_3(fusioni, vocabolario))
    print()
    print(f"Esercizi completati: {fatti} su 3.")
    if fatti < 3:
        print("Completa i TODO e rilancia: python3 esercizi.py")



# ----------------------------------------------------------------------
# SOLUZIONI COMMENTATE
#
# Decommenta una funzione alla volta e rilancia: il runner le riconosce una
# per una, in qualunque ordine.
#
# --- Esercizio 1 -------------------------------------------------------
# def scegli_coppia_wordpiece(coppie, simboli):
#     return max(
#         coppie.items(),
#         key=lambda kv: (kv[1] / (simboli[kv[0][0]] * simboli[kv[0][1]]),
#                         -kv[0][0], -kv[0][1]),
#     )[0]
#
# Cosa aspettarsi. Con la soglia a 20 le prime fusioni di WordPiece sono
# 'JS', 'JSO', 'JSON', 'BC', 'ABC', 'SC', 'ASC', 'ASCI': acronimi, cioe'
# sequenze le cui lettere non compaiono quasi mai altrove. Il BPE invece
# comincia dalle sequenze di spazi, che sono frequentissime ma anche
# frequentissime da sole, quindi il denominatore le affossa.
# Sulla compressione il confronto e' netto e va nella direzione che sorprende:
# 2.291 byte per token con il BPE contro 1.367 con WordPiece, cioe' il 40% in
# meno. Non e' un errore tuo: il criterio di WordPiece ottimizza la
# verosimiglianza di un modello unigramma, non la compressione, e su un
# vocabolario piccolo spende le sue prime voci su pezzi informativi e rari.
# Togliendo la soglia (SOGLIA_WORDPIECE = 1) il criterio sceglie coppie con
# due occorrenze in tutto il corpus, perche' per loro il punteggio e' 1/2
# mentre per una coppia frequentissima e' dell'ordine di 1e-4. E' il motivo
# per cui ogni implementazione reale di WordPiece ha una frequenza minima.
#
# --- Esercizio 2 -------------------------------------------------------
# def fertilita(testo, fusioni):
#     return len(codifica(testo, fusioni)) / len(PAROLE.findall(testo))
#
#
# def parti_necessarie(n_parole, token_per_parola, finestra, riservati):
#     utile = finestra - riservati
#     if utile <= 0:
#         raise ValueError(f"finestra utile non positiva: {utile} token")
#     token = n_parole * token_per_parola
#     return max(1, -(-int(token) // utile))
#
# Cosa aspettarsi. Il tokenizzatore di questo file ha 640 voci contro le
# decine di migliaia dei modelli veri, quindi le fertilita' assolute sono
# molto piu' alte di 1.5547 e 1.1429: sono i numeri di un vocabolario
# piccolo. Il RAPPORTO fra le due lingue, invece, resta vicino a quello
# misurato nell'articolo, perche' dipende da quanto il corpus di
# addestramento assomiglia alla lingua che stai tokenizzando - e qui il
# corpus e' inglese in entrambi i casi.
#
# Sul max(1, ...): un documento di zero parole ha bisogno di una parte, non di
# zero. Se non lo metti, il preventivo di un documento vuoto e' "0 parti" e un
# ciclo a valle non gira mai.
#
# --- Esercizio 3 -------------------------------------------------------
# def tronca_senza_rompere(identificativi, n_max, vocabolario):
#     n = max(0, min(n_max, len(identificativi)))
#     while n >= 0:
#         candidato = identificativi[:n]
#         stringa = decodifica(candidato, vocabolario)
#         if SOSTITUZIONE not in stringa:
#             return candidato, stringa
#         n -= 1
#     return [], ""
#
# Cosa aspettarsi. Su "perche'" con l'accento, cinque token con questo
# tokenizzatore, il taglio crudo a 4 token produce "perch" piu' U+FFFD:
# questa funzione torna indietro di un token e restituisce "perch".
# Su "🍓🍓🍓" ogni emoji e' quattro byte e quindi quattro token: i tagli a
# 1, 2 e 3 token tornano tutti alla stringa vuota, perche' non esiste nessun
# prefisso valido piu' corto di quattro.
#
# Variante lineare, se vuoi farla: invece di decodificare a ogni giro, scorri
# i byte del candidato dalla fine e scarta i byte di continuazione, cioe'
# quelli con (b & 0xC0) == 0x80, fino a trovare un byte iniziale; poi
# controlla che la sequenza che inizia li' sia completa guardando i bit alti
# del byte iniziale (110xxxxx = 2 byte, 1110xxxx = 3, 11110xxx = 4). La
# versione quadratica va benissimo per un prompt; quella lineare serve quando
# tronchi un corpus.
#
# UN'ULTIMA NOTA, che vale piu' dei tre esercizi. L'invariante "nessun U+FFFD"
# e' verificabile, e per questo l'esercizio ha un asserto. Il troncamento a
# meta' di una PAROLA non lo e': "Quando c" e' una stringa perfettamente
# valida. E' il motivo per cui il taglio sicuro non si fa sui token ma sui
# confini che decidi tu - paragrafi, frasi, blocchi - misurando i token di
# ciascuno prima di spedire.
# ----------------------------------------------------------------------


if __name__ == "__main__":
    main()
