How to solve Elevator Management System using Scala

Introduction

Quite recently I was asked to solve the Elevator Management System task using Scala. For those who don't know the task let me make some introduction.

Your main goal is to design and implement an Elevator Management System that could work in any building. Your system should be able to handle up to 16 elevators. It should also enable:

• support for elevator calls,
• current state update,
• perform simulation step,
• elevator's state update.

Suggested interface looks like this:

ElevatorSystem {
    def pickup(Int, Int)
    def update(Int, Int, Int)
    def step()
    def status(): [(Int, Int, Int), (Int, Int, Int), ...]
}

In the given example the elevator status (method: status ()) is described by the three: (elevator ID, current number floor, target floor number), and the method itself should return collections of such triples. Update (...) changes these numbers for one of the lifts. Request (pickup (...)) to the elevator has two numbers: reporting floor and direction (negative means down, positive means top). step () performs one simulation step.

We can freely change the interface if needed.

Solution proposal

Let's jump into the actual solution. Before we do so, a small disclaimer. This is just a proposal of a solution. It is not the best one, not the most functional one. It is just a fine solution for the task that can obviously be improved in many ways. As we are on the same page right now, let's move on!

Let’s start with the implementation part. I will briefly give you the context of the Direction trait which has only two implementations: Up and Down. Not much to say about these. The code of that is here:

sealed trait Direction

case object Up extends Direction

case object Down extends Direction

object Direction {
  implicit def direction2Int(d: Direction): Int = d match {
    case Down => -1
    case Up => 1
  }
}

The only interesting here might be the implicit transformer of Direction to Int value.

Let’s check the ElevatorState class. The purpose of the class is to keep the track of what’s happening with a single elevator in the system.

case class ElevatorState(floor: Int = 0, goalFloors: List[Int] = List.empty) {
  def standingStill: Boolean = goalFloors.isEmpty

  def isGoingUp: Boolean = !standingStill && floor < goalFloors.min

  def isGoingDown: Boolean = !standingStill && floor > goalFloors.min

  def isMoving: Boolean = !standingStill
}

Within that state, we keep the current elevator’s position and a list of floors that the particular elevator has to visit. Moreover, we can check whether it’s moving, going up or down or standing and waiting for the request.

Moving onto the heart of the system it’s time to check the implementation of the Elevator class itself. The code is as follows:

case class Elevator(id: Int) {
  var _state: ElevatorState = ElevatorState()

  def update(floor: Int, goalFloor: Int): Unit =
    _state = ElevatorState(floor, List(goalFloor))

  def move(floor: Int, direction: Int): Unit =
    _state = _state.copy(goalFloors = _state.goalFloors :+ floor)


  def step: Unit = {
    val step = if (state.isGoingUp) {
      1
    } else if (state.isGoingDown) {
      -1
    } else {
      0
    }
    _state = _state.copy(floor = _state.floor + step)

    // remove visited floors
    _state = _state.copy(goalFloors = _state.goalFloors.filterNot(floor => floor == _state.floor))
  }


  def movingCost(floor: Int, direction: Int): Int = {
    math.abs(state.floor - floor)
  }

  def state: ElevatorState = _state

  def toStatus: (Int, Int, List[Int]) = (id, state.floor, state.goalFloors)
}

Starting from the top we can spot that each elevator has its own id. The most important method here is movingCost method that is a function of a distance between the current position of the elevator (state.floor) and the requested floor (floor). It enables to calculate the distance for each elevator respectively. Also step function is helpful as it executes one simulation step and changes two things: the current position of the elevator and removes already visited floors. The rest of the class isn’t that interesting as it has trivial implementation (check above).

Now it’s time to connect all the pieces together and implement ElevatorSystem trait. I did that in a MyElevatorSystem class that can be checked below.

case class MyElevatorSystem(elevatorsNum: Int = 5) extends ElevatorSystem {

  require(elevatorsNum >= 0 && elevatorsNum <= 16,
    "Elevator system supports up to 16 elevators")

  val elevators: List[Elevator] = (0 until elevatorsNum).toList.map(n => Elevator(n))

  override def status(): List[(Int, Int, List[Int])] = {
    elevators.map(_.toStatus)
  }

  override def update(elevatorId: Int, currentFloor: Int, goalFloor: Int): Unit =
    elevators.find(e => e.id == elevatorId).foreach { e =>
      e.update(currentFloor, goalFloor)
    }


  override def pickup(requestedFloor: Int, direction: Int): Unit =
    elevators.minBy(_.movingCost(requestedFloor, direction)).move(requestedFloor, direction)


  override def step(): Unit = elevators.foreach(_.step)
}

To fulfil the requirement of operating up to 16 elevators require method at the beginning checks the condition. By default, we run 5 elevators. The most intriguing methods are update and pickup. The first one executes a system update for the chosen elevator so it can go to the appropriate floor. While the second one calculates distances from the requested floor for each elevator and chooses the closest one to serve the request. I’m totally aware that the distance function as a cost function is not the best one and probably it is not how the real elevators systems look like.

The rest of the methods are easy to check when we see the implementation.

Comparing to the interface in the task description I made one small change in status method as I used a List of Ints in the method signature so it looks like this:

trait ElevatorSystem {
  def pickup(floor: Int, direction: Int)

  def update(elevatorId: Int, floor: Int, goalFloor: Int)

  def step()

  def status(): List[(Int, Int, List[Int])]
}

The solution has only two test classes. One of them checks whether the correct elevator is being chosen to serve a new request. It is separated because the algorithm that chooses the appropriate elevator is one of the main points of the system and is responsible for time management so the travellers don’t have to wait too long.

The test is not complicated:

class CostSpec extends AnyFlatSpec with Matchers {

  "Elevator" should "calculate its moving cost" in {
    val e = Elevator(0)
    e.movingCost(floor = 4, direction = Up) shouldBe 4

    e.move(floor = 3, direction = Up)

    e.update(floor = 2, goalFloor = 2)

    e.movingCost(floor = 4, direction = Up) shouldBe 2

    e.update(floor = 4, goalFloor = 4)

    e.move(floor = 3, direction = Up)

    e.update(floor = 3, goalFloor = 3)

    e.movingCost(floor = -4, direction = Down) shouldBe 7
  }
}

The other is responsible for testing the whole system. In that test, we do a small situation and check if the state of the system is correct after some steps. The test is also pretty simple and looks more or less like this:

class ElevatorSystemSpec extends AnyFlatSpec with Matchers with BeforeAndAfter {

  "An ElevatorSystem" should "handle up to 16 elevators" in {
    MyElevatorSystem(elevatorsNum = 2).elevatorsNum should be(2)
    MyElevatorSystem(elevatorsNum = 16).elevatorsNum should be(16)

    an[IllegalArgumentException] should be thrownBy MyElevatorSystem(elevatorsNum = 200)
  }

  it should "query the state of the elevators" in {
    val elevatorSystem = MyElevatorSystem(elevatorsNum = 2)
    elevatorSystem.status() should contain theSameElementsAs List((0, 0, List()), (1, 0, List()))
  }

  it should "receive a pickup request" in {
    val elevatorSystem = MyElevatorSystem(3)

    // all elevators at ground floor
    elevatorSystem.elevatorsNum should be(3)

    // request at 1st floor to go down
    elevatorSystem.pickup(requestedFloor = 1, direction = Down)

    // go over resources and pick the first fulfilling the request=
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 0, List(1)), (1, 0, List()), (2, 0, List()))

    // elevator goes up as requested
    elevatorSystem.step()

    // first elevator at 1st floor
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 1, List()), (1, 0, List()), (2, 0, List()))

    // request at 4th floor to go down
    elevatorSystem.pickup(requestedFloor = 4, direction = Down)

    elevatorSystem.status() should contain theSameElementsAs
      List((0, 1, List(4)), (1, 0, List()), (2, 0, List()))
    elevatorSystem.step()

    elevatorSystem.status() should contain theSameElementsAs
      List((0, 2, List(4)), (1, 0, List()), (2, 0, List()))
    elevatorSystem.step()
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 3, List(4)), (1, 0, List()), (2, 0, List()))
    elevatorSystem.step()
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 4, List()), (1, 0, List()), (2, 0, List()))

    // update is used to tell where an elevator should go to
    elevatorSystem.update(0, 4, 2)

    // elevator id=0 is going down from 4 to 2
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 4, List(2)), (1, 0, List()), (2, 0, List()))

    // take me from 5th floor down
    elevatorSystem.pickup(requestedFloor = 5, direction = Down)
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 4, List(2, 5)), (1, 0, List()), (2, 0, List()))

    // take me from level 5 up
    elevatorSystem.pickup(requestedFloor = 1, direction = Up)
    elevatorSystem.status() should contain theSameElementsAs
      List((0, 4, List(2, 5)), (1, 0, List(1)), (2, 0, List()))

    elevatorSystem.step()
    elevatorSystem.step()
    elevatorSystem.step()
    elevatorSystem.step()
    elevatorSystem.step()

    elevatorSystem.status() should contain theSameElementsAs
      List((0, 5, List()), (1, 1, List()), (2, 0, List()))

    elevatorSystem.update(1, 1, 0)
    elevatorSystem.update(0, 5, 3)

    elevatorSystem.step()
    elevatorSystem.step()

    elevatorSystem.status() should contain theSameElementsAs
      List((0, 3, List()), (1, 0, List()), (2, 0, List()))
  }
}

Each test case is pretty descriptive. And you can also follow the flow in the comments of the above test suite.

Approach

If you are not interested in my working process you can skip that section. As usual, I have decided to use divide and conquer approach for solving that kind of task. Before I even start I check if I deeply understand the problem. I try to rephrase it and walk through the task manually with a dummy data set. After having a solution in mind I try to write pseudocode that solves the issue. Now it’s time to check if any step can be optimised. If not I start writing code with the tests first approach. If you haven't tried TDD yet you should give it a go. After that, the project is completed and tests are green. If I bump into any problem I debug code to check what’s wrong.

Summary

For sure the solution is not perfect and might be improved in many ways. For example, more tests might be added, it would be good to refactor some parts to domain objects e.g. Request instead of List of Ints, synchronise code, so it can be used in a multithreading environment, make design and implementation more functional e.g. remove mutable state, change the interface and remove unused arguments, use better algorithms to decide which elevator should realise the request. There is a lot of room for improvement and I’m totally aware of that. What’s more, it is also possible to add some libraries like akka or akka-streams to solve that but I decided to use only Scala with scala-test. For sure the project itself might be also extended. You may want to add some UI for animation or use it as a REST endpoint and so on.

Did I have fun while solving the task? Yes, a lot! On a daily basis, it’s not common to solve such problems and it was nice having a break for a production system to implement a task like this one. If you do not have a lot of practice at your current work or you want to practice such challenging tasks before the interview or just to play with Scala I highly recommend picking it up and trying to implement it by yourself and check my solution later on for comparison or when you get stuck.

If you are curious you can either implement that task yourself or check out my repository at Github here. You can check it out and follow the How to run instructions in Readme. If you have any questions or problems you can easily find me on Twitter: @marcinkrykowski!