Geen cache: geërfde kortingen
Waarom dit ertoe doet "Het herhaalt werk, dus onthoud de antwoorden" is een van de sterkste gewoonten in programmeren, mens of AI. Soms hoeft het werk helemaal niet te worden herhaald.
A shop vormen een boom: Garden staat onder Home, Tools onder Garden, enzovoort. Een marketingmanager kan een korting instellen op elke categorie, en deze geldt voor alles daaronder tenzij een dichere categorie zijn eigen korting instelt. De checkout zoekt de effectieve korting op voor duizenden categorieën tegelijk.
De 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]De voor de hand liggende oplossing voor herhaalde wandelingen door de boom is een cache. In dit probleem zijn caches verboden. Zoek naar een manier die de arbeid in de eerste plaats nooit herhaalt.
Schrijf effective_discounts(parents, own, queries). parents koppelt elke categorie aan zijn ouder, of None voor een topcategorie (er kunnen er meerdere zijn, en de dictionary staat niet in een specifieke volgorde). own koppelt sommige categorieën aan hun eigen korting. Voor elke categorie in queries geef je de korting van de dichtstbijzijnde categorie op zijn pad naar de top terug, beginnend bij zichzelf, die er een heeft in own; 0 als geen enkele dat heeft. Regel: geen cache of memo: geen functools cache decorators, geen naam met "cache" of "memo", en geen werkende antwoorden als de queries erom vragen en ze bewaren (een memo onder een andere naam). Loop eerst door de hele boom, lees dan de queries. Budget: maximaal 500.000 stappen (steps()) voor 3.000 categorieën, bomen tot een paar honderd niveaus diep, en 20.000 zoekopdrachten.
Een probleem ontdekt in deze les? Meld het · Vraag naar deze les
Deze oefening opent binnenkort
Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.
Deze browser blokkeert cookies voor learn.floati.life, dus lessen die je hier hebt afgerond kunnen niet in de juiste volgorde worden geopend. Sta cookies toe voor deze site en laad de pagina opnieuw.