Программа курса Урок 134 из 148 · Победите своего Призрака
Победите своего Призрака

Без кэша: унаследованные скидки

Почему это важно "Это повторяет работу, так что запомни ответы" - одна из сильнейших привычек в программировании, у людей и у ИИ. Иногда работу вообще не нужно повторять.

Категории магазина образуют дерево: Garden стоит под Home, Tools под Garden и так далее. Маркетолог может задать скидку на любую категорию, и она применяется ко всему ниже неё, если только более близкая категория не задаёт свою. Касса ищет действующую скидку сразу для тысяч категорий.

Данные

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]

Очевидное исправление повторных подъёмов по дереву - кэш. В этой задаче кэши запрещены. Ищите способ, который вообще никогда не повторяет работу.

Твоя очередь

Напишите effective_discounts(parents, own, queries). parents сопоставляет каждой категории её родителя или None для категории верхнего уровня (их может быть несколько, и dict без определённого порядка). own сопоставляет некоторым категориям их собственную скидку. Для каждой категории в queries верните скидку ближайшей категории на её пути к вершине, начиная с неё самой, у которой она есть в own; 0, если ни у одной нет. Правило: никакого кэша или memo: никаких кэширующих декораторов functools, никаких имён, содержащих "cache" или "memo", и никакого вычисления ответов по мере того, как их спрашивают запросы, с их сохранением (memo под другим именем). Сначала пройдите всё дерево, затем читайте запросы. Бюджет: не больше 500 000 шагов (steps()) для 3 000 категорий, деревьев глубиной до нескольких сотен уровней и 20 000 поисков.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.