Mini spreadsheet with formulas and cycle detection

Build Sheet with:

• set(cell, value): value is a number or a formula string starting with =, such as "=A1 + B2 * 2" or "=SUM(A1:A3) / 3".
• get(cell) -> float: the cell's current value. Empty cells are 0.

Ask:

• Formula grammar. Numbers, cell references, + - * /, parentheses, unary minus, and SUM(range). Enough to show a real parser; more functions are follow-ups.
• When are values computed? Eagerly: set recomputes everything that depends on the changed cell, so get is an O(1) lookup. (The lazy alternative computes on get and caches; mention it.)
• Cycles. A1 = B1 + 1 then B1 = A1 must be rejected, and the sheet must be left exactly as it was before the bad set.
• Division by zero. Raise on set, or store an error value? Store #DIV/0!-style errors as a follow-up; for now raise and reject the set.

Three parts:

1. Parse a formula once into an expression tree and collect the cells it references. A small recursive-descent parser over tokens keeps operator precedence right:

   expr   := term (("+" | "-") term)*
   term   := factor (("*" | "/") factor)*
   factor := NUMBER | CELL | "-" factor | "(" expr ")" | "SUM" "(" CELL ":" CELL ")"
   

2. Track the dependency graph. deps[c] is the set of cells c reads; dependents[c] the reverse. Setting c replaces its outgoing edges.

3. Check and recompute.

   • Cycle check before committing: the new formula for c creates a cycle exactly when c is reachable from one of its new references by following deps. DFS from the new references; if it reaches c, reject without changing anything.
   • Recompute in topological order: collect c and everything that transitively depends on it, then evaluate them in an order where each cell comes after the cells it reads (Kahn's algorithm restricted to that set). Each affected cell is computed exactly once, even when it is reachable along several paths (the diamond A1 → B1, C1 → D1).

If evaluation fails part-way (division by zero), restore the previous formulas, edges and values, so a rejected set leaves no trace.

import re
from collections import deque
from typing import Dict, List, Set, Tuple, Union

TOKEN = re.compile(r"\s*(?:(\d+\.?\d*)|([A-Z]+[0-9]+)|(SUM)|(.))")
CELL = re.compile(r"([A-Z]+)([0-9]+)$")


class CycleError(ValueError):
    pass


def _col(letters: str) -> int:
    n = 0
    for ch in letters:
        n = n * 26 + ord(ch) - 64
    return n


def _name(col: int, row: int) -> str:
    letters = ""
    while col:
        col, rem = divmod(col - 1, 26)
        letters = chr(65 + rem) + letters
    return f"{letters}{row}"


def expand_range(a: str, b: str) -> List[str]:
    (ca, ra), (cb, rb) = [(_col(m.group(1)), int(m.group(2))) for m in (CELL.match(a), CELL.match(b))]
    return [_name(c, r) for c in range(min(ca, cb), max(ca, cb) + 1)
            for r in range(min(ra, rb), max(ra, rb) + 1)]


class _Parser:
    def __init__(self, src: str) -> None:
        self.tokens: List[Tuple[str, str]] = []
        for num, cell, fn, other in TOKEN.findall(src):
            if num:
                self.tokens.append(("num", num))
            elif cell:
                self.tokens.append(("cell", cell))
            elif fn:
                self.tokens.append(("fn", fn))
            elif other.strip():
                self.tokens.append(("op", other))
        self.i = 0
        self.refs: Set[str] = set()

    def peek(self) -> Tuple[str, str]:
        return self.tokens[self.i] if self.i < len(self.tokens) else ("end", "")

    def take(self, kind: str, value: str = "") -> str:
        k, v = self.peek()
        if k != kind or (value and v != value):
            raise ValueError(f"expected {value or kind}, got {v or 'end'}")
        self.i += 1
        return v

    def parse(self):
        tree = self.expr()
        if self.peek()[0] != "end":
            raise ValueError(f"unexpected {self.peek()[1]}")
        return tree

    def expr(self):
        node = self.term()
        while self.peek() in (("op", "+"), ("op", "-")):
            node = (self.take("op"), node, self.term())
        return node

    def term(self):
        node = self.factor()
        while self.peek() in (("op", "*"), ("op", "/")):
            node = (self.take("op"), node, self.factor())
        return node

    def factor(self):
        kind, value = self.peek()
        if kind == "num":
            self.i += 1
            return ("num", float(value))
        if kind == "cell":
            self.i += 1
            self.refs.add(value)
            return ("ref", value)
        if (kind, value) == ("op", "-"):
            self.i += 1
            return ("neg", self.factor())
        if (kind, value) == ("op", "("):
            self.i += 1
            node = self.expr()
            self.take("op", ")")
            return node
        if kind == "fn":
            self.i += 1
            self.take("op", "(")
            a = self.take("cell")
            self.take("op", ":")
            b = self.take("cell")
            self.take("op", ")")
            cells = expand_range(a, b)
            self.refs.update(cells)
            return ("sum", cells)
        raise ValueError(f"unexpected {value or 'end'}")


class Sheet:
    def __init__(self) -> None:
        self.values: Dict[str, float] = {}
        self.trees: Dict[str, tuple] = {}
        self.deps: Dict[str, Set[str]] = {}
        self.dependents: Dict[str, Set[str]] = {}

    def get(self, cell: str) -> float:
        return self.values.get(cell, 0.0)

    def set(self, cell: str, value: Union[float, str]) -> None:
        if isinstance(value, str) and value.startswith("="):
            parser = _Parser(value[1:])
            tree, refs = parser.parse(), parser.refs
        else:
            tree, refs = ("num", float(value)), set()
        if cell in refs or self._reaches(refs, cell):
            raise CycleError(f"{cell} would depend on itself")
        saved = (dict(self.values), dict(self.trees),
                 {k: set(v) for k, v in self.deps.items()},
                 {k: set(v) for k, v in self.dependents.items()})
        try:
            for ref in self.deps.get(cell, set()):
                self.dependents[ref].discard(cell)
            self.deps[cell] = refs
            for ref in refs:
                self.dependents.setdefault(ref, set()).add(cell)
            self.trees[cell] = tree
            self._recompute(cell)
        except Exception:
            self.values, self.trees, self.deps, self.dependents = saved
            raise

    # ---- internals ----------------------------------------------------------
    def _reaches(self, starts: Set[str], target: str) -> bool:
        stack, seen = list(starts), set()
        while stack:
            c = stack.pop()
            if c == target:
                return True
            if c not in seen:
                seen.add(c)
                stack.extend(self.deps.get(c, ()))
        return False

    def _recompute(self, cell: str) -> None:
        affected, stack = {cell}, [cell]
        while stack:
            for d in self.dependents.get(stack.pop(), ()):
                if d not in affected:
                    affected.add(d)
                    stack.append(d)
        indegree = {c: len(self.deps.get(c, set()) & affected) for c in affected}
        ready = deque(c for c, n in indegree.items() if n == 0)
        while ready:
            c = ready.popleft()
            self.values[c] = self._eval(self.trees[c])
            for d in self.dependents.get(c, ()):
                if d in affected:
                    indegree[d] -= 1
                    if indegree[d] == 0:
                        ready.append(d)

    def _eval(self, node: tuple) -> float:
        kind = node[0]
        if kind == "num":
            return node[1]
        if kind == "ref":
            return self.get(node[1])
        if kind == "neg":
            return -self._eval(node[1])
        if kind == "sum":
            return sum(self.get(c) for c in node[1])
        a, b = self._eval(node[1]), self._eval(node[2])
        if kind == "+":
            return a + b
        if kind == "-":
            return a - b
        if kind == "*":
            return a * b
        if b == 0:
            raise ZeroDivisionError("division by zero")
        return a / b

Snapshotting the whole sheet on every set keeps the rollback obviously correct but costs O(sheet). In production, record only the touched cells' old values and edges (an undo log), which costs O(affected).

Let A be the number of cells affected by a change (the cell plus its transitive dependents) and E the edges among them.

• get: O(1).
• set: parse O(formula length + range size); cycle check O(cells reachable from the new references); recompute O(A + E) plus the evaluation cost of each affected formula.
• A SUM(A1:A1000) cell has 1,000 dependency edges; changing any of those 1,000 cells recomputes the sum in O(1,000). Follow-up 2 fixes this.

1. Lazy evaluation. Mark dependents dirty on set and compute on get with memoization. Cheaper when many cells change between reads; get is no longer O(1).
2. Big ranges. Instead of an edge from every cell in SUM(A1:A100000), register the range once in an interval index per column, and on a change find the ranges that contain the cell. Incremental aggregates (add the delta to the sum) make the update O(1) for SUM.
3. Error values. Store #DIV/0! or #REF! as values that propagate through formulas, instead of rejecting the set. That is how real spreadsheets behave and it lets users save a sheet mid-edit.
4. Collaboration. Two users editing cells at once: each set is an operation on one cell; order them on a server and recompute. Cycles created by two concurrent edits (each fine alone) must be detected at apply time on the server.
5. Large sheets. Millions of cells: store sparse maps per column, recompute on worker threads in topological levels, and stream visible values to the client first.

Mid-level (L4)

• Correct values for numbers and simple formulas with references, and updates that propagate to dependents.
• Detects at least direct cycles and refuses them.
• Tests a chain of dependencies.

Senior (L5)

• A real parser with precedence, parentheses and ranges; the dependency graph in both directions.
• Cycle detection before committing, and recomputation in topological order so each cell is computed once (diamond case).
• A failed set leaves the sheet unchanged.

Staff (L6+)

• Compares eager and lazy evaluation and handles large ranges with interval indexes and incremental aggregates.
• Error values that propagate, collaborative edits and how cycles across concurrent edits are caught.
• Plans for scale: sparse storage, parallel recomputation, visible-first updates.