Resposta A: OpenAI GPT-6 Sol
"""Um pequeno motor de planilha incremental. As fórmulas são analisadas em árvores de expressão. Referências e intervalos retangulares expandidos formam um grafo de dependências, com arestas reversas usadas para invalidar apenas os dependentes transitivos de uma célula alterada. Os valores são armazenados em cache e recalculados sob demanda. O recálculo primeiro encontra as células não armazenadas em cache que são alcançáveis e, em seguida, usa passagens iterativas de Kosaraju para identificar todas as células que estão em um ciclo. As células de ciclo são armazenadas em cache como #CYCLE; as demais células são...
Mostrar resposta completa ▼
"""Um pequeno motor de planilha incremental.
As fórmulas são analisadas em árvores de expressão. Referências e intervalos retangulares expandidos formam um grafo de dependências, com arestas reversas usadas para invalidar apenas os dependentes transitivos de uma célula alterada. Os valores são armazenados em cache e recalculados sob demanda. O recálculo primeiro encontra as células não armazenadas em cache que são alcançáveis e, em seguida, usa passagens iterativas de Kosaraju para identificar todas as células que estão em um ciclo. As células de ciclo são armazenadas em cache como #CYCLE; as demais células são avaliadas em ordem de dependência iterativa. As árvores de expressão também são avaliadas de forma iterativa, para que cadeias longas de dependências não consumam a pilha de chamadas do Python. Limpar ou alterar uma célula remove suas arestas antigas antes da invalidação, permitindo que ciclos detectados anteriormente desapareçam.
"""
import re
_CELL = re.compile(r"[A-Z][1-9][0-9]{0,2}\Z")
_NUMBER = re.compile(r"-?[0-9]+(?:\.[0-9]+)?\Z")
_TOKEN = re.compile(r"[A-Za-z_][A-Za-z_0-9]*|[0-9]+(?:\.[0-9]+)?|[()+\-*/,:]")
_ERRORS = {"#PARSE", "#DIV/0", "#CYCLE"}
def _cell_id(name):
if not isinstance(name, str) or _CELL.fullmatch(name) is None:
raise ValueError("invalid cell name")
return (int(name[1:]) - 1) * 26 + ord(name[0]) - ord("A")
def _number(text):
return float(text) if "." in text else int(text)
class _Parser:
def __init__(self, source):
self.tokens = []
self.deps = set()
pos = 0
while pos < len(source):
if source[pos].isspace():
pos += 1
continue
match = _TOKEN.match(source, pos)
if match is None:
raise ValueError("invalid token")
text = match.group()
kind = ("number" if text[0].isdigit() else
"word" if text[0].isalpha() or text[0] == "_" else text)
self.tokens.append((kind, text))
pos = match.end()
self.tokens.append(("end", ""))
self.pos = 0
def kind(self):
return self.tokens[self.pos][0]
def take(self, kind):
if self.kind() != kind:
raise ValueError("unexpected token")
text = self.tokens[self.pos][1]
self.pos += 1
return text
def reference(self):
name = self.take("word")
ref = _cell_id(name)
self.deps.add(ref)
return ref
def argument(self):
# Um intervalo só é válido quando constitui um argumento inteiro de função.
if (self.kind() == "word" and
self.tokens[self.pos + 1][0] == ":"):
first = self.reference()
self.take(":")
last = self.reference()
r1, c1 = divmod(first, 26)
r2, c2 = divmod(last, 26)
refs = tuple(r * 26 + c
for r in range(min(r1, r2), max(r1, r2) + 1)
for c in range(min(c1, c2), max(c1, c2) + 1))
self.deps.update(refs)
return ("range", refs)
return self.expression(0)
def expression(self, minimum):
kind = self.kind()
if kind == "-":
self.take("-")
left = ("unary", self.expression(3))
elif kind == "number":
left = ("number", _number(self.take("number")))
elif kind == "word":
if self.tokens[self.pos + 1][0] == "(":
name = self.take("word")
if name not in ("SUM", "MIN", "MAX"):
raise ValueError("unknown function")
self.take("(")
args = [self.argument()]
while self.kind() == ",":
self.take(",")
args.append(self.argument())
self.take(")")
left = ("function", name, tuple(args))
else:
left = ("reference", self.reference())
elif kind == "(":
self.take("(")
left = self.expression(0)
self.take(")")
else:
raise ValueError("expected expression")
while self.kind() in ("+", "-", "*", "/"):
op = self.kind()
precedence = 1 if op in ("+", "-") else 2
if precedence < minimum:
break
self.take(op)
right = self.expression(precedence + 1)
left = ("binary", op, left, right)
return left
def parse(self):
tree = self.expression(0)
self.take("end")
return tree, self.deps
class Sheet:
def __init__(self):
self._cells = {} # id -> (tipo, literal ou árvore de expressão)
self._deps = {} # id -> ids referenciados
self._reverse = {} # id referenciado -> ids dependentes
self._cache = {} # id -> valor avaliado
def set(self, cell: str, raw: str) -> None:
key = _cell_id(cell)
if raw == "":
entry, new_deps = None, set()
elif raw.startswith("="):
try:
tree, new_deps = _Parser(raw[1:]).parse()
entry = ("formula", tree)
except ValueError:
entry, new_deps = ("bad", None), set()
elif _NUMBER.fullmatch(raw):
entry, new_deps = ("literal", _number(raw)), set()
else:
entry, new_deps = ("bad", None), set()
for dep in self._deps.pop(key, ()):
users = self._reverse[dep]
users.remove(key)
if not users:
del self._reverse[dep]
if entry is None:
self._cells.pop(key, None)
else:
self._cells[key] = entry
if new_deps:
self._deps[key] = new_deps
for dep in new_deps:
self._reverse.setdefault(dep, set()).add(key)
# O novo grafo determina quais valores previamente armazenados em cache estão obsoletos.
pending = [key]
seen = {key}
for current in pending:
self._cache.pop(current, None)
for user in self._reverse.get(current, ()):
if user not in seen:
seen.add(user)
pending.append(user)
def get(self, cell: str) -> int | float | str:
key = _cell_id(cell)
if key not in self._cells:
return 0
if key not in self._cache:
self._recalculate(key)
return self._cache[key]
def _recalculate(self, root):
# Coleta apenas as células alcançáveis e não armazenadas em cache, e suas arestas reversas internas.
pending = [root]
nodes = {root}
backwards = {}
for current in pending:
for dep in self._deps.get(current, ()):
if dep not in self._cells or dep in self._cache:
continue
backwards.setdefault(dep, []).append(current)
if dep not in nodes:
nodes.add(dep)
pending.append(dep)
# Kosaraju iterativo: ordem de término, depois componentes do grafo reverso.
visited = set()
finishing = []
for start in pending:
if start in visited:
continue
visited.add(start)
stack = [(start, iter(self._deps.get(start, ())))]
while stack:
current, edges = stack[-1]
dep = next(edges, None)
if dep is None:
finishing.append(current)
stack.pop()
elif dep in nodes and dep not in visited:
visited.add(dep)
stack.append((dep, iter(self._deps.get(dep, ()))))
assigned = set()
for start in reversed(finishing):
if start in assigned:
continue
component = []
stack = [start]
assigned.add(start)
while stack:
current = stack.pop()
component.append(current)
for parent in backwards.get(current, ()):
if parent not in assigned:
assigned.add(parent)
stack.append(parent)
if len(component) > 1 or start in self._deps.get(start, ()):
for current in component:
self._cache[current] = "#CYCLE"
# Com as células cíclicas armazenadas em cache, as dependências restantes formam um DAG.
# A avaliação em pós-ordem é iterativa e avalia cada célula uma única vez.
visited = set()
stack = [(root, False)]
while stack:
current, ready = stack.pop()
if current in self._cache:
continue
if ready:
kind, contents = self._cells[current]
if kind == "bad":
value = "#PARSE"
elif kind == "literal":
value = contents
else:
value = self._evaluate(contents)
self._cache[current] = value
elif current not in visited:
visited.add(current)
stack.append((current, True))
for dep in self._deps.get(current, ()):
if dep in nodes and dep not in self._cache:
stack.append((dep, False))
def _evaluate(self, tree):
values = []
stack = [(tree, False)]
while stack:
node, ready = stack.pop()
kind = node[0]
if not ready:
if kind == "number":
values.append(node[1])
elif kind == "reference":
ref = node[1]
values.append(self._cache[ref] if ref in self._cells else 0)
elif kind == "range":
values.append([(self._cache[ref] if ref in self._cells else 0,
ref in self._cells) for ref in node[1]])
else:
stack.append((node, True))
if kind == "unary":
stack.append((node[1], False))
elif kind == "binary":
stack.append((node[3], False))
stack.append((node[2], False))
else:
for arg in reversed(node[2]):
stack.append((arg, False))
continue
if kind == "unary":
operand = values.pop()
values.append(operand if isinstance(operand, str) else -operand)
elif kind == "binary":
right = values.pop()
left = values.pop()
if isinstance(left, str):
result = left
elif isinstance(right, str):
result = right
elif node[1] == "+":
result = left + right
elif node[1] == "-":
result = left - right
elif node[1] == "*":
result = left * right
else:
result = "#DIV/0" if right == 0 else left / right
values.append(result)
else: # function
count = len(node[2])
args = values[-count:]
del values[-count:]
selected = []
error = None
for arg in args:
items = arg if isinstance(arg, list) else [(arg, True)]
for value, nonempty in items:
if isinstance(value, str):
if error is None:
error = value
elif node[1] == "SUM" or nonempty:
selected.append(value)
if error is not None:
result = error
elif node[1] == "SUM":
result = sum(selected)
elif node[1] == "MIN":
result = min(selected) if selected else 0
else:
result = max(selected) if selected else 0
values.append(result)
return values[0]
def _tests():
s = Sheet()
s.set("A1", "=-2+3*4")
assert s.get("A1") == 10
s.set("A1", "=-(2+3)*4")
assert s.get("A1") == -20
s.set("A2", "=8/2/2")
assert s.get("A2") == 2.0 and isinstance(s.get("A2"), float)
s.set("A1", "5")
s.set("B1", "7")
s.set("C1", "=SUM(B2:A1)")
assert s.get("C1") == 12
s.set("C2", "=MIN(A2:B2)")
s.set("D2", "=MAX(A2:B2)")
assert s.get("C2") == 2.0 and s.get("D2") == 2.0
s.set("A2", "")
assert s.get("C2") == 0 and s.get("D2") == 0
s.set("E1", "=1/0")
s.set("F1", "not a number")
s.set("G1", "=E1+F1")
s.set("H1", "=F1+E1")
assert s.get("G1") == "#DIV/0" and s.get("H1") == "#PARSE"
s.set("I1", "=I1+1")
assert s.get("I1") == "#CYCLE"
s.set("J1", "=K1")
s.set("K1", "=SUM(J1:J2)")
s.set("L1", "=J1+2")
assert s.get("J1") == s.get("K1") == s.get("L1") == "#CYCLE"
s.set("K1", "3")
assert s.get("J1") == 3 and s.get("L1") == 5
s.set("K1", "")
assert s.get("K1") == 0 and s.get("L1") == 2
for bad in ("=A0", "=AA1", "=A1000", "=A01", "=SUM(A1:A0)",
"=A1:B2", "=UNKNOWN(A1)"):
s.set("M1", bad)
assert s.get("M1") == "#PARSE"
for bad in ("a1", "A0", "AA1", "A01", "Z1000"):
for operation in (lambda: s.get(bad), lambda: s.set(bad, "1")):
try:
operation()
assert False, bad
except ValueError:
pass
chain = Sheet()
def name(index):
return chr(ord("A") + index % 26) + str(index // 26 + 1)
length = 20_000
chain.set(name(length - 1), "1")
for index in range(length - 2, -1, -1):
chain.set(name(index), "=" + name(index + 1) + "+1")
assert chain.get(name(0)) == length
chain.set(name(length - 1), "2")
assert chain.get(name(0)) == length + 1
if __name__ == "__main__":
_tests()Resultado
Votos de vitória
3 / 3
Pontuação média
Pontuação total
Comentário geral
A Resposta A é uma implementação completa e executável. Ela tem um analisador sintático real de precedência (precedence-climbing), e o menos unário se aplica com precedência maior que * e /, como exigido. Os intervalos são expandidos em dependências e funcionam com cantos invertidos. Arestas reversas permitem invalidar apenas as células que dependem de uma alteração. Os ciclos são encontrados com uma passagem iterativa de Kosaraju, incluindo laços próprios e ciclos que passam por intervalos, e tanto a avaliação das células quanto a das expressões são não recursivas. Ela trata as regras de erro corretamente: os erros vêm do primeiro operando da esquerda para a direita, e o erro de análise da própria célula tem prioridade. Células vazias contam como 0 em SOMA, mas são ignoradas por MÍN e MÁX, e os ciclos são desfeitos corretamente quando uma célula é editada ou limpa. Os testes cobrem todos os cenários exigidos, incluindo a cadeia de 20.000 células. Fraquezas menores: o analisador ainda recorre recursivamente em parênteses muito aninhados, a docstring é um pouco densa, e os testes estão em uma única função em vez de casos separados.
Ver detalhes da avaliação ▼
Correção
Peso 35%Precedência, menos unário, resultados int versus float, intervalos invertidos, MÍN/MÁX versus SOMA em células vazias, ordem dos erros, prioridade do erro de análise, detecção de ciclos por intervalos, propagação para células dependentes e resolução de ciclos após edições aparecem todos corretos. Nomes inválidos geram ValueError.
Completude
Peso 20%Entrega os três itens solicitados: o módulo, uma explicação de design e testes que cobrem todos os cenários listados, incluindo a cadeia de 20.000 células.
Qualidade do código
Peso 20%O analisador é bem estruturado, os algoritmos iterativos são bem organizados e o código não usa eval. O código é denso em alguns pontos, e os testes estão agrupados em uma única função.
Valor prático
Peso 15%Utilizável como está. Escala para cadeias longas e recalcula apenas as células afetadas.
Seguimento de instruções
Peso 10%Segue a API, usa apenas a biblioteca padrão e atende aos requisitos de não recursão e de cálculo incremental. A explicação é concisa e corresponde ao código.
Pontuação total
Comentário geral
A Resposta A oferece um motor de planilha completo, robusto e totalmente implementado, que atende a todos os requisitos do enunciado. Inclui um analisador sintático real de descida recursiva, grafos de dependência explícitos com mapeamento direto e reverso, detecção iterativa de ciclos com o algoritmo de Kosaraju, avaliação iterativa de expressões e casos de teste abrangentes. Trata corretamente os casos de borda e implementa invalidação incremental em vez de limpar todo o cache.
Ver detalhes da avaliação ▼
Correção
Peso 35%Implementa a semântica exata para análise sintática, operadores, intervalos, propagação de erros, detecção de ciclos e atualizações de múltiplas células, passando em todos os casos de teste abrangentes.
Completude
Peso 20%Fornece o código completo do módulo, a explicação do projeto e testes abrangentes que cobrem todos os casos de borda exigidos e cadeias de estresse.
Qualidade do código
Peso 20%Código Python limpo, bem estruturado e modular, com algoritmos robustos para análise sintática, rastreamento de dependências e avaliação iterativa.
Valor prático
Peso 15%Totalmente pronto para produção dentro da especificação, suportando cadeias de 20.000 células de forma iterativa, sem limites de recursão, e mantendo atualizações incrementais do cache.
Seguimento de instruções
Peso 10%Segue rigorosamente todas as definições de API, a formatação, o levantamento de erros, os requisitos não funcionais e as diretrizes de entrega.
Pontuação total
Comentário geral
A Resposta A oferece um motor completo e executável, com parser real, rastreamento explícito de dependências, invalidação de cache direcionada, detecção iterativa de ciclos e avaliação de dependências não recursiva. Seus testes cobrem os cenários solicitados, incluindo uma cadeia de 20.000 células e atualizações por essa cadeia. A principal limitação de robustez é o parsing recursivo de expressões muito aninhadas; a meta de desempenho para operações mistas também não é demonstrada.
Ver detalhes da avaliação ▼
Correção
Peso 35%A implementação trata corretamente a precedência, os tipos numéricos do resultado, intervalos invertidos, o tratamento de células vazias, a propagação ordenada de erros e a pertinência a ciclos por meio de componentes fortemente conectados. Remover dependências de células com erro de sintaxe preserva a prioridade desse erro. O parsing recursivo ainda pode gerar RecursionError em fórmulas válidas muito aninhadas.
Completude
Peso 20%Inclui o módulo completo, uma explicação concisa do design e asserções executáveis que cobrem todas as categorias de teste solicitadas. Testes adicionais para a prioridade de erro de sintaxe na própria fórmula e para erros concorrentes envolvendo ciclos fortaleceriam a suíte.
Qualidade do código
Peso 20%A análise, a manutenção do grafo, o recálculo e a avaliação de expressões estão claramente separados. As pilhas explícitas de percurso e as fases do grafo documentadas tornam a implementação manutenível, apesar da complexidade. As tuplas para os nós sintáticos e a constante de erro não utilizada são pequenos problemas de acabamento.
Valor prático
Peso 15%As dependências reversas limitam a invalidação às células afetadas, as leituras em cache são baratas e o percurso do grafo é linear no subgrafo relevante. O teste de cadeia longa exercita tanto a avaliação inicial quanto uma atualização a montante, sem recursão de dependências. Não há teste de tempo para operações mistas que comprove a meta de vazão declarada.
Seguimento de instruções
Peso 10%Usa apenas a biblioteca padrão, expõe a API anotada solicitada, fornece uma explicação curta e precisa e inclui o caso de estresse solicitado. A implementação segue a abordagem incremental e o processamento não recursivo de dependências exigidos.