Design a Vending Machine and an Elevator (State Machines)

export class InvalidTransition extends Error {}export type Result = { ok: true; item?: string; change?: number[] } | { ok: false; reason: string };type Product = { name: string; priceCents: number; qty: number };const COINS = [100, 25, 10, 5]; // cents; the only coins we accept and give backexport function makeChange(cents: number): number[] {  const out: number[] = [];  for (const c of COINS) while (cents >= c) { out.push(c); cents -= c; }  if (cents !== 0) throw new Error("amount is not a multiple of 5 cents");  return out;}// Each state decides what every event does. Events a state cannot accept throw.interface VState {  readonly name: string;  insert(m: VendingMachine, cents: number): Result;  select(m: VendingMachine, code: string): Result;  cancel(m: VendingMachine): Result;  repair(m: VendingMachine): Result;}function invalid(state: string, event: string): never {  throw new InvalidTransition(`${event} is not allowed in state ${state}`);}const Idle: VState = {  name: "idle",  insert(m, cents) { m.balance += cents; m.state = HasMoney; return { ok: true }; },  select() { return invalid("idle", "select"); },  cancel() { return invalid("idle", "cancel"); },  repair() { return invalid("idle", "repair"); },};const HasMoney: VState = {  name: "hasMoney",  insert(m, cents) { m.balance += cents; return { ok: true }; },  select(m, code) {    const p = m.inventory.get(code);    if (!p) return { ok: false, reason: "unknown code" };    if (p.qty === 0) return { ok: false, reason: "sold out" };    if (m.balance < p.priceCents) return { ok: false, reason: `insert ${p.priceCents - m.balance} more cents` };    if (!m.dispense(code)) { // hardware failed: give the money back and stop selling      const refund = makeChange(m.balance);      m.balance = 0;      m.state = OutOfService;      return { ok: false, reason: `jam, refunded ${refund.join("+")}` };    }    p.qty--;    const change = makeChange(m.balance - p.priceCents);    m.balance = 0;    m.state = Idle;    return { ok: true, item: p.name, change };  },  cancel(m) {    const change = makeChange(m.balance);    m.balance = 0;    m.state = Idle;    return { ok: true, change };  },  repair() { return invalid("hasMoney", "repair"); },};const OutOfService: VState = {  name: "outOfService",  insert() { return invalid("outOfService", "insert"); },  select() { return invalid("outOfService", "select"); },  cancel() { return invalid("outOfService", "cancel"); },  repair(m) { m.state = Idle; return { ok: true }; },};export class VendingMachine {  balance = 0;  state: VState = Idle;  readonly inventory: Map<string, Product>;  readonly dispense: (code: string) => boolean; // injected hardware  constructor(products: Record<string, Product>, dispense: (code: string) => boolean = () => true) {    this.inventory = new Map(Object.entries(products).map(([k, v]) => [k, { ...v }]));    this.dispense = dispense;  }  get stateName(): string { return this.state.name; }  insert(cents: number) { return this.state.insert(this, cents); }  select(code: string) { return this.state.select(this, code); }  cancel() { return this.state.cancel(this); }  repair() { return this.state.repair(this); }}

import { Elevator, FirstComeFirstServed, Scan, type Scheduler } from "./elevator.ts";import { VendingMachine, InvalidTransition } from "./vending.ts";const vm = new VendingMachine({ A1: { name: "chips", priceCents: 125, qty: 1 } });console.log(vm.stateName, vm.insert(100), vm.stateName);console.log(vm.select("A1"));console.log(vm.insert(100), vm.select("A1"), vm.stateName);try { vm.select("A1"); } catch (e) { console.log(e instanceof InvalidTransition, (e as Error).message); }

import { InvalidTransition } from "./vending.ts";export type EState = "idle" | "movingUp" | "movingDown" | "doorsOpen" | "fault";export type EEvent = "request" | "arrive" | "doorTimeout" | "fault" | "reset";export type Dir = "up" | "down";// Strategy: which way to go, and whether to stop here. pending is in arrival order.export interface Scheduler {  direction(floor: number, last: Dir, pending: number[]): Dir | null;  stopHere(floor: number, pending: number[]): boolean;}export class Scan implements Scheduler { // "elevator algorithm": keep going one way, then turn  direction(floor: number, last: Dir, pending: number[]): Dir | null {    const above = pending.some((f) => f > floor);    const below = pending.some((f) => f < floor);    if (last === "up") return above ? "up" : below ? "down" : null;    return below ? "down" : above ? "up" : null;  }  stopHere(floor: number, pending: number[]): boolean {    return pending.includes(floor); // stop for anyone on the way  }}export class FirstComeFirstServed implements Scheduler {  direction(floor: number, _last: Dir, pending: number[]): Dir | null {    if (pending.length === 0) return null;    return pending[0] > floor ? "up" : "down";  }  stopHere(floor: number, pending: number[]): boolean {    return pending[0] === floor; // only the oldest request counts  }}type Next = EState | ((e: Elevator) => EState);// The whole behaviour in one table. A missing cell means "not allowed".const TABLE: Record<EState, Partial<Record<EEvent, Next>>> = {  idle:       { request: (e) => e.decide(), fault: "fault" },  movingUp:   { request: "movingUp", arrive: (e) => e.onArrive("up"), fault: "fault" },  movingDown: { request: "movingDown", arrive: (e) => e.onArrive("down"), fault: "fault" },  doorsOpen:  { request: "doorsOpen", doorTimeout: (e) => e.decide(), fault: "fault" },  fault:      { reset: (e) => e.decide() }, // resume the requests that were waiting};export class Elevator {  floor = 0;  state: EState = "idle";  pending: number[] = [];  travelled = 0;  stops: number[] = []; // floors where the doors opened, in order  private last: Dir = "up";  private readonly sched: Scheduler;  private readonly topFloor: number;  constructor(sched: Scheduler, topFloor = 10) {    this.sched = sched;    this.topFloor = topFloor;  }  send(event: EEvent, floor?: number): EState {    const next = TABLE[this.state][event];    if (next === undefined) throw new InvalidTransition(`${event} is not allowed in state ${this.state}`);    if (event === "request") {      if (!Number.isInteger(floor) || floor! < 0 || floor! > this.topFloor) throw new RangeError(`no floor ${floor}`);      if (!this.pending.includes(floor!)) this.pending.push(floor!);    }    this.state = typeof next === "function" ? next(this) : next;    return this.state;  }  decide(): EState {    if (this.sched.stopHere(this.floor, this.pending)) return this.open();    const d = this.sched.direction(this.floor, this.last, this.pending);    if (d === null) return "idle";    this.last = d;    return d === "up" ? "movingUp" : "movingDown";  }  onArrive(d: Dir): EState {    if (this.sched.stopHere(this.floor, this.pending)) return this.open();    return d === "up" ? "movingUp" : "movingDown";  }  private open(): EState {    this.pending = this.pending.filter((f) => f !== this.floor);    this.stops.push(this.floor);    return "doorsOpen";  }  // One step of time: move one floor, or close the doors.  tick(): void {    if (this.state === "movingUp" || this.state === "movingDown") {      this.floor += this.state === "movingUp" ? 1 : -1;      this.travelled++;      this.send("arrive");    } else if (this.state === "doorsOpen") this.send("doorTimeout");  }}

function run(name: string, sched: Scheduler) {  const e = new Elevator(sched);  for (const f of [5, 2, 8, 3]) e.send("request", f);  while (e.state !== "idle") e.tick();  console.log(name.padEnd(5), "stops:", e.stops.join(" "), "| floors travelled:", e.travelled);}run("scan", new Scan());run("fcfs", new FirstComeFirstServed());const lift = new Elevator(new Scan());try { lift.send("arrive"); } catch (e) { console.log((e as Error).message); }

$ node demo.tsidle { ok: true } hasMoney{ ok: false, reason: 'insert 25 more cents' }{ ok: true } { ok: true, item: 'chips', change: [ 25, 25, 25 ] } idletrue select is not allowed in state idlescan  stops: 2 3 5 8 | floors travelled: 8fcfs  stops: 5 2 8 3 | floors travelled: 19arrive is not allowed in state idle

test("vending: the full transition matrix", () => {  const events = ["insert", "select", "cancel", "repair"] as const;  const makers = {    idle: () => new VendingMachine(products),    hasMoney: () => { const m = new VendingMachine(products); m.insert(5); return m; },    outOfService: () => { const m = new VendingMachine(products, () => false); m.insert(125); m.select("A1"); return m; },  };  const throws: Record<string, string[]> = {    idle: ["select", "cancel", "repair"],    hasMoney: ["repair"],    outOfService: ["insert", "select", "cancel"],  };  for (const [state, make] of Object.entries(makers)) {    for (const ev of events) {      const m = make();      assert.equal(m.stateName, state);      const call = () => (ev === "insert" ? m.insert(5) : ev === "select" ? m.select("A1") : m[ev]());      if (throws[state].includes(ev)) assert.throws(call, InvalidTransition, `${state}/${ev}`);      else assert.doesNotThrow(call, `${state}/${ev}`);    }  }});

$ node --test --test-reporter=spec state.test.ts | LC_ALL=C sed 's/\xE2\x9C\x94/pass/; s/\xE2\x84\xB9/#/'pass vending: pay, get item and change, go back to idle (3.291634ms)pass vending: business failures keep the money and the state (0.386883ms)pass vending: a jam refunds and takes the machine out of service until repaired (0.685565ms)pass vending: the full transition matrix (0.866313ms)pass makeChange uses the biggest coins first (0.393002ms)pass elevator: scan serves floors on the way, in floor order (0.521624ms)pass elevator: first-come-first-served keeps request order and travels further (0.381602ms)pass elevator: a request made while moving is picked up if it is on the way (0.187408ms)pass elevator: events a state cannot accept are rejected (0.696541ms)pass elevator: a fault stops everything until reset (0.641554ms)# tests 10# suites 0# pass 10# fail 0# cancelled 0# skipped 0# todo 0# duration_ms 232.741462