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.
É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.
Ce navigateur bloque les cookies pour learn.floati.life, donc les leçons que tu as terminées ici ne peuvent pas s'ouvrir dans l'ordre. Autorise les cookies pour ce site et recharge la page.