Designing an Elevator System

from enum import Enum


class Direction(Enum):
    UP = "UP"
    DOWN = "DOWN"
    IDLE = "IDLE"

#pragma once

enum class Direction {
    UP,
    DOWN,
    IDLE
};

class Direction {
    static UP = "UP";
    static DOWN = "DOWN";
    static IDLE = "IDLE";
}

export default Direction;

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

from elevator.model.direction import Direction


@dataclass(frozen=True)
class Request:
    floor: int
    direction: Optional[Direction] = None  # None for internal car calls

    def __str__(self) -> str:
        dir_part = f", dir={self.direction.value}" if self.direction else ""
        return f"Request[floor={self.floor}{dir_part}]"

#pragma once
#include <string>
#include <optional>
#include "Direction.h"

class Request {
    int floor_;
    std::optional<Direction> direction_; // nullopt for internal car calls

public:
    Request(int floor, std::optional<Direction> direction)
        : floor_(floor), direction_(direction) {}

    int getFloor() const { return floor_; }
    std::optional<Direction> getDirection() const { return direction_; }

    std::string toString() const {
        std::string s = "Request[floor=" + std::to_string(floor_);
        if (direction_.has_value()) {
            s += ", dir=" + std::to_string(static_cast<int>(direction_.value()));
        }
        return s + "]";
    }
};

import Direction from "./Direction.js";

class Request {
    #floor;
    #direction; // null for internal car calls

    constructor(floor, direction = null) {
        this.#floor = floor;
        this.#direction = direction;
    }

    getFloor() { return this.#floor; }
    getDirection() { return this.#direction; }

    toString() {
        const dirPart = this.#direction ? `, dir=${this.#direction}` : "";
        return `Request[floor=${this.#floor}${dirPart}]`;
    }
}

export default Request;

from __future__ import annotations
from sortedcontainers import SortedList
from typing import Optional, TYPE_CHECKING

from elevator.model.direction import Direction

if TYPE_CHECKING:
    from elevator.movement.movement_strategy import MovementStrategy


class ElevatorCar:
    def __init__(self, car_id: int, start_floor: int) -> None:
        self._id = car_id
        self._current_floor = start_floor
        self._direction = Direction.IDLE
        # Committed stops, split by travel direction for LOOK scheduling.
        self._up_stops: SortedList[int] = SortedList()
        self._down_stops: SortedList[int] = SortedList()

    def add_stop(self, floor: int) -> None:
        """Commit to serving a floor. Bucketed by where it sits relative to us."""
        if floor == self._current_floor:
            self._open_doors()
            return
        if floor > self._current_floor:
            self._up_stops.add(floor)
        else:
            self._down_stops.add(floor)
        if self._direction == Direction.IDLE:
            self._direction = Direction.UP if floor > self._current_floor else Direction.DOWN

    def step(self, strategy: MovementStrategy) -> None:
        """Advance one floor toward the strategy's chosen target."""
        target: Optional[int] = strategy.next_floor(self)
        if target is None:
            self._direction = Direction.IDLE
            return

        if target > self._current_floor:
            self._current_floor += 1
            self._direction = Direction.UP
        elif target < self._current_floor:
            self._current_floor -= 1
            self._direction = Direction.DOWN

        if self._current_floor == target:
            self._up_stops.discard(target)
            self._down_stops.discard(target)
            self._open_doors()

    def _open_doors(self) -> None:
        print(f"  🚪 Car {self._id} opens doors at floor {self._current_floor}")

    def distance_to(self, floor: int) -> int:
        """Cost function the dispatcher uses."""
        return abs(self._current_floor - floor)

    @property
    def id(self) -> int:
        return self._id

    @property
    def current_floor(self) -> int:
        return self._current_floor

    @property
    def direction(self) -> Direction:
        return self._direction

    @property
    def up_stops(self) -> SortedList[int]:
        return self._up_stops

    @property
    def down_stops(self) -> SortedList[int]:
        return self._down_stops

    @property
    def is_idle(self) -> bool:
        return len(self._up_stops) == 0 and len(self._down_stops) == 0

    def __str__(self) -> str:
        return (f"Car {self._id} @floor {self._current_floor} "
                f"({self._direction.value}) stops↑{list(self._up_stops)} ↓{list(self._down_stops)}")

#pragma once
#include <set>
#include <string>
#include <iostream>
#include <cmath>
#include <optional>
#include "Direction.h"

// Forward declaration
class MovementStrategy;

class ElevatorCar {
    int id_;
    int currentFloor_;
    Direction direction_ = Direction::IDLE;
    std::set<int> upStops_;
    std::set<int> downStops_;

    void openDoors() {
        std::cout << "  🚪 Car " << id_ << " opens doors at floor " << currentFloor_ << "\n";
    }

public:
    ElevatorCar(int id, int startFloor) : id_(id), currentFloor_(startFloor) {}

    void addStop(int floor) {
        if (floor == currentFloor_) { openDoors(); return; }
        if (floor > currentFloor_) upStops_.insert(floor);
        else downStops_.insert(floor);
        if (direction_ == Direction::IDLE) {
            direction_ = floor > currentFloor_ ? Direction::UP : Direction::DOWN;
        }
    }

    void step(MovementStrategy& strategy);

    int distanceTo(int floor) const { return std::abs(currentFloor_ - floor); }

    int getId() const { return id_; }
    int getCurrentFloor() const { return currentFloor_; }
    Direction getDirection() const { return direction_; }
    const std::set<int>& getUpStops() const { return upStops_; }
    const std::set<int>& getDownStops() const { return downStops_; }
    std::set<int>& getUpStopsMut() { return upStops_; }
    std::set<int>& getDownStopsMut() { return downStops_; }
    bool isIdle() const { return upStops_.empty() && downStops_.empty(); }

    void setDirection(Direction d) { direction_ = d; }
    void setCurrentFloor(int f) { currentFloor_ = f; }

    std::string toString() const {
        std::string s = "Car " + std::to_string(id_) + " @floor " + std::to_string(currentFloor_);
        s += " (" + std::to_string(static_cast<int>(direction_)) + ") stops↑[";
        for (auto it = upStops_.begin(); it != upStops_.end(); ++it) {
            if (it != upStops_.begin()) s += ", ";
            s += std::to_string(*it);
        }
        s += "] ↓[";
        for (auto it = downStops_.begin(); it != downStops_.end(); ++it) {
            if (it != downStops_.begin()) s += ", ";
            s += std::to_string(*it);
        }
        return s + "]";
    }
};

import Direction from "./Direction.js";

class ElevatorCar {
    #id;
    #currentFloor;
    #direction = Direction.IDLE;
    #upStops = new Set();   // Sorted via manual iteration
    #downStops = new Set();

    constructor(id, startFloor) {
        this.#id = id;
        this.#currentFloor = startFloor;
    }

    /** Commit to serving a floor. Bucketed by where it sits relative to us. */
    addStop(floor) {
        if (floor === this.#currentFloor) { this.#openDoors(); return; }
        if (floor > this.#currentFloor) this.#upStops.add(floor);
        else this.#downStops.add(floor);
        if (this.#direction === Direction.IDLE) {
            this.#direction = floor > this.#currentFloor ? Direction.UP : Direction.DOWN;
        }
    }

    /** Advance one floor toward the strategy's chosen target. */
    step(strategy) {
        const target = strategy.nextFloor(this);
        if (target === null) { this.#direction = Direction.IDLE; return; }

        if (target > this.#currentFloor) { this.#currentFloor++; this.#direction = Direction.UP; }
        else if (target < this.#currentFloor) { this.#currentFloor--; this.#direction = Direction.DOWN; }

        if (this.#currentFloor === target) {
            this.#upStops.delete(target);
            this.#downStops.delete(target);
            this.#openDoors();
        }
    }

    #openDoors() {
        console.log(`  🚪 Car ${this.#id} opens doors at floor ${this.#currentFloor}`);
    }

    distanceTo(floor) { return Math.abs(this.#currentFloor - floor); }

    getId() { return this.#id; }
    getCurrentFloor() { return this.#currentFloor; }
    getDirection() { return this.#direction; }
    getUpStops() { return [...this.#upStops].sort((a, b) => a - b); }
    getDownStops() { return [...this.#downStops].sort((a, b) => a - b); }
    isIdle() { return this.#upStops.size === 0 && this.#downStops.size === 0; }

    toString() {
        return `Car ${this.#id} @floor ${this.#currentFloor} (${this.#direction}) ` +
            `stops↑[${this.getUpStops()}] ↓[${this.getDownStops()}]`;
    }
}

export default ElevatorCar;

from __future__ import annotations
from abc import ABC, abstractmethod
from typing import Optional, TYPE_CHECKING

if TYPE_CHECKING:
    from elevator.model.elevator_car import ElevatorCar


class MovementStrategy(ABC):
    @abstractmethod
    def next_floor(self, car: ElevatorCar) -> Optional[int]:
        """Return the floor the car should head toward next, or None if it has none."""
        ...

#pragma once
#include <optional>

class ElevatorCar;

class MovementStrategy {
public:
    virtual ~MovementStrategy() = default;
    /** @return the floor the car should head toward next, or nullopt if it has none. */
    virtual std::optional<int> nextFloor(ElevatorCar& car) = 0;
};

/**
 * @interface MovementStrategy
 * @method nextFloor(car: ElevatorCar): number | null
 */
class MovementStrategy {
    /** @return the floor the car should head toward next, or null if it has none. */
    nextFloor(car) {
        throw new Error("nextFloor() must be implemented");
    }
}

export default MovementStrategy;

from __future__ import annotations
from typing import Optional, TYPE_CHECKING

from elevator.model.direction import Direction
from elevator.movement.movement_strategy import MovementStrategy

if TYPE_CHECKING:
    from elevator.model.elevator_car import ElevatorCar


class LookStrategy(MovementStrategy):
    def next_floor(self, car: ElevatorCar) -> Optional[int]:
        floor = car.current_floor
        direction = car.direction

        if direction == Direction.UP:
            # Find nearest stop at or above current floor
            idx = car.up_stops.bisect_left(floor)
            if idx < len(car.up_stops):
                return car.up_stops[idx]
            # Nothing more above: reverse and serve the highest pending below.
            return car.down_stops[-1] if car.down_stops else None

        if direction == Direction.DOWN:
            # Find nearest stop at or below current floor
            idx = car.down_stops.bisect_right(floor) - 1
            if idx >= 0:
                return car.down_stops[idx]
            return car.up_stops[0] if car.up_stops else None

        # IDLE: pick whichever set has work, nearest first.
        if car.up_stops:
            return car.up_stops[0]
        if car.down_stops:
            return car.down_stops[-1]
        return None

#pragma once
#include "MovementStrategy.h"
#include "ElevatorCar.h"
#include "Direction.h"

class LookStrategy : public MovementStrategy {
public:
    std::optional<int> nextFloor(ElevatorCar& car) override {
        int floor = car.getCurrentFloor();
        Direction dir = car.getDirection();

        if (dir == Direction::UP) {
            // ceiling: first element >= floor
            auto it = car.getUpStops().lower_bound(floor);
            if (it != car.getUpStops().end()) return *it;
            // Nothing more above: reverse.
            if (car.getDownStops().empty()) return std::nullopt;
            return *car.getDownStops().rbegin();
        }
        if (dir == Direction::DOWN) {
            // floor: last element <= floor
            auto it = car.getDownStops().upper_bound(floor);
            if (it != car.getDownStops().begin()) { --it; return *it; }
            if (car.getUpStops().empty()) return std::nullopt;
            return *car.getUpStops().begin();
        }
        // IDLE: pick whichever set has work, nearest first.
        if (!car.getUpStops().empty()) return *car.getUpStops().begin();
        if (!car.getDownStops().empty()) return *car.getDownStops().rbegin();
        return std::nullopt;
    }
};

import Direction from "../model/Direction.js";
import MovementStrategy from "./MovementStrategy.js";

class LookStrategy extends MovementStrategy {
    nextFloor(car) {
        const floor = car.getCurrentFloor();
        const dir = car.getDirection();
        const upStops = car.getUpStops();   // sorted ascending
        const downStops = car.getDownStops(); // sorted ascending

        if (dir === Direction.UP) {
            const up = upStops.find(s => s >= floor);
            if (up !== undefined) return up;
            // Nothing more above: reverse.
            return downStops.length > 0 ? downStops[downStops.length - 1] : null;
        }
        if (dir === Direction.DOWN) {
            const down = [...downStops].reverse().find(s => s <= floor);
            if (down !== undefined) return down;
            return upStops.length > 0 ? upStops[0] : null;
        }
        // IDLE: pick whichever set has work, nearest first.
        if (upStops.length > 0) return upStops[0];
        if (downStops.length > 0) return downStops[downStops.length - 1];
        return null;
    }
}

export default LookStrategy;

from __future__ import annotations
from abc import ABC, abstractmethod
from typing import List, TYPE_CHECKING

if TYPE_CHECKING:
    from elevator.model.elevator_car import ElevatorCar
    from elevator.model.request import Request


class DispatchStrategy(ABC):
    @abstractmethod
    def select_car(self, cars: List[ElevatorCar], request: Request) -> ElevatorCar:
        """Pick the best car to serve the given request."""
        ...

#pragma once
#include <vector>
#include "ElevatorCar.h"
#include "Request.h"

class DispatchStrategy {
public:
    virtual ~DispatchStrategy() = default;
    virtual ElevatorCar& selectCar(std::vector<ElevatorCar>& cars, const Request& request) = 0;
};

/**
 * @interface DispatchStrategy
 * @method selectCar(cars: ElevatorCar[], request: Request): ElevatorCar
 */
class DispatchStrategy {
    selectCar(cars, request) {
        throw new Error("selectCar() must be implemented");
    }
}

export default DispatchStrategy;

from __future__ import annotations
from typing import List, TYPE_CHECKING

from elevator.dispatch.dispatch_strategy import DispatchStrategy

if TYPE_CHECKING:
    from elevator.model.elevator_car import ElevatorCar
    from elevator.model.request import Request


class NearestCarDispatch(DispatchStrategy):
    def select_car(self, cars: List[ElevatorCar], request: Request) -> ElevatorCar:
        best: ElevatorCar | None = None
        best_cost = float("inf")

        for car in cars:
            cost = car.distance_to(request.floor)
            # Nudge idle cars to win ties so busy cars don't get piled on.
            if not car.is_idle:
                cost += 1
            if cost < best_cost:
                best_cost = cost
                best = car

        assert best is not None
        return best

#pragma once
#include <vector>
#include <limits>
#include "DispatchStrategy.h"

class NearestCarDispatch : public DispatchStrategy {
public:
    ElevatorCar& selectCar(std::vector<ElevatorCar>& cars, const Request& request) override {
        ElevatorCar* best = nullptr;
        int bestCost = std::numeric_limits<int>::max();

        for (auto& car : cars) {
            int cost = car.distanceTo(request.getFloor());
            // Nudge idle cars to win ties so busy cars don't get piled on.
            if (!car.isIdle()) cost += 1;
            if (cost < bestCost) { bestCost = cost; best = &car; }
        }
        return *best;
    }
};

import DispatchStrategy from "./DispatchStrategy.js";

class NearestCarDispatch extends DispatchStrategy {
    selectCar(cars, request) {
        let best = null;
        let bestCost = Infinity;

        for (const car of cars) {
            let cost = car.distanceTo(request.getFloor());
            // Nudge idle cars to win ties so busy cars don't get piled on.
            if (!car.isIdle()) cost += 1;
            if (cost < bestCost) { bestCost = cost; best = car; }
        }
        return best;
    }
}

export default NearestCarDispatch;

from __future__ import annotations
from typing import List, Optional

from elevator.dispatch.dispatch_strategy import DispatchStrategy
from elevator.dispatch.nearest_car_dispatch import NearestCarDispatch
from elevator.model.direction import Direction
from elevator.model.elevator_car import ElevatorCar
from elevator.model.request import Request
from elevator.movement.look_strategy import LookStrategy
from elevator.movement.movement_strategy import MovementStrategy


class ElevatorSystem:
    def __init__(
        self,
        car_count: int,
        dispatch: Optional[DispatchStrategy] = None,
        movement: Optional[MovementStrategy] = None,
    ) -> None:
        self._dispatch = dispatch or NearestCarDispatch()
        self._movement = movement or LookStrategy()
        self._cars: List[ElevatorCar] = [
            ElevatorCar(i, 0) for i in range(1, car_count + 1)
        ]

    def request_hall_call(self, floor: int, direction: Direction) -> None:
        """Hall call: someone on `floor` wants to go `direction`. Dispatcher picks the car."""
        req = Request(floor, direction)
        car = self._dispatch.select_car(self._cars, req)
        print(f"↳ Hall call {req} assigned to Car {car.id}")
        car.add_stop(floor)

    def request_car_call(self, car_id: int, floor: int) -> None:
        """Car call: passenger inside `car_id` presses `floor`."""
        car = self._cars[car_id - 1]
        print(f"↳ Car call: Car {car_id} → floor {floor}")
        car.add_stop(floor)

    def step(self) -> None:
        """Advance the whole system by one tick."""
        for car in self._cars:
            if not car.is_idle:
                car.step(self._movement)

    def all_idle(self) -> bool:
        return all(car.is_idle for car in self._cars)

    def print_state(self) -> None:
        for car in self._cars:
            print(f"  {car}")

#pragma once
#include <vector>
#include <memory>
#include <iostream>
#include <algorithm>
#include "ElevatorCar.h"
#include "Request.h"
#include "Direction.h"
#include "DispatchStrategy.h"
#include "MovementStrategy.h"
#include "NearestCarDispatch.h"
#include "LookStrategy.h"

class ElevatorSystem {
    std::vector<ElevatorCar> cars_;
    std::unique_ptr<DispatchStrategy> dispatch_;
    std::unique_ptr<MovementStrategy> movement_;

public:
    ElevatorSystem(int carCount,
                   std::unique_ptr<DispatchStrategy> dispatch = std::make_unique<NearestCarDispatch>(),
                   std::unique_ptr<MovementStrategy> movement = std::make_unique<LookStrategy>())
        : dispatch_(std::move(dispatch)), movement_(std::move(movement)) {
        for (int i = 1; i <= carCount; ++i) cars_.emplace_back(i, 0);
    }

    void requestHallCall(int floor, Direction dir) {
        Request req(floor, dir);
        auto& car = dispatch_->selectCar(cars_, req);
        std::cout << "↳ Hall call " << req.toString() << " assigned to Car " << car.getId() << "\n";
        car.addStop(floor);
    }

    void requestCarCall(int carId, int floor) {
        auto& car = cars_[carId - 1];
        std::cout << "↳ Car call: Car " << carId << " → floor " << floor << "\n";
        car.addStop(floor);
    }

    void step() {
        for (auto& car : cars_) {
            if (!car.isIdle()) car.step(*movement_);
        }
    }

    bool allIdle() const {
        return std::all_of(cars_.begin(), cars_.end(),
                           [](const ElevatorCar& c) { return c.isIdle(); });
    }

    void printState() const {
        for (const auto& car : cars_) std::cout << "  " << car.toString() << "\n";
    }
};

import Direction from "./model/Direction.js";
import ElevatorCar from "./model/ElevatorCar.js";
import Request from "./model/Request.js";
import NearestCarDispatch from "./dispatch/NearestCarDispatch.js";
import LookStrategy from "./movement/LookStrategy.js";

class ElevatorSystem {
    #cars = [];
    #dispatch;
    #movement;

    constructor(carCount, dispatch = new NearestCarDispatch(), movement = new LookStrategy()) {
        this.#dispatch = dispatch;
        this.#movement = movement;
        for (let i = 1; i <= carCount; i++) this.#cars.push(new ElevatorCar(i, 0));
    }

    /** Hall call: someone on `floor` wants to go `dir`. Dispatcher picks the car. */
    requestHallCall(floor, dir) {
        const req = new Request(floor, dir);
        const car = this.#dispatch.selectCar(this.#cars, req);
        console.log(`↳ Hall call ${req.toString()} assigned to Car ${car.getId()}`);
        car.addStop(floor);
    }

    /** Car call: passenger inside `carId` presses `floor`. */
    requestCarCall(carId, floor) {
        const car = this.#cars[carId - 1];
        console.log(`↳ Car call: Car ${carId} → floor ${floor}`);
        car.addStop(floor);
    }

    /** Advance the whole system by one tick. */
    step() {
        for (const car of this.#cars) {
            if (!car.isIdle()) car.step(this.#movement);
        }
    }

    allIdle() {
        return this.#cars.every(car => car.isIdle());
    }

    printState() {
        this.#cars.forEach(c => console.log(`  ${c.toString()}`));
    }
}

export default ElevatorSystem;

from elevator.elevator_system import ElevatorSystem
from elevator.model.direction import Direction


def main() -> None:
    system = ElevatorSystem(2)  # nearest-car + LOOK

    print("=== Requests coming in ===")
    system.request_hall_call(5, Direction.UP)    # someone at floor 5 going up
    system.request_hall_call(2, Direction.UP)    # someone at floor 2 going up
    system.request_car_call(1, 8)               # passenger in car 1 wants floor 8
    system.request_hall_call(9, Direction.DOWN)  # someone at floor 9 going down

    print("\nInitial state:")
    system.print_state()

    print("\n=== Simulation ===")
    tick = 0
    while not system.all_idle() and tick < 30:
        tick += 1
        print(f"\n[tick {tick}]")
        system.step()
        system.print_state()

    print(f"\n=== All requests served in {tick} ticks ===")


if __name__ == "__main__":
    main()

#include <iostream>
#include "ElevatorSystem.h"
#include "Direction.h"

int main() {
    ElevatorSystem system(2); // nearest-car + LOOK

    std::cout << "=== Requests coming in ===\n";
    system.requestHallCall(5, Direction::UP);   // someone at floor 5 going up
    system.requestHallCall(2, Direction::UP);   // someone at floor 2 going up
    system.requestCarCall(1, 8);               // passenger in car 1 wants floor 8
    system.requestHallCall(9, Direction::DOWN); // someone at floor 9 going down

    std::cout << "\nInitial state:\n";
    system.printState();

    std::cout << "\n=== Simulation ===\n";
    int tick = 0;
    while (!system.allIdle() && tick < 30) {
        tick++;
        std::cout << "\n[tick " << tick << "]\n";
        system.step();
        system.printState();
    }

    std::cout << "\n=== All requests served in " << tick << " ticks ===\n";
    return 0;
}

import ElevatorSystem from "./ElevatorSystem.js";
import Direction from "./model/Direction.js";

const system = new ElevatorSystem(2); // nearest-car + LOOK

console.log("=== Requests coming in ===");
system.requestHallCall(5, Direction.UP);   // someone at floor 5 going up
system.requestHallCall(2, Direction.UP);   // someone at floor 2 going up
system.requestCarCall(1, 8);               // passenger in car 1 wants floor 8
system.requestHallCall(9, Direction.DOWN); // someone at floor 9 going down

console.log("\nInitial state:");
system.printState();

console.log("\n=== Simulation ===");
let tick = 0;
while (!system.allIdle() && tick < 30) {
    tick++;
    console.log(`\n[tick ${tick}]`);
    system.step();
    system.printState();
}

console.log(`\n=== All requests served in ${tick} ticks ===`);