CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 5 min read

The code

State classes, stock and change.

The state interface and the two states:

interface State {
    String insert(VendingMachine m, int coin);
    String select(VendingMachine m, String code);
    String cancel(VendingMachine m);
}

class Idle implements State {
    public String insert(VendingMachine m, int coin) {
        m.accept(coin); m.setState(new HasMoney());
        return "balance " + m.balance();
    }
    public String select(VendingMachine m, String code) { return "insert coins first"; }
    public String cancel(VendingMachine m) { return "nothing to return"; }
}

class HasMoney implements State {
    public String insert(VendingMachine m, int coin) {
        m.accept(coin); return "balance " + m.balance();
    }
    public String select(VendingMachine m, String code) {
        Product p = m.inventory().product(code);
        if (m.inventory().stock(code) == 0)  return "sold out, balance " + m.balance();
        if (m.balance() < p.price())         return "need " + (p.price() - m.balance()) + " more";
        Optional<Map<Integer,Integer>> change = m.bank().makeChange(m.balance() - p.price());
        if (change.isEmpty())                return "cannot give change, cancel to get a refund";
        m.bank().remove(change.get()); m.inventory().take(code);
        m.clear(); m.setState(new Idle());
        return "dispensed " + p.name() + " change " + change.get();
    }
    public String cancel(VendingMachine m) {
        Map<Integer,Integer> back = new LinkedHashMap<>(m.inserted());
        m.bank().remove(back); m.clear(); m.setState(new Idle());
        return "refund " + back;
    }
}

In select every check comes before any change of state. The sale only changes things after the stock, balance and change checks have passed. That is the failure atomicity of Level 5, module 1: a refused sale leaves the machine exactly as it was.

The machine passes each call to the state, under one lock so that two users cannot interleave (Level 5, module 3):

synchronized String insert(int coin)    { return state.insert(this, coin); }
synchronized String select(String code) { return state.select(this, code); }
synchronized String cancel()            { return state.cancel(this); }

An inserted coin goes into the coin bank straight away and is also recorded in the list of inserted coins. That way the bank has the coins available as change, and a cancel can hand back the very coins that were put in.

Making change is the interesting part. A greedy loop takes the largest coin that fits, repeatedly. With an unlimited supply of 1, 2, 5 and 10 that always works. With a limited supply it can fail even when an answer exists. Take a bank with one 5-rupee coin and three 2-rupee coins, and a change of 6. Greedy takes the 5, then needs 1, finds none, and gives up. The answer 2 + 2 + 2 exists. The bank therefore searches: for each coin size from the largest, try the most coins possible, then fewer, and backtrack if the rest cannot be made.

Optional<Map<Integer,Integer>> makeChange(int amount) {
    Map<Integer,Integer> out = new LinkedHashMap<>();
    return search(0, amount, out) ? Optional.of(out) : Optional.empty();
}
private boolean search(int i, int left, Map<Integer,Integer> out) {
    if (left == 0) return true;
    if (i == DENOMS.length) return false;
    int d = DENOMS[i], max = Math.min(left / d, coins.get(d));
    for (int k = max; k >= 0; k--) {
        if (k > 0) out.put(d, k);
        if (search(i + 1, left - k * d, out)) return true;
        out.remove(d);
    }
    return false;
}

With one 5 and three 2s, makeChange(6) gives three 2s. makeChange(9) gives 5 + 2 + 2. makeChange(1) gives nothing, since no 1-rupee coin is in stock. The search is small because there are four coin sizes.

A run, with chips (code A1, price 12, stock 1), juice (B2, price 20, stock 2), gum (C3, price 12, stock 3), and a bank starting with one 5 and three 2s:

Action Result
Select A1 with no coins "insert coins first"
Insert 10, select A1 balance 10, then "need 2 more"
Insert 2, select A1 balance 12, then dispensed with no change
Select A1 again "insert coins first"
Insert 10, select A1, cancel "sold out, balance 10", then refund of one 10
Insert 10, 10, 5, select B2 balance 25, dispensed with change one 5
Insert 10, 5, select C3 balance 15, change 3 needed, "cannot give change"
Cancel refund of one 10 and one 5
Select "Z9" "no slot Z9"

In the second to last row, the bank has 2-rupee coins but no 1-rupee coin, so 3 cannot be made. The machine does not take the sale. The user gets the original coins back.

Greedy method

A greedy method repeatedly takes the largest or best-looking choice that fits, and never goes back to reconsider.

Example: taking the 5-rupee coin first for a change of 6, and then finding that no 1-rupee coin is left.

Check yourself: 1. Why can greedy change fail with a limited stock? 2. What does the machine return on cancel, and how does it know? 3. In select, why are all checks before the state changes?