The harness in code · Code exercises

An approval-gate state machine

Implement the gate that decides each credit note once, refuses late, repeated and self-approved decisions, and turns silence into expired, never approved.

codehardExercise · 4 min · 45 of 75

On this page

A gate decides once. The four states are the easy part; the work is in what it refuses, and in a clock that turns silence into "expired" rather than "approved".

The situation

The 40-person wholesaler this module uses in place of the agency turns each damaged delivery to one of its 900 cafés into a credit note. Its automation drafts each one (the café, the lines, the amount) and posts it to you in chat with Approve and Reject buttons. Every credit note over $200 waits for a person; last quarter that was 140 requests.

Three went wrong. An approval tapped two days after the request issued a $380 credit to a café the bookkeeper had already refunded by phone. A double tap on Approve issued the same $260 credit twice. And the drafting agent, which had the approve tool in its tool list, approved its own $540 request.

A request now expires 4 hours after it is made, 14,400 seconds, and an expired request goes to the escalation queue, never to the accounting API. Approval gates decides where gates go and how long their clocks run; this exercise builds the one in why we write these five by hand.

The question

Implement the gate so that each of the three incidents is a refused event and the examples below hold. The read at now applies the clock too, so a request nobody touched reads as expired.

def solve(events, ttl, now):
    """events: [(t, item, action, actor)], t non-decreasing, in seconds. action is
    "request", "approve" or "reject"; actor names who sent it. ttl: seconds a request
    stays pending. now: when the states are read, at or after the last event.
    A request opens an unused item as "pending" with deadline t + ttl and records its
    actor as the requester. An approve or reject is accepted only while the item is
    pending, before its deadline, and from an actor other than the requester.
    Returns (refused, states): the indices of refused events, in order, and a dict
    mapping every opened item to "pending", "approved", "rejected" or "expired" at now."""

R = (0, "cn-1", "request", "agent")
solve([R, (600, "cn-1", "approve", "founder")], 14400, 1000)
    -> ([], {"cn-1": "approved"})
solve([R, (600, "cn-1", "approve", "founder"), (601, "cn-1", "approve", "founder")], 14400, 1000)
    -> ([2], {"cn-1": "approved"})        # the double tap
solve([R, (172800, "cn-1", "approve", "founder")], 14400, 172800)
    -> ([1], {"cn-1": "expired"})         # two days late
solve([R, (5, "cn-1", "approve", "agent")], 14400, 10)
    -> ([1], {"cn-1": "pending"})         # the agent approving itself

Only pending moves. A refused event is a loop that changes nothing, and the clock leads to expired, never to approved.

A strong answer · Rubric · Where answers go wrong · Solution

Write your answer first, then open

A strong answer

Four states, and the legal moves as data: (pending, approve) → approved and (pending, reject) → rejected. Every pair missing from the table is refused, which is how the double tap fails: the second approve finds approved, has no row, and changes nothing (example 2). A refusal never mutates the gate.

Inside one event the order is fixed. First the clock: a pending item at or past t + ttl becomes expired, the same boundary the key store uses, so an approval at exactly 4 hours is late. The two-day tap finds expired and is refused (example 3): the $380 incident. Then the table. Then the guard: the actor must not be the requester. The agent's own approval is refused and the request stays pending for a real one (example 4), the $540 incident. Remove the approve tool from the agent as well; the guard is what holds when someone adds it back.

Expiry is lazy, applied when an event touches the item and again at the read, so no timer is needed for correctness. A sweeper still has to read the gate every few minutes and move expired items to a person, as escalation paths and the manager requires; otherwise an expired request is correct and unseen. A reused id and a decision on an unknown id are refused too: a revised credit note gets a new id.

The three incidents cost $380 + $260 + $540 = $1,180 in one quarter. What would move the 4 hours is decisions routinely taking longer while nothing changes underneath them, and even then a second approver beats a longer clock.

Rubric

holds the legal moves in a table and refuses every pair not in it, with no state change on a refusal
applies the clock before the table, so a decision at or after the deadline is refused and the item reads expired
refuses a decision from the requester and leaves the request pending for someone else
refuses a second request under a used id and any decision on an unknown one
expires untouched requests at the read, and names the sweeper that takes them to escalation
maps each of the three incidents to the refusal that stops it

Where answers go wrong

"A status field and an if per button." It works until someone adds a button. A "reopen" handler written later lets an approved credit note be approved again, because nothing says which moves exist; with a table, a new move is a new row someone has to write.

"Expire with a timer that fires at 4 hours." The timer is lost on a restart, and a tap that lands before a busy worker runs the timer goes through at 4 hours and 2 seconds. Comparing the event's time with the deadline is what holds.

"On timeout, approve: you would have said yes." The $380 credit was exactly an item whose answer had changed while it waited. An expired request goes to escalation, never to the API.

Solution

Python 3 · standard library57 lines · 12 of 12 tests passing

"""An approval-gate state machine — pending, approved, rejected, expired, with a clock and a refusal for everything else."""

# The only legal moves out of pending. Anything not in the table is refused,
# so a new action is refused until someone adds a row for it.
DECISIONS = {
    ("pending", "approve"): "approved",
    ("pending", "reject"): "rejected",
}


def expire(gate, item, t):
    """The clock runs before the table: a pending item at or past its deadline is expired."""
    entry = gate[item]
    if entry["state"] == "pending" and t >= entry["deadline"]:
        entry["state"] = "expired"


def step(gate, t, item, action, actor, ttl):
    """Apply one event. Returns True if the gate accepted it; a refused event changes nothing."""
    if action == "request":
        if item in gate:
            return False                          # one id, one decision: a revised request gets a new id
        gate[item] = {"state": "pending", "deadline": t + ttl, "requester": actor}
        return True
    if item not in gate:
        return False                              # a decision on nothing
    expire(gate, item, t)
    entry = gate[item]
    nxt = DECISIONS.get((entry["state"], action))
    if nxt is None:
        return False                              # double tap, late tap, approve after reject
    if actor == entry["requester"]:
        return False                              # the requester cannot decide its own request
    entry["state"] = nxt
    return True


def solve(events, ttl, now):
    """events: [(t, item, action, actor)], t non-decreasing, in seconds. action is
    "request", "approve" or "reject"; actor names who sent it. ttl: seconds a request
    stays pending. now: when the states are read, at or after the last event.
    A request opens an unused item as "pending" with deadline t + ttl and records its
    actor as the requester. An approve or reject is accepted only while the item is
    pending, before its deadline, and from an actor other than the requester.
    Returns (refused, states): the indices of refused events, in order, and a dict
    mapping every opened item to "pending", "approved", "rejected" or "expired" at now."""
    gate = {}
    refused = []
    for i, (t, item, action, actor) in enumerate(events):
        if not step(gate, t, item, action, actor, ttl):
            refused.append(i)
    for item in gate:
        expire(gate, item, now)                   # nothing waits silently: the read applies the clock too
    return refused, {item: entry["state"] for item, entry in gate.items()}


H4 = 14400                                        # four hours, in seconds

The cases that ran

TESTS = [
    # the examples on the page
    (([(0, "cn-1", "request", "agent"), (600, "cn-1", "approve", "founder")], H4, 1000),
     ([], {"cn-1": "approved"})),
    (([(0, "cn-1", "request", "agent"), (600, "cn-1", "approve", "founder"), (601, "cn-1", "approve", "founder")], H4, 1000),
     ([2], {"cn-1": "approved"})),
    (([(0, "cn-1", "request", "agent"), (172800, "cn-1", "approve", "founder")], H4, 172800),
     ([1], {"cn-1": "expired"})),
    (([(0, "cn-1", "request", "agent"), (5, "cn-1", "approve", "agent")], H4, 10),
     ([1], {"cn-1": "pending"})),
    # an approval at exactly the deadline is late
    (([(0, "cn-1", "request", "agent"), (H4, "cn-1", "approve", "founder")], H4, H4),
     ([1], {"cn-1": "expired"})),
    # the clock expires a request nobody touched, at the read
    (([(0, "cn-1", "request", "agent")], H4, H4), ([], {"cn-1": "expired"})),
    (([(0, "cn-1", "request", "agent")], H4, H4 - 1), ([], {"cn-1": "pending"})),
    # a refused self-approval leaves the request open for a real one
    (([(0, "cn-1", "request", "agent"), (5, "cn-1", "approve", "agent"), (600, "cn-1", "approve", "founder")], H4, 1000),
     ([1], {"cn-1": "approved"})),
    # rejected is final
    (([(0, "cn-1", "request", "agent"), (60, "cn-1", "reject", "founder"), (120, "cn-1", "approve", "founder")], H4, 1000),
     ([2], {"cn-1": "rejected"})),
    # a reused id and a decision on an unknown id are both refused
    (([(0, "cn-1", "request", "agent"), (1, "cn-1", "request", "agent"), (2, "cn-9", "approve", "founder")], H4, 10),
     ([1, 2], {"cn-1": "pending"})),
    # two items on one clock: one decided in time, one left to expire
    (([(0, "cn-1", "request", "agent"), (100, "cn-2", "request", "agent"), (200, "cn-2", "reject", "bookkeeper")], 300, 300),
     ([], {"cn-1": "expired", "cn-2": "rejected"})),
    (([], H4, 0), ([], {})),
]