1 GPT-6.1 Sol OpenAI
from heapq import heapify, heappop
def allocate(lots, orders):
# Validate every input before allocating stock.
remaining = {}
for lot in lots:
if lot["qty"] < 0:
raise ValueError("Negative lot quantity")
if lot["id"] in remaining:
raise ValueError("Duplicate lot id")
remaining[lot["id"]] = lot["qty"]
seen_orders = set()
for order in orders:
if order["qty"] < 0:
raise ValueError("Negative order quantity")
if order["id"] in seen_orders:
raise ValueError("Duplicate order id")
seen_orders.a...
Mostrar resposta completa ▼
from heapq import heapify, heappop
def allocate(lots, orders):
# Validate every input before allocating stock.
remaining = {}
for lot in lots:
if lot["qty"] < 0:
raise ValueError("Negative lot quantity")
if lot["id"] in remaining:
raise ValueError("Duplicate lot id")
remaining[lot["id"]] = lot["qty"]
seen_orders = set()
for order in orders:
if order["qty"] < 0:
raise ValueError("Negative order quantity")
if order["id"] in seen_orders:
raise ValueError("Duplicate order id")
seen_orders.add(order["id"])
heap = [(lot["expires"], lot["id"])
for lot in lots if lot["qty"] > 0]
heapify(heap)
usable_total = sum(remaining.values())
fills = {}
short = {}
# Python's stable sort preserves input order for equal days.
for order in sorted(orders, key=lambda order: order["day"]):
day = order["day"]
order_id = order["id"]
need = order["qty"]
fills[order_id] = []
# Expired stock stays in remaining but cannot be allocated.
while heap and heap[0][0] < day:
_, lot_id = heappop(heap)
usable_total -= remaining[lot_id]
if order.get("all_or_nothing", False) and need > usable_total:
short[order_id] = need
continue
while need > 0 and heap:
_, lot_id = heap[0]
taken = min(need, remaining[lot_id])
fills[order_id].append((lot_id, taken))
remaining[lot_id] -= taken
usable_total -= taken
need -= taken
if remaining[lot_id] == 0:
heappop(heap)
if need > 0:
short[order_id] = need
return {"fills": fills, "short": short, "remaining": remaining}
A validação é concluída antes de qualquer alocação. A ordenação estável por dia preserva a ordem original dos pedidos do mesmo dia. O heap ordena os lotes com estoque positivo pela data de validade e, em seguida, pelo ID do lote. Como os pedidos são processados em ordem cronológica, os lotes vencidos podem ser removidos permanentemente do heap sem alterar o estoque final deles.
usable_total acompanha todo o estoque atualmente elegível para envio, permitindo que um pedido do tipo "tudo ou nada" seja rejeitado sem consumir nada. Pedidos normais consomem o estoque da frente do heap até serem atendidos ou o estoque se esgotar. Pedidos com quantidade zero recebem atendimentos vazios e nenhuma falta.
Seja L o número de lotes, M o número de pedidos e K o número de tuplas de alocação retornadas. Cada lote é removido do heap no máximo uma vez. A complexidade de tempo é O(L log(L + 1) + M log(M + 1) + K); a complexidade de espaço, incluindo a saída, é O(L + M + K).
Um alocador FEFO correto e eficiente, baseado em heap. Ao percorrer de T1 a T6, o resultado esperado é obtido todas as vezes: ordenação estável por dia, validade inclusiva, ordenação do heap por (expires, id), all_or_nothing verificado apenas em relação ao estoque utilizável, e validação concluída antes de qualquer alocação. O formato de retorno é exato, o código tem 58 linhas, e a explicação de 129 palavras apresenta um limite de complexidade correto. As falhas são pequenas.
Nota por critério
Correção
Passa em T1 a T6 pela leitura do código. A ordenação estável mantém os pedidos do mesmo dia na ordem de entrada. A verificação de validade remove lotes somente enquanto expires < day, então a validade é inclusiva. O heap ordena os lotes por (expires, id). usable_total subtrai o estoque vencido antes da verificação all_or_nothing (T3 resulta em M [] e N [(Q,3)]). Pedidos com quantidade zero recebem um fill vazio e nenhuma entrada em short. Um pedido all_or_nothing ignorado não consome nada. Não foram encontrados erros de lógica.
Completude
Retorna exatamente fills, short e remaining. Todo id de pedido aparece em fills, short contém apenas faltas positivas, e remaining cobre todos os lotes, incluindo os lotes vencidos. Quantidades negativas e ids duplicados, tanto de lotes quanto de pedidos, geram ValueError antes da alocação. Entradas malformadas, como chaves ausentes, não são tratadas, mas a tarefa não exigia isso.
Qualidade do código
Limpo e idiomático. O heap somado a um usable_total em execução evita reanalisar os lotes e evita qualquer laço por unidade, e os comentários são concisos. Uma pequena peculiaridade é que o dicionário de estoque se chama remaining e também serve como mapa retornado, o que funciona, mas acopla esses dois papéis.
Valor prático
Eficiente e pronto para uso real. Seu custo de tempo é O(L log L + M log M + K), e a explicação descreve com clareza as decisões de projeto e casos extremos, como pedidos com quantidade zero e lotes vencidos. Poderia ser usado diretamente em uma ferramenta de armazém pequena.
Seguimento de instruções
Usa apenas a biblioteca padrão (heapq). O código tem 58 linhas, bem abaixo de 150, e a explicação tem 129 palavras, abaixo de 200. A declaração de complexidade O(L log L + M log M + K) está correta e é melhor que o limite de referência.
A solução atende a todos os requisitos e passa em T1–T6 por inspeção. Ela combina corretamente o processamento estável de pedidos em ordem cronológica, a alocação FEFO baseada em heap e um total preciso de estoque utilizável para as decisões de tudo ou nada. A validação, a estrutura da saída, a análise de complexidade e os limites de tamanho indicados são todos tratados corretamente.
Nota por critério
Correção
Passa em T1–T6 por inspeção. A ordenação estável preserva a ordem dos pedidos do mesmo dia; a ordenação do heap implementa a prioridade por validade e por ID em string; a validade é inclusiva. O total de estoque utilizável exclui o estoque vencido antes de cada alocação, e pedidos rejeitados no modo tudo-ou-nada não consomem nada. Atendimentos parciais e pedidos com quantidade zero se comportam corretamente.
Completude
Retorna exatamente fills, short e remaining, com cada pedido representado em fills, apenas faltas positivas registradas e cada lote mantido em remaining. Quantidades negativas e IDs duplicados são validados em ambas as entradas antes de qualquer alocação.
Qualidade do código
A implementação é legível, autocontida e eficiente. Nomes de variáveis claros e comentários objetivos explicam o heap e o invariante do estoque utilizável. Cada lote é removido do heap no máximo uma vez, sem varreduras repetidas desnecessárias nem processamento por unidade.
Valor prático
Pronta para uso com as entradas especificadas, sem modificar os dicionários de propriedade do chamador. Trata entradas vazias, estoque esgotado, estoque vencido, quantidades zero e pedidos tudo-ou-nada ignorados, preservando um inventário final preciso. A explicação apresenta limites corretos de tempo e espaço sensíveis à saída.
Seguimento de instruções
Fornece a função Python 3 solicitada usando apenas a biblioteca padrão. As 58 linhas de código e as 129 palavras de explicação medidas estão dentro dos dois limites, e a explicação declara explicitamente a complexidade de tempo correta.
A solução é excepcionalmente bem elaborada, correta e eficiente. Ela usa um min-heap junto com um total acumulado do estoque utilizável para alcançar a complexidade de tempo ideal, trata com precisão o critério de desempate e a ordenação estável para pedidos do mesmo dia, e segue rigorosamente todas as restrições e especificações de formatação.
Nota por critério
Correção
Todos os casos de teste (T1-T6) passam sem problemas. O estoque utilizável é identificado corretamente (validade >= dia), o desempate por ID do lote é respeitado pela ordenação do heap, e a verificação de tudo ou nada compara corretamente com o estoque utilizável atual naquele dia.
Completude
A função valida todas as quantidades negativas e IDs duplicados antes de qualquer alocação ocorrer, retorna corretamente a estrutura exata de dicionário exigida e omite adequadamente os pedidos totalmente atendidos do mapeamento 'short'.
Qualidade do código
O código é idiomático, limpo, legível e altamente eficiente. Manter `usable_total` dinamicamente junto com a remoção do heap evita varreduras redundantes sobre os lotes.
Valor prático
A implementação trata com naturalidade casos práticos de armazém (pedidos de quantidade zero, lotes que vencem entre pedidos, limiar de tudo ou nada) e está pronta para produção.
Seguimento de instruções
Seguiu estritamente todos os limites de número de linhas (58 linhas <= 150), os limites de contagem de palavras da explicação (129 palavras <= 200), as restrições da biblioteca padrão, e incluiu uma análise clara de complexidade de tempo.