Sequential Access Optimization (SCAN)

Determine the next floor for an elevator using the SCAN (elevator) algorithm -- the same strategy used in disk-head scheduling to minimize seek time.

Problem

Given:

• current_floor -- where the elevator is now
• direction -- currently moving UP or DOWN
• buttons -- a list of pressed buttons like ['5D', '3U', '7D'] where the number is the floor and the suffix indicates whether the button was pressed going UP, DOWN, or INSIDE the elevator

Determine the next floor the elevator should visit.

Approach

This implements the SCAN algorithm (also called the elevator algorithm):

1. Classify buttons into UP, DOWN, and INSIDE lists based on their suffix.
2. Sort floors in the current direction of travel.
3. Check if direction reversal is needed -- if no remaining floors lie ahead in the current direction, flip.
4. Build the visit order: Starting from the current floor, take all floors ahead in the current direction, then append floors in the opposite direction (reversed).
5. Return the first floor in the resulting ordered list.

The key insight: the elevator continues in one direction, serving all requests along the way, then reverses -- exactly like a disk head doing a SCAN sweep across platters. This minimizes total seek distance compared to naive FCFS scheduling.

Implementation

from enum import Enum
from random import choice, sample


class ButtonType(Enum):
    UP = "U"
    DOWN = "D"
    INSIDE = "I"


class Button:
    def __init__(self, button_str):
        self.floor = int(button_str[:-1])
        self.type = ButtonType(button_str[-1])


def map_input_buttons_to_lists(buttons):
    by_type = {
        bt: [Button(x) for x in buttons if x.endswith(bt.value)]
        for bt in ButtonType
    }
    # INSIDE buttons are reachable regardless of direction
    inside = by_type[ButtonType.INSIDE]
    by_type[ButtonType.UP] = by_type[ButtonType.UP] + inside
    by_type[ButtonType.DOWN] = by_type[ButtonType.DOWN] + inside
    return by_type


def check_direction(current_floor, direction, floors_map):
    """Return True if direction should reverse (no reachable floors ahead)."""
    return bool(
        floors_map[direction] and (
            (direction == ButtonType.UP and
             max(b.floor for b in floors_map[direction]) < current_floor) or
            (direction == ButtonType.DOWN and
             min(b.floor for b in floors_map[direction]) > current_floor)
        )
    )


def sort_floors_to_visit(current_floor, direction, opposite_dir, floors_map):
    """Build ordered visit list: floors ahead first, then opposite direction."""
    reverse = (direction == ButtonType.DOWN)
    floor_list = sorted(floors_map[direction], key=lambda x: x.floor, reverse=reverse)

    next_floor = next(
        (x for x in floor_list
         if (x.floor >= current_floor and direction == ButtonType.UP) or
            (x.floor <= current_floor and direction == ButtonType.DOWN)),
        None
    )

    if next_floor:
        idx = floor_list.index(next_floor)
        floor_list = floor_list[idx:] + sorted(floors_map[opposite_dir], key=lambda x: x.floor)
    else:
        floor_list.extend(sorted(floors_map[opposite_dir], key=lambda x: x.floor))

    return floor_list


def next_floor(current_floor, direction, buttons):
    floors_map = map_input_buttons_to_lists(buttons)

    if check_direction(current_floor, direction, floors_map):
        direction = ButtonType.DOWN if direction == ButtonType.UP else ButtonType.UP

    opposite_dir = ButtonType.DOWN if direction == ButtonType.UP else ButtonType.UP
    visit_order = sort_floors_to_visit(current_floor, direction, opposite_dir, floors_map)

    return visit_order[0].floor if visit_order else None


# Test harness
class TestData:
    TEST_FLOORS = [
        ['5D', '3U'],
        ['5D', '3U', '7D'],
        ['5D', '3U', '2U', '7D', '10U'],
    ]


def main():
    test_cases = [
        (choice(range(1, 21)), choice(list(ButtonType)),
         sample(TestData.TEST_FLOORS[i % len(TestData.TEST_FLOORS)],
                len(TestData.TEST_FLOORS[i % len(TestData.TEST_FLOORS)])))
        for i in range(20)
    ]
    for i, (floor, direction, buttons) in enumerate(test_cases):
        result = next_floor(floor, direction, buttons)
        print(f"Test {i}: floor={floor}, dir={direction.value}, "
              f"buttons={buttons}, next={result}")


if __name__ == "__main__":
    main()

Complexity

• Time: O(n log n) for sorting the button lists, where n = number of buttons
• Space: O(n) for the classified and sorted lists

Takeaway

SCAN is one of those algorithms where the real-world analogy (elevator) makes it click immediately. The same sequential-access principle matters in data loaders -- FFCV and WebDataset use sequential sharded reads because random I/O on spinning disks is 10-100x slower.

---

Back to Software Design