Design an Elevator System

from __future__ import annotations

import threading
from enum import Enum
from typing import Protocol


class Dir(Enum):
    """The car's state: a tiny state machine (IDLE <-> UP/DOWN)."""
    IDLE = "idle"
    UP = "up"
    DOWN = "down"


class Car:
    def __init__(self, name: str, floor: int):
        self.name, self.floor, self.dir = name, floor, Dir.IDLE
        self.stops: set[int] = set()

    def add_stop(self, floor: int) -> None:
        if floor == self.floor and self.dir is Dir.IDLE:
            return
        self.stops.add(floor)
        if self.dir is Dir.IDLE:
            self.dir = Dir.UP if floor > self.floor else Dir.DOWN

    def _has_stop(self, d: Dir) -> bool:
        return any((d is Dir.UP and f > self.floor) or (d is Dir.DOWN and f < self.floor) for f in self.stops)

    def step(self) -> bool:
        """LOOK: keep going while there are stops ahead, then turn. True if it stopped."""
        if not self.stops:
            self.dir = Dir.IDLE
            return False
        if not self._has_stop(self.dir):
            self.dir = Dir.DOWN if self.dir is Dir.UP else Dir.UP
        self.floor += 1 if self.dir is Dir.UP else -1
        if self.floor in self.stops:
            self.stops.remove(self.floor)
            if not self.stops:
                self.dir = Dir.IDLE
            return True
        return False


class Dispatcher(Protocol):
    """The Strategy that decides which car answers a hall call."""
    def pick(self, cars: list[Car], floor: int, d: Dir) -> Car: ...


class Nearest:
    def __init__(self, floors: int):
        self.floors = floors

    def cost(self, c: Car, floor: int, d: Dir) -> int:
        dist = abs(c.floor - floor)
        if c.dir is Dir.IDLE:
            return dist
        if c.dir is Dir.UP and d is Dir.UP and floor >= c.floor:
            return dist
        if c.dir is Dir.DOWN and d is Dir.DOWN and floor <= c.floor:
            return dist
        return dist + 2 * self.floors  # it must finish its trip and come back

    def pick(self, cars: list[Car], floor: int, d: Dir) -> Car:
        return min(cars, key=lambda c: self.cost(c, floor, d))  # min() keeps the first on ties


class Building:
    def __init__(self, floors: int, dispatcher: Dispatcher, *cars: Car):
        self._lock = threading.Lock()
        self.floors, self.dispatcher, self.cars = floors, dispatcher, list(cars)

    def call(self, floor: int, d: Dir) -> str:
        with self._lock:
            if not 0 <= floor < self.floors:
                raise ValueError(f"no floor {floor}")
            c = self.dispatcher.pick(self.cars, floor, d)
            c.add_stop(floor)
            return c.name

    def press(self, car: str, floor: int) -> None:
        with self._lock:
            next(c for c in self.cars if c.name == car).add_stop(floor)

    def tick(self) -> list[str]:
        with self._lock:
            return [f"car {c.name} opens at {c.floor}" for c in self.cars if c.step()]

    def idle(self) -> tuple[bool, str]:
        with self._lock:
            if any(c.dir is not Dir.IDLE for c in self.cars):
                return False, ""
            return True, ", ".join(f"{c.name} at {c.floor}" for c in self.cars)


b = Building(10, Nearest(10), Car("A", 0), Car("B", 9))


def call(t: int, floor: int, d: Dir) -> None:
    car = b.call(floor, d)
    print(f"t{t:<2} call floor {floor} {d.value:<4} -> car {car}")


def press(t: int, car: str, floor: int) -> None:
    b.press(car, floor)
    print(f"t{t:<2} car {car}: passenger goes to {floor}")


call(0, 3, Dir.UP)
call(0, 7, Dir.DOWN)
for t in range(1, 21):
    for e in b.tick():
        print(f"t{t:<2} {e}")
    if t == 2:
        press(t, "B", 1)
    elif t == 3:
        press(t, "A", 8)
        call(t, 5, Dir.DOWN)
    done, where = b.idle()
    if done:
        print(f"t{t:<2} all cars idle: {where}")
        break

// The car's state: a tiny state machine (idle <-> up/down).
type Dir = "idle" | "up" | "down";

class Car {
  readonly name: string;
  floor: number;
  dir: Dir = "idle";
  readonly stops = new Set<number>();
  constructor(name: string, floor: number) {
    this.name = name;
    this.floor = floor;
  }
  addStop(floor: number): void {
    if (floor === this.floor && this.dir === "idle") return;
    this.stops.add(floor);
    if (this.dir === "idle") this.dir = floor > this.floor ? "up" : "down";
  }
  private hasStop(d: Dir): boolean {
    for (const f of this.stops) if ((d === "up" && f > this.floor) || (d === "down" && f < this.floor)) return true;
    return false;
  }
  // LOOK: keep going while there are stops ahead, then turn. True if it stopped.
  step(): boolean {
    if (this.stops.size === 0) {
      this.dir = "idle";
      return false;
    }
    if (!this.hasStop(this.dir)) this.dir = this.dir === "up" ? "down" : "up";
    this.floor += this.dir === "up" ? 1 : -1;
    if (this.stops.delete(this.floor)) {
      if (this.stops.size === 0) this.dir = "idle";
      return true;
    }
    return false;
  }
}

// The Strategy that decides which car answers a hall call.
interface Dispatcher {
  pick(cars: Car[], floor: number, d: Dir): Car;
}

class Nearest implements Dispatcher {
  readonly floors: number;
  constructor(floors: number) {
    this.floors = floors;
  }
  cost(c: Car, floor: number, d: Dir): number {
    const dist = Math.abs(c.floor - floor);
    if (c.dir === "idle") return dist;
    if (c.dir === "up" && d === "up" && floor >= c.floor) return dist;
    if (c.dir === "down" && d === "down" && floor <= c.floor) return dist;
    return dist + 2 * this.floors; // it must finish its trip and come back
  }
  pick(cars: Car[], floor: number, d: Dir): Car {
    return cars.reduce((best, c) => (this.cost(c, floor, d) < this.cost(best, floor, d) ? c : best));
  }
}

// No lock: one thread, and nothing here awaits.
class Building {
  readonly floors: number;
  readonly dispatcher: Dispatcher;
  readonly cars: Car[];
  constructor(floors: number, dispatcher: Dispatcher, ...cars: Car[]) {
    this.floors = floors;
    this.dispatcher = dispatcher;
    this.cars = cars;
  }
  call(floor: number, d: Dir): string {
    if (floor < 0 || floor >= this.floors) throw new Error(`no floor ${floor}`);
    const c = this.dispatcher.pick(this.cars, floor, d);
    c.addStop(floor);
    return c.name;
  }
  press(car: string, floor: number): void {
    this.cars.find((c) => c.name === car)!.addStop(floor);
  }
  tick(): string[] {
    return this.cars.filter((c) => c.step()).map((c) => `car ${c.name} opens at ${c.floor}`);
  }
  idle(): [boolean, string] {
    if (this.cars.some((c) => c.dir !== "idle")) return [false, ""];
    return [true, this.cars.map((c) => `${c.name} at ${c.floor}`).join(", ")];
  }
}

const b = new Building(10, new Nearest(10), new Car("A", 0), new Car("B", 9));
const tt = (t: number) => `t${String(t).padEnd(2)}`;
function call(t: number, floor: number, d: Dir): void {
  console.log(`${tt(t)} call floor ${floor} ${d.padEnd(4)} -> car ${b.call(floor, d)}`);
}
function press(t: number, car: string, floor: number): void {
  b.press(car, floor);
  console.log(`${tt(t)} car ${car}: passenger goes to ${floor}`);
}

call(0, 3, "up");
call(0, 7, "down");
for (let t = 1; t <= 20; t++) {
  for (const e of b.tick()) console.log(`${tt(t)} ${e}`);
  if (t === 2) press(t, "B", 1);
  if (t === 3) {
    press(t, "A", 8);
    call(t, 5, "down");
  }
  const [done, where] = b.idle();
  if (done) {
    console.log(`${tt(t)} all cars idle: ${where}`);
    break;
  }
}

use std::collections::BTreeSet;
use std::fmt;
use std::sync::Mutex;

// The car's state: a tiny state machine (Idle <-> Up/Down).
#[derive(Clone, Copy, PartialEq)]
enum Dir { Idle, Up, Down }

impl fmt::Display for Dir {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad(match self { Dir::Idle => "idle", Dir::Up => "up", Dir::Down => "down" })
    }
}

struct Car { name: &'static str, floor: i32, dir: Dir, stops: BTreeSet<i32> }

impl Car {
    fn new(name: &'static str, floor: i32) -> Car { Car { name, floor, dir: Dir::Idle, stops: BTreeSet::new() } }

    fn add_stop(&mut self, floor: i32) {
        if floor == self.floor && self.dir == Dir::Idle { return; }
        self.stops.insert(floor);
        if self.dir == Dir::Idle { self.dir = if floor > self.floor { Dir::Up } else { Dir::Down }; }
    }

    fn has_stop(&self, d: Dir) -> bool {
        self.stops.iter().any(|&f| (d == Dir::Up && f > self.floor) || (d == Dir::Down && f < self.floor))
    }

    // LOOK: keep going while there are stops ahead, then turn. True if it stopped.
    fn step(&mut self) -> bool {
        if self.stops.is_empty() { self.dir = Dir::Idle; return false; }
        if !self.has_stop(self.dir) { self.dir = if self.dir == Dir::Up { Dir::Down } else { Dir::Up }; }
        self.floor += if self.dir == Dir::Up { 1 } else { -1 };
        if self.stops.remove(&self.floor) {
            if self.stops.is_empty() { self.dir = Dir::Idle; }
            return true;
        }
        false
    }
}

// The Strategy that decides which car answers a hall call (returns an index into cars).
trait Dispatcher: Send { fn pick(&self, cars: &[Car], floor: i32, d: Dir) -> usize; }

struct Nearest { floors: i32 }
impl Nearest {
    fn cost(&self, c: &Car, floor: i32, d: Dir) -> i32 {
        let dist = (c.floor - floor).abs();
        match (c.dir, d) {
            (Dir::Idle, _) => dist,
            (Dir::Up, Dir::Up) if floor >= c.floor => dist,
            (Dir::Down, Dir::Down) if floor <= c.floor => dist,
            _ => dist + 2 * self.floors, // it must finish its trip and come back
        }
    }
}
impl Dispatcher for Nearest {
    fn pick(&self, cars: &[Car], floor: i32, d: Dir) -> usize {
        let mut best = 0;
        for i in 1..cars.len() { if self.cost(&cars[i], floor, d) < self.cost(&cars[best], floor, d) { best = i; } }
        best
    }
}

struct Building { floors: i32, dispatcher: Box<dyn Dispatcher>, cars: Mutex<Vec<Car>> }

impl Building {
    fn call(&self, floor: i32, d: Dir) -> Result<&'static str, String> {
        if floor < 0 || floor >= self.floors { return Err(format!("no floor {floor}")); }
        let mut cars = self.cars.lock().unwrap();
        let i = self.dispatcher.pick(&cars, floor, d);
        cars[i].add_stop(floor);
        Ok(cars[i].name)
    }
    fn press(&self, car: &str, floor: i32) {
        let mut cars = self.cars.lock().unwrap();
        if let Some(c) = cars.iter_mut().find(|c| c.name == car) { c.add_stop(floor); }
    }
    fn tick(&self) -> Vec<String> {
        let mut cars = self.cars.lock().unwrap();
        cars.iter_mut().filter_map(|c| c.step().then(|| format!("car {} opens at {}", c.name, c.floor))).collect()
    }
    fn idle(&self) -> Option<String> {
        let cars = self.cars.lock().unwrap();
        if cars.iter().any(|c| c.dir != Dir::Idle) { return None; }
        Some(cars.iter().map(|c| format!("{} at {}", c.name, c.floor)).collect::<Vec<_>>().join(", "))
    }
}

fn main() {
    let b = Building { floors: 10, dispatcher: Box::new(Nearest { floors: 10 }), cars: Mutex::new(vec![Car::new("A", 0), Car::new("B", 9)]) };
    let call = |t: i32, floor: i32, d: Dir| {
        let car = b.call(floor, d).unwrap();
        println!("t{t:<2} call floor {floor} {d:<4} -> car {car}");
    };
    let press = |t: i32, car: &str, floor: i32| {
        b.press(car, floor);
        println!("t{t:<2} car {car}: passenger goes to {floor}");
    };

    call(0, 3, Dir::Up);
    call(0, 7, Dir::Down);
    for t in 1..=20 {
        for e in b.tick() { println!("t{t:<2} {e}"); }
        match t {
            2 => press(t, "B", 1),
            3 => { press(t, "A", 8); call(t, 5, Dir::Down); }
            _ => {}
        }
        if let Some(where_) = b.idle() { println!("t{t:<2} all cars idle: {where_}"); break; }
    }
}

import java.util.List;
import java.util.TreeSet;
import java.util.stream.Collectors;

public class Main {
    // The car's state: a tiny state machine (IDLE <-> UP/DOWN).
    enum Dir {
        IDLE, UP, DOWN;
        @Override public String toString() { return name().toLowerCase(); }
    }

    static final class Car {
        final String name;
        int floor;
        Dir dir = Dir.IDLE;
        final TreeSet<Integer> stops = new TreeSet<>();
        Car(String name, int floor) { this.name = name; this.floor = floor; }

        void addStop(int f) {
            if (f == floor && dir == Dir.IDLE) return;
            stops.add(f);
            if (dir == Dir.IDLE) dir = f > floor ? Dir.UP : Dir.DOWN;
        }

        boolean hasStop(Dir d) {
            return d == Dir.UP ? stops.higher(floor) != null : stops.lower(floor) != null;
        }

        // LOOK: keep going while there are stops ahead, then turn. True if it stopped.
        boolean step() {
            if (stops.isEmpty()) { dir = Dir.IDLE; return false; }
            if (!hasStop(dir)) dir = dir == Dir.UP ? Dir.DOWN : Dir.UP;
            floor += dir == Dir.UP ? 1 : -1;
            if (stops.remove(floor)) {
                if (stops.isEmpty()) dir = Dir.IDLE;
                return true;
            }
            return false;
        }
    }

    // The Strategy that decides which car answers a hall call.
    interface Dispatcher { Car pick(List<Car> cars, int floor, Dir d); }

    record Nearest(int floors) implements Dispatcher {
        int cost(Car c, int floor, Dir d) {
            int dist = Math.abs(c.floor - floor);
            if (c.dir == Dir.IDLE) return dist;
            if (c.dir == Dir.UP && d == Dir.UP && floor >= c.floor) return dist;
            if (c.dir == Dir.DOWN && d == Dir.DOWN && floor <= c.floor) return dist;
            return dist + 2 * floors; // it must finish its trip and come back
        }
        public Car pick(List<Car> cars, int floor, Dir d) {
            Car best = cars.get(0);
            for (Car c : cars) if (cost(c, floor, d) < cost(best, floor, d)) best = c;
            return best;
        }
    }

    static final class Building {
        private final int floors;
        private final Dispatcher dispatcher;
        private final List<Car> cars;
        Building(int floors, Dispatcher d, Car... cars) { this.floors = floors; this.dispatcher = d; this.cars = List.of(cars); }

        synchronized String call(int floor, Dir d) {
            if (floor < 0 || floor >= floors) throw new IllegalArgumentException("no floor " + floor);
            Car c = dispatcher.pick(cars, floor, d);
            c.addStop(floor);
            return c.name;
        }
        synchronized void press(String car, int floor) {
            cars.stream().filter(c -> c.name.equals(car)).findFirst().orElseThrow().addStop(floor);
        }
        synchronized List<String> tick() {
            return cars.stream().filter(Car::step).map(c -> "car " + c.name + " opens at " + c.floor).toList();
        }
        synchronized String idle() {
            if (cars.stream().anyMatch(c -> c.dir != Dir.IDLE)) return null;
            return cars.stream().map(c -> c.name + " at " + c.floor).collect(Collectors.joining(", "));
        }
    }

    static Building b = new Building(10, new Nearest(10), new Car("A", 0), new Car("B", 9));

    static void call(int t, int floor, Dir d) {
        System.out.printf("t%-2d call floor %d %-4s -> car %s%n", t, floor, d, b.call(floor, d));
    }

    static void press(int t, String car, int floor) {
        b.press(car, floor);
        System.out.printf("t%-2d car %s: passenger goes to %d%n", t, car, floor);
    }

    public static void main(String[] args) {
        call(0, 3, Dir.UP);
        call(0, 7, Dir.DOWN);
        for (int t = 1; t <= 20; t++) {
            for (String e : b.tick()) System.out.printf("t%-2d %s%n", t, e);
            if (t == 2) press(t, "B", 1);
            if (t == 3) { press(t, "A", 8); call(t, 5, Dir.DOWN); }
            String where = b.idle();
            if (where != null) { System.out.printf("t%-2d all cars idle: %s%n", t, where); break; }
        }
    }
}

#include <cstdio>
#include <cstdlib>
#include <memory>
#include <mutex>
#include <optional>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

// The car's state: a tiny state machine (Idle <-> Up/Down).
enum class Dir { Idle, Up, Down };
const char* name(Dir d) { return d == Dir::Up ? "up" : d == Dir::Down ? "down" : "idle"; }

struct Car {
    Car(std::string n, int f) : name(std::move(n)), floor(f) {}
    std::string name;
    int floor;
    Dir dir = Dir::Idle;
    std::set<int> stops;

    void addStop(int f) {
        if (f == floor && dir == Dir::Idle) return;
        stops.insert(f);
        if (dir == Dir::Idle) dir = f > floor ? Dir::Up : Dir::Down;
    }
    bool hasStop(Dir d) const {
        return d == Dir::Up ? stops.upper_bound(floor) != stops.end() : stops.lower_bound(floor) != stops.begin();
    }
    // LOOK: keep going while there are stops ahead, then turn. True if it stopped.
    bool step() {
        if (stops.empty()) {
            dir = Dir::Idle;
            return false;
        }
        if (!hasStop(dir)) dir = dir == Dir::Up ? Dir::Down : Dir::Up;
        floor += dir == Dir::Up ? 1 : -1;
        if (stops.erase(floor)) {
            if (stops.empty()) dir = Dir::Idle;
            return true;
        }
        return false;
    }
};

// The Strategy that decides which car answers a hall call.
class Dispatcher {
public:
    virtual ~Dispatcher() = default;
    virtual size_t pick(const std::vector<Car>& cars, int floor, Dir d) const = 0;
};

class Nearest : public Dispatcher {
public:
    explicit Nearest(int floors) : floors_(floors) {}
    int cost(const Car& c, int floor, Dir d) const {
        int dist = std::abs(c.floor - floor);
        if (c.dir == Dir::Idle) return dist;
        if (c.dir == Dir::Up && d == Dir::Up && floor >= c.floor) return dist;
        if (c.dir == Dir::Down && d == Dir::Down && floor <= c.floor) return dist;
        return dist + 2 * floors_;  // it must finish its trip and come back
    }
    size_t pick(const std::vector<Car>& cars, int floor, Dir d) const override {
        size_t best = 0;
        for (size_t i = 1; i < cars.size(); i++)
            if (cost(cars[i], floor, d) < cost(cars[best], floor, d)) best = i;
        return best;
    }

private:
    int floors_;
};

class Building {
public:
    Building(int floors, std::unique_ptr<Dispatcher> d, std::vector<Car> cars)
        : floors_(floors), dispatcher_(std::move(d)), cars_(std::move(cars)) {}

    std::string call(int floor, Dir d) {
        std::lock_guard lock(mu_);
        if (floor < 0 || floor >= floors_) throw std::invalid_argument("no floor " + std::to_string(floor));
        Car& c = cars_[dispatcher_->pick(cars_, floor, d)];
        c.addStop(floor);
        return c.name;
    }
    void press(const std::string& car, int floor) {
        std::lock_guard lock(mu_);
        for (auto& c : cars_)
            if (c.name == car) c.addStop(floor);
    }
    std::vector<std::string> tick() {
        std::lock_guard lock(mu_);
        std::vector<std::string> opened;
        for (auto& c : cars_)
            if (c.step()) opened.push_back("car " + c.name + " opens at " + std::to_string(c.floor));
        return opened;
    }
    std::optional<std::string> idle() {
        std::lock_guard lock(mu_);
        std::string where;
        for (const auto& c : cars_) {
            if (c.dir != Dir::Idle) return std::nullopt;
            where += (where.empty() ? "" : ", ") + c.name + " at " + std::to_string(c.floor);
        }
        return where;
    }

private:
    std::mutex mu_;
    int floors_;
    std::unique_ptr<Dispatcher> dispatcher_;
    std::vector<Car> cars_;
};

int main() {
    Building b(10, std::make_unique<Nearest>(10), {Car{"A", 0}, Car{"B", 9}});
    auto call = [&](int t, int floor, Dir d) {
        std::string car = b.call(floor, d);
        std::printf("t%-2d call floor %d %-4s -> car %s\n", t, floor, name(d), car.c_str());
    };
    auto press = [&](int t, const std::string& car, int floor) {
        b.press(car, floor);
        std::printf("t%-2d car %s: passenger goes to %d\n", t, car.c_str(), floor);
    };

    call(0, 3, Dir::Up);
    call(0, 7, Dir::Down);
    for (int t = 1; t <= 20; t++) {
        for (const auto& e : b.tick()) std::printf("t%-2d %s\n", t, e.c_str());
        if (t == 2) press(t, "B", 1);
        if (t == 3) {
            press(t, "A", 8);
            call(t, 5, Dir::Down);
        }
        if (auto where = b.idle()) {
            std::printf("t%-2d all cars idle: %s\n", t, where->c_str());
            break;
        }
    }
}