Conteúdo do curso Lição 134 de 148 · Supere seu Fantasma
Supere seu Fantasma

Sem cache: descontos herdados

Por que isso importa "Ele repete o trabalho, então lembre das respostas" é um dos hábitos mais fortes em programação, humana ou de IA. Às vezes o trabalho não precisa ser repetido de jeito nenhum.

As categorias da loja

A formam uma árvore: Jardim fica sob Casa, Ferramentas sob Jardim, e assim por diante. Um gerente de marketing pode definir um desconto em qualquer categoria, e ele se aplica a tudo abaixo dela, a menos que uma categoria mais próxima defina a sua própria. O checkout busca o desconto efetivo para milhares de categorias de uma só vez.

Os dados

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]

A correção óbvia para caminhadas repetidas na árvore é um cache. Neste problema, caches são proibidos. Procure por uma forma que nunca repita o trabalho desde o início.

Sua vez

Escreva effective_discounts(parents, own, queries). parents mapeia cada categoria para seu pai, ou None para uma categoria de nível superior (pode haver várias, e o dicionário não está em nenhuma ordem específica). own mapeia algumas categorias para seu próprio desconto. Para cada categoria em queries, retorne o desconto da categoria mais próxima em seu caminho para o topo, começando por ela mesma, que tenha um em own; 0 se nenhuma tiver. Regra: sem cache ou memo: nenhum functools cache decorators, nenhum nome contendo "cache" ou "memo", e nenhuma resposta de trabalho para fora, pois as consultas pedem e mantêm elas (um memo com outro nome). Percorra a árvore inteira primeiro, depois leia as consultas. Orçamento: no máximo 500.000 passos (steps()) para 3.000 categorias, árvores de até algumas centenas de níveis de profundidade, e 20.000 buscas.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.