Recently I started wondering what does it take to build an elevator software? How do the current elevators work? How do they know how to prioritise their requests from all the different floors and in different directions. I started digging to find answers to those questions and I decided to write an article about it. This article will not only give answers but I will also apply my findings in practice.

Hoes does an elevator work?

Every elevator works differently based on its real-world allocation and it's fairly difficult to build such an algorithm. All algorithms might differ from each other but looking at the most basic example, an elevator is using the so-called C-SCAN algorithm. This algorithm is used for Disk Scheduling also known as I/O scheduling.

From an elevator perspective, the algorithm works as follows:

1. Request array represents an array storing which floors the elevator has been requested from
2. The elevator services always from floor 0 to the highest floor.
3. While moving down, the elevator does not service any of the requests.
4. When the elevator reaches the beginning (floor 0), reverse the direction.
5. While moving up, the elevator services all floors one by one.
6. Currently serviced floor now becomes the new position of the elevator.
7. Go to step 6 until the elevator reaches the highest floor.
8. If the elevator reaches the highest floor, reverse the direction and go to step 3 until all requests have been serviced.

Going through the steps you can see that there are some performance optimisations which can be done here. For example:

• Point 3, the elevator will be quicker if it services any outstanding requests going down to floor 0.
• Point 7 - there is no point of going to the highest floor if there isn't a request for that floor
• Point 8 - it will make more sense to reverse the direction once the highest request has been serviced

Building the algorithm

This implementation of the algorithm will be purely functional using Vanilla Javascript. You should be able to test the code directly in the browser. The implementation will apply the proposed performance optimisations for points 3,7 and 8.

• To start with let's create an elevator class
• Let's assign a start method which will start processing the requests. We will pass the floor requests to it and the current floor of the elevator.

class Elevator {
  /**
   * Start service elevator requests
   * @param {number[]} requests - Floor Requests
   * @param {number} currFloor - Current Floor
   */
  start(requests = [], currFloor = 0) {}
}

Looking at requirement #2, the elevator will always go up first. We should organise the requests so we get to serve the higher floors first and then serve the floors below the current elevator floor.

class Elevator {
  minimumFloor = 0;

  /**
   * Start service elevator requests
   * @param {number[]} requests - Floor Requests
   * @param {number} currFloor - Current Floor
   */
  start(requests = [], currFloor = 0) {
    const organisedRequests = this.organiseRequests(requests, currFloor);
  }

  /**
   * Organise requests - higher floors first and then lower floors
   * @param {number[]} arr - Service Requests
   * @param {number} currFloor - Current Elevator Floor
   */
  organiseRequests(arr, currFloor) {
    const { highFloors, lowFloors } = arr.reduce(
      (acc, curr) => {
        const isHighFloor = curr >= currFloor;
        return isHighFloor
          ? {
              ...acc,
              highFloors: [...acc.highFloors, curr],
            }
          : {
              ...acc,
              lowFloors: [...acc.lowFloors, curr],
            };
      },
      { lowFloors: [], highFloors: [] }
    );

    // Sorting high floors, asc order
    highFloors.sort((a, b) => a - b);
    // Sorting low floors, desc order
    lowFloors.sort((a, b) => b - a);

    // The last floor should always be the minimum floor - 0
    return [...highFloors, ...lowFloors, this.minimumFloor];
  }
}

Let's highlight what is going on in organiseRequests.

1. The requests are divided into two separate lists - one for higher floors and the other one for lower floors based on the elevator's current floor.
2. The higher floors are sorted by ascending order, e.g. 5,6,7,8
3. The lower floors are sorted by descending order so when the elevator goes down, it starts picking the lowest high first to the lowest floor, e.g. 4,3,2,1.
4. The method returns an array with all floor lists merged into one, starting with the high floors.
5. The minimum possible floor is also added to the requests list as the elevator should always finish all requests on the ground floor.

Now its time to service all organised requests. To do this, the algorithm will iterate through the organised list and serve the different requests.

The function looks like this

  /**
   * Serve all elevator requests
   * @param {number[]} arr - Floor Requests
   * @param {number} currFloor - Current Floor
   */
  serviceRequests(arr, currFloor) {
    arr.forEach((currItem) => {
      currFloor = currItem;
      console.log("Floor: ", currFloor);
    });
  }

As you can see this method is servicing requests by iterating over the organised list. Another thing to mention is that the current floor of the elevator is getting assigned to the currently serviced floor. (point 6) Lastly, log the current floor in the console.

Here is the full implementation:

class Elevator {
  minimumFloor = 0;

  /**
   * Start service elevator requests
   * @param {number[]} requests - Floor Requests
   * @param {number} currFloor - Current Floor
   */
  start(requests = [], currFloor = 0) {
    const organisedRequests = this.organiseRequests(requests, currFloor);

    this.serviceRequests(organisedRequests, currFloor);
  }

  /**
   * Organise requests - higher floors first and then lower floors
   * @param {number[]} arr - Service Requests
   * @param {number} currFloor - Current Elevator Floor
   */
  organiseRequests(arr, currFloor) {
    const { highFloors, lowFloors } = arr.reduce(
      (acc, curr) => {
        const isHighFloor = curr >= currFloor;
        return isHighFloor
          ? {
              ...acc,
              highFloors: [...acc.highFloors, curr],
            }
          : {
              ...acc,
              lowFloors: [...acc.lowFloors, curr],
            };
      },
      { lowFloors: [], highFloors: [] }
    );

    // Sorting high floors, asc order
    highFloors.sort((a, b) => a - b);
    // Sorting low floors, desc order
    lowFloors.sort((a, b) => b - a);

    // The last floor should always be the minimum floor - 0
    return [...highFloors, ...lowFloors, this.minimumFloor];
  }

  /**
   * Serve all elevator requests
   * @param {number[]} arr - Floor Requests
   * @param {number} currFloor - Current Floor
   */
  serviceRequests(arr, currFloor) {
    arr.forEach((currItem) => {
      currFloor = currItem;
      console.log("Floor: ", currFloor);
    });
  }
}

Once the elevator is executed the output will be logged in the console:

function init() {
  const requests = [100, 79, 34, 67, 60, 92, 11, 55, 41, 77];
  const currFloor = 50;

  const elevator = new Elevator();
  elevator.start(requests, currFloor);
}
init();

Output:

Floor:  55
Floor:  60
Floor:  67
Floor:  77
Floor:  79
Floor:  92
Floor:  100
Floor:  41
Floor:  34
Floor:  11
Floor:  0

Conclusion

It was interesting to find out the order of which the elevator prioritises its requests. It is safe to say that an elevator's last destination will always be the ground floor.

Keep in mind this is the most basic way of how an elevator can work. There are lots of optimisations and real-world scenarios where the elevator's algorithm will be completely different than this one, probably most of the cases.