1
\$\begingroup\$

I solved the following Kata on Codewars: https://www.codewars.com/kata/58905bfa1decb981da00009e/train/cpp

It was a lot of fun to solve it.

Here everything you need to know so no need to use the link.

Synopsis A multi-floor building has a Lift in it.

People are queued on different floors waiting for the Lift.

Some people want to go up. Some people want to go down.

The floor they want to go to is represented by a number (i.e. when they enter the Lift this is the button they will press)

BEFORE (people waiting in queues)               AFTER (people at their destinations)
                   +--+                                          +--+ 
  /----------------|  |----------------\        /----------------|  |----------------\
10|                |  | 1,4,3,2        |      10|             10 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 9|                |  | 1,10,2         |       9|                |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 8|                |  |                |       8|                |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 7|                |  | 3,6,4,5,6      |       7|                |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 6|                |  |                |       6|          6,6,6 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 5|                |  |                |       5|            5,5 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 4|                |  | 0,0,0          |       4|          4,4,4 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 3|                |  |                |       3|            3,3 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 2|                |  | 4              |       2|          2,2,2 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 1|                |  | 6,5,2          |       1|            1,1 |  |                |
  |----------------|  |----------------|        |----------------|  |----------------|
 G|                |  |                |       G|          0,0,0 |  |                |
  |====================================|        |====================================|

Rules

Lift Rules

  • The Lift only goes up or down!

  • Each floor has both UP and DOWN Lift-call buttons (except top and ground floors which have only DOWN and UP respectively)

  • The Lift never changes direction until there are no more people wanting to get on/off in the direction it is already travelling

  • When empty the Lift tries to be smart. For example,

  • If it was going up then it may continue up to collect the highest floor person wanting to go down

  • If it was going down then it may continue down to collect the lowest floor person wanting to go up

  • The Lift has a maximum capacity of people

  • When called, the Lift will stop at a floor even if it is full, although unless somebody gets off nobody else can get on!

  • If the lift is empty, and no people are waiting, then it will return to the ground floor

People Rules

  • People are in "queues" that represent their order of arrival to wait for the Lift

  • All people can press the UP/DOWN Lift-call buttons

  • Only people going the same direction as the Lift may enter it

  • Entry is according to the "queue" order, but those unable to enter do not block those behind them that can

  • If a person is unable to enter a full Lift, they will press the UP/DOWN Lift-call button again after it has departed without them

Kata Task

  • Get all the people to the floors they want to go to while obeying the Lift rules and the People rules

  • Return a list of all floors that the Lift stopped at (in the order visited!)

NOTE: The Lift always starts on the ground floor (and people waiting on the ground floor may enter immediately)

I/O

Input

  • queues a list of queues of people for all floors of the building.

  • The height of the building varies

  • 0 = the ground floor

  • Not all floors have queues

  • Queue index [0] is the "head" of the queue

  • Numbers indicate which floor the person wants go to

  • capacity maximum number of people allowed in the lift

  • Parameter validation - All input parameters can be assumed OK. No need to check for things like:

    • People wanting to go to floors that do not exist
    • People wanting to take the Lift to the floor they are already on
    • Buildings with < 2 floors
    • Basements

Output

A list of all floors that the Lift stopped at (in the order visited!)

I solved this with C++. Here is the code with basic tests:

#include <algorithm>
#include <cassert>
#include <vector>
#include <optional>
#include <set>

enum class Direction{
  up,
  down
};

using Queues = std::vector<std::vector<int>>;

bool queuesEmpty(Queues& queues)
{
  for(const auto& queue : queues) {
    if(!queue.empty()) {
      return false;
    }
  }
  return true;
}

void movePeopleIntoLift(std::multiset<int>& passengers, 
  std::vector<int>& peopleOnFloor, std::vector<int>& newPassengers) 
{
  for(const auto& newPassenger : newPassengers) {
    peopleOnFloor.erase(std::find(peopleOnFloor.begin(), peopleOnFloor.end(), 
      newPassenger));
  }

  for(const auto& newPassenger : newPassengers) {
    passengers.insert(newPassenger);
  }
}

std::optional<int> highestFloorAboveLiftPushedDown(int liftPos, 
  const Queues& queues) 
{
  for(std::size_t i = queues.size() -1; i != static_cast<std::size_t>(liftPos); 
    --i) {
    for(const auto& person : queues[i]) {
      if(person < i) { // person wants to go down
        return {i};
      }
    }
  }
  return {};
}

std::optional<int> nextFloorAboveLiftPushedUp(
  int liftPos, const Queues& queues)
{
  if(std::size_t(liftPos) >= queues.size() - 2) {
    return {};
  }
  for(std::size_t i = liftPos + 1; i < queues.size(); ++i) {
    for(const auto& person : queues[i]) {
      if(person > i) {
        return {i};
      }
    }
  }
  return {};
}

std::optional<int> nextFloorUnderLiftPushedDown(
  int liftPos, const Queues& queues)
{
  if(liftPos <= 1) {
    return {};
  }
  for(std::size_t i = liftPos - 1; i!= std::size_t(0) - 1; --i) {
    for(const auto& person : queues[i]) {
      if(person < i) {
        return {i};
      }
    }
  }
  return {};
}


std::optional<int> lowestFloorUnderLiftPushedUp(int liftPos, 
  const Queues& queues) 
{
  for(std::size_t  i = 0; i < static_cast<std::size_t>(liftPos); 
    ++i) {
    for(const auto& person : queues[i]) {
      if(person > i) { // person wants to go up
        return {i};
      }
    }
  }
  return {};
}

std::optional<int> passengerDestinationLowerThanLiftPos(int liftPos, 
  const std::multiset<int>& passengers) {
  auto it = std::find_if(passengers.crbegin(), passengers.crend(), 
    [curr = liftPos](int passenger){
    return passenger < curr;
  });
  if(it != passengers.crend()) {
    return {*it};
  }
  return {};
}

std::optional<int> passengerDestinationHigherThanLiftPos(int liftPos, 
  const std::multiset<int>& passengers) {
  auto it = std::find_if(passengers.cbegin(), passengers.cend(), 
    [curr = liftPos](int passenger){
    return passenger > curr;
  });
  if(it != passengers.cend()) {
    return {*it};
  }
  return {};
}

class Lift{
public:
  Lift(const Queues& queues, int capacity);

  void emptyQueues();

  std::vector<int> visitedFloors() const;
private:
  void releasePassengersWithCurrentFloorDestination();

  void goUp();

  void addPeopleWhoWantToGoUp(std::vector<int>& peopleOnFloor);

  bool goUpWithoutPassengers();

  bool goUpToNextFloorPushedUp();
  bool goUpToHighestFloorPushedDown();

  void goUpWithPassengers();

  int getNextFloorUpWithPerson() const;

  void goDown();

  void addPeopleWhoWantToGoDown(std::vector<int>& peopleOnFloor);

  bool goDownWithoutPassengers();

  bool goDownToNextFloorPushedDown();
  bool goDownToLowestFloorPushedUp();


  void goDownWithPassengers();

  int getNextFloorDownWithPerson() const;

  void arriveToFloor(int floor);

  int currentFloor() const;

  void changeDirection();
  Direction direction() const;

  std::multiset<int> mPassangers{};
  std::vector<int> mVisitedFloors{};
  Direction mDirection = Direction::up;
  int mCurrentFloor = 0;
  int mCapacity;
  
  Queues mQueues;
};

Lift::Lift(const Queues& queues, int capacity)
  :mQueues{queues}, mCapacity{capacity}
{
}

void Lift::emptyQueues()
{ 
  arriveToFloor(0);
  bool goToStartPosition = false;
  for(;;) {
    while(mDirection == Direction::up) {
      goUp();
    }
    while(mDirection == Direction::down) {
      goDown();

      if(queuesEmpty(mQueues) && mPassangers.empty()) {
        goToStartPosition = true;
        break;
      }
    }
    if(goToStartPosition) {
      break;
    }
  }
  if(mCurrentFloor != 0) {
    arriveToFloor(0);
  }
}

std::vector<int> Lift::visitedFloors() const
{
  return mVisitedFloors;
}

void Lift::releasePassengersWithCurrentFloorDestination()
{
  mPassangers.erase(mCurrentFloor);
}

void Lift::goUp()
{
  releasePassengersWithCurrentFloorDestination();
  addPeopleWhoWantToGoUp(mQueues[mCurrentFloor]);
  if(mPassangers.empty()) {
    if(goUpToNextFloorPushedUp()) {
      return;
    }
    if(goUpToHighestFloorPushedDown()) {
      changeDirection();
      addPeopleWhoWantToGoDown(mQueues[mCurrentFloor]);
      return;
    }
    changeDirection();
  }
  else {
    goUpWithPassengers();
  }
}

void Lift::addPeopleWhoWantToGoUp(std::vector<int>& peopleOnFloor)
{
  std::vector<int> newPassengers;

  for(const auto& person : peopleOnFloor) {
    if(newPassengers.size() + mPassangers.size() >= mCapacity) {
      break;
    }
    if(person > mCurrentFloor) {
      newPassengers.push_back(person);
    }
  }

  movePeopleIntoLift(mPassangers, peopleOnFloor, newPassengers);
}

bool Lift::goUpToNextFloorPushedUp()
{
  auto optNextFloorUp = nextFloorAboveLiftPushedUp(
    mCurrentFloor, mQueues);
  if(optNextFloorUp) {
    arriveToFloor(*optNextFloorUp);
    return true;
  }
  return false;
}

bool Lift::goUpToHighestFloorPushedDown()
{
  auto optHighestFloorDown = highestFloorAboveLiftPushedDown(
    mCurrentFloor, mQueues);
  if(optHighestFloorDown) {
    arriveToFloor(*optHighestFloorDown);
    return true;
  }
  return false;
}

void Lift::goUpWithPassengers()
{
  auto higherFloor = getNextFloorUpWithPerson();
  arriveToFloor(higherFloor);
}

int Lift::getNextFloorUpWithPerson() const
{
  auto itPosPassengerUp = std::find_if(mPassangers.cbegin(), mPassangers.cend(), 
    [curr = mCurrentFloor](const auto& val)
    {
      return val > curr;
    }
  );

  // there should be always a person who wants to get higher
  assert(itPosPassengerUp != mPassangers.cend());
  
  auto optPosUp = nextFloorAboveLiftPushedUp(
    mCurrentFloor, mQueues);
  if(optPosUp && *optPosUp < *itPosPassengerUp) {
    return *optPosUp;
  }
  return *itPosPassengerUp;
}

void Lift::goDown()
{
  releasePassengersWithCurrentFloorDestination();
  addPeopleWhoWantToGoDown(mQueues[mCurrentFloor]);
  if(mPassangers.empty()) {
    if(goDownToNextFloorPushedDown()) {
      return;
    }
    if(goDownToLowestFloorPushedUp()) {
      changeDirection();
      addPeopleWhoWantToGoUp(mQueues[mCurrentFloor]);
      return;
    }
    if(!queuesEmpty(mQueues)) {
      changeDirection();
    }
  }
  else {
    goDownWithPassengers();
  }
}

void Lift::addPeopleWhoWantToGoDown(std::vector<int>& peopleOnFloor)
{
  std::vector<int> newPassengers;

  for(const auto& person : peopleOnFloor) {
    if(newPassengers.size() + mPassangers.size() >= mCapacity) {
      break;
    }
    if(person < mCurrentFloor) {
      newPassengers.push_back(person);
    }
  }

  movePeopleIntoLift(mPassangers, peopleOnFloor, newPassengers);
}

bool Lift::goDownToNextFloorPushedDown()
{
  auto optNextFloorDown = nextFloorUnderLiftPushedDown(
    mCurrentFloor, mQueues);
  if(optNextFloorDown) {
    arriveToFloor(*optNextFloorDown);
    return true;
  }
  return false;
}

bool Lift::goDownToLowestFloorPushedUp()
{
  auto optLowestFloorUp = lowestFloorUnderLiftPushedUp(
    mCurrentFloor, mQueues);
  if(optLowestFloorUp) {
    arriveToFloor(*optLowestFloorUp);
    return true;
  }
  return false;
}

void Lift::goDownWithPassengers()
{
  auto lowerFloor = getNextFloorDownWithPerson();
  arriveToFloor(lowerFloor);
}

int Lift::getNextFloorDownWithPerson() const
{
  auto itPosPassengerDown = std::find_if(mPassangers.crbegin(), mPassangers.crend(), 
    [curr = mCurrentFloor](const auto& val)
    {
      return val < curr;
    }
  );
  // there should be always a person who wants to get down
  assert(itPosPassengerDown != mPassangers.crend());

  auto optPosDown = nextFloorUnderLiftPushedDown(
    mCurrentFloor, mQueues);
  if(optPosDown && *optPosDown > *itPosPassengerDown) {
    return *optPosDown;
  }
  return *itPosPassengerDown;
}

void Lift::arriveToFloor(int floor)
{
  mCurrentFloor = floor;
  mVisitedFloors.push_back(mCurrentFloor);
}

int Lift::currentFloor() const
{
  return mCurrentFloor;
}

void Lift::changeDirection()
{
  if(mDirection == Direction::up) {
    mDirection = Direction::down;
  }
  else {
    mDirection = Direction::up;
  }
}

Direction Lift::direction() const
{
  return mDirection;
}

std::vector<int> the_lift(std::vector<std::vector<int>> queues, int capacity) 
{
  Lift lift(queues, capacity);
  lift.emptyQueues();
  return lift.visitedFloors();
}

int main()
{
    std::vector<std::vector<int>> queues; std::vector<int> result;

    // lift exactly full
    queues = { {}, {}, {5,5,5,5,5}, {}, {}, {}, {} };
    result = {0, 2, 5, 0};
    assert(the_lift(queues, 5) == result);

    // up
    queues = { {}, {}, {5,5,5}, {}, {}, {}, {} };
    result = {0, 2, 5, 0};
    assert(the_lift(queues, 5) == result);
    
    // down
    queues = { {}, {}, {1,1}, {}, {}, {}, {} };
    result = {0, 2, 1, 0};
    assert(the_lift(queues, 5) == result);
    
    // up and up
    queues = { {}, {3}, {4}, {}, {5}, {}, {} };
    result = {0, 1, 2, 3, 4, 5, 0};
    assert(the_lift(queues, 5) == result);
    
    // down and down
    queues = { {}, {0}, {}, {}, {2}, {3}, {} };
    result = {0, 5, 4, 3, 2, 1, 0};
    assert(the_lift(queues, 5) == result);

    // yoyo
    queues = { {}, {}, {4,4,4,4}, {}, {2, 2, 2, 2}, {}, {} };
    result = {0, 2, 4, 2, 4, 2, 0};
    assert(the_lift(queues, 2) == result);

    // lift full up
    queues = { {3, 3, 3, 3, 3, 3}, {}, {}, {}, {}, {}, {} };
    result = {0, 3, 0, 3, 0};
    assert(the_lift(queues, 5) == result);

    // lift full down
    queues = { {}, {}, {}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {}, {}, {} };
    result = {0, 3, 1, 3, 1, 3, 1, 0};
    assert(the_lift(queues, 5) == result);

    // lift full up and down
    queues = { {3, 3, 3, 3, 3, 3}, {}, {}, {}, {}, {4, 4, 4, 4, 4, 4 }, {} };
    result = {0, 3, 5, 4, 0, 3, 5, 4, 0};
    assert(the_lift(queues, 5) == result);

    // Tricky_queues
    queues = { {}, {0, 0, 0, 6}, {}, {}, {}, {6, 6, 0, 0, 0, 6}, {} };
    result = {0, 1, 5, 6, 5, 1, 0, 1, 0};
    assert(the_lift(queues, 5) == result);

    // Highlander
    queues = { {}, {2}, {3, 3, 3}, {1}, {}, {}, {} };
    result = {0, 1, 2, 3, 1, 2, 3, 2, 3, 0};
    assert(the_lift(queues, 1) == result);

    // Fire drill
    queues = { {}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0} };
    result = {0, 6, 5, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 4, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0};
    assert(the_lift(queues, 5) == result);   

}

As a note. Codewars only allows one file per solution. That's why I have not separated the class in files.

What do you think can be improved?

Is the code easy to read?

Could I have used more algorithms from the standard library?

I feel like I needed a lot of code to get this working.

My approach was like this:

First solve the problem without the required capacity.

Just for that I rewrote the whole thing like 2 or 3 times because I was missing some requirements.

That let me pass the first few tests.

I would also like some hints how its best to tackle a complex problem like this better.

Then I added the capacity and went through the remaining tests. It was like maybe 2 hours of coding and 5h debugging and fixing to pass the tests.

\$\endgroup\$
4
\$\begingroup\$

Nice code. Your function names are very clear, and it's great to see the unit tests included with the code.

Some tests I'm surprised not to see:

  • see the trivial test, with no passengers waiting. That's the first test I would have written. Writing this test first helps get a good testable interface that can then be used to write the next-simplest test get that passing.
  • tests of capacity other than 5. Do we know that other capacities work? In particular, are passengers carried in the correct order of queueing?
  • tests with up passengers waiting behind down passengers, and vice versa.

Here's a couple of extra tests:

// nothing to do
queues = { {} };
result = {0};
assert(the_lift(queues, 1) == result);

// lift full up and down, but don't block passengers
queues = { {}, {3,3,3,0,0,0,0,0,3}, {}, {1,1,1}, };
result = {0, 1, 3, 1, 0, 1, 3, 1, 0, 1, 0};
assert(the_lift(queues, 2) == result);

And some that expose fragility in the code:

// no floors (seg fault)
queues = { };
result = {0};
assert(the_lift(queues, 1) == result);

// no capacity (infinite loop)
queues = { {1}, {} };
result = {0};
assert(the_lift(queues, 0) == result);

// passenger not changing floor (infinite loop)
queues = { {0} };
result = {0};
assert(the_lift(queues, 1) == result);

One thing I would change about the tests is that they currently abort (using assert()) at the first failure. When writing or refactoring code, it's likely to cause multiple tests to fail, and that's useful information to identify the cause. I'd like to see all failures reported to std::cerr and the return value indicate whether all tests succeeded. That's what the usual test frameworks manage, and it's not hard to do.


I get a few compiler warnings that could easily be fixed:

g++ -std=c++2a -fconcepts -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds  -Weffc++       254000.cpp    -o 254000
254000.cpp: In function ‘std::optional<int> highestFloorAboveLiftPushedDown(int, const Queues&)’:
254000.cpp:43:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
       if(person < i) { // person wants to go down
          ~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> nextFloorAboveLiftPushedUp(int, const Queues&)’:
254000.cpp:59:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
       if(person > i) {
          ~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> nextFloorUnderLiftPushedDown(int, const Queues&)’:
254000.cpp:75:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
       if(person < i) {
          ~~~~~~~^~~
254000.cpp: In function ‘std::optional<int> lowestFloorUnderLiftPushedUp(int, const Queues&)’:
254000.cpp:90:17: warning: comparison of integer expressions of different signedness: ‘const int’ and ‘std::size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
       if(person > i) { // person wants to go up
          ~~~~~~~^~~
254000.cpp: In constructor ‘Lift::Lift(const Queues&, int)’:
254000.cpp:172:10: warning: ‘Lift::mQueues’ will be initialized after [-Wreorder]
   Queues mQueues;
          ^~~~~~~
254000.cpp:170:7: warning:   ‘int Lift::mCapacity’ [-Wreorder]
   int mCapacity;
       ^~~~~~~~~
254000.cpp:175:1: warning:   when initialized here [-Wreorder]
 Lift::Lift(const Queues& queues, int capacity)
 ^~~~
254000.cpp: In member function ‘void Lift::addPeopleWhoWantToGoUp(std::vector<int>&)’:
254000.cpp:240:50: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
     if(newPassengers.size() + mPassangers.size() >= mCapacity) {
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
254000.cpp: In member function ‘void Lift::addPeopleWhoWantToGoDown(std::vector<int>&)’:
254000.cpp:326:50: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
     if(newPassengers.size() + mPassangers.size() >= mCapacity) {
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

I think we should use an unsigned type for the floor number throughout (probably std::size_t; it might be worth writing a type alias, using Floor = std::size_t;).


There's quite a bit of duplication between "up" and "down" functions that could be reduced. For example,

int Lift::getNextFloorUpWithPerson() const
{
  auto itPosPassengerUp = std::find_if(mPassangers.cbegin(), mPassangers.cend(), 
    [curr = mCurrentFloor](const auto& val)
    {
      return val > curr;
    }
  );

  // there should be always a person who wants to get higher
  assert(itPosPassengerUp != mPassangers.cend());
  
  auto optPosUp = nextFloorAboveLiftPushedUp(
    mCurrentFloor, mQueues);
  if(optPosUp && *optPosUp < *itPosPassengerUp) {
    return *optPosUp;
  }
  return *itPosPassengerUp;
}

int Lift::getNextFloorDownWithPerson() const
{
  auto itPosPassengerDown = std::find_if(mPassangers.crbegin(), mPassangers.crend(), 
    [curr = mCurrentFloor](const auto& val)
    {
      return val < curr;
    }
  );
  // there should be always a person who wants to get down
  assert(itPosPassengerDown != mPassangers.crend());

  auto optPosDown = nextFloorUnderLiftPushedDown(
    mCurrentFloor, mQueues);
  if(optPosDown && *optPosDown > *itPosPassengerDown) {
    return *optPosDown;
  }
  return *itPosPassengerDown;
}

These could be combined with a small helper function, especially if we change Direction to be integer-based and define up as 1 and down as -1:

enum Direction{
  up = 1,
  down = -1,
};

template<typename Iter>
int Lift::getNextFloorWithPerson(Iter first, Iter last) const
{
    auto const next_passenger_iter =
        std::find_if(first, last,
                     [this](const auto& val) { return val * mDirection > mCurrentFloor * mDirection; });

    // there should be always a person who wants to get higher
    assert(next_passenger_iter != last);

    for (int i = mCurrentFloor + mDirection;  i != *next_passenger_iter;  i += mDirection) {
        // is there a person waiting between, going our direction?
        if (std::any_of(mQueues[i].cbegin(), mQueues[i].cend(),
                       [i,this](auto const& person){ return person * mDirection > i * mDirection; })) {
            return i;
        }
    }
    return *next_passenger_iter;
}

And we can inline the uses in the one place each they are called:

void Lift::goUpWithPassengers()
{
  auto higherFloor = getNextFloorWithPerson(mPassangers.cbegin(), mPassangers.cend());
  arriveToFloor(higherFloor);
}

void Lift::goDownWithPassengers()
{
  auto lowerFloor = getNextFloorWithPerson(mPassangers.crbegin(), mPassangers.crend());
  arriveToFloor(lowerFloor);
}

There might be value in splitting the queues at each floor into two: one for upward passengers, and one for downward passengers.


Trivial: spelling mPassangersmPassengers.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the feedback. I agree its quite basic to use only asserts as tests. In a real project I would use something like gtest framework for the test. \$\endgroup\$ – Sandro4912 Dec 29 '20 at 14:31
  • \$\begingroup\$ some test like the no Floor test I did not bother because the description above in I/O explicitly states that the building will be never < 2 floors. \$\endgroup\$ – Sandro4912 Dec 29 '20 at 14:33
  • \$\begingroup\$ Sure, we could skip testing the invalid input cases. But I often understand my code better if I check for such cases and deal with them explicitly. It's a personal preference, and I wouldn't reject the code on that basis. TBH, I misread that, but I've edited the question to make the formatting clearer. \$\endgroup\$ – Toby Speight Dec 29 '20 at 14:38
3
\$\begingroup\$

Standard Algorithms

You can make more use of standard algorithms. For one example consider your queuesEmpty:

bool queuesEmpty(Queues& queues)
{
  for(const auto& queue : queues) {
    if(!queue.empty()) {
      return false;
    }
  }
  return true;
}

Given a choice, I'd probably write this more like:

bool queuesEmpty(Queues& queues) {
    return std::all_of(queues.begin(), queues.end(), [](auto const &q) { return q.empty(); });
}

[I'll probably add more later.]

\$\endgroup\$
1
\$\begingroup\$

To answer the question, "how to go about solving problems like this", here's a work-through of how I would approach it.

Start with the simplest test you can think of and ensure that it fails. For me, that's a single queue, which is empty. Most of the work here is in creating the test framework, to print the code location and failing values (which I wouldn't normally have to write, if using an existing test framework). The rest is in creating the interface to the class under test.

#include <algorithm>
#include <cstdlib>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <source_location>
#include <vector>

using Floor = std::size_t;
    
// return zero on success, or non-zero on failure
static int test_lift(std::size_t capacity,
                     const std::vector<std::vector<Floor>>& queues,
                     const std::vector<Floor>& expect_visited,
                     const std::source_location& location = std::source_location::current())
{
    Lift lift(capacity, queues);
    lift.emptyQueues();
    const auto actual_visited = lift.visitedFloors();
    if (actual_visited == expect_visited) {
        return 0; // success
    }
    std::cerr << location.file_name() << ':' << location.line() << ": FAIL: expected {";
    std::copy(expect_visited.begin(), expect_visited.end(),
                  std::ostream_iterator<Floor>{std::cerr,","});
    std::cerr << "} but got {";
    std::copy(actual_visited.begin(), actual_visited.end(),
                  std::ostream_iterator<Floor>{std::cerr,","});
    std::cerr << "}\n";
    return 1;
}


int main()
{
    int failures = 0;

    failures += test_lift(1, {{}}, {0});

    if (!failures) {
        return EXIT_SUCCESS;
    }
    std::cerr << failures << " failures reported.\n";
    return EXIT_FAILURE;
}

Now write the minimal Lift class that enables the test to compile:

class Lift
{
public:
    Lift(std::size_t capacity,
         const std::vector<std::vector<Floor>> queues)
    {}

    void emptyQueues()
    {}

    std::vector<Floor> visitedFloors() const
    {
        return {};
    }
};

The test will fail (important - otherwise how do we know the test itself works?), and we can change visitedFloors() to make it pass:

    std::vector<Floor> visitedFloors() const
    {
        return {0};
    }

Now it's time to add our next failing test:

failures += test_lift(1, {{}}, {0});
failures += test_lift(1, {{1}, {}}, {0,1,0});

We need to do more work to make this one pass:

#include <utility>

class Lift
{
    const std::size_t capacity;
    std::vector<std::vector<Floor>> queues;
    std::vector<Floor> visited= { 0 };
    Floor current = 0;

public:
    Lift(std::size_t capacity,
         const std::vector<std::vector<Floor>> queues)
        : capacity{capacity},
          queues{std::move(queues)}
    {}

    void emptyQueues()
    {
        // go up and down once
        while (current < queues.size() - 1) {
            ++current;
            visited.push_back(current);
        }
        while (current > 0) {
            --current;
            visited.push_back(current);
        }
    }

    const std::vector<Floor>& visitedFloors() const
    {
        return visited;
    }
};

Although we have made this test pass, we know it's not correct. We're stopping on every floor, not just the requested ones. Let's add a test that we don't stop everywhere:

failures += test_lift(1, {{2}, {}, {}}, {0,2,0});

And make it pass, then fix the tests we broke:

#include <set>


class Lift
{
    // ...
    std::multiset<Floor> passengers = {};

    // ...
    void emptyQueues()
    {
        // get ground-floor passengers
        passengers.insert(queues[0].begin(), queues[0].end());
        while (!passengers.empty()) {
            // go up and down once
            while (current < queues.size() - 1) {
                ++current;
                if (passengers.count(current) > 0) {
                    visited.push_back(current);
                    passengers.erase(current);
                }
            }
            while (current > 0) {
                --current;
                if (passengers.count(current) > 0) {
                    visited.push_back(current);
                }
            }
        }
        // return to ground floor
        if (visited.back() != 0) {
            visited.push_back(0);
        }
    }

Now, let's add tests that exceed the lift capacity:

failures += test_lift(1, {{1,1}, {}}, {0,1,0,1,0});
failures += test_lift(1, {{1,2}, {}, {}}, {0,1,0,2,0});
failures += test_lift(1, {{2,1}, {}, {}}, {0,2,0,1,0});

The last two of these ensure that we pick up passengers in the correct order.

I'm going to add a private function to transfer passengers from the queue to the lift, as we'll need this in a few places:

void add_passengers(std::vector<Floor>& queue)
{
    auto const add_one =
        [this](Floor requested) {
            if (passengers.size() >= capacity) {
                return false;
            }
            passengers.insert(requested);
            return true;
        };
    queue.erase(std::remove_if(queue.begin(), queue.end(), add_one), queue.end());
}

And use it in emptyQueues:

void emptyQueues()
{
    // get ground-floor passengers
    add_passengers(queues[0]);
    while (!passengers.empty()) {
        // go up and down once
        while (current < queues.size() - 1) {
            ++current;
            if (passengers.count(current) > 0 || !queues[current].empty()) {
                visited.push_back(current);
                passengers.erase(current);
                add_passengers(queues[current]);
            }
        }
        while (current > 0) {
            --current;
            if (passengers.count(current) > 0 || !queues[current].empty()) {
                visited.push_back(current);
                passengers.erase(current);
                add_passengers(queues[current]);
            }
        }
    }
    // return to ground floor
    if (visited.back() != 0) {
        visited.push_back(0);
    }
}

Now we're picking up passengers at all floors, but we need to be selective about their direction of travel. Again, write some tests:

failures += test_lift(1, {{}, {0,2}, {}}, {0,1,2,1,0});

This one failed right away because we're still only moving if we have passengers. So change the condition to also move if there are any queues waiting:

    while (!passengers.empty() || any_waiting()) {

And implement the function:

private:
    bool any_waiting() const
    {
        return std::any_of(queues.begin(), queues.end(),
                           [](auto& q){ return !q.empty() });
    }

I think I've shown enough now how to solve smaller problems and build up to the full solution a test at a time.


After implementing the rest of the code, and a couple of rounds of refactoring, I ended up with:

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <set>
#include <vector>

using Floor = std::size_t;

class Lift
{
    const std::size_t capacity;
    std::vector<std::vector<Floor>> up_queue = {};
    std::vector<std::vector<Floor>> down_queue = {};
    std::vector<Floor> visited= { 0 };
    std::multiset<Floor> passengers = {};

    bool any_waiting() const
    {
        return std::any_of(up_queue.begin(), up_queue.end(),
                           [](auto& q){ return !q.empty(); })
            || std::any_of(down_queue.begin(), down_queue.end(),
                           [](auto& q){ return !q.empty(); });
    }

    void visit_floor(Floor floor, std::vector<Floor>& queue)
    {
        // if there's waiting passengers, we have to stop, even if no-one can get on
        bool have_visited = passengers.erase(floor) > 0 || !queue.empty();
        if (have_visited && visited.back() != floor) {
            // yes, we stopped here
            visited.push_back(floor);
        }
        // now move passengers from queue
        auto const add_one =
            [this](Floor requested) {
                if (passengers.size() >= capacity) { return false; }
                passengers.insert(requested);
                return true;
            };
        queue.erase(std::remove_if(queue.begin(), queue.end(), add_one), queue.end());
    }

public:
    Lift(std::size_t capacity,
         const std::vector<std::vector<Floor>> queues)
        : capacity{capacity}
    {
        // split the input into up traffic and down traffic
        auto floors = queues.size();
        up_queue.resize(floors);
        down_queue.resize(floors);
        for (std::size_t actual = 0;  actual < floors;  ++actual) {
            std::vector<Floor>& up = up_queue[actual];
            std::vector<Floor>& down = down_queue[actual];
            for (auto wanted: queues[actual]) {
                if (wanted < actual) {
                    down.push_back(wanted);
                } else if (actual < wanted && wanted < floors) {
                    up.push_back(wanted);
                }
            }
        }
    }

    void emptyQueues()
    {
        Floor current = 0;
        while (!passengers.empty() || any_waiting()) {
            // go up and down once
            while (current < up_queue.size() - 1) {
                visit_floor(current, up_queue[current]);
                ++current;
            }
            while (current > 0) {
                visit_floor(current, down_queue[current]);
                --current;
            }
        }
        // return to ground floor
        if (visited.back() != 0) {
            visited.push_back(0);
        }
    }

    const std::vector<Floor>& visitedFloors() const
    {
        return visited;
    }
};

And the tests (slightly modified, to compile with C++17)

#include <cstdlib>
#include <iostream>

// return zero on success, or non-zero on failure
static int test_lift(std::size_t capacity,
                     const std::vector<std::vector<Floor>>& queues,
                     const std::vector<Floor>& expect_visited)
{
    Lift lift(capacity, queues);
    lift.emptyQueues();
    const auto actual_visited = lift.visitedFloors();
    if (actual_visited == expect_visited) {
        return 0; // success
    }
    std::cerr << "FAIL: expected {";
    std::copy(expect_visited.begin(), expect_visited.end(),
                  std::ostream_iterator<Floor>{std::cerr,","});
    std::cerr << "} but got {";
    std::copy(actual_visited.begin(), actual_visited.end(),
                  std::ostream_iterator<Floor>{std::cerr,","});
    std::cerr << "}\n";
    return 1;
}


int main()
{
    int failures = 0;
    failures += test_lift(1, {{}}, {0});
    failures += test_lift(1, {{1}, {}}, {0,1,0});
    failures += failures += test_lift(1, {{2}, {}, {}}, {0,2,0});
    failures += test_lift(1, {{1}, {}, {}}, {0,1,0});
    failures += test_lift(1, {{}, {}, {1}}, {0,2,1,0});
    failures += test_lift(1, {{}, {}, {1, 1}}, {0,2,1,2,1,0});
    failures += test_lift(1, {{1,1}, {}}, {0,1,0,1,0});
    failures += test_lift(1, {{}, {0,0}}, {0,1,0,1,0});
    failures += test_lift(1, {{1,2}, {}, {}}, {0,1,0,2,0});
    failures += test_lift(1, {{2,1}, {}, {}}, {0,2,0,1,0});
    failures += test_lift(1, {{}, {0,2}, {}}, {0,1,2,1,0});
    // lift full up and down
    failures += test_lift(2, {{3,3,3}, {}, {}, {}, {}, {4,4,4}, {}},
              {0,3,5,4,0,3,5,4,0});
    // Highlander
    failures += test_lift(1, {{}, {2}, {3,3,3}, {1}, {}, {}, {}},
              {0,1,2,3,1,2,3,2,3,0});
    // queuing order
    failures += test_lift(2, {{}, {}, {4,1,4,3,1}, {}, {}},
              {0,2,4,2,1,2,3,0});
    // Fire drill
    failures += test_lift(5, {{}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0}},
               {0,6,5,4,3,2,1,0,5,4,3,2,1,0,4,3,2,1,0,3,2,1,0,1,0});

    if (!failures) {
        return EXIT_SUCCESS;
    }
    std::cerr << failures << " failures reported.\n";
    return EXIT_FAILURE;
}

Notes on this implementation:

  • The most obvious thing is splitting the queues into "up" and "down" queues. I didn't do that straight away, but it soon made sense to filter the directions when we construct the Lift object.
  • Instead of searching for the next floor to visit, we look at every floor on the way, and decide when we reach it whether or not to record a visit.
  • I've tested for some of the invalid input cases that the challenge told us not to bother with. Although deemed unnecessary, some of these (asking for a non-existent floor, or for the passenger's current floor) were so easy to add in whilst splitting the queues, it seemed better to just clean the data as we went.
  • There's still more that can be improved. For example, we consider every waiting passenger when we stop, even if we already know there's no more room. Perhaps when we split the queues, we could use std::queue for storage rather than std::vector, and replace the erase-remove with a simple pop() loop that finishes when no more passengers can be moved (because either the car is full or the queue is empty).
  • We might refactor if (visited.back() != floor) { visited.push_back(floor); } into a small record_visit() function.

Notes on the process:

  • I've described how I would solve this, using a Test-Driven Development (TDD) approach. This is well suited to any problem which can be specified in terms of inputs and outputs.
  • The mantra of TDD is "Red - Green - REFACTOR" and it's that refactor step (also called "reduce complexity" or "remove duplications") that helps you get your code small and simple. It's worth spending more time on refactoring as you go; don't wait until you have all your tests in place, but do a little refactoring every iteration.
  • The design is emergent, rather than planned. We don't start off knowing what structures we'll need to support the functionality until we get there. That helps keep the code simple, as we don't implement anything that we think we'll need later - just the things we actually do need.
  • When we refactor, we only need to worry about keeping the existing tests passing, and not any future ones we haven't written yet. So we can make large changes to the interface early on, but that becomes more difficult once we've written a large body of tests. It makes sense to write tests that help define the interface at the beginning, and later to concentrate on those that nail down the implementation. That's why I like to start with tests of invalid inputs, where appropriate, rather than leaving the error reporting until last (I know this particular problem doesn't have any error reporting, but the princple still stands).
  • It's not unusual to throw away the initial structure - that's what happens as you gain more insight into the problem space. So don't be dispirited when you do so - the work isn't wasted, despite how it looks (from outside of your head).
  • We can make the steps larger, writing several tests at a time when we're confident we can make them pass in one go. But when the code gets difficult, we can always fall back to testing the smallest possible increment in each step, and that helps us to make perceptible progress even when we're struggling.
  • On longer-term projects, I find it helpful to end the day with a failing test. That sounds counter-intuitive if you're used to tidying up when you finish, but the advantage is that you then start the next session with a clear place to start working; I find that helps me get back into the rhythm, without having to think what to implement next. Even on a one-afternoon program, it's a good state to leave things when you stop for a tea break!
\$\endgroup\$
4
  • \$\begingroup\$ I kinda did it like that. I just started on an more complicated test and build up with that. I had like the first 3 test pass and realized then on the 4 test that my design was crap and reworked it because i could not pass the next test like it was. I also had a up and down queue before but I couldn't get it to work and throw it away. +Points for source_location I didn't knew about that. \$\endgroup\$ – Sandro4912 Dec 29 '20 at 15:33
  • \$\begingroup\$ The XP mantra is "Red - Green - REFACTOR" and it's that refactor step (also called "reduce complexity" or "remove duplications") that helps you get your code small and simple. Perhaps spend more time on refactoring as you go; don't wait until you have all your tests in place, but do a little refactoring every iteration. With test-driven development like this, it's not unusual to throw away the initial structure - that's how you gain the most insight into the problem space. So don't be dispirited when you do so - the work isn't wasted, despite how it looks (from outside of your head). \$\endgroup\$ – Toby Speight Dec 29 '20 at 18:48
  • 1
    \$\begingroup\$ This review is a good synopsis of TDD \$\endgroup\$ – Edward Dec 29 '20 at 22:00
  • \$\begingroup\$ Thanks @Edward; that's exactly what I wanted to convey. I've incorporated that link (and my long comment about TDD refactoring) into the answer now. \$\endgroup\$ – Toby Speight Dec 30 '20 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.