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.
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.
Este navegador está bloqueando las cookies de learn.floati.life, así que las lecciones que terminaste aquí no se pueden abrir en orden. Permite las cookies de este sitio y recarga.