Simplified In-Memory Spreadsheet

Implement a simplified in-memory spreadsheet that supports three core operations: SET, GET, and SUM, mirroring basic Excel functionality.

Assumptions and Requirements

• Cell Identification: Cells are identified by standard Excel-like coordinates.
  • Columns are single uppercase letters from 'A' to 'Z'.
  • Rows are integers from 1 to 1000.
  • A cell ID is a string, e.g., 'A1', 'B2', 'Z1000'.
• Cell Content: Each cell can contain either:
  • A numeric integer value.
  • A formula representing the sum of other cells or rectangular ranges of cells.

Operations

1. SET(cellId, value)

   • Assigns a numeric integer value to the specified cellId.
   • Any existing formula or previous value in cellId is overwritten.
   • Returns the value that was set.

2. GET(cellId)

   • Returns the current evaluated integer value of the cell.
   • If the cell contains a formula (from a SUM operation), its value is the sum of its referenced cells, recursively evaluated.

3. SUM(cellId, refs)

   • Stores a formula in cellId. This formula is defined as the sum of all cells specified in refs.
   • refs is a list of references, where each reference can be:
     • A single cell ID (e.g., 'B2').
     • A rectangular range in the format 'A1:B2', representing all cells whose column is between 'A' and 'B' (inclusive) and whose row is between 1 and 2 (inclusive).
   • Returns the evaluated sum of the newly stored formula.

Behavioral Example

The implementation should be consistent with the following sequence, demonstrating dependency updates:

• SET('A1', 1) → returns 1
• SET('B2', 2) → returns 2
• SUM('C1', ['A1', 'B2']) → returns 3 (C1's formula is A1 + B2)
• SUM('D1', ['C1', 'A1']) → returns 4 (D1's formula is C1 + A1)
• SET('A1', 10) → returns 10
• GET('D1') → returns 22 (D1 evaluates to (A1+B2) + A1 = (10+2) + 10 = 22)

Additional Requirements and Edge Cases

• Dependency Updates: Updating a cell (via SET or SUM) must correctly affect any other cells whose formulas depend (directly or transitively) on that cell. Subsequent GET calls must return up-to-date values.
• Dependency Chains: The system must handle chains of dependencies (e.g., A1 used by B1, which is used by C1, etc.).
• Cycle Detection: You must handle potential cycles in formulas (e.g., A1 depends on B1, and B1 later depends on A1).
  • Define and implement a reasonable behavior for cyclic dependencies (e.g., detect cycles during evaluation or update and prevent them, or return an error/special behavior). Clearly state your chosen behavior in code comments.
• Efficiency: Aim for an efficient implementation that avoids recomputing large dependency graphs from scratch on every GET.

Design and implement the data structures and methods to support these operations.