07 — Vending Machine System

“Design a vending machine. Coins in, snack out, change back.”

The brief sounds mechanical: build an object model — a set of classes and the relationships between them — for a machine that takes coins, dispenses a snack, and returns the right change.

The vending machine is not the interesting part. Two things underneath it are:

• A state machine: a design where the same button press means different things depending on what the machine is currently doing. Press A1 with no money in and it refuses. Press it with 75 cents in and it sells. Press it while the motor is still turning and it refuses again, for a different reason.
• The change-making algorithm: a real computer-science problem hiding inside a money question. The obvious rule for making change is wrong, and it is wrong in a way you can demonstrate in three lines of Python.

By the end of this chapter you should be able to:

1. Say exactly when one class per state beats a chain of if statements — and when it does not.
2. Explain why holding the customer’s coins aside, instead of banking them immediately, deletes an entire category of failure.
3. Run Python that shows the obvious change-making rule refusing to pay out thirty cents from a machine that is physically holding thirty cents.

What goes in, and what comes out

The five requests

Fix the shape of the thing before drawing any classes. The object at the centre is a VendingMachine, and it accepts five requests. Three come from a person and two come from the hardware, which matters more than it sounds like it should.

The block below is the interface, written as input and output pairs. Read the OUT lines carefully: none of them says “returns X”.

IN   insert_coin(25)      a coin, measured in cents, dropped into the slot
OUT  nothing is returned. The coin is now held aside in `escrow` -- money
     belonging to nobody yet, defined in section 1 -- and `credit` reads 25
     ...or it raises InvalidOperation: -35 is not a coin this machine takes

IN   select("A1")         a column code punched on the keypad
OUT  nothing is returned. The answer shows up as changes you can observe:
     `coin_return` receives the change, the slot's count drops by one,
     `credit` returns to 0, and the machine is now DISPENSING
     ...or it raises OutOfStock / InsufficientFunds / ExactChangeOnly
     and changes NOTHING -- the credit is untouched, the state is unchanged

IN   dispensed()          the HARDWARE reporting that the motor finished
OUT  nothing is returned. The product is in `tray` and the machine is IDLE

IN   cancel() then refunded()
OUT  nothing is returned. The customer's own coins are in `coin_return`

Why nothing returns a value

None of those five calls returns a value. The output of this design is not a return value; it is a set of observable changes to four places — the tray, the coin return, the inventory count, and a log of which state the machine moved to.

That is why the tests later in the chapter assert on m.tray, m.coin_return, m.slots["A1"].count and m.transitions rather than on what a method handed back.

Say that out loud in the interview. Naming your observation points before you write code is what makes the code testable.

The two things that go wrong

Both are visible in the block above.

First: the machine is trivial and the state machine is not. Every candidate writes if status == "idle" ... elif status == "has_money". It works. It keeps working right up to the third state, at which point one method contains every rule the machine has. Adding a fourth state then means editing five methods that each already handle four cases, and the type checker cannot help with any of it.

Second: the money hides a real algorithm. Making change is not “give the biggest coin that fits”.

That rule — always take the largest coin that still fits — is called a greedy strategy, because it commits to the locally best choice and never reconsiders. Greedy is optimal on the United States coin system, and only because that system happens to be what mathematicians call canonical: a currency where greedy always lands on the fewest coins.

Even on US coins it breaks the moment the machine runs low. A vending machine’s coin store is finite, and greedy has no way to back out of a choice that strands it. Decision 3 change making and where greedy fails shows a machine that can pay 30 cents and refuses to, because greedy took the quarter.

Optional background

Three links, offered for depth. None is required to follow this chapter.

• The interview method — how to spend the 45 minutes — is 02 — the object-oriented design (OOD) framework.
• The pattern vocabulary is 03 — object-oriented programming (OOP) fundamentals. The three patterns this chapter needs are defined on the spot when they arrive: State (one class per situation the machine can be in), Command (a request turned into an object you can queue and log), and Strategy (a swappable policy object).
• The lock in Decision 2 the machine is a monitor not a singleton fixes the same read-then-write race that 05 — Movie Ticket Booking traces against a cinema seat. The version you need is restated here in full, so you can stay in this file.

1. Clarifying questions that change the design

Four questions decide which classes exist at all. Ask them before drawing anything, because each answer adds or deletes a class rather than merely adjusting one.

A yes puts the middle column into your design; a no is a whole piece you do not have to build.

Escrow, defined

Row two turns on a word that needs defining. Escrow is money held aside by the machine, belonging to nobody yet. It goes to the operator when the sale completes, or back to the customer when it does not.

The escrow question is the one that separates a design from a diagram. Compare the two answers concretely:

• No escrow. Coins drop straight into the bank. A customer puts in a dollar, changes her mind, and presses cancel. The machine now has to make one dollar of change out of the same bank — and if it only holds two quarters, it cannot. The cancel fails.
• Escrow. The dollar sits in a holding area. Cancel hands back the identical coin. There is no arrangement of coins in the machine that can make this impossible.

That is one decision that removes an entire failure mode.

Scope

Say the scope out loud before you start drawing. This design does not cover the electrical protocol that drives the physical motor, does not cover telemetry back to a fleet operator, and does not cover pricing promotions.

2. Actors and use cases

An actor is anyone or anything that sends the system a request. Three parties touch this machine, and the third one is the one candidates forget. Listing it is what turns the design from a function into a state machine.

Hardware being an actor is the reason a DISPENSING state exists at all.

If a selection instantly produced a snack, select would be an ordinary function: money in, product out, done. No state needed.

But the motor takes a second, and it can jam. So the machine has to sit in a situation where it has taken the money, has not yet delivered, and must refuse every button until the hardware reports back. Events that arrive from the machine are what make this a state machine rather than a function.

3. Core objects, and where behaviour lives

A first draft is one VendingMachine class holding a status string, a credit integer and a dictionary of products. That draft is not wrong about the data. It is wrong about where the rules go.

The four classes and the one field

The table below names each object, what it is responsible for, and — the column that carries the argument — why it is not simply a field on the machine.

Two words in that table are jargon and both are load-bearing.

A denomination is a coin value the machine recognises — 1, 5, 10, 25 and 100 cents here. So CoinBank is a mapping from each denomination to how many of that coin are physically in the machine.

An operation is total when it is defined for every input and can never fail. Escrow makes cancel total: there is no arrangement of coins in the machine that can make “give the customer back the exact metal she just put in” impossible.

Why exact change only is not a state

The display on a real machine sometimes reads “exact change only”. That looks like a mode, and candidates model it as one. Do not.

It is a predicate — a function returning true or false, computed on demand from data you already have. Over CoinBank, the predicate is: “does there exist a change amount I could be asked for that I cannot pay?” Because it is computed, it is recomputed after every transaction and shown on the display.

Modelling it as a state doubles the state count. Every one of the five states would gain an exact-change twin, giving ten, to represent something one function answers on demand.

A condition you can compute is never a state; a state is something you must remember. That sentence answers about a third of the follow-ups this problem generates.

4. Class diagram

The arrowheads in a class diagram carry claims that the boxes do not, so every arrow below gets read back as an English sentence.

The diagram is abridged: it shows the fields and methods that carry design weight, not every field on every class. The full field list for VendingMachine is in Working python the state machine. What to look at first is the shape — a five-way inheritance fan under State, and three lines out of VendingMachine that are not all the same kind of line.

classDiagram
    class VendingMachine {
        +int credit
        +list~int~ escrow
        +Slot pending
    }
    class State {
        <<abstract>>
        +insert_coin(machine, coin)
        +select(machine, code)
        +dispensed(machine)
        +cancel(machine)
        +refunded(machine)
    }
    class Idle
    class HasMoney
    class Dispensing
    class Refunding
    class OutOfService
    class Slot {
        +str code
        +str name
        +int price_cents
        +int count
    }
    class CoinBank {
        +dict counts
        +deposit(coins)
        +withdraw(plan)
        +plan_change(amount, extra) dict
        +exact_change_only(prices, max_payment) bool
    }

    VendingMachine "1" o-- "1" State : current
    State <|-- Idle : inheritance
    State <|-- HasMoney : inheritance
    State <|-- Dispensing : inheritance
    State <|-- Refunding : inheritance
    State <|-- OutOfService : inheritance
    VendingMachine "1" *-- "1..*" Slot : composition
    VendingMachine "1" *-- "1" CoinBank : composition

The notation

This is a UML class diagram. UML is the Unified Modeling Language, the standard set of shapes for drawing software structure.

Each box is a class. The lines inside a box are its fields and methods, and a leading + means public — visible to callers outside the class. <<abstract>> marks a class that is never instantiated on its own and exists to be inherited from.

The quoted numbers on the ends of a line are multiplicities: how many objects sit at that end. 1 means exactly one; 1..* means one or more.

Three line styles appear here and they mean three different things:

• <|-- is inheritance. The class at the arrowhead is the parent; the class at the tail is a child that is substitutable for it.
• *-- is composition, drawn with a filled diamond. The owner controls the part’s lifetime, and destroying the owner destroys the part.
• o-- is aggregation, drawn with a hollow diamond. A “has a” that does not own a lifetime, so the part can outlive the whole or be shared with others.

Reading the arrows back as sentences

Three arrows, three claims.

VendingMachine "1" o-- "1" State — a vending machine has exactly one current state, held by aggregation. Aggregation and not composition because the state objects hold no data and are shared between machines: the machine points at one without owning its lifetime. Decision 2 the machine is a monitor not a singleton explains why sharing them is safe.

State <|-- Idle and its four siblings — Idle, HasMoney, Dispensing, Refunding and OutOfService each inherit from State. The claim is substitutability: any of them can be dropped into the current slot and the machine will not notice the difference, because the machine only ever calls the five methods on the base class.

VendingMachine "1" *-- "1..*" Slot and *-- "1" CoinBank — a vending machine composes one or more slots and exactly one coin bank. Scrap the machine and the columns and the coin hopper go with it. That is what the filled diamond of composition asserts and what the hollow diamond of aggregation denies.

The hopper in that last sentence is the physical container of coins available for paying change. CoinBank is its software model.

What this class structure assumes

A class diagram is a frozen bet about what will change.

Every abstract type you draw says “I expect this to vary”. Every field you hard-code says “I expect this to hold forever”.

Naming those bets out loud is the transferable skill here. The specific vending machine is not going to be your job; the habit of stating your own assumptions is. The general form of the argument is What a class structure assumes. What follows is this design’s version.

Assumed to vary

These are the things the design expects to change, so each one got a type, an interface or a parameter. The third column is the price of having bet wrong.

Assumed fixed

These are baked into the structure rather than into a parameter. Changing one is a rewrite, not a configuration change.

The set of events is fixed at five, because the event list is the method list on the State base class.

This is the asymmetry worth naming without being asked: the State pattern makes adding a state cheap and adding an event expensive. A new state is a new class that touches nothing else. A new event is a new method on the base class, plus a decision in every existing state about whether to override it.

Four more fixed assumptions:

• One customer at a time. That is why credit is a single integer and pending is a single Slot rather than a queue.
• Money is a whole number of cents in one currency. No rounding, no floating point.
• One process, one lock. No distributed coordination.
• A purchase is exactly one item. Extension 3 buying several items at once deliberately breaks this one to show what it was holding up.

What any state machine assumes

Two of the assumptions above are not about vending machines at all. They are what any state machine is built on, and an interviewer probing the design is usually probing one of them.

1. The set of states is closed and known at design time.

Five classes are a claim that the machine is never in a sixth situation.

What breaks when it is: cut the power halfway through DISPENSING. On reboot the machine is in “I took the money and I do not know whether the snack fell”, which is not one of the five. You then either add a sixth state that exists only to be resolved at boot, or you pick one of the five arbitrarily and accept that some customers are robbed and some are given free snacks.

Extension 2 a maintenance and restock mode shows the subtler version: a state that has to remember where to return to afterwards is a state whose identity is not in the flat set. There are two honest repairs and both are expensive. One is a separate copy of that state per destination, and the set explodes. The other is a machine that keeps a return address — a hierarchical state machine, which is a different and larger kind of machine than this one.

2. Transitions are total — every combination of (state, event) has a defined outcome, with none left undefined.

Five states and five events give twenty-five combinations, and all twenty-five must mean something. The base class makes this true by construction: any combination a subclass does not override inherits a polite refusal.

What breaks without totality is Decision 1 state objects not a status field’s central point. An if/elif chain with a missing branch does not fail to compile. It falls off the end of the method and returns None, and the caller reads that as success.

Totality by inheritance has its own cost, and it is worth conceding. A combination you deliberately refused and a combination you forgot to implement look identical from outside — both produce the same courteous rejection. So a forgotten override presents in the field as “the button does nothing” rather than as a crash.

3. One state captures the whole situation.

This third assumption sits underneath both of the others. The moment two things vary independently — a door that can be open or shut while a payment is authorised or not — the honest model is the product of the two, and the state count multiplies instead of adding. Extension 1 card payment is where this design first feels that pressure.

What a different assumption would have produced

This is the part worth rehearsing. It is what interviewers reach for when they want to know whether you chose the design or copied it.

• If there were only two states, the if/elif version is correct and the State pattern is overhead. That crossover is argued with numbers in Decision 1 state objects not a status field.
• If the events churned instead of the states — new buttons every quarter, a stable set of situations — you would invert the design: keep the state as an enumerated value and write the transitions as a table of data, with one function per event reading the table. Adding an event is then one entry, and adding a state is a column everywhere. The State pattern is the wrong bet on that axis.
• If the machine gave no change, CoinBank, make_change and the entire exact-change predicate disappear, and the money model collapses to one integer.
• If dispensing were instantaneous and could not jam, DISPENSING and Refunding both vanish, hardware stops being an actor, and this stops being a state-machine problem at all — a fact worth stating, because the interviewer chose the version that has hardware in it on purpose.

5. Decision 1: State objects, not a status field

The case for one class per state is best made by counting: how many decisions the naive version has to get right, how many the State version has to write down, and where the line between them falls.

The version everybody writes

The block below is the naive design. It holds the machine’s situation in a status string and branches on it in every method. It is genuinely fine at two states.

Two things to look at: the comment inside insert_coin marking where the third, fourth and fifth branches would go, and the fact that select returns a value while the real design’s select returns nothing.

from __future__ import annotations

import threading
from abc import ABC
from dataclasses import dataclass
from typing import Iterable, Mapping, Protocol


class VendingError(Exception): ...
class InsufficientFunds(VendingError): ...
class OutOfStock(VendingError): ...
class ExactChangeOnly(VendingError): ...
class InvalidOperation(VendingError): ...


class StatusMachine:
    """One string field, one branch per (state, event) pair."""

    def __init__(self, price: int) -> None:
        self.status, self.credit, self.price = "idle", 0, price

    def insert_coin(self, coin: int) -> None:
        if self.status == "idle":
            self.credit += coin
            self.status = "has_money"
        elif self.status == "has_money":
            self.credit += coin
        # "dispensing" needs a third branch here, "refunding" a fourth,
        # "out_of_service" a fifth -- in THIS method, and in every other one.

    def select(self) -> str:
        if self.status != "has_money":
            raise InvalidOperation(self.status)       # and the same five-way fan-out
        if self.credit < self.price:
            raise InsufficientFunds(self.price - self.credit)
        self.credit -= self.price
        self.status = "idle"
        return "product"


# Drive it once, so the shortcut is visible rather than asserted.
s = StatusMachine(price=65)
for c in (25, 25, 25):
    s.insert_coin(c)
assert s.status == "has_money" and s.credit == 75
assert s.select() == "product"
assert s.status == "idle"
assert s.credit == 10        # the 10c of change is still sitting in `credit`,
                             # and the machine is back in "idle" holding it

The worked call at the bottom pays 75 cents for a 65-cent item. The item comes out, the status goes back to "idle" — and the 10 cents of change is still sitting in self.credit, because this version has no coin bank and no way to hand metal back. That stranded credit is the first thing the real design has to fix.

Python idioms in that block

Four of them, and they recur through the chapter.

• from __future__ import annotations tells Python to store type annotations as plain text instead of evaluating them. That lets you name a type before the class it names has been defined, and lets newer type syntax run on older interpreters.
• class VendingError(Exception): ... defines an exception type with an empty body. The ... is the literal Ellipsis object, used here purely as “nothing to write”.
• The exceptions are nested: InsufficientFunds inherits from VendingError, so a caller can catch one specific failure or catch all of them with a single except VendingError.
• Several imports here — ABC, dataclass, Iterable, Mapping, Protocol — are for blocks further down. A few of those blocks repeat their own imports so each can be copied out on its own, so this is not the file’s only import line.

The full transition table

The real machine has five states and five events. Writing out every combination is the step that makes the argument countable.

Read down a row to see everything one state does. Read down a column to see how one button behaves everywhere. Bold marks a cell that actually changes something; every other cell is some flavour of refusal.

The count

Now count what each design has to write — the arithmetic is the argument.

states                                         5
events                                         5
cells in the transition table
  5 x 5                                       =  25
cells in bold: transitions that do something   6
cells that reject, return the coin, or throw
  25 - 6                                      =  19
code units under State: 5 base defaults plus 6 overrides
  5 + 6                                       =  11

Nineteen of the twenty-five cells are “refuse politely”, and they are all the same refusal.

The if/elif version has to write all 25 somewhere, spread across 5 methods, with nothing enforcing that any of them is complete.

The State version writes the 19 once, as defaults on the base class, and overrides the 6 that matter. Eleven code units instead of twenty-five branches — and each one is a named method on a named type rather than a string comparison.

The scaling difference

This is the sentence to say out loud:

Adding a state to the if/elif version means auditing every event handler for a missing branch, and a missed one is silent — the method falls off the end and returns None. Adding a State subclass means writing only the transitions that state actually has; everything else inherits the refusal.

What State costs

Name this without being asked.

You can no longer read the machine’s behaviour top to bottom. select is spread across five classes, so answering “what happens if I press A1 right now” means knowing the current state first — a debugger question rather than a reading question.

Five extra types for a machine that fits on a napkin is a real tax. At two states the if/elif really is better. The crossover is the third state, which is why the brief for this chapter is the third state.

6. Decision 2: the machine is a monitor, not a Singleton

A vending machine really does have a concurrency bug, and one lock fixes it. The pattern candidates reach for at exactly this moment, though, deserves to be refused.

The race

A thread is an independent line of execution running inside the same program, sharing all of its memory. Two of them exist here whether you plan for them or not: a coin sensor firing on a hardware interrupt, and a button. They touch the same two fields.

The trace below runs time downward, with the two threads in two columns. Watch the button thread read credit once, then act on that stale reading after the coin sensor has changed it.

 coin sensor thread                       button thread
                                          select("A1"): seen = credit -> 65
 a 25c coin drops
   credit = 65 + 25 -> 90
                                          price 65 <= seen 65, allow
                                          credit = seen - price -> 0
 -- the cola is dispensed. The customer put in 90c for a 65c item and is owed
 -- 25c -- but `credit` was overwritten with the stale 65 minus the price, so
 -- the 25c is simply gone: no change, no coin return, and nothing in the log
 -- that looks wrong

That is a race condition: the outcome depends on the relative timing of two threads, and one of the possible interleavings is wrong.

The shape is always the same — read a value, decide something based on it, write a value back. The damage happens when the world moves between the read and the write.

A race that only sometimes reproduces is hard to argue about, so the block below performs the bad interleaving by hand. There are no real threads in it; the four statements after u.credit = 65 are the two threads’ steps, written in the damaging order. The failure is then an assertion rather than an anecdote.

class UnsafeMachine:
    """Read credit, decide, write credit -- with the world moving in between."""

    def __init__(self, price: int) -> None:
        self.credit, self.price, self.sold = 0, price, 0

    def commit(self, seen: int) -> None:
        self.sold += 1
        self.credit = seen - self.price       # writes back a stale total


u = UnsafeMachine(price=65)
u.credit = 65
seen = u.credit             # button thread reads
u.credit += 25              # coin sensor thread, in between
u.commit(seen)              # button thread writes back what it saw
assert u.sold == 1 and u.credit == 0, "the 25c vanished"

That last assertion passes, and that is the point: it is documenting the bug, not guarding against it.

u.sold == 1 says a cola went out. u.credit == 0 says the machine thinks it owes nothing. But the customer handed over 90 cents for a 65-cent item, so 25 cents is unaccounted for. commit wrote back seen - price, and seen was read before the coin landed.

The fix: the machine is a monitor

A monitor is an object with one lock, taken by every public method, so that only one thread is ever inside the object at a time.

Here every public method takes that one lock, because state, credit, escrow, inventory and the coin bank must move together or not at all.

The lock is an RLock — re-entrant, meaning the same thread may take it again without deadlocking itself — rather than a plain Lock. The reason to allow re-entry is that a future state method might call back into a guarded entry point.

No state does today. Every state method in Working python the state machine touches m.accept, m.to, m.bank, m.escrow, m.tray and m.coin_return, and not one of those takes the lock. If none ever will, a plain Lock is the honest choice.

Fine-grained locks — one lock per field instead of one per object — buy nothing here. There is one customer and one hopper, so the contention is one event at a time by construction.

Why not a Singleton

This is the point in the interview where the word Singleton arrives, and it should be refused.

A Singleton is a class rigged so that only one instance of it can ever exist in a program, usually by hiding the constructor behind a get_instance() that returns the same object forever.

The reasoning “there is one physical machine, so the class should be a Singleton” confuses a fact about the world with a constraint on the code. The table below takes each claim in turn.

Two terms from that table. An invariant is a statement that must be true at every observable moment. Lazy initialisation is creating the single object on first use rather than at startup — which is itself a read-then-write race between threads, the exact bug this section opened with.

Construct one VendingMachine in main() and pass it in. That is the entire replacement, and it is strictly better in every dimension the Singleton claimed. Handing an object its collaborators from outside instead of letting it fetch them is called dependency injection, and the whole of it here is one constructor argument.

Flyweight is not Singleton

There is one legitimate shared-instance move in this design: the State objects.

IDLE, HAS_MONEY and friends hold no data. Sharing them is a flyweight — one immutable instance shared by every user, because there is nothing in it to tell users apart. It is not a singleton. There is no global state because there is no state, and that is the entire difference between the two patterns.

The unguarded surface

State this caveat before an interviewer finds it.

state, credit, escrow, pending, transitions and bank.counts are public here for readability, and the lock guards the methods, not the fields. Three consequences:

• m.state = DISPENSING; m.pending = m.slots['A1']; m.dispensed() is a free snack in three lines, and never touches the lock.
• m.accept(1_000_000) is public and unguarded — it has to be, because the states call it — so it credits a million cents while m.state still reads idle.
• m.bank.counts[25] = 10**9 is infinite change.

The flyweights are exposed the same way: IDLE is a module-level name anyone can assign to.

In production these are private with read-only accessors, and the enforcement that actually matters lives below the object model, in the hardware and the audited cash count. The lock protects the method, not the field.

7. Working Python: the state machine

The design now becomes running code, in two blocks: the states first, then the machine that holds the data and the lock.

The base class and the five states

The first block has three parts. Read them in this order:

1. State, the base class. Its five methods are the five defaults — the nineteen refusals from the table above, written once.
2. The five subclasses. Each one overrides only the cells that do something. Count the overrides as you read: there are six.
3. The last two lines, which create one shared instance of each state and bind it to a module-level name in capitals.

class State(ABC):
    """Defaults refuse. Subclasses override only the cells that do something."""

    name: str                                          # a plain attribute...

    def __init_subclass__(cls, **kw: object) -> None:   # ...checked when the
        super().__init_subclass__(**kw)                 # SUBCLASS is defined
        if not isinstance(getattr(cls, "name", None), str):
            raise TypeError(f"{cls.__name__} must define `name` as a str")

    def insert_coin(self, m: "VendingMachine", coin: int) -> None:
        m.coin_return.append(coin)                     # not accepting money now

    def select(self, m: "VendingMachine", code: str) -> None:
        raise InvalidOperation(f"select is not valid in {self.name}")

    def dispensed(self, m: "VendingMachine") -> None:
        raise InvalidOperation(f"nothing is dispensing in {self.name}")

    def cancel(self, m: "VendingMachine") -> None:
        raise InvalidOperation(f"nothing to cancel in {self.name}")

    def refunded(self, m: "VendingMachine") -> None:
        raise InvalidOperation(f"no refund in flight in {self.name}")


class Idle(State):
    name = "idle"

    def insert_coin(self, m: "VendingMachine", coin: int) -> None:
        m.accept(coin)
        m.to(HAS_MONEY)


class HasMoney(State):
    name = "has_money"

    def insert_coin(self, m: "VendingMachine", coin: int) -> None:
        m.accept(coin)

    def select(self, m: "VendingMachine", code: str) -> None:
        slot = m.slots.get(code)
        if slot is None or slot.count == 0:
            raise OutOfStock(code)                     # credit and state survive
        if m.credit < slot.price_cents:
            raise InsufficientFunds(slot.price_cents - m.credit)
        plan = m.bank.plan_change(m.credit - slot.price_cents, extra=m.escrow)
        if plan is None:
            raise ExactChangeOnly(m.credit - slot.price_cents)
        m.bank.deposit(m.escrow)                       # escrow commits only now
        m.escrow.clear()
        m.bank.withdraw(plan)
        m.coin_return.extend(d for d, k in sorted(plan.items()) for _ in range(k))
        slot.count -= 1
        m.credit, m.pending = 0, slot
        m.to(DISPENSING)

    def cancel(self, m: "VendingMachine") -> None:
        m.to(REFUNDING)


class Dispensing(State):
    name = "dispensing"

    def dispensed(self, m: "VendingMachine") -> None:
        if m.pending is None:                          # not `assert`: that line
            raise InvalidOperation("dispensed with nothing pending")   # is gone
        m.tray.append(m.pending.name)                  # under `python -O`
        m.pending = None
        m.to(IDLE)


class Refunding(State):
    name = "refunding"

    def refunded(self, m: "VendingMachine") -> None:
        m.coin_return.extend(m.escrow)                 # the customer's own coins
        m.escrow.clear()
        m.credit = 0
        m.to(IDLE)


class OutOfService(State):
    name = "out_of_service"                            # every default applies


IDLE, HAS_MONEY = Idle(), HasMoney()
DISPENSING, REFUNDING, OUT_OF_SERVICE = Dispensing(), Refunding(), OutOfService()

The defaults

The five methods on State are the nineteen refusals, written once.

Four of them raise InvalidOperation. The fifth does not, and the exception is deliberate: the default for insert_coin returns the coin instead of raising. A coin arriving at the wrong moment is physically real. It is metal, it is inside the machine, and it has to go somewhere — so it goes straight to coin_return.

OutOfService overrides nothing at all. Every default applies, which is exactly what “out of service” means.

Two Python idioms

class State(ABC) inherits from ABC, short for abstract base class: the marker that this class exists to be subclassed rather than instantiated directly.

__init_subclass__ is a hook Python runs at the moment a subclass is defined — not when one is constructed. So class Broken(State): name = 42, and a subclass that forgets name entirely, both fail at import time, before any machine exists. That is earlier and louder than failing at construction.

Why not @property plus @abstractmethod

The obvious way to require name is that decorator pair. This listing does not use it, and the reason is worth a subsection, because the mistake recurs wherever a base class tries to demand a member rather than a method.

@property + @abstractmethod reads as a read-only, type-checked field. It is neither.

It is not read-only. Every subclass satisfies it with a plain class attribute (name = "idle"), and a plain class attribute is not a data descriptor — an object defining __set__, which is what makes a property intercept assignment. So IDLE.name = "has_money" writes straight through onto the shared flyweight. Every machine in the process then records the wrong move into m.transitions, which is the exact surface What interviewers probe tells you to assert on.

It is not type-checked either. @abstractmethod catches only a missing name. class Broken(State): name = 42 constructs happily, and its refusals read “select is not valid in 42”.

The three __init_subclass__ lines catch the missing name and the wrong type, at import time. They do not make name read-only, and nothing short of a real descriptor would — that is the same public-field problem as Decision 2 the machine is a monitor not a singleton’s unguarded surface. The point of the change is to stop the code claiming a guarantee it never delivered.

HasMoney.select, line by line

This is the only long method in the design, and it is where every money rule lives. Walk it:

1. slot = m.slots.get(code) — look up the column. If it does not exist, or its count is 0, raise OutOfStock. Nothing has been written yet, so the credit and the state survive untouched.
2. if m.credit < slot.price_cents — raise InsufficientFunds carrying the shortfall. Again, nothing written.
3. plan = m.bank.plan_change(...) — ask the bank for a plan, a dict of denomination to count, for the change owed. extra=m.escrow lets the customer’s own coins count toward paying her change; Decision 3 change making and where greedy fails explains why. If the bank cannot pay, plan is None and this raises ExactChangeOnly. Still nothing written.
4. Only now does anything move. m.bank.deposit(m.escrow) banks the customer’s coins, m.escrow.clear() empties the holding area, m.bank.withdraw(plan) removes the change coins, and the extend(...) line pushes the actual coins into coin_return.
5. slot.count -= 1, m.credit = 0, m.pending = slot, and m.to(DISPENSING).

The three raises all happen before the first write. That ordering is the whole “never eat the customer’s money” requirement, and it is a property of where the raises sit, not of any extra code.

The other five overrides

Idle.insert_coin accepts the coin and moves to HAS_MONEY. HasMoney.insert_coin accepts it and stays. HasMoney.cancel moves to REFUNDING and does nothing else — the refund itself happens when the hardware reports back.

Dispensing.dispensed puts m.pending.name — the product label off the Slot — into m.tray, clears pending, and returns to IDLE. The guard at the top is a raise and not an assert, and the inline comment says why: assert statements are stripped when Python runs under the -O flag, so a real invariant check must not be written as one.

Refunding.refunded extends coin_return with the escrow list itself — literally the coins the customer put in, not an equivalent amount — then clears escrow, zeroes credit, and returns to IDLE. That is escrow’s payoff made concrete.

The flyweight lines

The last two lines create one shared instance of each state and bind it to a module-level name. That is the flyweight from Decision 2 the machine is a monitor not a singleton, and it is safe precisely because the objects carry no per-machine data.

Safe to share, that is. They are still module-level names anyone can assign to.

The context: Slot and VendingMachine

The second block is the data side: a four-field record (Slot), a constructor, two internal helpers (to and accept), and the five public entry points.

Notice that the five entry points are one line each, apart from a guard on insert_coin, and that they all look the same. That sameness is the point of the pattern.

@dataclass
class Slot:
    code: str
    name: str
    price_cents: int
    count: int


class VendingMachine:
    def __init__(self, slots: Iterable[Slot], bank: "CoinBank") -> None:
        self.slots = {s.code: s for s in slots}
        self.bank = bank
        # what the coin mechanism physically recognises; nothing else gets in
        self.accepted = frozenset(bank.counts) or frozenset({1, 5, 10, 25, 100})
        self.state: State = IDLE
        self.credit = 0
        self.escrow: list[int] = []
        self.coin_return: list[int] = []
        self.tray: list[str] = []
        self.pending: Slot | None = None
        self.transitions: list[str] = []
        self._lock = threading.RLock()

    def to(self, s: State) -> None:
        self.transitions.append(f"{self.state.name}->{s.name}")
        self.state = s

    def accept(self, coin: int) -> None:
        self.escrow.append(coin)
        self.credit += coin

    # every public entry point is guarded; the machine is the monitor
    def insert_coin(self, coin: int) -> None:
        if coin not in self.accepted:            # validate at the boundary, or a
            raise InvalidOperation(              # negative coin reaches the bank
                f"not a recognised coin: {coin!r}")
        with self._lock: self.state.insert_coin(self, coin)

    def select(self, code: str) -> None:
        with self._lock: self.state.select(self, code)

    def dispensed(self) -> None:
        with self._lock: self.state.dispensed(self)

    def cancel(self) -> None:
        with self._lock: self.state.cancel(self)

    def refunded(self) -> None:
        with self._lock: self.state.refunded(self)

The eleven fields on the machine

Grouped by what they are for:

credit and escrow look redundant and are not. credit is the total in cents, which is what the price comparison needs. escrow is the list of individual coins, which is what a refund needs in order to hand back the identical metal.

The or on the accepted line is a fallback: frozenset({}) is empty and therefore falsy, so a CoinBank({}) produces a machine that recognises the default five US denominations rather than nothing at all.

Three more Python idioms

@dataclass is a decorator that writes the boilerplate for a class whose job is to hold fields. From the four annotated names it generates __init__, __repr__ and __eq__, so Slot("A1", "cola", 65, 2) works without a constructor being typed out. Note the four fields, in order: code, name, price_cents, count. The name is the product label, and it is what Dispensing.dispensed puts into m.tray.

threading.RLock() is the re-entrant lock from Decision 2 the machine is a monitor not a singleton. with self._lock: acquires it for the duration of the indented statement and releases it even if that statement raises.

Slot | None on pending reads “either a Slot or nothing”. It spells out that between a selection and a dispense there is exactly one item owed, and at all other times there is none.

Why insert_coin validates before the lock

insert_coin is the one entry point that does something before taking the lock, and that is worth defending — an unguarded line at the top of a monitor looks like a mistake.

A coin denomination is a fact about the hardware, not about the state, so no state should have to check it.

If nobody checks it, here is what happens. insert_coin(-35) reaches escrow, reaches CoinBank.deposit, and lands a -35 key in counts. make_change then indexes past the end of its own table and raises IndexError on every later call — for ever, not just once. insert_coin(0) is the quiet version: it moves the machine to HAS_MONEY with a credit of zero.

A machine that accepts a negative coin is not a modelling nicety; it is the reason the design says money is a whole number of cents in the first place. Validate the alphabet of the input at the edge and every state downstream gets to assume it.

One honest limitation of this stand-in. accepted is derived from the bank’s denomination keys, so CoinBank({5: 100}) builds a machine that refuses a dollar until the operator declares that denomination with a count of zero. A real coin recogniser is a property of the mechanism, not of what happens to be in the hopper. In production, accepted is a constructor argument of its own.

The five delegations

Every other public method does the same two things and nothing else: take the lock, and hand the event to whatever object is currently in self.state.

That is the whole State pattern — the context does not decide anything, it delegates and records.

to() is the recording half. It appends a string like "idle->has_money" to self.transitions before swapping the state. That is what makes the machine testable from outside: m.transitions is a readable history rather than a field you have to guess at.

One gap worth naming

Nothing in this listing ever transitions into OUT_OF_SERVICE. It is reachable only by assigning m.state directly, which is precisely the unguarded surface Decision 2 the machine is a monitor not a singleton warned about. A complete machine would enter it on a jam report or an empty machine; the demo in Decision 3 change making and where greedy fails reaches in by hand and says so.

8. Decision 3: change-making, and where greedy fails

The obvious change-making rule fails in two different ways, so it has to be replaced with one that is always right — and the replacement is cheap enough that you can price it exactly.

Two functions, side by side

The block below defines two functions that answer the same question and disagree.

greedy_change takes the biggest coin that fits, as many as the machine holds, then moves to the next denomination. It never reconsiders.

make_change is exact. It uses dynamic programming — solving a problem by building a table of answers to smaller versions of the same problem, so each sub-answer is computed once and then looked up rather than recomputed. Here the smaller problems are “what is the fewest coins that make amount a using only the first i denominations”, and the table is filled from a = 0 upwards.

Both return a dict of denomination to count, or None when the amount cannot be paid at all.

from __future__ import annotations

from typing import Mapping


def greedy_change(amount: int, counts: Mapping[int, int]) -> dict[int, int] | None:
    """Biggest coin that fits, as many as the hopper holds. No backtracking."""
    plan, rest = {}, amount
    for d in sorted(counts, reverse=True):
        k = min(rest // d, counts[d])
        if k:
            plan[d], rest = k, rest - k * d
    return plan if rest == 0 else None


def make_change(amount: int, counts: Mapping[int, int]) -> dict[int, int] | None:
    """Fewest coins from a FINITE hopper. Bounded coin change, exact."""
    INF = 10 ** 9
    denoms = sorted(counts)
    dp = [0] + [INF] * amount
    take = [[0] * (amount + 1) for _ in denoms]
    for i, d in enumerate(denoms):
        prev, cur = dp, [INF] * (amount + 1)
        for a in range(amount + 1):
            best, best_k = prev[a], 0
            for k in range(1, counts[d] + 1):
                if k * d > a:
                    break
                if prev[a - k * d] + k < best:
                    best, best_k = prev[a - k * d] + k, k
            cur[a], take[i][a] = best, best_k
        dp = cur
    if dp[amount] >= INF:
        return None
    plan, a = {}, amount
    for i in range(len(denoms) - 1, -1, -1):
        if take[i][a]:
            plan[denoms[i]] = take[i][a]
            a -= take[i][a] * denoms[i]
    return plan

Decoding make_change

The exact version solves bounded coin change. Bounded because each denomination has a limited supply, unlike the textbook version where you may use any coin as often as you like. That bound is what makes it a vending machine problem instead of a homework problem.

Four names carry the algorithm:

• dp[a] holds the fewest coins that make amount a, using the denominations processed so far.
• INF = 10 ** 9 is a stand-in for “impossible” — large enough that any real answer beats it. The final if dp[amount] >= INF: return None is the “cannot pay” exit.
• The for i, d in enumerate(denoms) loop processes one denomination at a time, building cur from prev. The inner for k in range(1, counts[d] + 1) tries taking 1, 2, … up to however many of that coin the hopper actually holds, and breaks as soon as k * d overshoots a. Taking none of it is already covered by the initial best, best_k = prev[a], 0.
• take[i][a] remembers how many of denomination i the best answer for a used. Without it you would know the coin count and not the coins. The final backwards loop reads take to reconstruct the actual plan.

None is the signal the machine turns into “exact change only”.

Where greedy is wrong, and where it is right

Two coin systems defeat greedy, and they defeat it for different reasons. The block below runs three cases: greedy failing outright, greedy succeeding badly, and greedy being right.

# 1. Canonical denominations, finite hopper. This is the vending machine case.
hopper = {25: 1, 10: 3, 5: 0, 1: 0}
assert greedy_change(30, hopper) is None        # takes the 25, then is stuck on 5
assert make_change(30, hopper) == {10: 3}       # 30 is payable, in three dimes

# 2. Non-canonical denominations, unlimited hopper. Greedy succeeds, badly.
odd = {1: 10, 3: 10, 4: 10}
g = greedy_change(6, odd)
assert g == {4: 1, 1: 2} and sum(g.values()) == 3
best = make_change(6, odd)
assert best == {3: 2} and sum(best.values()) == 2

# On US coins with a deep hopper, greedy IS optimal -- which is why the myth persists.
deep = {25: 99, 10: 99, 5: 99, 1: 99}
assert greedy_change(41, deep) == make_change(41, deep) == {25: 1, 10: 1, 5: 1, 1: 1}

Case 1 is the one to lead with, because it needs no exotic currency.

The hopper holds one quarter and three dimes: 55 cents, and 30 of it is payable. Greedy takes the quarter, needs 5 more, has no nickels and no pennies, and returns None. The machine prints “exact change only” and keeps the customer’s dollar. make_change finds {10: 3}.

The failure is not in the denominations. It is that greedy commits to the quarter and cannot undo it.

Case 2 is the textbook counter-example — {1, 3, 4} making 6 — and it shows the other failure mode. Greedy takes the 4, then two 1s: three coins. Two 3s would have done it in two. Greedy finds an answer, just not the fewest, which drains the hopper faster and brings case 1 on sooner.

The third case is why the myth survives. A coin system in which greedy is always optimal is exactly what canonical means, and US coins with a deep hopper meet that definition: greedy_change(41, deep) and make_change(41, deep) return the same quarter, dime, nickel and penny.

What exactness costs

The cost of exactness is a table.

Written in big-O notation — a way of stating how a cost grows with input size, ignoring constants — it is O(amount x total_coins) time and O(amount x denominations) memory.

At 100 cents of change and four denominations, take is 4 rows of 101 cells and the whole thing computes in microseconds. The DP is free at vending-machine scale. The only reason anyone uses greedy here is that they assumed it gave the same answer.

CoinBank: the two questions the machine asks

CoinBank wraps the algorithm. Its four methods split into two pairs: deposit/withdraw move coins, and plan_change/exact_change_only answer questions.

The argument to notice is extra on plan_change, and the two arguments on exact_change_only. Both are explained below the block.

from __future__ import annotations

from typing import Iterable, Mapping


class CoinBank:
    def __init__(self, counts: Mapping[int, int]) -> None:
        self.counts = dict(counts)

    def deposit(self, coins: Iterable[int]) -> None:
        for c in coins:
            self.counts[c] = self.counts.get(c, 0) + 1

    def withdraw(self, plan: Mapping[int, int]) -> None:
        for d, k in plan.items():
            self.counts[d] -= k

    def plan_change(self, amount: int,
                    extra: Iterable[int] = ()) -> dict[int, int] | None:
        """`extra` is the escrow: it joins the bank at commit, so it can pay change."""
        counts = dict(self.counts)
        for c in extra:
            counts[c] = counts.get(c, 0) + 1
        return make_change(amount, counts) if amount else {}

    def exact_change_only(self, prices: Iterable[int], max_payment: int) -> bool:
        """Can every change amount this machine can actually owe be paid?

        The reachable set is {payment - price} over the payments the coin set can
        form up to `max_payment` and the prices actually stocked. Sweeping a
        hard-coded 5..95 assumes a five-cent price granularity nothing enforces.
        """
        denoms = sorted(self.counts) or [1, 5, 10, 25, 100]
        payable = [True] + [False] * max_payment          # payments a customer
        for a in range(1, max_payment + 1):               # can actually hand over
            payable[a] = any(a >= d and payable[a - d] for d in denoms)
        owed = {p - price for p in range(max_payment + 1) if payable[p]
                for price in prices if p >= price}
        return any(make_change(a, self.counts) is None for a in owed)

extra: where escrow pays for itself a second time

The coins the customer just inserted are not in the bank yet. But they will be, the instant the sale commits — so they are legitimately available to pay her own change.

plan_change copies self.counts, adds the escrow coins to the copy, and plans against that. A machine that ignores this refuses sales it could have made.

That is also why HasMoney.select calls deposit before withdraw. The plan may well spend a coin the customer just inserted, so the escrow has to reach counts first or the withdrawal would drive a count negative.

One more subtlety in plan_change: if amount else {} short-circuits zero change to an empty dict without calling the DP. An empty dict is falsy, which is why HasMoney.select tests if plan is None and not if not plan. Writing the truthiness test there would reject every exact-payment sale.

exact_change_only: why it takes two arguments

This is the predicate that drives the display, and its signature is the interesting part.

The obvious implementation sweeps range(5, 100, 5) — the change amounts a five-cent price granularity can produce. Neither the 5, nor the 100, nor the step is derived from anything.

And nothing in this design enforces five-cent granularity. Slot(price_cents=63) is legal, and insert_coin takes any accepted denomination. So the hard-coded sweep answers a question about a machine you do not have, and it answers it in the most damaging direction: a bank of nothing but nickels passes the 5..95 sweep, lights “change available”, and then refuses a 63-cent sale because 37 cents is not a multiple of five.

The version here derives the sweep instead, in three steps:

1. payable[a] is filled bottom-up: which payment totals can a customer actually hand over, given the denominations this bank knows about?
2. owed is {p - price} over every payable payment p and every stocked price where p >= price. That is the set of change amounts the machine can genuinely be asked for.
3. Return True if any of them cannot be paid.

Six lines, and the assumption is gone.

It still ignores escrow, and that is deliberate. This predicate is a display, recomputed between customers, when escrow is empty by construction. plan_change is the one that runs mid-sale, and it is the one that takes extra.

The whole machine, driven

The block below is the full design running. It is long, so here is the running order before you read it:

1. Build a bank and a machine with two slots — cola at 65 cents with 2 in stock, chips at 100 cents with 0 in stock.
2. Insert two quarters. Then two refusals, InsufficientFunds and OutOfStock, each followed by an assertion that the credit and the state did not move.
3. Insert a third quarter and complete the sale: 10 cents change, DISPENSING, stock down to 1.
4. Press select again while the motor is still turning, and get InvalidOperation.
5. Report dispensed(), then check the tray and the full transition log.
6. Insert a dollar, cancel, and get the same dollar coin back.
7. ExactChangeOnly on a machine with an empty bank, with the credit still the customer’s — then four direct calls to the predicate, including the 63-cent price that a hard-coded 5..95 sweep would have got wrong.
8. Feed three invalid coins and confirm none reaches escrow or the bank.
9. Assign m.state by hand to exercise OUT_OF_SERVICE, which nothing else can reach.
10. Fire fifty threads at the lock.

bank = CoinBank({100: 1, 25: 4, 10: 4, 5: 4, 1: 10})
m = VendingMachine([Slot("A1", "cola", 65, 2), Slot("B2", "chips", 100, 0)], bank)

m.insert_coin(25)
m.insert_coin(25)
assert m.state is HAS_MONEY and m.credit == 50

try:                                  # insufficient funds: nothing moves
    m.select("A1")
    raise AssertionError
except InsufficientFunds as e:
    assert e.args[0] == 15
assert m.state is HAS_MONEY and m.credit == 50

try:                                  # out of stock: credit is NOT confiscated
    m.select("B2")
    raise AssertionError
except OutOfStock:
    pass
assert m.credit == 50

m.insert_coin(25)                     # 75c against a 65c cola -> 10c change
m.select("A1")
assert m.state is DISPENSING and m.coin_return == [10] and m.credit == 0
assert m.slots["A1"].count == 1       # decremented at commit, not at dispense

try:                                  # the hardware has not reported back yet
    m.select("A1")
    raise AssertionError
except InvalidOperation:
    pass

m.dispensed()
assert m.state is IDLE and m.tray == ["cola"]
assert m.transitions == ["idle->has_money", "has_money->dispensing",
                         "dispensing->idle"]

# cancel returns the customer's own coins, so it can never fail for lack of change
m.insert_coin(100)
m.cancel()
m.refunded()
assert m.state is IDLE and m.coin_return == [10, 100] and m.credit == 0

# exact-change-only, as a consequence of the bank rather than a mode
empty = VendingMachine([Slot("A1", "cola", 65, 1)], CoinBank({}))
empty.insert_coin(100)
try:
    empty.select("A1")
    raise AssertionError
except ExactChangeOnly as e:
    assert e.args[0] == 35
assert empty.state is HAS_MONEY and empty.credit == 100   # still the customer's
assert CoinBank({}).exact_change_only([65], 100) is True
assert CoinBank({25: 9, 10: 9, 5: 9, 1: 9}).exact_change_only([65], 100) is False

# and the predicate is derived, so a price that is not a multiple of five is
# covered: 100c against a 63c snack owes 37c, and a bank of nickels cannot pay it
assert CoinBank({5: 100}).exact_change_only([63], 100) is True
assert CoinBank({5: 100}).exact_change_only([65], 100) is False

# a coin the mechanism does not recognise never reaches escrow or the bank
for bad_coin in (-35, 0, 3):
    try:
        m.insert_coin(bad_coin)
        raise AssertionError(f"accepted {bad_coin}")
    except InvalidOperation:
        pass
assert m.credit == 0 and m.escrow == [] and all(d > 0 for d in m.bank.counts)

# OUT_OF_SERVICE overrides nothing, so every base default applies. Nothing in
# this listing transitions into it, so the demo assigns `state` directly --
# which is exactly the unguarded surface section 6 warned about.
m.state = OUT_OF_SERVICE
m.insert_coin(25)                     # base default: straight to the coin return
assert m.coin_return[-1] == 25 and m.credit == 0 and m.escrow == []
try:
    m.select("A1")
    raise AssertionError
except InvalidOperation as e:
    assert "out_of_service" in str(e)
m.state = IDLE                        # put it back for the rest of the file

# the monitor holds under concurrent coin drops
box = VendingMachine([Slot("A1", "cola", 65, 50)], CoinBank({25: 40}))
threads = [threading.Thread(target=box.insert_coin, args=(25,)) for _ in range(50)]
for t in threads:
    t.start()
for t in threads:
    t.join()
assert box.credit == 1250 and len(box.escrow) == 50

What the last block proves

Fifty threads drop a quarter each at the same time. Because every entry point takes the lock, the total is 50 x 25 = 1250 cents with fifty coins in escrow, every time.

Without the lock, credit += coin inside accept is a read-modify-write, and some of those increments are lost — the Decision 2 the machine is a monitor not a singleton race, at scale.

The two assertions candidates drop

OutOfStock and ExactChangeOnly leave the credit alone and the state unchanged.

A machine that eats your dollar because a column is empty is the single most common real-world complaint about vending machines. It is a state-machine bug: the rejection was written as a transition instead of a refusal.

The assertions that pin this down are assert m.credit == 50 after the OutOfStock block, and assert empty.state is HAS_MONEY and empty.credit == 100 after the ExactChangeOnly block. Both say the same thing — the money is still the customer’s.

One more worth noticing: assert m.slots["A1"].count == 1 fires while the machine is still DISPENSING. Stock is decremented at commit, not at dispense.

The alternative — waiting for the hardware to report back — leaves the count reading 2 after the money has already been taken. Cut the power in that window and the machine reboots believing it still has two colas when it has one. Committing the money and the stock in the same step is what keeps the two numbers in agreement.

9. Extension 1: card payment

Add a second way to pay and the whole point of the design so far comes due: most of it should survive. Coins are already in the box; a card is a promise. That difference propagates.

The block below is the interface a card terminal and a coin mechanism both satisfy. It is three method signatures and no implementation — a shape, not a class to inherit from.

from typing import Protocol


class PaymentMethod(Protocol):
    def authorize(self, amount_cents: int) -> str: ...
    def capture(self, ref: str, amount_cents: int) -> None: ...
    def void(self, ref: str) -> None: ...

Protocol is Python’s way of declaring an interface by shape rather than by ancestry. Any object that happens to have these three methods with these signatures satisfies PaymentMethod — no inheritance, no registration.

That is called structural typing, and it is what lets a coin-handling class and a card terminal be the same kind of thing to HasMoney.select without either of them being edited.

The three methods are the standard card vocabulary:

• authorise asks the bank to set the money aside and returns a reference string.
• capture actually takes it.
• void cancels an authorisation that was never captured.

What changes

The machine gains one new state, AUTHORIZING, sitting between HAS_MONEY and DISPENSING. An authorisation is a network call that takes seconds, and the machine must refuse buttons while it is in flight.

cancel in AUTHORIZING becomes void, not a coin return.

And capture moves after dispensed. A captured card plus a jammed motor is a chargeback — the customer disputes the charge and the bank claws it back, with a fee. An authorised-but-not-captured card is nothing at all.

What does not change

Slot, CoinBank, make_change, the State base class and every existing transition survive untouched.

Coin purchases keep working because PaymentMethod is a Protocol and coins are just the implementation where authorize means “the metal is already in escrow”.

What it costs

The ordering rule “capture after dispense” is now a correctness property spread across two states, and nothing in the type system enforces it.

It also introduces a failure the coin machine did not have: an authorisation that succeeds while the network reply is lost. Fixing that needs an idempotency key — a caller-supplied identifier that makes a repeated request produce the same single effect rather than a second charge. That machinery belongs to system design 27 — Payment System.

10. Extension 2: a maintenance and restock mode

A maintenance mode is where the return on decision 1 arrives: a sixth state creates a swarm of new table cells, and almost none of them have to be written.

The change is one state (MAINTENANCE) and two events (restock, and service_key for the physical key an operator turns). The arithmetic below is what that does to the table.

states after adding MAINTENANCE                6
events after adding restock and service_key    7
cells in the new table
  6 x 7                                       =  42
cells in the old table
  5 x 5                                       =  25
new cells to reason about
  42 - 25                                     =  17
new transitions actually written               3

The return on decision 1

Seventeen new cells. Three of them do anything:

• IDLE --service_key--> MAINTENANCE
• MAINTENANCE --restock--> MAINTENANCE
• MAINTENANCE --service_key--> IDLE

The other fourteen are inherited refusals, which is the return on decision 1 arriving on schedule.

The if/elif version would need seventeen new branches hand-written across seven methods. The two nobody remembers to write are the silent ones.

The question to raise unprompted

What does the service key do in HAS_MONEY?

It cannot drop straight to MAINTENANCE — there is a customer’s money in escrow.

The honest answer is a guarded transition: one that only fires when a condition holds, and runs a step first. Refund, then enter.

Write that as HAS_MONEY.service_key -> REFUNDING(then=MAINTENANCE) and you have just introduced a “where to go afterwards” field. That field is the assumption from What this class structure assumes cracking: the flat set of states can no longer say which situation the machine is in without also remembering where it came from.

That is the first sign a flat state machine wants to become a hierarchical one, where states nest inside parent states and a child can hand control back to whatever invoked it. Say that you see it, and that you would not build it for one case.

Why MAINTENANCE and OUT_OF_SERVICE are not one state

They look identical. Both refuse everything a customer can do. Merging them is wrong, and the reason is the exit condition:

• OUT_OF_SERVICE leaves automatically, by a predicate, when a slot is restocked or the bank is refilled.
• MAINTENANCE leaves only when a human turns the key.

Two states with the same behaviour and different exits are two states.

What it costs

Restocking changes what exact_change_only(...) answers, and the display has to be recomputed on exit. So MAINTENANCE -> IDLE is the first transition with a real side effect on something outside the state machine.

That is an Observer-shaped need — a pattern where interested parties register to be told when something changes, instead of the changing object knowing each of them by name. One display does not justify building one yet.

11. Extension 3: buying several items at once

This is the extension where the design breaks. Reaching an extension you cannot absorb cleanly and saying so is worth more than defending the design, and interviewers use this one to find out which you will do.

DISPENSING was written assuming one pending slot and one completion event. That is visible in the code: pending is typed Slot | None, and Dispensing.dispensed clears it and goes to IDLE.

A cart of three items needs three dispenses, any of which can jam. The state machine has no way to say “two of three delivered”.

What it forces

Four changes. The first three are absorbable. The fourth is not — read the table with that in mind.

Two terms from that table.

The Command pattern is what lets three pending dispenses sit in a list and be retried, logged or failed one at a time — each is an object carrying its own request.

A self-loop is a transition from a state back to itself. dispensed arrives, one item leaves the queue, and the machine stays in DISPENSING rather than moving on.

The last row is the design breaking

With one item, the change plan was computed before anything physical moved — steps 1 to 3 of Working python the state machine’s HasMoney.select walkthrough, all before the first write. A failure was free.

With a cart, the refund amount is not known until the hardware has finished. By then the coins may not be there, and you cannot un-deliver a snack.

Two honest resolutions, both with a real cost:

• Reserve the worst-case change at selection time. Holds coins that may turn out not to be needed, which makes exact_change_only fire more often.
• Issue a credit slip. That is a new object, and now the machine has state that survives the customer walking away.

Pick one out loud. An interviewer asking about multi-item is usually checking whether you notice that a design can be wrong.

12. What interviewers probe

These are the five follow-ups this problem reliably produces. The right-hand column is the answer that ends the follow-up rather than extending it — each one concedes what is true about the probe and then names the specific fact that settles it.

The second row is the closed-state-set assumption from What this class structure assumes being probed directly, and the answer that lands is the one that admits the machine has landed outside its five states and names the policy for getting back inside them.

Cheat sheet

One line per claim you should be able to make from memory, with the number or the name that backs it.

Related:

• 02 — The OOD Framework is the six-step method for the 45 minutes. Its section on the five assumptions generalises What this class structure assumes here.
• 03 — OOP Fundamentals treats State, Command and “why a flyweight is not a singleton” as topics in their own right.
• 05 — Movie Ticket Booking traces the same read-decide-write race with a seat instead of a coin.
• 06 — Unix File Search is the opposite end of the spectrum: behaviour that lives in composed predicates instead of states.