Answer A: OpenAI GPT-6 Sol
"""A small incremental spreadsheet engine. Formulas are parsed into expression trees. References and expanded rectangular ranges form a dependency graph, with reverse edges used to invalidate only transitive dependents of a changed cell. Values are cached and recalculated on demand. Recalculation first finds reachable uncached cells, then uses iterative Kosaraju passes to identify every cell on a cycle. Cycle cells are cached as #CYCLE; the remaining cells are evaluated in iterative dependency order. Expression trees are evaluated iteratively too, so long dependency chains do not consume the Python call stack. C...
Show Full Answer ▼
"""A small incremental spreadsheet engine.
Formulas are parsed into expression trees. References and expanded rectangular
ranges form a dependency graph, with reverse edges used to invalidate only
transitive dependents of a changed cell. Values are cached and recalculated on
demand. Recalculation first finds reachable uncached cells, then uses iterative
Kosaraju passes to identify every cell on a cycle. Cycle cells are cached as
#CYCLE; the remaining cells are evaluated in iterative dependency order.
Expression trees are evaluated iteratively too, so long dependency chains do
not consume the Python call stack. Clearing or changing a cell removes its old
edges before invalidation, allowing previously detected cycles to disappear.
"""
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):
# A range is legal only when it constitutes an entire function argument.
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 -> (kind, literal or expression tree)
self._deps = {} # id -> referenced ids
self._reverse = {} # referenced id -> dependent ids
self._cache = {} # id -> evaluated value
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)
# The new graph determines which previously cached values are stale.
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):
# Collect only reachable, uncached cells and their internal reverse edges.
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)
# Iterative Kosaraju: finishing order, then reverse-graph components.
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"
# With cyclic cells cached, the remaining dependencies form a DAG.
# Postorder evaluation is iterative and evaluates each cell once.
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()Result
Winning Votes
3 / 3
Average Score
Total Score
Overall Comments
Answer A is a complete, runnable implementation. It has a real precedence-climbing parser, and unary minus binds tighter than * and / as required. Ranges are expanded into dependencies and work with reversed corners. Reverse edges let it invalidate only the cells that depend on a change. Cycles are found with an iterative Kosaraju pass, including self-loops and cycles that run through ranges, and both cell evaluation and expression evaluation are non-recursive. It handles the error rules correctly: errors come from the first operand left to right, and a cell's own parse error wins. Empty cells count as 0 in SUM but are ignored by MIN and MAX, and cycles clear correctly when a cell is edited or cleared. The tests cover every required scenario, including the 20,000-cell chain. Minor weaknesses: the parser still recurses on deeply nested parentheses, the docstring is a little dense, and the tests are one function rather than separate cases.
View Score Details ▼
Correctness
Weight 35%Precedence, unary minus, int vs float results, reversed ranges, MIN/MAX vs SUM on empty cells, error order, parse-error priority, cycle detection through ranges, propagation to dependent cells, and cycles resolving after edits all appear correct. Invalid names raise ValueError.
Completeness
Weight 20%Provides all three deliverables: the module, a design explanation, and tests covering every listed scenario, including the 20,000-cell chain.
Code Quality
Weight 20%The parser is cleanly structured, the iterative algorithms are well organised, and the code has no eval. The code is dense in places, and the tests are lumped into one function.
Practical Value
Weight 15%Usable as is. It scales to long chains and recomputes only affected cells.
Instruction Following
Weight 10%Follows the API, uses only the standard library, and meets the non-recursive and incremental requirements. The explanation is concise and matches the code.
Total Score
Overall Comments
Answer A provides a complete, robust, and fully implemented spreadsheet engine that matches every requirement in the prompt. It includes a real recursive descent parser, explicit dependency graphs with forward and reverse mapping, an iterative Kosaraju cycle detection algorithm, iterative expression evaluation, and thorough test cases. It handles edge cases correctly and implements incremental invalidation rather than wholesale cache clearing.
View Score Details ▼
Correctness
Weight 35%Implements exact semantics for parsing, operators, ranges, error propagation, cycle detection, and multi-cell updates, passing all comprehensive test cases.
Completeness
Weight 20%Provides the complete module code, design explanation, and comprehensive tests covering all required edge cases and stress chains.
Code Quality
Weight 20%Clean, well-structured, modular Python code with robust algorithms for parsing, dependency tracking, and iterative evaluation.
Practical Value
Weight 15%Fully production-ready for the specification, supporting 20,000-cell chains iteratively without recursion limits and maintaining incremental cache updates.
Instruction Following
Weight 10%Strictly follows all API definitions, formatting, error raising, non-functional requirements, and deliverable guidelines.
Total Score
Overall Comments
Answer A provides a complete, runnable engine with a real parser, explicit dependency tracking, targeted cache invalidation, iterative cycle detection, and non-recursive dependency evaluation. Its tests cover the requested scenarios, including a 20,000-cell chain and updates through that chain. The main robustness limitation is recursive parsing of deeply nested expressions; the mixed-operation performance target is also not demonstrated.
View Score Details ▼
Correctness
Weight 35%The implementation correctly handles precedence, numeric result types, reversed ranges, empty-cell treatment, ordered error propagation, and cycle membership using strongly connected components. Removing dependencies for parse-error cells preserves their own parse-error priority. Recursive parsing can still raise RecursionError on sufficiently deeply nested valid formulas.
Completeness
Weight 20%Includes the full module, a concise design explanation, and executable assertions covering every requested test category. Additional tests for own-formula parse-error priority and competing errors involving cycles would strengthen the suite.
Code Quality
Weight 20%Parsing, graph maintenance, recalculation, and expression evaluation are clearly separated. Explicit traversal stacks and documented graph phases make the implementation maintainable despite its complexity. Tuple-based syntax nodes and the unused error constant are minor polish issues.
Practical Value
Weight 15%Reverse dependencies limit invalidation to affected cells, cached reads are inexpensive, and graph traversal is linear in the relevant subgraph. The supplied long-chain test exercises both initial evaluation and an upstream update without dependency recursion. No mixed-operation timing test establishes the stated throughput target.
Instruction Following
Weight 10%Uses only the standard library, exposes the requested annotated API, supplies a short and accurate explanation, and includes the requested stress case. The implementation follows the required incremental and non-recursive dependency-processing approach.