Lehrplan Lektion 134 von 148 · Überliste deinen Geist
Überliste deinen Geist

Kein Cache: vererbte Rabatte

Warum das wichtig ist "Es wiederholt Arbeit, also merke dir die Antworten" ist eine der stärksten Gewohnheiten in der Programmierung, ob Mensch oder KI. Manchmal muss die Arbeit gar nicht wiederholt werden.

A Kategorien eines Shops bilden einen Baum: Garten liegt unter Heim, Werkzeuge unter Garten und so weiter. Ein Marketingmanager kann einen Rabatt auf jede Kategorie festlegen, und dieser gilt für alles darunter, sofern keine nähere Kategorie einen eigenen festlegt. Der Checkout sucht den effektiven Rabatt für tausende Kategorien gleichzeitig heraus.

Die Daten

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]

Die offensichtliche Lösung für wiederholte Wege im Baum ist ein Cache. In diesem Problem sind Caches verboten. Suche nach einem Weg, der die Arbeit von vornherein nie wiederholt.

Du bist dran

Schreibe effective_discounts(parents, own, queries). parents ordnet jede Kategorie ihrer übergeordneten Kategorie zu, oder None für eine oberste Kategorie (es kann mehrere geben, und das dict ist in keiner bestimmten Reihenfolge). own ordnet einige Kategorien ihrem eigenen Rabatt zu. Gib für jede Kategorie in queries den Rabatt der nächstgelegenen Kategorie auf ihrem Pfad nach oben zurück, beginnend bei sich selbst, die einen in own hat; 0, wenn keine einen hat. Regel: kein cache oder memo: keine functools cache Dekoratoren, kein Name, der "cache" oder "memo" enthält, und keine fertigen Antworten ausgeben, da die Abfragen danach fragen und sie behalten (ein memo unter anderem Namen). Gehe zuerst den ganzen Baum durch, dann lies die Abfragen. Budget: maximal 500.000 steps (steps()) für 3.000 Kategorien, Bäume bis zu einigen hundert Ebenen tief und 20.000 Lookups.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.