Programma Lezione 134 di 148 · Batti il tuo Fantasma
Batti il tuo Fantasma

Niente cache: sconti ereditati

Perché è importante "Ripete del lavoro, quindi ricorda le risposte" è una delle abitudini più forti della programmazione, umana o dell'IA. A volte il lavoro non ha bisogno di essere ripetuto affatto.

Le categorie di un negozio formano un albero: Giardino sta sotto Casa, Attrezzi sotto Giardino, e così via. Un responsabile marketing può impostare uno sconto su qualsiasi categoria, e vale per tutto ciò che sta sotto a meno che una categoria più vicina non imposti il proprio. La cassa cerca lo sconto effettivo per migliaia di categorie alla volta.

I dati

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

La soluzione ovvia per le ripetute risalite nell'albero è una cache. In questo problema le cache sono vietate. Cerca un modo che non ripeta mai il lavoro fin dall'inizio.

Tocca a te

Scrivi effective_discounts(parents, own, queries). parents associa ogni categoria al suo genitore, o a None per una categoria di primo livello (possono essercene diverse, e il dict non ha un ordine particolare). own associa alcune categorie al loro sconto. Per ogni categoria in queries, restituisci lo sconto della categoria più vicina sul suo percorso verso l'alto, partendo da se stessa, che ne ha uno in own; 0 se nessuna ce l'ha. Regola: niente cache o memo: niente decoratori di cache di functools, nessun nome che contenga "cache" o "memo", e niente risposte calcolate man mano che le domande le chiedono e poi conservate (un memo con un altro nome). Percorri prima tutto l'albero, poi leggi le domande. Budget: al massimo 500,000 passi (steps()) per 3,000 categorie, alberi profondi fino a qualche centinaio di livelli, e 20,000 ricerche.

Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione

Questo esercizio si apre presto

Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.