Spreadsheet Engine: Spec Fidelity + Performance (sheet.py)
A hard, original agentic coding task. Models must implement a spreadsheet engine from a precise written spec: a recursive-descent formula parser, integer arithmetic with truncating division, lazy IF, row-major error ordering in range aggregates, static cycle detection that ignores IF laziness, and UNDO. The spec also lists six performance families (deep chains, 100k-cell ranges with point updates, cycle toggling, wide rectangles, 10k-character nested formulas) that naive solutions fail. Outputs are deterministic stdin/stdout, so each submission can be scored objectively by running it against the public example and hidden tests.
Prompt
# Task: Implement a spreadsheet engine ("sheet.py") Write a single Python 3.11 file, sheet.py, using only the standard library. It reads commands from stdin (one per line) and writes results to stdout. You will be graded ONLY on exact output match against hidden tests (correctness + performance), so follow the spec literally. Where the spec is silent, it is silent on purpose: nothing in hidden tests depends on it. ## Grid Columns A–Z (single uppercase letter), rows 1–100000 (no leading zeros). All cells start empty. An empty cell has value 0. ## Commands Command word and target cell are always well-formed. Everything after the target cell may be malformed. - `SET <cell> <content>`: content is the rest of the line after the single space following <cell>, with trailing whitespace/CR stripped. - If content matches ^-?[0-9]+$ it is an integer literal (leading zeros allowed; "-0" is 0). - If content starts with '=' it is a formula (grammar below). An invalid formula makes the cell's value #PARSE! (the cell then has no dependencies). - Anything else (including empty content, or "- 5") → #PARSE!. - `CLEAR <cell>`: make the cell empty. - `GET <cell>`: print the cell's current value. - `UNDO`: revert the most recent not-yet-undone SET or CLEAR, restoring the cell's exact previous content (empty, literal, formula, or the invalid text). Every SET/CLEAR is undoable, even if it changed nothing. There is no REDO. If nothing is left to undo, print NOOP. Otherwise print nothing. - `CYCLES`: print the number of cells that are currently cyclic (defined below). Values print as a decimal integer (arbitrary precision, "-" for negatives) or exactly one of: #PARSE! #DIV/0! #CYCLE! ## Formula grammar (after '=') Spaces may appear between tokens but never inside a token. expr := term (('+' | '-') term)* term := unary (('*' | '/') unary)* unary := '-' unary | primary primary := INT | CELL | func | '(' expr ')' func := ('SUM' | 'MIN' | 'MAX') '(' range ')' | 'IF' '(' expr ',' expr ',' expr ')' range := CELL ':' CELL (any two corners; denotes the bounding rectangle) INT := [0-9]+ (leading zeros allowed) CELL := [A-Z][1-9][0-9]* (row must be 1..100000) Function names are uppercase only. A range may appear only as a function argument. Anything not derivable from this grammar is #PARSE!. Formulas may be up to 10,000 characters with arbitrarily deep nesting. ## Evaluation semantics - Integer arithmetic only. '/' truncates toward zero (-7/2 = -3). Division by zero → #DIV/0!. - Errors propagate. For a binary operator, evaluate the left operand first; if it is an error, that is the result (the right operand is NOT evaluated). Otherwise evaluate the right operand; if it is an error, that is the result. - IF(c, a, b): evaluate c. If it is an error, that is the result. If c ≠ 0, evaluate and return only a; otherwise only b. The untaken branch is never evaluated. - SUM/MIN/MAX(range): scan the rectangle in ROW-MAJOR order (row ascending, then column ascending). If any cell is an error, the result is the error of the FIRST erroring cell in that order. Otherwise aggregate, with empty cells counting as 0 (so MIN over empties and positives is 0). - A cell holding #PARSE! evaluates to #PARSE!. ## Cycles (static, not dynamic) Build the dependency graph: edge X → Y if Y's formula mentions X directly or X lies inside a range in Y's formula. Count BOTH branches of every IF, taken or not. A cell is cyclic if it lies on a directed cycle (a self-reference counts). A cyclic cell's value is #CYCLE!, regardless of IF laziness. A non-cyclic cell that reads a cyclic cell receives #CYCLE! as that operand's value, subject to the normal ordering and laziness rules above. ## Limits and performance ≤ 200,000 commands per test; 10 s per test on CPython 3.11; 1 GB memory. Intermediate magnitudes stay below 10^30. The hidden performance tests include (at least) these families: P1 A1=1, A(i)=A(i-1)+1 up to A100000, then 100,000 × GET A100000. P2 B1=SUM(A1:A100000) over literals, then ~100,000 interleaved point SETs on column A and GET B1. P3 Like P2 with MIN/MAX, where some point SETs make cells errors (e.g. =1/0) and later fix them. P4 The P1 chain, then 50 × [SET A1 =A100000; GET A50000; CYCLES; UNDO; GET A50000; CYCLES]. P5 1,000 formula cells, each an aggregate over a large random rectangle (up to A1:Z100000), with 1,000 random point SETs interleaved with GETs of random formula cells. P6 Single formulas of ~10,000 characters with nesting depth in the thousands. A correct but slow solution fails these tests. ## Public example Input: UNDO SET A1 10 SET A2 =A1*3 SET A3 =A2/-4 GET A3 SET B1 =SUM(A1:A3) GET B1 SET A1 =B1 GET A2 CYCLES UNDO GET B1 CYCLES SET C1 =IF(A1-10, B9/0, 7) GET C1 SET C2 =IF(0, C2, 5) GET C2 SET C3 =IF(0,C2,5)+C1 GET C3 SET D1 =SUM(C1:C3) GET D1 SET F1 =1/0 + C2 SET E2 =2 +* 3 SET G1 =MAX(F2:E1) GET G1 SET H3 -4 SET H4 =-7/2 SET G2 =MIN(H1:H5)+MAX(H1:H5)*100 GET G2 GET H4 CLEAR C2 GET D1 UNDO GET D1 GET Z99999 CYCLES SET K1 007 SET K2 -0 SET K3 =K1*-(2+1)--9/2 GET K3 GET K2 SET K4 - 5 GET K4 Expected output: NOOP -7 33 #CYCLE! 4 33 0 7 #CYCLE! 12 #CYCLE! #DIV/0! -4 -3 19 #CYCLE! 0 1 -17 0 #PARSE! ## Deliverables 1. The complete sheet.py. 2. A design note of at most 250 words covering: your data structures, the complexity of each command, how you handle cycle detection incrementally, and the edge cases you deliberately handled.
Answer guidance
GRADING PRIORITY: correctness of sheet.py against the spec > performance design > design note quality. 1. PUBLIC EXAMPLE (disqualifying if wrong). The program must print exactly these 21 lines: NOOP, -7, 33, #CYCLE!, 4, 33, 0, 7, #CYCLE!, 12, #CYCLE!, #DIV/0!, -4, -3, 19, #CYCLE!, 0, 1, -17, 0, #PARSE! 2. SEMANTIC TRAPS (check each in the code): - Division truncates toward zero. Python's // floors, so -7/2 must give -3, not -4. The example checks this through A2/-4 = -7 and -7/2 = -3. - Binary operators evaluate left first and short-circuit on an error. "1/0 + C2" gives #DIV/0!, not #CYCLE!. - IF is lazy for errors: an error in the untaken branch must not propagate. - Cycles are STATIC: both IF branches count as edges, so =IF(0, C2, 5) in C2 is #CYCLE!. A non-cyclic cell that references a cyclic cell only in an untaken branch still evaluates normally (C3 = 12). - Range aggregates return the first error in ROW-MAJOR order. MAX(F2:E1) must give #DIV/0! (from F1), not #PARSE! (from E2, which column-major order would find first). Reversed range corners must be normalized. - Empty cells count as 0 in MIN/MAX. MIN(H1:H5)+MAX(H1:H5)*100 = -4. - Plain literals: "007" = 7, "-0" prints 0, "- 5" is #PARSE!. Lowercase function names, "AA1", "A0", "A01", and bare ranges outside functions are all #PARSE!. - UNDO restores exact previous content, including empty cells and invalid text. It prints NOOP when nothing is left to undo. CLEAR of an empty cell is still undoable. - CYCLES counts every cell on any directed cycle, including self-loops. In the example, 4 cells form one SCC through a range edge. 3. PERFORMANCE DESIGN (the hidden families P1–P6; assess from the code): - No Python recursion on deep dependency chains (P1, P4) or on deeply nested formulas (P6). An iterative evaluator and parser are required, or equivalent (raising the recursion limit alone risks a C-stack crash). - Memoization plus dirty invalidation, so repeated GETs of an unchanged cell are O(1) (P1). - Range dependencies indexed without expanding them per cell. A 100k-cell range must not create 100k edges. - Aggregate structure for ranges with point updates (Fenwick or segment tree per column, or equivalent). It must also locate the first error in row-major order efficiently (P2, P3, P5). Re-summing the whole range on every GET fails. - Cycle detection that doesn't redo full-graph work on every command, and never enumerates every cell of a range to find formula cells. 4. SCORING GUIDE: - Fails the public example: 0–2/10 - Passes the example but misses 2+ semantic traps: 3–4/10 - Semantics correct, but recursion or naive range handling would fail performance: 5–7/10 - Semantics correct and a plausible design for all of P1–P6: 8–10/10. Reserve 10 for clean, verified code whose design note correctly states per-command complexity. Authoritative scoring is running each sheet.py locally against the public example and a hidden test suite (a naive oracle for small random tests, plus the P1–P6 generators). Treat this rubric as a review aid, not a substitute for execution.
Response not available
Response not available