Problem 329258 · hard · Level 03 Linear Management & Searching

Spreadsheet Cells That Ask Each Other

py-closures · py-higher-order · py-exceptions · memoisation · cycle detection

In a tiny spreadsheet every cell has a formula: a function that takes one argument, get, and returns the cell's value. A formula asks for other cells by calling get(name). For example {"a": lambda get: 2, "b": lambda get: get("a") * 10} gives b the value 20.

Write make_sheet(formulas) that returns a function value(name), which returns the value of cell name:

  • A formula runs at most once over the life of the sheet: after it has produced a value, that value is reused by every later value or get call.
  • Asking for a name that has no formula raises KeyError(name).
  • A cell that (directly or through other cells) needs its own value is a cycle: raise ValueError with the message "cycle: " followed by the cells involved, from the repeated cell back to itself, joined by " -> ", for example "cycle: a -> b -> a".
  • Any other exception raised by a formula (such as ZeroDivisionError) passes through unchanged, and nothing is stored for a cell whose formula did not finish.
  • After any error, the sheet keeps working: other cells can still be asked for, and asking again starts afresh.

The tests use the helper query(make_sheet, formulas, names), which builds one sheet, asks for each name in turn, and returns (answers, calls): each answer is the value, or "ValueError: message" or "KeyError: message" for those errors and just the exception's name for any other, and calls counts how often each formula ran. budget_sheet(months) builds a larger sheet. Both are available with Run.

Examples

Input:  query(make_sheet, {"a": lambda get: 2, "b": lambda get: get("a") * 10,
                           "c": lambda get: get("b") + get("a")}, ["c", "b"])
Output: ([22, 20], {"c": 1, "b": 1, "a": 1})

Input:  query(make_sheet, {"a": lambda get: get("b"), "b": lambda get: get("a"), "c": lambda get: 5},
              ["a", "c", "b"])
Output: (["ValueError: cycle: a -> b -> a", 5, "ValueError: cycle: b -> a -> b"],
         {"a": 2, "b": 2, "c": 1})

Input:  query(make_sheet, {"x": lambda get: get("nope")}, ["x"])
Output: (["KeyError: 'nope'"], {"x": 1})

Constraints

  • Up to 2000 cells; chains of cells that depend on each other are at most 150 long.
  • Formulas do not catch the exceptions raised by get.

Goals

  • Pass a function to other functions so they can ask for the values they need
  • Keep a cache and a list of cells in progress inside a closure
  • Report a circular reference with a precise error, and clean up with `finally` so the sheet stays usable
Starting Python…