Eager Spreadsheet Formulas with Constant-Time Reads

Implement a spreadsheet with set_cell, get_cell, arithmetic formulas, dependency updates, and circular-reference rejection. Each successful write must leave computed values ready so a subsequent get_cell is a constant-time cached read.

Implement eager_sheet(operations: string[][]) -> string[]. Each row is ["set", cell, raw] or ["get", cell]. Return one string per operation:

• A successful set returns "OK".
• A set that would introduce a circular reference returns "CYCLE" and leaves the previous sheet unchanged.
• A get returns the cell's computed integer in canonical decimal notation, with no leading plus or leading zeros; zero is "0".

Formula and edit contract

The source describes formulas and dependency/cycle handling but does not give a grammar. This practice version explicitly uses:

• Cell names are uppercase letters followed by a positive decimal row number with no leading zeros, such as A1 or AA10.
• Raw values are signed integer strings or formulas beginning with =.
• Formula grammar is term (('+' | '-') term)*, where a term is a nonnegative integer or a cell reference. Spaces may surround tokens. Unary signs and parentheses inside formulas are excluded.
• Unset cells evaluate to zero. Repeated references contribute repeatedly, so =A1+A1 counts the value twice.
• Set replaces the entire previous definition, including its dependency links. It may change a literal to a formula or a formula to a literal.
• Direct and indirect cycles are rejected before the edit becomes visible. A failed set preserves both the old definition and every previously computed value.
• On a successful set, update every affected dependent value before processing the next operation. Implement get using stored results, without dependency traversal on reads.

Constraints

• There are at most 500 operations and at most 100 terms per formula.
• All names and expressions are syntactically valid.
• Numeric tokens, stored literals, and all intermediate arithmetic results for an acyclic prospective sheet fit in a signed 32-bit integer.
• The sheet starts empty, and operations are processed sequentially.
• Cycle-error serialization, unset-cell behavior, grammar, and bounds are explicit practice assumptions. The constant-time-read requirement and the need to consider write-versus-read evaluation come from the reported task.

Examples

operations = [
  ["set","A1","2"],
  ["set","B1","=A1+1"],
  ["set","C1","=A1+B1"],
  ["set","A1","5"],
  ["get","C1"]
]
result = ["OK","OK","OK","OK","11"]

operations = [
  ["set","A1","=B1"],
  ["set","B1","=A1+1"],
  ["get","A1"],
  ["set","A1","3"],
  ["set","B1","=A1+1"],
  ["get","B1"]
]
result = ["OK","CYCLE","0","OK","OK","4"]

The rejected edit in the second example leaves B1 unset. Replacing A1 with a literal later removes the dependency that would have completed the cycle.

Hint: Keep both graph directions

One graph direction identifies a formula's inputs. The other identifies which cached values can change after an input edit. Recompute dependents only after their changed inputs are ready.

Eager Spreadsheet Evaluation with Atomic Cycle Rejection

Approach

For each write, copy the definitions and replace the target definition only in that prospective map. A memoized dependency DFS evaluates all prospective definitions. The active recursion set detects an edge back to an unfinished cell, which is exactly a directed cycle; reject that write without assigning either the prospective map or its temporary cache. On success, each referenced value has been computed before its consumer, and repeated formula terms are added or subtracted separately. Commit both the definitions and complete cache together. This bounded implementation deliberately rebuilds every defined value at each successful write, which includes every affected dependent and simplifies atomicity. Reads perform only a cache lookup; unset names default to zero. Formula-to-literal edits automatically discard prior dependencies because the old expression is replaced.

• Time complexity: Expected O(1) per get. O(V+E+L) per set for V referenced/defined cells, E reference occurrences, and L total expression characters in the prospective sheet; across Q writes, O(Q*(V+E+L)).
• Space complexity: O(V+E+L) for definitions, prospective state, cache, parsed traversal work and recursion; output O(number of operations).