Temario Lección 134 de 148 · Gánale a tu Fantasma
Gánale a tu Fantasma

Sin caché: descuentos heredados

Por qué importa "Repite trabajo, así que recuerda las respuestas" es uno de los hábitos más fuertes de la programación, humana o de IA. A veces el trabajo no necesita repetirse en absoluto.

Las categorías de una tienda forman un árbol: Jardín está bajo Hogar, Herramientas bajo Jardín, y así. Una responsable de marketing puede poner un descuento en cualquier categoría, y se aplica a todo lo que hay debajo salvo que una categoría más cercana ponga el suyo. El pago consulta el descuento efectivo de miles de categorías a la vez.

Los datos

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]

El arreglo obvio para los recorridos repetidos hacia arriba del árbol es una caché. En este problema las cachés están prohibidas. Busca una forma que nunca repita el trabajo desde el principio.

Tu turno

Escribe effective_discounts(parents, own, queries). parents relaciona cada categoría con su padre, o con None para una categoría de nivel superior (puede haber varias, y el diccionario no está en ningún orden concreto). own relaciona algunas categorías con su propio descuento. Para cada categoría de queries, devuelve el descuento de la categoría más cercana en su camino hacia arriba, empezando por ella misma, que tenga uno en own; 0 si ninguna lo tiene. Regla: nada de caché ni memo: ningún decorador de caché de functools, ningún nombre que contenga "cache" o "memo", y nada de calcular las respuestas a medida que las piden las consultas y guardarlas (un memo con otro nombre). Recorre primero el árbol entero, y luego lee las consultas. Presupuesto: como mucho 500,000 pasos (steps()) para 3,000 categorías, árboles de hasta unos cientos de niveles de profundidad y 20,000 consultas.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.