Programme Leçon 134 sur 148 · Bats ton Fantôme
Bats ton Fantôme

Pas de cache : les remises héritées

Pourquoi c'est important « Ça répète du travail, donc retiens les réponses » est une des habitudes les plus fortes en programmation, humaine ou IA. Parfois, le travail n'a pas du tout besoin d'être répété.

Les catégories d'une boutique forment un arbre : Jardin est sous Maison, Outils sous Jardin, et ainsi de suite. Une personne du marketing peut fixer une remise sur n'importe quelle catégorie, et elle s'applique à tout ce qui est en dessous sauf si une catégorie plus proche fixe la sienne. La caisse cherche la remise effective de milliers de catégories à la fois.

Les données

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 solution évidente aux remontées répétées dans l'arbre est un cache. Dans ce problème, les caches sont interdits. Cherche une façon qui ne répète jamais le travail au départ.

À ton tour

Écris effective_discounts(parents, own, queries). parents associe chaque catégorie à son parent, ou à None pour une catégorie de premier niveau (il peut y en avoir plusieurs, et le dict n'est dans aucun ordre particulier). own associe certaines catégories à leur propre remise. Pour chaque catégorie de queries, renvoie la remise de la catégorie la plus proche sur son chemin vers le haut, en commençant par elle-même, qui en a une dans own ; 0 si aucune n'en a. Règle : pas de cache ni de mémo : pas de décorateurs de cache de functools, pas de nom contenant « cache » ou « memo », et pas de réponses calculées au fur et à mesure que les requêtes les demandent puis gardées (un mémo sous un autre nom). Parcours d'abord tout l'arbre, puis lis les requêtes. Budget : au plus 500 000 étapes (steps()) pour 3 000 catégories, des arbres jusqu'à quelques centaines de niveaux de profondeur, et 20 000 recherches.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.