Design a Vending Machine.

# vending.py, part 1: products, money, and change-making from a limited cash box
from __future__ import annotations

import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass

DENOMINATIONS = (1, 2, 5, 10, 20)  # rupees: coins, plus the ₹20 note


@dataclass(frozen=True)
class Product:
    code: str
    name: str
    price: int


@dataclass
class Slot:
    product: Product
    count: int


def make_change(amount: int, cash: dict[int, int]) -> dict[int, int] | None:
    """Fewest coins that make `amount` using only what is in the box, or None.
    Greedy fails here: ₹6 from {5: 1, 2: 3} is 2 + 2 + 2, and greedy grabs the 5 first."""
    best: dict[int, dict[int, int]] = {0: {}}
    for coin, have in sorted(cash.items(), reverse=True):
        nxt = dict(best)
        for total, combo in best.items():
            for k in range(1, have + 1):
                t = total + k * coin
                if t > amount:
                    break
                c = {**combo, coin: k}
                if t not in nxt or sum(c.values()) < sum(nxt[t].values()):
                    nxt[t] = c
        best = nxt
    return best.get(amount)

# part 2: the states. Each one answers every event; most answers are "not now"
class State(ABC):
    name = "?"

    def insert(self, m: VendingMachine, coin: int) -> str:
        m.returned.append(coin)
        return f"{self.name}: coin returned"

    def select(self, m: VendingMachine, code: str) -> str:
        return f"{self.name}: can't select now"

    def cancel(self, m: VendingMachine) -> str:
        return f"{self.name}: nothing to cancel"

    def item_dropped(self, m: VendingMachine) -> str:
        return f"{self.name}: ignored sensor event"


class Idle(State):
    name = "IDLE"

    def insert(self, m: VendingMachine, coin: int) -> str:
        m.escrow.append(coin)
        m.state = HasMoney()
        return f"balance ₹{m.balance}"

    def select(self, m: VendingMachine, code: str) -> str:
        return "insert money first"


class HasMoney(State):
    name = "HAS_MONEY"

    def insert(self, m: VendingMachine, coin: int) -> str:
        m.escrow.append(coin)
        return f"balance ₹{m.balance}"

    def select(self, m: VendingMachine, code: str) -> str:
        slot = m.slots.get(code)
        if slot is None or slot.count == 0:
            return f"{code} sold out, pick another or cancel"
        if m.balance < slot.product.price:
            return f"{slot.product.name} is ₹{slot.product.price}, add ₹{slot.product.price - m.balance}"
        box = dict(m.cash)
        for c in m.escrow:  # the customer's own coins can be part of their change
            box[c] = box.get(c, 0) + 1
        change = make_change(m.balance - slot.product.price, box)
        if change is None:
            return "can't make change: exact amount only"
        m.commit(slot, box, change)
        m.state = Dispensing()
        return f"dispensing {slot.product.name}"

    def cancel(self, m: VendingMachine) -> str:
        m.returned.extend(m.escrow)  # give back the very coins that went in
        m.escrow.clear()
        m.state = Idle()
        return "cancelled, coins returned"


class Dispensing(State):
    name = "DISPENSING"

    def item_dropped(self, m: VendingMachine) -> str:
        m.state = Idle() if any(s.count for s in m.slots.values()) else SoldOut()
        return f"done, now {m.state.name}"


class SoldOut(State):
    name = "SOLD_OUT"

    def select(self, m: VendingMachine, code: str) -> str:
        return "sold out"

# part 3: the machine (the context). It holds data; the current state decides what an event means
class VendingMachine:
    def __init__(self, slots: list[Slot], cash: dict[int, int]) -> None:
        self.slots = {s.product.code: s for s in slots}
        self.cash = dict(cash)  # coins the machine owns
        self.escrow: list[int] = []  # coins inserted for the current sale, not yet the machine's
        self.returned: list[int] = []  # what falls into the return tray
        self.state: State = Idle() if any(s.count for s in slots) else SoldOut()
        self._lock = threading.Lock()  # button presses, the coin acceptor and remote refills race

    @property
    def balance(self) -> int:
        return sum(self.escrow)

    def commit(self, slot: Slot, box: dict[int, int], change: dict[int, int]) -> None:
        slot.count -= 1
        for coin, n in change.items():
            box[coin] -= n
            self.returned.extend([coin] * n)
        self.cash = {c: n for c, n in box.items() if n}
        self.escrow.clear()

    def insert(self, coin: int) -> str:
        if coin not in DENOMINATIONS:
            self.returned.append(coin)
            return "unknown coin returned"
        with self._lock:
            return self.state.insert(self, coin)

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

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

    def item_dropped(self) -> str:  # the drop sensor saw the item fall
        with self._lock:
            return self.state.item_dropped(self)

    def refill(self, code: str, n: int) -> None:
        with self._lock:
            self.slots[code].count += n
            if isinstance(self.state, SoldOut):
                self.state = Idle()

    def take_tray(self) -> list[int]:
        out, self.returned = self.returned, []
        return out

# part 4: a few customers
if __name__ == "__main__":
    vm = VendingMachine(
        [Slot(Product("A1", "Masala chips", 20), 2), Slot(Product("B2", "Mango drink", 35), 1)],
        cash={5: 1, 2: 3},
    )
    print(vm.select("A1"))  # insert money first
    print(vm.insert(10), "|", vm.insert(5), "|", vm.select("A1"))  # balance 15: add ₹5
    print(vm.insert(10), "|", vm.select("A1"))  # balance 25: dispensing, change ₹5
    print(vm.insert(10), vm.item_dropped(), vm.take_tray())  # coin returned while busy; tray [5, 10]

    print(vm.insert(20), "|", vm.insert(20), "|", vm.select("B2"))  # ₹40 for 35: change 5 from the box
    print(vm.item_dropped(), vm.take_tray())
    print(vm.insert(10), vm.select("A1"), "| cash:", vm.cash)  # 10 for 20: add ₹10
    print(vm.cancel(), vm.take_tray())  # cancelled, [10]

    vm2 = VendingMachine([Slot(Product("C3", "Biscuits", 14), 5)], cash={5: 1, 2: 3})
    print(vm2.insert(20), "|", vm2.select("C3"), vm2.take_tray())  # change ₹6 = 2+2+2; greedy takes the 5 and gets stuck
    vm3 = VendingMachine([Slot(Product("C3", "Biscuits", 14), 5)], cash={5: 1})
    print(vm3.insert(20), "|", vm3.select("C3"))  # can't make change: exact amount only
    print(vm.select("A1"), vm.insert(20), vm.select("A1"), vm.item_dropped())  # last chips: SOLD_OUT
    print(vm.insert(5), vm.take_tray())  # SOLD_OUT returns coins

insert money first
balance ₹10 | balance ₹15 | Masala chips is ₹20, add ₹5
balance ₹25 | dispensing Masala chips
DISPENSING: coin returned done, now IDLE [5, 10]
balance ₹20 | balance ₹40 | dispensing Mango drink
done, now IDLE [5]
balance ₹10 Masala chips is ₹20, add ₹10 | cash: {2: 3, 10: 2, 20: 2}
cancelled, coins returned [10]
balance ₹20 | dispensing Biscuits [2, 2, 2]
balance ₹20 | can't make change: exact amount only
insert money first balance ₹20 dispensing Masala chips done, now SOLD_OUT
SOLD_OUT: coin returned [5]