Spreadsheet Engine: References, Ranges, Cycles and Scale

Spreadsheet Engine: References, Ranges, Cycles and Scale

You've joined the team that owns the calculation engine behind a lightweight spreadsheet product. A sheet is a grid of cells; a cell holds a number, some text, or a formula such as =A1+B2*2. Customers are reporting wrong totals, and three roadmap items are queued behind that: range functions, circular-reference detection, and making big sheets fast.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against an empty sheet and returns exactly one result per operation. A request that cannot be carried out comes back as an "error: <reason>" string and changes nothing. Problems *inside* a formula are not request errors: they become cell values such as "#DIV/0".

• All arguments are strings. A wrong number or type of arguments returns "error: invalid arguments", an unknown operation name "error: unknown operation".
• A ref is one capital letter A-Z followed by a row 1-9999 with no leading zeros (B3). Anything else, including lower case, is invalid cell. A range is two refs joined by : (A1:C3); it covers the rectangle between the corners, which may be written in either order.
• Content. "" clears the cell (same as clear). Text starting with = is a formula. A whole string of the form -?digits or -?digits.digits is a number. Anything else is text, kept exactly as typed (" 5" and "5." are text).
• Values are returned as: a number (an integer when it is a whole number, otherwise rounded to 6 decimal places), the text, null for a blank cell, or an error string such as "#DIV/0".
• Formulas may contain numbers, cell refs, + - * /, unary minus, parentheses, function calls and spaces. * and / bind tighter than + and -; operators of the same precedence group left to right (10-3-2 is 5, 8/4/2 is 1). A formula that cannot be parsed makes set return error: invalid formula and leaves the cell as it was.
• In arithmetic a blank cell counts as 0, text gives #VALUE, and dividing by zero gives #DIV/0. A formula that is just a ref shows the referenced value as is (text stays text, a blank cell shows 0). An unknown function name gives #NAME. ABS takes exactly one argument (otherwise #VALUE); MIN/MAX take any number of arguments, skip blank and text values, and give 0 when there is no number.
• Errors propagate. If an operand is an error, so is the result; when both operands of an operator are errors the left one wins. For function arguments the first error from left to right wins.

Worked example

[["set", "A1", "10"], ["set", "B2", "5"], ["set", "C3", "=A1+B2"], ["get", "C3"],
 ["values", "A1:C3"]]

returns

[true, true, true, 15, [10, null, null, null, 5, null, null, null, 15]]

Part 1 — Wrong totals

Goal. Customers see wrong numbers in three situations. Find the causes and fix them.

Rules

1. A reference in a formula reads exactly the cell it names (=A2+B1 reads A2 and B1, whichever rows and columns they are in).
2. Operators of the same precedence group left to right.
3. Clearing a cell (clear, or set with "") makes every formula that depends on it recalculate as if the cell were blank.
4. values reports the cells of its range row by row, left to right.

Part 2 — Ranges and aggregate functions

Goal. Support A1:B3 ranges and the functions customers asked for.

Rules

1. A range may be written wherever an expression is allowed, but it only has a value as a function argument; used any other way (=A1:A3, =A1:A3+1, =ABS(A1:A3)) the formula's value is #VALUE. Both ends of a range must be valid refs, otherwise error: invalid formula.
2. New functions SUM, AVERAGE and COUNT; MIN and MAX now accept ranges. Each takes any number of arguments; each argument is an expression, a cell ref or a range. They look at the numbers among all arguments (the cells of a range in row-major order) and skip blank and text cells, whether they arrive through a range or a single ref. SUM of nothing is 0, AVERAGE of nothing is #DIV/0, COUNT is how many numbers there were, MIN/MAX of nothing is 0.
3. If any argument value is an error the function returns it (the first one, in argument order and row-major order within a range). That includes COUNT.
4. A cell that has not been filled in yet, or is filled in or cleared later, is still part of the range: formulas that use the range update when any cell inside it changes.
5. fill_down moves both corners of a range down, like any other reference.

Example. With A1=1, A2=2, B1=3, B3=10, the formula =SUM(A1:B3) is 16 (blanks skipped). =SUM(B3:A1) is the same range.

Part 3 — Circular references

Goal. A formula that (indirectly) depends on itself must produce #CYCLE instead of misbehaving.

Rules

1. A cell is in a cycle if following the references in its formula (a range refers to every cell inside it) can lead back to the cell. A formula that refers to itself, or whose range includes itself, is a cycle.
2. Every cell in a cycle has the value #CYCLE.
3. Every cell that depends on a cycle cell, directly or through other cells or ranges, also has the value #CYCLE, whatever else its formula contains. #CYCLE takes priority over every other error: =1/0+B1 is #CYCLE if B1 is.
4. set returns true even when it creates a cycle. Editing or clearing a cell so the cycle no longer exists restores normal values everywhere.
5. Long dependency chains that are *not* cycles must work: a chain of 100 cells, each = the one above + 1, shows the right number at the bottom.

Example. With A1: =B1+1, B1: =A1+1 and C1: =A1*2, all three cells show #CYCLE. After set B1 "5", A1 is 6 and C1 is 12.

Part 4 — Big sheets (stretch)

Goal. Finance models fill thousands of cells with chained formulas and then change inputs over and over. Make that fast without changing any result.

Rules

1. Every result stays exactly as in Parts 1-3.
2. A fill_down that creates a chain of 2,500 formulas (each referring to the cell above) must work, and so must changing the top of that chain and reading the bottom.
3. With about 4,000 formula cells in the sheet (long independent chains), hundreds of single-cell edits must stay fast: an edit has to recalculate only the edited cell and the cells that depend on it, not the whole sheet.
4. A formula that is replaced must stop depending on the cells its old version read.

Notes

• refs.py, lexer.py, errors.py and cells.py are known-good.
• You may use the AI assistant freely. Later parts must not break earlier ones; the hidden tests re-check every part. Parts 1-3 is a strong result; Part 4 is a stretch.