"""Reference solution — Spreadsheet Formula Evaluation.

DO NOT READ BEFORE YOU HAVE RUN THE PROBLEM UNDER THE CLOCK.
Teaching text: ../../../WARMUP.md § Chapter 7.

Three things carry this problem.

1. THREE VISIT STATES, NOT TWO. WHITE unvisited, GREY on the current recursion
   stack, BLACK fully explored. Reaching a GREY node is a back edge, which is
   exactly a cycle. A two-state "visited" set conflates "on my current path"
   with "already finished", so it either misses cycles or flags a legal diamond
   (A->B->D, A->C->D) as one.

2. THE REVERSE GRAPH. The forward graph answers "what does this cell read".
   Incremental recompute needs "what reads this cell". Keep both, and DETACH
   the stale reverse edges when a formula changes, or phantom recomputation
   accumulates silently over the life of the sheet.

3. NO eval(). Even with __builtins__ stripped there are known escapes through
   attribute traversal on literals. A tokenizer plus a recursive-descent parser
   is about sixty lines and it only knows the operations you implemented.
"""

from __future__ import annotations

import re
from collections import deque

CELL_RE = re.compile(r"^([A-Z]+)([0-9]+)$")
TOKEN_RE = re.compile(r"""
      (?P<number>\d+(?:\.\d+)?)
    | (?P<range>[A-Z]+[0-9]+:[A-Z]+[0-9]+)
    | (?P<cell>[A-Z]+[0-9]+)
    | (?P<name>[A-Z_][A-Z_0-9]*)
    | (?P<op>[-+*/(),])
    | (?P<space>\s+)
""", re.VERBOSE)


class CycleError(Exception):
    def __init__(self, cycle):
        self.cycle = cycle
        super().__init__(" -> ".join(cycle))


class ParseError(Exception):
    pass


# ---------------------------------------------------------------------------
# Tokenizer + recursive-descent parser -> an AST of plain tuples
# ---------------------------------------------------------------------------


def tokenize(text):
    tokens, pos = [], 0
    while pos < len(text):
        match = TOKEN_RE.match(text, pos)
        if match is None:
            raise ParseError(f"unexpected character {text[pos]!r} at {pos}")
        pos = match.end()
        kind = match.lastgroup
        if kind != "space":
            tokens.append((kind, match.group()))
    return tokens


class _Parser:
    """expr := term (('+'|'-') term)*
       term := unary (('*'|'/') unary)*
      unary := '-' unary | atom
       atom := number | cell | range | NAME '(' args ')' | '(' expr ')'
    """

    def __init__(self, tokens):
        self._t, self._i = tokens, 0

    def _peek(self):
        return self._t[self._i] if self._i < len(self._t) else (None, None)

    def _take(self, value=None):
        kind, text = self._peek()
        if kind is None or (value is not None and text != value):
            raise ParseError(f"expected {value!r}, got {text!r}")
        self._i += 1
        return text

    def parse(self):
        node = self.expr()
        if self._i != len(self._t):
            raise ParseError(f"trailing input at token {self._i}")
        return node

    def expr(self):
        node = self.term()
        while self._peek()[1] in ("+", "-"):
            op = self._take()
            node = ("binop", op, node, self.term())
        return node

    def term(self):
        node = self.unary()
        while self._peek()[1] in ("*", "/"):
            op = self._take()
            node = ("binop", op, node, self.unary())
        return node

    def unary(self):
        if self._peek()[1] == "-":
            self._take()
            return ("neg", self.unary())
        return self.atom()

    def atom(self):
        kind, text = self._peek()
        if kind == "number":
            self._take()
            return ("num", float(text) if "." in text else int(text))
        if kind == "range":
            self._take()
            start, end = text.split(":")
            return ("range", start, end)
        if kind == "cell":
            self._take()
            return ("cell", text)
        if kind == "name":
            self._take()
            self._take("(")
            args = []
            if self._peek()[1] != ")":
                args.append(self.expr())
                while self._peek()[1] == ",":
                    self._take()
                    args.append(self.expr())
            self._take(")")
            return ("call", text, args)
        if text == "(":
            self._take()
            node = self.expr()
            self._take(")")
            return node
        raise ParseError(f"unexpected token {text!r}")


def parse_formula(body):
    return _Parser(tokenize(body)).parse()


def expand_range(start, end):
    c0, r0 = CELL_RE.match(start).groups()
    c1, r1 = CELL_RE.match(end).groups()
    for col in range(_col_index(c0), _col_index(c1) + 1):
        for row in range(int(r0), int(r1) + 1):
            yield f"{_col_name(col)}{row}"


def _col_index(name):
    value = 0
    for ch in name:
        value = value * 26 + (ord(ch) - 64)
    return value


def _col_name(index):
    out = ""
    while index:
        index, rem = divmod(index - 1, 26)
        out = chr(65 + rem) + out
    return out


def refs_of(node, out):
    kind = node[0]
    if kind == "cell":
        out.add(node[1])
    elif kind == "range":
        out.update(expand_range(node[1], node[2]))
    elif kind == "binop":
        refs_of(node[2], out)
        refs_of(node[3], out)
    elif kind == "neg":
        refs_of(node[1], out)
    elif kind == "call":
        for arg in node[2]:
            refs_of(arg, out)
    return out


def uses_volatile(node, volatile_names):
    kind = node[0]
    if kind == "call":
        if node[1] in volatile_names:
            return True
        return any(uses_volatile(a, volatile_names) for a in node[2])
    if kind == "binop":
        return uses_volatile(node[2], volatile_names) or \
               uses_volatile(node[3], volatile_names)
    if kind == "neg":
        return uses_volatile(node[1], volatile_names)
    return False


# ---------------------------------------------------------------------------


class Sheet:
    WHITE, GREY, BLACK = 0, 1, 2

    def __init__(self):
        self._raw = {}
        self._ast = {}
        self._value = {}
        self._deps = {}          # cell -> set of cells it reads
        self._dependents = {}    # cell -> set of cells that read it
        self._cycles = {}        # cell -> the cycle path it belongs to
        self._volatile = {}      # NAME -> callable
        self._volatile_cells = set()
        self.evaluations = 0

    # ---- volatile functions ---------------------------------------------
    def register_volatile(self, name, fn):
        self._volatile[name] = fn

    # ---- editing ---------------------------------------------------------
    def set_cell(self, cell, raw):
        self._raw[cell] = raw

        # Detach stale reverse edges FIRST, or phantom dependents accumulate
        # and incremental recompute quietly degrades toward full recompute.
        for old in self._deps.get(cell, ()):
            dependents = self._dependents.get(old)
            if dependents:
                dependents.discard(cell)

        if isinstance(raw, str) and raw.startswith("="):
            try:
                node = parse_formula(raw[1:])
            except ParseError:
                self._ast[cell] = None
                self._deps[cell] = set()
                self._value[cell] = "#ERROR"
                self._volatile_cells.discard(cell)
                self._recompute_from(cell)
                return
            self._ast[cell] = node
            self._deps[cell] = refs_of(node, set())
            if uses_volatile(node, self._volatile):
                self._volatile_cells.add(cell)
            else:
                self._volatile_cells.discard(cell)
        else:
            self._ast[cell] = None
            self._deps[cell] = set()
            self._volatile_cells.discard(cell)

        for dep in self._deps[cell]:
            self._dependents.setdefault(dep, set()).add(cell)

        self._recompute_from(cell)

    # ---- graph -----------------------------------------------------------
    def _dirty_set(self, changed):
        seen, queue = {changed}, deque([changed])
        while queue:
            node = queue.popleft()
            for dependent in self._dependents.get(node, ()):
                if dependent not in seen:
                    seen.add(dependent)
                    queue.append(dependent)
        return seen

    def _toposort(self, subset):
        color = {c: self.WHITE for c in subset}
        order, path = [], []

        def visit(node):
            state = color.get(node, self.BLACK)
            if state == self.BLACK:
                return
            if state == self.GREY:                      # back edge == cycle
                raise CycleError(path[path.index(node):] + [node])
            color[node] = self.GREY
            path.append(node)
            for dep in self._deps.get(node, ()):
                if dep in color:
                    visit(dep)
            path.pop()
            color[node] = self.BLACK
            order.append(node)

        for cell in sorted(subset):
            visit(cell)
        return order

    def _recompute_from(self, changed):
        dirty = self._dirty_set(changed)
        for cell in dirty:
            self._cycles.pop(cell, None)
        try:
            order = self._toposort(dirty)
        except CycleError as exc:
            for cell in exc.cycle:
                self._cycles[cell] = list(exc.cycle)
                self._value[cell] = "#CIRCULAR"
            # Cells outside the cycle still evaluate.
            rest = [c for c in dirty if c not in self._cycles]
            try:
                for cell in self._toposort(set(rest)):
                    self._value[cell] = self._evaluate(cell)
            except CycleError:
                pass
            return
        for cell in order:
            self._value[cell] = self._evaluate(cell)

    def recalc(self):
        """Force a pass. Volatile cells and their dependents must recompute."""
        if not self._volatile_cells:
            return
        dirty = set()
        for cell in self._volatile_cells:
            dirty |= self._dirty_set(cell)
        for cell in self._toposort(dirty):
            self._value[cell] = self._evaluate(cell)

    # ---- evaluation ------------------------------------------------------
    def _numeric(self, cell):
        value = self._value.get(cell, 0)
        return value if isinstance(value, (int, float)) else 0

    def _evaluate(self, cell):
        self.evaluations += 1
        node = self._ast.get(cell)
        if node is None:
            raw = self._raw.get(cell, 0)
            if isinstance(raw, str) and raw.startswith("="):
                return "#ERROR"
            return raw
        try:
            return self._eval_node(node)
        except ZeroDivisionError:
            return "#ERROR"
        except Exception:
            return "#ERROR"

    def _eval_node(self, node):
        kind = node[0]
        if kind == "num":
            return node[1]
        if kind == "cell":
            if self._value.get(node[1]) == "#CIRCULAR":
                raise ValueError("circular")
            return self._numeric(node[1])
        if kind == "neg":
            return -self._eval_node(node[1])
        if kind == "binop":
            left, right = self._eval_node(node[2]), self._eval_node(node[3])
            op = node[1]
            if op == "+":
                return left + right
            if op == "-":
                return left - right
            if op == "*":
                return left * right
            if right == 0:
                raise ZeroDivisionError
            result = left / right
            return int(result) if float(result).is_integer() else result
        if kind == "range":
            return [self._numeric(c) for c in expand_range(node[1], node[2])]
        if kind == "call":
            name, args = node[1], node[2]
            if name in self._volatile:
                return self._volatile[name]()
            values = []
            for arg in args:
                evaluated = self._eval_node(arg)
                if isinstance(evaluated, list):
                    values.extend(evaluated)
                else:
                    values.append(evaluated)
            if name == "SUM":
                return sum(values)
            if name == "MIN":
                return min(values) if values else 0
            if name == "MAX":
                return max(values) if values else 0
            if name == "COUNT":
                return len(values)
            raise ValueError(f"unknown function {name}")
        raise ValueError(f"unknown node {kind}")

    # ---- reads -----------------------------------------------------------
    def get_value(self, cell):
        return self._value.get(cell, 0)

    def cycle_for(self, cell):
        return list(self._cycles[cell]) if cell in self._cycles else None