Design a Vending Machine

from __future__ import annotations

import threading
from dataclasses import dataclass

DENOMINATIONS = [100, 50, 20, 10, 5]  # largest first


@dataclass
class Product:
    name: str
    price: int
    stock: int


class VendingError(Exception):
    pass


def make_change(amount: int, bank: dict[int, int]) -> tuple[list[int], dict[int, int], bool]:
    """Pay `amount` from `bank`, largest coin first, working on a copy."""
    left, coins = dict(bank), []
    for d in DENOMINATIONS:
        while amount >= d and left.get(d, 0) > 0:
            amount -= d
            left[d] -= 1
            coins.append(d)
    return coins, left, amount == 0


class Idle:
    """State: no money inserted."""

    def insert(self, m: Machine, coin: int) -> None:
        m.inserted.append(coin)
        m.state = HasMoney()

    def choose(self, m: Machine, slot: str):
        raise VendingError("insert money first")

    def cancel(self, m: Machine) -> list[int]:
        raise VendingError("nothing to refund")


class HasMoney:
    """State: the customer has a balance and can buy or cancel."""

    def insert(self, m: Machine, coin: int) -> None:
        m.inserted.append(coin)

    def choose(self, m: Machine, slot: str) -> tuple[str, list[int]]:
        p = m.slots.get(slot)
        if p is None:
            raise VendingError("no such slot")
        if p.stock == 0:
            raise VendingError(f"{p.name} is sold out")
        bal = sum(m.inserted)
        if bal < p.price:
            raise VendingError(f"{p.name} costs {p.price} tk, insert {p.price - bal} tk more")
        bank = dict(m.bank)
        for c in m.inserted:  # inserted coins can be used for change
            bank[c] = bank.get(c, 0) + 1
        change, after, ok = make_change(bal - p.price, bank)
        refund = m.inserted
        m.inserted, m.state = [], Idle()
        if not ok:
            raise VendingError(f"cannot make change, refunded {fmt(refund)}")
        m.bank = after
        p.stock -= 1
        return p.name, change

    def cancel(self, m: Machine) -> list[int]:
        refund = m.inserted
        m.inserted, m.state = [], Idle()
        return refund


class Machine:
    def __init__(self, slots: dict[str, Product], bank: dict[int, int]):
        self._lock = threading.Lock()
        self.state: Idle | HasMoney = Idle()
        self.slots, self.bank = slots, bank
        self.inserted: list[int] = []

    def insert(self, coin: int) -> None:
        with self._lock:
            if coin not in DENOMINATIONS:
                raise VendingError("not a valid coin")
            self.state.insert(self, coin)

    def choose(self, slot: str) -> tuple[str, list[int]]:
        with self._lock:
            return self.state.choose(self, slot)

    def cancel(self) -> list[int]:
        with self._lock:
            return self.state.cancel(self)

    def balance(self) -> int:
        with self._lock:
            return sum(self.inserted)


def fmt(coins: list[int]) -> str:
    return "[" + " ".join(map(str, coins)) + "]"  # same format as Go


m = Machine({"A1": Product("Chips", 30, 2), "B2": Product("Juice", 65, 3), "C3": Product("Water", 20, 0)},
            {20: 2, 10: 2, 5: 2})


def show(action: str, result: str) -> None:
    print(f"{action:<14} -> {result}")


def insert(c: int) -> None:
    try:
        m.insert(c)
        show(f"insert {c}", f"balance {m.balance()} tk")
    except VendingError as e:
        show(f"insert {c}", f"rejected: {e}")


def choose(slot: str) -> None:
    try:
        name, change = m.choose(slot)
        show(f"select {slot}", f"{name}, change {sum(change)} tk {fmt(change)}")
    except VendingError as e:
        show(f"select {slot}", str(e))


insert(20)
choose("A1")
insert(20)
choose("A1")
choose("B2")
insert(100)
choose("B2")
insert(50)
choose("C3")
show("cancel", f"refunded {fmt(m.cancel())}")
insert(3)
insert(100)
choose("A1")
print(f"stock: A1 {m.slots['A1'].stock}, B2 {m.slots['B2'].stock}, C3 {m.slots['C3'].stock}")

const DENOMINATIONS = [100, 50, 20, 10, 5]; // largest first

interface Product {
  readonly name: string;
  readonly price: number;
  stock: number;
}

type Bank = Map<number, number>;

// Pay `amount` from `bank`, largest coin first, working on a copy.
function makeChange(amount: number, bank: Bank): [number[], Bank, boolean] {
  const left = new Map(bank);
  const coins: number[] = [];
  for (const d of DENOMINATIONS) {
    while (amount >= d && (left.get(d) ?? 0) > 0) {
      amount -= d;
      left.set(d, left.get(d)! - 1);
      coins.push(d);
    }
  }
  return [coins, left, amount === 0];
}

const fmt = (coins: number[]) => `[${coins.join(" ")}]`; // same format as Go

// The State pattern: each state answers the same three events in its own way.
interface State {
  insert(m: Machine, coin: number): void;
  choose(m: Machine, slot: string): { product: string; change: number[] };
  cancel(m: Machine): number[];
}

const idle: State = {
  insert(m, coin) {
    m.inserted.push(coin);
    m.state = hasMoney;
  },
  choose() {
    throw new Error("insert money first");
  },
  cancel() {
    throw new Error("nothing to refund");
  },
};

const hasMoney: State = {
  insert(m, coin) {
    m.inserted.push(coin);
  },
  choose(m, slot) {
    const p = m.slots.get(slot);
    if (!p) throw new Error("no such slot");
    if (p.stock === 0) throw new Error(`${p.name} is sold out`);
    const bal = m.balance();
    if (bal < p.price) throw new Error(`${p.name} costs ${p.price} tk, insert ${p.price - bal} tk more`);
    const bank = new Map(m.bank);
    for (const c of m.inserted) bank.set(c, (bank.get(c) ?? 0) + 1); // inserted coins can be used for change
    const [change, after, ok] = makeChange(bal - p.price, bank);
    const refund = m.inserted;
    m.inserted = [];
    m.state = idle;
    if (!ok) throw new Error(`cannot make change, refunded ${fmt(refund)}`);
    m.bank = after;
    p.stock--;
    return { product: p.name, change };
  },
  cancel(m) {
    const refund = m.inserted;
    m.inserted = [];
    m.state = idle;
    return refund;
  },
};

// No lock: JavaScript runs this on one thread and nothing here awaits.
class Machine {
  state: State = idle;
  inserted: number[] = [];
  readonly slots: Map<string, Product>;
  bank: Bank;
  constructor(slots: Map<string, Product>, bank: Bank) {
    this.slots = slots;
    this.bank = bank;
  }
  insert(coin: number): void {
    if (!DENOMINATIONS.includes(coin)) throw new Error("not a valid coin");
    this.state.insert(this, coin);
  }
  choose(slot: string) {
    return this.state.choose(this, slot);
  }
  cancel(): number[] {
    return this.state.cancel(this);
  }
  balance(): number {
    return this.inserted.reduce((a, b) => a + b, 0);
  }
}

const m = new Machine(
  new Map([
    ["A1", { name: "Chips", price: 30, stock: 2 }],
    ["B2", { name: "Juice", price: 65, stock: 3 }],
    ["C3", { name: "Water", price: 20, stock: 0 }],
  ]),
  new Map([[20, 2], [10, 2], [5, 2]]),
);

const show = (action: string, result: string) => console.log(`${action.padEnd(14)} -> ${result}`);
function insert(c: number): void {
  try {
    m.insert(c);
    show(`insert ${c}`, `balance ${m.balance()} tk`);
  } catch (e) {
    show(`insert ${c}`, `rejected: ${(e as Error).message}`);
  }
}
function choose(slot: string): void {
  try {
    const s = m.choose(slot);
    show(`select ${slot}`, `${s.product}, change ${s.change.reduce((a, b) => a + b, 0)} tk ${fmt(s.change)}`);
  } catch (e) {
    show(`select ${slot}`, (e as Error).message);
  }
}

insert(20);
choose("A1");
insert(20);
choose("A1");
choose("B2");
insert(100);
choose("B2");
insert(50);
choose("C3");
show("cancel", `refunded ${fmt(m.cancel())}`);
insert(3);
insert(100);
choose("A1");
const st = (s: string) => m.slots.get(s)!.stock;
console.log(`stock: A1 ${st("A1")}, B2 ${st("B2")}, C3 ${st("C3")}`);

use std::collections::HashMap;
use std::sync::Mutex;

const DENOMINATIONS: [u32; 5] = [100, 50, 20, 10, 5]; // largest first

struct Product { name: &'static str, price: u32, stock: u32 }

// Pay `amount` from `bank`, largest coin first, working on a copy.
fn make_change(mut amount: u32, bank: &HashMap<u32, u32>) -> (Vec<u32>, HashMap<u32, u32>, bool) {
    let mut left = bank.clone();
    let mut coins = vec![];
    for d in DENOMINATIONS {
        while amount >= d && left.get(&d).copied().unwrap_or(0) > 0 {
            amount -= d;
            *left.get_mut(&d).unwrap() -= 1;
            coins.push(d);
        }
    }
    (coins, left, amount == 0)
}

fn fmt(coins: &[u32]) -> String { // same format as Go
    format!("[{}]", coins.iter().map(|c| c.to_string()).collect::<Vec<_>>().join(" "))
}

// The states as an enum; each event is a match on the current state.
#[derive(Clone, Copy, PartialEq)]
enum State { Idle, HasMoney }

struct Inner { state: State, slots: HashMap<&'static str, Product>, bank: HashMap<u32, u32>, inserted: Vec<u32> }

struct Machine { inner: Mutex<Inner> } // everything that changes lives inside the lock

impl Machine {
    fn insert(&self, coin: u32) -> Result<(), String> {
        if !DENOMINATIONS.contains(&coin) { return Err("not a valid coin".into()); }
        let mut m = self.inner.lock().unwrap();
        m.inserted.push(coin);
        m.state = State::HasMoney;
        Ok(())
    }

    fn choose(&self, slot: &str) -> Result<(&'static str, Vec<u32>), String> {
        let mut guard = self.inner.lock().unwrap();
        let m = &mut *guard;
        if m.state == State::Idle { return Err("insert money first".into()); }
        let bal: u32 = m.inserted.iter().sum();
        let p = m.slots.get(slot).ok_or("no such slot")?;
        if p.stock == 0 { return Err(format!("{} is sold out", p.name)); }
        if bal < p.price { return Err(format!("{} costs {} tk, insert {} tk more", p.name, p.price, p.price - bal)); }
        let (name, price) = (p.name, p.price);
        let mut bank = m.bank.clone();
        for &c in &m.inserted { *bank.entry(c).or_insert(0) += 1; } // inserted coins can be used for change
        let (change, after, ok) = make_change(bal - price, &bank);
        let refund = std::mem::take(&mut m.inserted);
        m.state = State::Idle;
        if !ok { return Err(format!("cannot make change, refunded {}", fmt(&refund))); }
        m.bank = after;
        m.slots.get_mut(slot).unwrap().stock -= 1;
        Ok((name, change))
    }

    fn cancel(&self) -> Result<Vec<u32>, String> {
        let mut m = self.inner.lock().unwrap();
        if m.state == State::Idle { return Err("nothing to refund".into()); }
        m.state = State::Idle;
        Ok(std::mem::take(&mut m.inserted))
    }

    fn balance(&self) -> u32 { self.inner.lock().unwrap().inserted.iter().sum() }
    fn stock(&self, slot: &str) -> u32 { self.inner.lock().unwrap().slots[slot].stock }
}

fn main() {
    let slots = HashMap::from([
        ("A1", Product { name: "Chips", price: 30, stock: 2 }),
        ("B2", Product { name: "Juice", price: 65, stock: 3 }),
        ("C3", Product { name: "Water", price: 20, stock: 0 }),
    ]);
    let m = Machine { inner: Mutex::new(Inner { state: State::Idle, slots, bank: HashMap::from([(20, 2), (10, 2), (5, 2)]), inserted: vec![] }) };

    let show = |action: &str, result: &str| println!("{action:<14} -> {result}");
    let insert = |c: u32| match m.insert(c) {
        Ok(()) => show(&format!("insert {c}"), &format!("balance {} tk", m.balance())),
        Err(e) => show(&format!("insert {c}"), &format!("rejected: {e}")),
    };
    let choose = |slot: &str| match m.choose(slot) {
        Ok((name, change)) => show(&format!("select {slot}"), &format!("{name}, change {} tk {}", change.iter().sum::<u32>(), fmt(&change))),
        Err(e) => show(&format!("select {slot}"), &e),
    };

    insert(20);
    choose("A1");
    insert(20);
    choose("A1");
    choose("B2");
    insert(100);
    choose("B2");
    insert(50);
    choose("C3");
    if let Ok(r) = m.cancel() { show("cancel", &format!("refunded {}", fmt(&r))); }
    insert(3);
    insert(100);
    choose("A1");
    println!("stock: A1 {}, B2 {}, C3 {}", m.stock("A1"), m.stock("B2"), m.stock("C3"));
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class Main {
    static final int[] DENOMINATIONS = {100, 50, 20, 10, 5}; // largest first

    static final class Product {
        final String name;
        final int price;
        int stock;
        Product(String name, int price, int stock) { this.name = name; this.price = price; this.stock = stock; }
    }

    static final class VendingException extends Exception {
        private static final long serialVersionUID = 1L;
        VendingException(String msg) { super(msg); }
    }

    record Sale(String product, List<Integer> change) {}

    record Change(List<Integer> coins, Map<Integer, Integer> left, boolean ok) {}

    // Pay `amount` from `bank`, largest coin first, working on a copy.
    static Change makeChange(int amount, Map<Integer, Integer> bank) {
        Map<Integer, Integer> left = new HashMap<>(bank);
        List<Integer> coins = new ArrayList<>();
        for (int d : DENOMINATIONS) {
            while (amount >= d && left.getOrDefault(d, 0) > 0) {
                amount -= d;
                left.merge(d, -1, Integer::sum);
                coins.add(d);
            }
        }
        return new Change(coins, left, amount == 0);
    }

    static String fmt(List<Integer> coins) { // same format as Go
        return coins.stream().map(String::valueOf).collect(Collectors.joining(" ", "[", "]"));
    }

    // The State pattern: each state answers the same three events in its own way.
    interface State {
        void insert(Machine m, int coin);
        Sale choose(Machine m, String slot) throws VendingException;
        List<Integer> cancel(Machine m) throws VendingException;
    }

    static final class Idle implements State {
        public void insert(Machine m, int coin) { m.inserted.add(coin); m.state = new HasMoney(); }
        public Sale choose(Machine m, String slot) throws VendingException { throw new VendingException("insert money first"); }
        public List<Integer> cancel(Machine m) throws VendingException { throw new VendingException("nothing to refund"); }
    }

    static final class HasMoney implements State {
        public void insert(Machine m, int coin) { m.inserted.add(coin); }

        public Sale choose(Machine m, String slot) throws VendingException {
            Product p = m.slots.get(slot);
            if (p == null) throw new VendingException("no such slot");
            if (p.stock == 0) throw new VendingException(p.name + " is sold out");
            int bal = m.balanceUnlocked();
            if (bal < p.price) throw new VendingException(p.name + " costs " + p.price + " tk, insert " + (p.price - bal) + " tk more");
            Map<Integer, Integer> bank = new HashMap<>(m.bank);
            for (int c : m.inserted) bank.merge(c, 1, Integer::sum); // inserted coins can be used for change
            Change ch = makeChange(bal - p.price, bank);
            List<Integer> refund = m.inserted;
            m.inserted = new ArrayList<>();
            m.state = new Idle();
            if (!ch.ok()) throw new VendingException("cannot make change, refunded " + fmt(refund));
            m.bank = ch.left();
            p.stock--;
            return new Sale(p.name, ch.coins());
        }

        public List<Integer> cancel(Machine m) {
            List<Integer> refund = m.inserted;
            m.inserted = new ArrayList<>();
            m.state = new Idle();
            return refund;
        }
    }

    static final class Machine {
        State state = new Idle();
        final Map<String, Product> slots;
        Map<Integer, Integer> bank;
        List<Integer> inserted = new ArrayList<>();

        Machine(Map<String, Product> slots, Map<Integer, Integer> bank) { this.slots = slots; this.bank = bank; }

        synchronized void insert(int coin) throws VendingException {
            boolean valid = false;
            for (int d : DENOMINATIONS) valid |= d == coin;
            if (!valid) throw new VendingException("not a valid coin");
            state.insert(this, coin);
        }
        synchronized Sale choose(String slot) throws VendingException { return state.choose(this, slot); }
        synchronized List<Integer> cancel() throws VendingException { return state.cancel(this); }
        synchronized int balance() { return balanceUnlocked(); }
        int balanceUnlocked() { return inserted.stream().mapToInt(Integer::intValue).sum(); }
    }

    static Machine m;

    static void show(String action, String result) { System.out.printf("%-14s -> %s%n", action, result); }

    static void insert(int c) {
        try {
            m.insert(c);
            show("insert " + c, "balance " + m.balance() + " tk");
        } catch (VendingException e) {
            show("insert " + c, "rejected: " + e.getMessage());
        }
    }

    static void choose(String slot) {
        try {
            Sale s = m.choose(slot);
            int total = s.change().stream().mapToInt(Integer::intValue).sum();
            show("select " + slot, s.product() + ", change " + total + " tk " + fmt(s.change()));
        } catch (VendingException e) {
            show("select " + slot, e.getMessage());
        }
    }

    public static void main(String[] args) throws VendingException {
        Map<String, Product> slots = new HashMap<>();
        slots.put("A1", new Product("Chips", 30, 2));
        slots.put("B2", new Product("Juice", 65, 3));
        slots.put("C3", new Product("Water", 20, 0));
        m = new Machine(slots, new HashMap<>(Map.of(20, 2, 10, 2, 5, 2)));

        insert(20);
        choose("A1");
        insert(20);
        choose("A1");
        choose("B2");
        insert(100);
        choose("B2");
        insert(50);
        choose("C3");
        show("cancel", "refunded " + fmt(m.cancel()));
        insert(3);
        insert(100);
        choose("A1");
        System.out.printf("stock: A1 %d, B2 %d, C3 %d%n", slots.get("A1").stock, slots.get("B2").stock, slots.get("C3").stock);
    }
}

#include <cstdio>
#include <map>
#include <memory>
#include <mutex>
#include <numeric>
#include <stdexcept>
#include <string>
#include <vector>

const std::vector<int> kDenominations{100, 50, 20, 10, 5};  // largest first

struct Product {
    std::string name;
    int price, stock;
};

struct VendingError : std::runtime_error {
    using std::runtime_error::runtime_error;
};

std::string fmt(const std::vector<int>& coins) {  // same format as Go
    std::string s = "[";
    for (size_t i = 0; i < coins.size(); i++) s += (i ? " " : "") + std::to_string(coins[i]);
    return s + "]";
}

// Pay `amount` from `bank`, largest coin first, working on a copy.
bool makeChange(int amount, std::map<int, int>& bank, std::vector<int>& coins) {
    for (int d : kDenominations)
        while (amount >= d && bank[d] > 0) {
            amount -= d;
            bank[d]--;
            coins.push_back(d);
        }
    return amount == 0;
}

struct Sale {
    std::string product;
    std::vector<int> change;
};

class Machine;

// The State pattern: each state answers the same three events in its own way.
class State {
public:
    virtual ~State() = default;
    virtual void insert(Machine& m, int coin) = 0;
    virtual Sale choose(Machine& m, const std::string& slot) = 0;
    virtual std::vector<int> cancel(Machine& m) = 0;
};

class Machine {
public:
    Machine(std::map<std::string, Product> slots, std::map<int, int> bank);
    void insert(int coin);
    Sale choose(const std::string& slot);
    std::vector<int> cancel();
    int balance();
    int stock(const std::string& slot) {
        std::lock_guard lock(mu_);
        return slots.at(slot).stock;
    }

    // Used by the states, always under the lock.
    std::unique_ptr<State> state;
    std::map<std::string, Product> slots;
    std::map<int, int> bank;
    std::vector<int> inserted;
    int balanceUnlocked() const { return std::accumulate(inserted.begin(), inserted.end(), 0); }

private:
    std::mutex mu_;
};

class Idle : public State {
public:
    void insert(Machine& m, int coin) override;
    Sale choose(Machine&, const std::string&) override { throw VendingError("insert money first"); }
    std::vector<int> cancel(Machine&) override { throw VendingError("nothing to refund"); }
};

class HasMoney : public State {
public:
    void insert(Machine& m, int coin) override { m.inserted.push_back(coin); }
    Sale choose(Machine& m, const std::string& slot) override {
        auto it = m.slots.find(slot);
        if (it == m.slots.end()) throw VendingError("no such slot");
        Product& p = it->second;
        if (p.stock == 0) throw VendingError(p.name + " is sold out");
        int bal = m.balanceUnlocked();
        if (bal < p.price)
            throw VendingError(p.name + " costs " + std::to_string(p.price) + " tk, insert " + std::to_string(p.price - bal) + " tk more");
        std::map<int, int> bank = m.bank;
        for (int c : m.inserted) bank[c]++;  // inserted coins can be used for change
        std::vector<int> change;
        bool ok = makeChange(bal - p.price, bank, change);
        std::vector<int> refund = std::move(m.inserted);
        m.inserted.clear();
        m.state = std::make_unique<Idle>();  // `this` is destroyed here: touch only locals from now on
        if (!ok) throw VendingError("cannot make change, refunded " + fmt(refund));
        m.bank = bank;
        p.stock--;
        return {p.name, change};
    }
    std::vector<int> cancel(Machine& m) override {
        std::vector<int> refund = std::move(m.inserted);
        m.inserted.clear();
        m.state = std::make_unique<Idle>();
        return refund;
    }
};

void Idle::insert(Machine& m, int coin) {
    m.inserted.push_back(coin);
    m.state = std::make_unique<HasMoney>();  // replaces (destroys) this Idle object; return right away
}

Machine::Machine(std::map<std::string, Product> s, std::map<int, int> b)
    : state(std::make_unique<Idle>()), slots(std::move(s)), bank(std::move(b)) {}

void Machine::insert(int coin) {
    std::lock_guard lock(mu_);
    bool valid = false;
    for (int d : kDenominations) valid |= d == coin;
    if (!valid) throw VendingError("not a valid coin");
    state->insert(*this, coin);
}
Sale Machine::choose(const std::string& slot) {
    std::lock_guard lock(mu_);
    return state->choose(*this, slot);
}
std::vector<int> Machine::cancel() {
    std::lock_guard lock(mu_);
    return state->cancel(*this);
}
int Machine::balance() {
    std::lock_guard lock(mu_);
    return balanceUnlocked();
}

int main() {
    Machine m({{"A1", {"Chips", 30, 2}}, {"B2", {"Juice", 65, 3}}, {"C3", {"Water", 20, 0}}}, {{20, 2}, {10, 2}, {5, 2}});
    auto show = [](const std::string& action, const std::string& result) {
        std::printf("%-14s -> %s\n", action.c_str(), result.c_str());
    };
    auto insert = [&](int c) {
        try {
            m.insert(c);
            show("insert " + std::to_string(c), "balance " + std::to_string(m.balance()) + " tk");
        } catch (const VendingError& e) {
            show("insert " + std::to_string(c), std::string("rejected: ") + e.what());
        }
    };
    auto choose = [&](const std::string& slot) {
        try {
            Sale s = m.choose(slot);
            int total = std::accumulate(s.change.begin(), s.change.end(), 0);
            show("select " + slot, s.product + ", change " + std::to_string(total) + " tk " + fmt(s.change));
        } catch (const VendingError& e) {
            show("select " + slot, e.what());
        }
    };

    insert(20);
    choose("A1");
    insert(20);
    choose("A1");
    choose("B2");
    insert(100);
    choose("B2");
    insert(50);
    choose("C3");
    show("cancel", "refunded " + fmt(m.cancel()));
    insert(3);
    insert(100);
    choose("A1");
    std::printf("stock: A1 %d, B2 %d, C3 %d\n", m.stock("A1"), m.stock("B2"), m.stock("C3"));
}