Sharpen your Coding Skills - Elevator Puzzle |

Written by Joe Celko | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Page 2 of 2
## ANSWER
Knuth, Donald, You can also look up Karp's algorithm. The key to the algorithm is not to treat the people already in the elevator as any different to the people waiting for the lift. The algorithm works with an up and a down mode of operation. You also need to keep track of the number of people wanting to move higher than a given floor and those wanting to move lower. This is a complicated piece of book-keeping but it is what makes the algorithm work, so we can't avoid it. On each floor k you need to count u So if there is one person on each floor wanting to go to the floors as indicated, then uk for floor 3 is 1 because on floor 3 and below there is only one person wanting to go higher than floor 3. For floor 2 u
You can see the other values for u
## UpThe basic idea is to start in the lobby and fill the car with passengers with the highest possible destination floor - as the car is finite some might not get on. Move up one floor i.e. k=k+1. Drop off all the passengers off the next floor up to create a combined pool of passengers waiting for the elevator. Adjust the values of u As long as u Allow passengers with the highest possible destination floor to get onto the elevator and move to floor k+1 Yes some passengers have had to get out a the wrong floor - but as Knuth says "
## DownIf there are no passengers on the floor or below wanting to go higher then we switch to the down-moving mode. Treating all of the passengers on the floor and in the lift as a single pool, let on the passengers who want to go to the lowest floors. Move down to floor k-1 and adjust or recompute the values of u As long as u If u Repeat until everyone is where they want to be. You should be able to see that this algorithm corresponds to picking at each floor the passengers who want to travel the maximum distance in the current direction - irrespective of whether they are already on the lift or not. The really clever bit is working out when to change direction of travel based on the total number of people who want to move up at or below the floor. This is is Karp's algorithm and it is proved to be the way to get everyone to the right floor in the minimum total time.
The simplest case to illustrate the algorithm is if there is one person per floor and the elevator car only holds one person. Suppose we start with:
Where the numbers in the people waiting column shows which floor the people want to be on. The first up phase takes the person wanting to go to floor 3 and moves up to floor 2 - where they all get out to produce:
Notice that we have updated u As u Now the passenger that wants to go to the highest floor is floor 4. This means the passenger who got on at floor 1 is left behind on the wrong floor. This gives:
As u In this case the passenger riding to the fourth floor stays in the lift and makes it to their floor at the next step.
As u We now select passengers wanting to go to the lowest floors hence the passenger wanting to go to floor 1 gets in.
Notice that at this point we don't switch back to going up because u
At this point u
At this point u
A this point we have u One last move down delivers the final person to the correct floor.
And with this the job is done. Of course to see the algorithm really work you need to have more floors, more people and a bigger car. But the idea of getting everyone out at each floor and then picking the ones going the maximum distance in either the up or down direction is the key to the algorithm. *Joe Celko is best known as the database expert who writes books on SQL, data and databases. But before that, he was an honest developer obsessed with finding good algorithms and clean code.*
Programmer Puzzle - Hermit Boxes Jigsaw Puzzles and The MacMahon Squares Vertex Coverings And The Cool Kids Problem Merkles and Social Engineering If you want to send in solutions to any of them either use the Comments section or email editor@i-programmer.info. To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |