from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum


class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0


class ElevatorState(Enum):
    STOPPED = "stopped"
    MOVING = "moving"
    MAINTENANCE = "maintenance"


@dataclass(frozen=True)
class HallRequest:                       # external: a floor plus the desired direction
    floor: int
    direction: Direction


class ElevatorCar:
    def __init__(self, car_id: int, floor: int = 0, capacity: int = 8):
        self.car_id, self.current_floor, self.capacity = car_id, floor, capacity
        self.direction = Direction.IDLE
        self.state = ElevatorState.STOPPED
        self.occupants = 0
        self.up_stops: set[int] = set()      # floors to serve while going up
        self.down_stops: set[int] = set()    # floors to serve while going down
        self.log: list[str] = []

    # ---- requests -------------------------------------------------------
    def add_stop(self, floor: int) -> None:
        if self.state is ElevatorState.MAINTENANCE:
            raise RuntimeError(f"car {self.car_id} is out of service")
        if floor == self.current_floor and self.direction is Direction.IDLE:
            return                                    # already here, doors will just open
        (self.up_stops if floor > self.current_floor else self.down_stops).add(floor)
        if self.direction is Direction.IDLE:
            self.direction = Direction.UP if floor > self.current_floor else Direction.DOWN
            self.state = ElevatorState.MOVING

    @property
    def pending(self) -> int:
        return len(self.up_stops) + len(self.down_stops)

    def is_full(self) -> bool:
        return self.occupants >= self.capacity

    # ---- movement (LOOK) ------------------------------------------------
    def _next_stop(self) -> int | None:
        if self.direction is Direction.UP:
            ahead = [f for f in self.up_stops if f > self.current_floor]
            if ahead:
                return min(ahead)
            return max(self.down_stops) if self.down_stops else None   # time to reverse
        if self.direction is Direction.DOWN:
            below = [f for f in self.down_stops if f < self.current_floor]
            if below:
                return max(below)
            return min(self.up_stops) if self.up_stops else None       # time to reverse
        return None

    def step(self) -> None:
        """Move one floor, or stop and open the doors if this floor is a stop."""
        if self.state is ElevatorState.MAINTENANCE:
            return
        target = self._next_stop()
        if target is None:
            self.direction, self.state = Direction.IDLE, ElevatorState.STOPPED
            return

        if target == self.current_floor:
            self.up_stops.discard(target)
            self.down_stops.discard(target)
            self.log.append(f"car{self.car_id}: doors open at {target}")
            if self.pending == 0:
                self.direction, self.state = Direction.IDLE, ElevatorState.STOPPED
            return

        step = 1 if target > self.current_floor else -1
        self.current_floor += step
        self.direction = Direction.UP if step == 1 else Direction.DOWN
        self.state = ElevatorState.MOVING
        if self.current_floor in self.up_stops or self.current_floor in self.down_stops:
            self.up_stops.discard(self.current_floor)
            self.down_stops.discard(self.current_floor)
            self.log.append(f"car{self.car_id}: doors open at {self.current_floor}")


class DispatchStrategy(ABC):
    @abstractmethod
    def choose(self, cars: list[ElevatorCar], req: HallRequest) -> ElevatorCar | None: ...


class NearestSuitableCar(DispatchStrategy):
    PENALTY = 1_000

    def _cost(self, car: ElevatorCar, req: HallRequest) -> int:
        distance = abs(car.current_floor - req.floor)
        if car.direction is Direction.IDLE:
            return distance
        moving_toward = (
            (car.direction is Direction.UP and req.floor >= car.current_floor) or
            (car.direction is Direction.DOWN and req.floor <= car.current_floor)
        )
        if moving_toward and car.direction is req.direction:
            return distance                       # free: served along the way
        return distance + self.PENALTY            # would need to turn around

    def choose(self, cars, req):
        eligible = [c for c in cars
                    if c.state is not ElevatorState.MAINTENANCE and not c.is_full()]
        if not eligible:
            return None
        return min(eligible, key=lambda c: (self._cost(c, req), c.pending, c.car_id))


class ElevatorSystem:
    def __init__(self, cars: list[ElevatorCar], strategy: DispatchStrategy):
        self.cars, self.strategy = cars, strategy

    def hall_request(self, floor: int, direction: Direction) -> ElevatorCar:
        car = self.strategy.choose(self.cars, HallRequest(floor, direction))
        if car is None:
            raise RuntimeError("no car available")
        car.add_stop(floor)
        return car

    def step(self, ticks: int = 1) -> None:
        for _ in range(ticks):
            for car in self.cars:
                car.step()


# --- an en-route car beats an idle one ---------------------------------------
a = ElevatorCar(1, floor=3); a.add_stop(10)          # car 1: at floor 3, heading UP to 10
b = ElevatorCar(2, floor=8)                          # car 2: idle at floor 8
system = ElevatorSystem([a, b], NearestSuitableCar())

chosen = system.hall_request(5, Direction.UP)
assert chosen is a                                    # picked up on the way, not the idle car

# --- the car sweeps: floor 5, then floor 10, never 10 then back --------------
system.step(12)
assert "car1: doors open at 5" in a.log
assert a.log.index("car1: doors open at 5") < a.log.index("car1: doors open at 10")

# --- a car in maintenance is never dispatched ---------------------------------
a.state = ElevatorState.MAINTENANCE
assert system.hall_request(2, Direction.DOWN) is b

print(a.log)
print("car2 sent to floor 2:", sorted(b.down_stops))