Vending Machine

1import java.util.*;
2/** Single-session vending model. The caller executes hardware commands outside this monitor. */
3public final class Solution {
4    private Solution() {}
5    public enum State { IDLE, COLLECTING, DISPENSING }
6    public enum Outcome { SUCCESS, FAILED, UNKNOWN }
7    public record Product(String id, int price) {
8        public Product { if (id == null || id.isBlank() || price < 1 || price > 10000) throw new IllegalArgumentException("product"); }
9    }
10    public record Command(String attemptId, String productId, Map<Integer,Integer> change) {
11        public Command { change = Map.copyOf(change); }
12    }
13    public record Result(Outcome outcome, Map<Integer,Integer> returnedCoins) {
14        public Result { returnedCoins = Map.copyOf(returnedCoins); }
15    }
16    public static final class Machine {
17        private final Map<String,Product> products;
18        private final Map<String,Integer> stock;
19        private final Set<Integer> denominations;
20        private Map<Integer,Integer> cash;
21        private final Map<Integer,Integer> escrow = new TreeMap<>();
22        private final Map<String,Result> results = new HashMap<>();
23        private State state = State.IDLE;
24        private Product selected;
25        private Command pending;
26        private Map<Integer,Integer> reservedCash;
27        public Machine(List<Product> products, Map<String,Integer> stock, Map<Integer,Integer> cash) {
28            var p = new HashMap<String,Product>();
29            for (Product product : products) if (p.put(product.id(), product) != null) throw new IllegalArgumentException("duplicate product");
30            this.products = Map.copyOf(p); this.stock = new HashMap<>(stock);
31            if (!stock.keySet().equals(p.keySet()) || stock.values().stream().anyMatch(n -> n < 0)) throw new IllegalArgumentException("stock");
32            if (cash.isEmpty() || cash.size() > 20 || cash.entrySet().stream().anyMatch(e -> e.getKey() < 1 || e.getKey() > 10000 || e.getValue() < 0 || e.getValue() > 1000)) throw new IllegalArgumentException("cash");
33            if (value(cash) > 1_000_000) throw new IllegalArgumentException("cash capacity");
34            this.cash = new TreeMap<>(cash); denominations = Set.copyOf(cash.keySet());
35        }
36        public synchronized void select(String id) {
37            if (state != State.IDLE) throw new IllegalStateException("session active");
38            Product p = products.get(id);
39            if (p == null) throw new IllegalArgumentException("unknown product");
40            if (stock.get(id) == 0) throw new IllegalStateException("sold out");
41            selected = p; state = State.COLLECTING;
42        }
43        public synchronized void insert(int coin) {
44            if (state != State.COLLECTING) throw new IllegalStateException("not collecting");
45            if (!denominations.contains(coin) || credit() + coin > 10000) throw new IllegalArgumentException("unsupported coin or credit limit");
46            escrow.merge(coin,1,Integer::sum);
47        }
48        public synchronized Command confirm(String attemptId) {
49            if (attemptId == null || attemptId.isBlank()) throw new IllegalArgumentException("attempt");
50            if (pending != null && pending.attemptId().equals(attemptId)) return pending;
51            if (results.containsKey(attemptId)) throw new IllegalArgumentException("completed attempt ID; query result");
52            if (state != State.COLLECTING || credit() < selected.price()) throw new IllegalStateException("not funded");
53            var available = new TreeMap<>(cash); escrow.forEach((coin,n) -> available.merge(coin,n,Integer::sum));
54            if (value(available) > 1_000_000) throw new IllegalStateException("cash capacity reached");
55            Map<Integer,Integer> change = change(credit()-selected.price(), available);
56            if (change == null) throw new IllegalStateException("exact change unavailable");
57            // No mutation before a complete change plan exists.
58            var after = new TreeMap<>(available); change.forEach((coin,n) -> after.put(coin,after.get(coin)-n));
59            pending = new Command(attemptId,selected.id(),change); reservedCash = after;
60            stock.put(selected.id(),stock.get(selected.id())-1); state = State.DISPENSING;
61            return pending;
62        }
63        public synchronized Result complete(String attemptId, Outcome outcome) {
64            Objects.requireNonNull(outcome);
65            Result prior = results.get(attemptId);
66            if (prior != null) {
67                if (outcome != prior.outcome() && outcome != Outcome.UNKNOWN) throw new IllegalStateException("contradictory result");
68                return prior;
69            }
70            if (state != State.DISPENSING || !pending.attemptId().equals(attemptId)) throw new IllegalArgumentException("unknown attempt");
71            if (outcome == Outcome.UNKNOWN) return new Result(outcome,Map.of()); // Keep reservation and escrow.
72            Result result;
73            if (outcome == Outcome.SUCCESS) { cash = reservedCash; result = new Result(outcome,pending.change()); }
74            else { stock.put(selected.id(),stock.get(selected.id())+1); result = new Result(outcome,escrow); }
75            results.put(attemptId,result); reset(); return result;
76        }
77        public synchronized Map<Integer,Integer> cancel() {
78            if (state != State.COLLECTING) throw new IllegalStateException("cannot cancel");
79            Map<Integer,Integer> refund = Map.copyOf(escrow); reset(); return refund;
80        }
81        public synchronized Result result(String attemptId) { return results.get(attemptId); }
82        public synchronized State state() { return state; }
83        public synchronized int stock(String id) { if (!stock.containsKey(id)) throw new IllegalArgumentException("product"); return stock.get(id); }
84        public synchronized int credit() { return value(escrow); }
85        public synchronized int cashValue() { return value(cash); }
86        private void reset() { escrow.clear(); selected=null;pending=null;reservedCash=null;state=State.IDLE; }
87    }
88    public static int value(Map<Integer,Integer> coins) {
89        int sum=0; for(var e:coins.entrySet())sum=Math.addExact(sum,Math.multiplyExact(e.getKey(),e.getValue()));return sum;
90    }
91    /** Bounded subset-sum DP, not greedy: descending sums isolate each physical coin. */
92    public static Map<Integer,Integer> change(int amount, Map<Integer,Integer> inventory) {
93        if (amount < 0 || amount > 10000) throw new IllegalArgumentException("amount");
94        var ways = new ArrayList<Map<Integer,Integer>>(Collections.nCopies(amount+1,null));ways.set(0,Map.of());
95        for(var e:new TreeMap<>(inventory).entrySet()) {
96            int coin=e.getKey(),count=e.getValue();
97            if(coin<=0||count<0)throw new IllegalArgumentException("inventory");
98            for(int copy=0;copy<Math.min(count,amount/coin);copy++) {
99                for(int sum=amount;sum>=coin;sum--)if(ways.get(sum)==null&&ways.get(sum-coin)!=null) {
100                    var combination=new TreeMap<>(ways.get(sum-coin));combination.merge(coin,1,Integer::sum);ways.set(sum,Map.copyOf(combination));
101                }
102            }
103        }
104        return ways.get(amount);
105    }
106}
107