Kurrikulum Leson 134 van 148 · Breek jou Ghost
Breek jou Ghost

Geen cache: geërfde afslagverkortinge

Waarom dit saak maak "Dit herhaal werk, so onthou die antwoorde" is een van die sterkste gewoontes in programmering, mens of KI. Soms hoef die werk glad nie herhaal te word nie.

A winkel se kategorieë vorm 'n boom: Tuin sit onder Huis, Gereedskap onder Tuin, en so aan. 'n Bemarkingsbestuurder kan 'n afslag op enige kategorie stel, en dit geld vir alles daaronder tensy 'n nader kategorie sy eie stel. Die checkout soek die effektiewe afslag vir duisende kategorieë gelyktydig op.

Die data

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 duidelike oplossing vir herhaalde stappe op die boom is 'n cache. In hierdie probleem is caches verbied. Soek 'n manier wat die werk nooit herhaal nie.

Jou beurt

Skryf effective_discounts(parents, own, queries). parents koppel elke kategorie na sy ouer, of None vir 'n topvlak-kategorie (daar kan verskeie wees, en die dict is in geen spesifieke volgorde nie). own koppel sommige kategorieë na hul eie afslag. Vir elke kategorie in queries, gee die afslag van die naaste kategorie op sy pad na die top, beginnend by homself, wat een in own het; 0 as geen een het nie. Rule: geen cache of memo: geen functools cache decorators, geen naam wat "cache" of "memo" bevat, en geen werkende antwoorde uit as die navrae daarvoor vra en dit hou ('n memo onder 'n ander naam). Gaan deur die hele boom eerste, dan lees die navrae. Budget: maksimum 500,000 stappe (steps()) vir 3,000 kategorieë, bome tot 'n paar honderd vlakke diep, en 20,000 soektogte.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.