Problem 536622 · hard · Level 05 Advanced Algorithms & Graphs

All or Nothing, Even Inside Each Other

py-context-managers · py-classes · py-api-design · transactions · rollback · nesting

A club treasurer moves money between members' accounts. A group of moves either happens completely or not at all: if anything goes wrong halfway, every balance must be as it was before the group started. Groups can contain smaller groups, and a small group that fails may be caught and ignored by the larger one.

Write a class Ledger(balances), where balances is a dictionary from account name to a whole number of pounds. The ledger keeps its own copy of it.

  • deposit(acct, x) adds x to acct, creating the account with balance 0 first if it does not exist.
  • withdraw(acct, x) takes x from acct. transfer(src, dst, x) moves x from src to dst.
  • An operation raises ValueError if x <= 0 or if it would make a balance negative, and KeyError for an account that does not exist (deposits excepted). A failed operation changes nothing.
  • balances() returns a new sorted list of (acct, balance) pairs.
  • journal() returns a new list of the committed operations, oldest first, as tuples ("deposit", acct, x), ("withdraw", acct, x) or ("transfer", src, dst, x).
  • transaction() returns a context manager; with ledger.transaction(): gives the ledger itself to as. If the block raises, every change made inside it (including changes from nested blocks that had succeeded) is undone, and the exception continues to the caller. If it succeeds, its changes stay, but they join the journal only when the outermost open transaction succeeds. Operations outside any transaction are committed at once.
  • depth is the number of transactions currently open.

Setup helpers, available with Run: run_ledger(initial, script) plays a script of operations and nested transactions (its docstring lists the steps, including ("fail", message), which raises on purpose, and ("peek",), which records depth, journal length and balances), no_aliasing(), and busy_day(n, seed), a long random day of nested transactions.

Examples

Input:  run_ledger({"ana": 100, "ben": 50}, [
            ("transfer", "ana", "ben", 30),
            ("tx", [("withdraw", "ben", 80), ("deposit", "cat", 10), ("fail", "card declined")], True),
            ("tx", [("deposit", "ana", 5), ("tx", [("withdraw", "ana", 500)], True),
                    ("peek",), ("transfer", "ben", "ana", 1)], True)])
Output: ([("ana", 76), ("ben", 79)],
         [("transfer", "ana", "ben", 30), ("deposit", "ana", 5), ("transfer", "ben", "ana", 1)],
         ["RuntimeError: card declined", "ValueError", (1, 1, [("ana", 75), ("ben", 80)])])

Constraints

  • Up to 20 accounts and 10**4 operations; transactions nest at most 10 deep.

Goals

  • Undo every change made inside a failed `with` block, and only those
  • Support nested blocks with a stack of saved states
  • Keep uncommitted work invisible until the outermost block succeeds
Starting Python…