Spreadsheet III

Build a small spreadsheet engine. Like Excel or Google Sheets, a cell can hold a plain value (5, "total") or a formula that derives its value from other cells. When you change a cell, every cell that depends on it — directly or indirectly — must recompute, and the rest must stay untouched. The catch every real spreadsheet has to handle: a circular reference, where a formula ends up depending on itself (A reads B, B reads A). You must detect it and refuse to compute, rather than recurse forever.

You implement a Spreadsheet class. A formula is written as a function of a getter, so the engine can discover dependencies by watching which cells the formula reads while it runs.

Signature

class Spreadsheet {
  // Store a literal (number | string) OR a formula.
  // A formula is a function that receives a `get` callback and
  // returns a value, e.g. (get) => get('A') + get('B').
  set(name: string, value: number | string | ((get: (n: string) => any) => any)): void;

  // Return the cell's computed value. Memoized: re-reading without an
  // upstream change does not re-run the formula. Recomputed when any
  // cell it (transitively) depends on changes.
  // Throws Error('circular reference') if the cell is part of a cycle.
  get(name: string): any;
}

Examples

A literal-plus-formula chain that recomputes after a set:

const sheet = new Spreadsheet();
sheet.set('A', 2);
sheet.set('B', 3);
sheet.set('C', (get) => get('A') + get('B'));
sheet.get('C'); // → 5

sheet.set('A', 10);
sheet.get('C'); // → 13   (C recomputed because A changed)

A circular reference is detected and throws:

const sheet = new Spreadsheet();
sheet.set('A', (get) => get('B') + 1);
sheet.set('B', (get) => get('A') + 1); // A → B → A
sheet.get('A'); // throws Error('circular reference')

Notes

• Dependencies are discovered, not declared. A formula's dependencies are exactly the cells it calls get on during evaluation. They can change between recomputes (a formula that branches on a flag reads different cells depending on the flag), so the engine must re-record them on every recompute.
• Memoization is required. Reading a cell twice with nothing changed in between must return the cached value without re-invoking the formula. Re-evaluating only happens after an upstream cell changes.
• Recompute is transitive. Setting A must invalidate not just cells that read A, but cells that read those cells, all the way down the chain.
• A cycle is any path of formula dependencies that returns to its start — a cell reading itself, or any longer loop (A → B → C → A). get on a cell inside such a loop throws Error('circular reference').
• Reading an unset cell returns undefined. Setting a literal over a formula (or vice-versa) replaces the cell's behavior entirely.
• Don't worry about parsing string formulas like "=A1+B1", ranges like SUM(A1:A10), or async cells — formulas are plain synchronous functions here.