I think I read once that when elevators still had operators, larger buildings would have one or more dispatch agents in the lobby that would line people up at the appropriate elevator for the range of floors they intended to visit.
Taller buildings with complex and highly trafficked elevators still do this only using electronics. Employees swipe their badges at a podium which reads what floor they work on and indicates which elevator they should proceed to. The system can intelligently schedule the elevator for that person to use knowing where their destination is.
I'm in a building with a mere nine floors that has such a system (the only buttons in the elevators themselves are door open, door close and alarm). I imagine that the technology will increasingly appear in the smaller buildings as their elevators are built or refurbished.
Whenever I use those sorts of lifts I find it very unsettling - it's interesting, because floor buttons vs external destination buttons give me no more control over the lift, but as a user I become very anxious when my mechanism for "driving" the lift is taken away.
I used to work in a 50-story building that had banks of elevators, each of which was hard-coded to only visit the lobby and the appropriate range of floors. For example, the first bank would only visit 2-13, the 2nd bank would visit 14-25, etc. The elevator cars only had buttons inside for the floors they were allowed to visit. There were also a couple service/freight elevators that could visit all floors (including a couple of service/equipment floors that weren't reachable at all by the normal elevators), and had a human operator/guard who logged badge numbers, floors, and property-removal authorization forms.
I think this sort of elevator allocation is fairly common for tall buildings, because it's horribly inefficient for people going to the 44th floor to have to wait while people get on and off at all of the 42 floors in between!
In very tall buildings, to reach the highest floors you might have to take an express car to a higher lift lobby, where you change cars (because it's also inefficient for the 2-13 lift to have an empty shaft that's never used for 80 floors above 13).
This is awesome, I'm closing it now though as well.
This is how teaching should be...this exercise isn't at all about programming and more about how to think. This can be simplified into a drag and drop block language and given to grade school kids as a really good exercise.
Many programmers in the professional world today would really struggle with this because they never learned to actually think, they just "program" (copy paste, edit work already done by others). They don't actually create new things or find solutions themselves.
My kids played this first time around, they would have been grade 5 or 6 at the time and got through to level 7 before hacking the level selection and trying random levels to see which ones their approach worked with.
I spent way too much time with Robocode a few years back. Those advanced "surfing" bots some people built though... It was quite disheartening having not the slightest bit of a chance as a novice programmer.
It's the best one for doing challenges that use actual test cases. This challenge could easily be ported to that site (and I think there already are a few elevator ones)
I am also stuck at number ten. There is a link "Wiki and solutions" in which I guess we could find some useful theory. Still haven't taken a look at it.
1. Because maybe the author wanted to keep the property hidden and only expose a getter function and hide the setter?
2. Same reason. They are being set internally. A sane programmer would not give you the power to do that because its a product of internal calculations.
3. Naming of method/function and variables is the second hardest thing in programming :)
4. The callback of on.('floor_button_pressed') gives you an floorNumber argument which is more than sufficient. What event in real life would you describe with on('in-droor-button-press') ?
This is great! Many times I've thought it would be cool to develop a programming logic harness for elevator logic, but I've never come close to starting.
I think many developers have been waiting for an elevator thinking "Damn this thing is DUMB! I could do a way better job coding the logic for this..." Can finally test it out.
No, I never did really. Programming an elevator sounds very tedious, but it never sounded very hard. Elevators are heavy equipment, and there are edge cases around safety near heavy equipment: I'd rather not have to learn those first-hand.
However, I do think this is a great exercise for people new to programming. It's a common enough scenario that most people can recite 80% of the requirements of an elevator from memory.
This was was posed as the the first homework assignment in my first undergrad CS class (15 years ago). I don't think a single person managed to do it.
It's a classic example of a problem that you think is appropriate to throw at new programmers but find out it goes terribly wrong because the hard part is designing a suitable state machine first. If you just start coding without a full model that covers all the edge cases, it quickly degenerates to a mess of ad-hoc heuristics and spaghetti.
That actually seems like the perfect first programming problem (after some syntax), an appreciation of how seemingly simple problems can blow up in your face is a nice intro to a career in software anyway :).
Same exact thing, about 16 years ago for me. He presented it (I think) to see who procrastinated on the project, knowing it'd take way longer than it sounded.
Same as me, 16 years as well. Was this kind of assignment in vogue at the time, discussed between professors / grad students at academic conferences?
My assignment involved writing assembly on some virtual machine with a weird byte/word size and dozens of addressing modes, as well as a (virtual) tape device. I think it was called CUSP but I can't find any references for it now.
Or maybe a behaviour tree, which is how I would have (tried) to design it with.
I hope I get something like this on an interview, instead of "reverse binary tree" like questions. This actually seems like a fun problem to solve. Knowing my defect brain, it would put a lot of effort into this because it's kinda fun.
Also because I already have a ton of ideas on how to implement this - not that I already have.
Just off the top of my head.
A BT that tracks current floor, direction, some predicates for inputs e.g ignore input 2 if direction is up and current floor is 3.
That would satisfy the current test conditions. HOWEVER.. a better style would be to keep that in queue with an indicator (UI) that it's on the queue after current direction has hit its highest floor.
Could add another predicate that the elevator won't stop for 'caller' on third floor if it's filled (maxWeightReached) and everyone are going to bottom floor.
Eventually you could maximise the amount of people it moves based on space available and how many have called the elevator using their condo NFC tags.
Seriously, this what dev interviews should look like.
Not sure why I am being downvoted here.
A FSM would make things very hard to read compared to a BT.
The fact that you would have to use a stack to pop events shows that it might not be the best suited use.
There is nothing that dictates that you use a stack when designing a FSM. I'm not going to argue that a BT wouldn't be a good solution, I'm sure it can be used to make a reasonable one.
In any case, a well designed FSM would get you a long way. Since the input (pressed buttons) is finite, you can cover every single case and weight according to importance of floor and wait time.
I was actually promoting a stack as that would make things easier, but it's still tacked on a solution that isn't as good.
A well designed FSM doesn't necessarily mean an easily read FSM.
I always try to draw states and transitions on paper, and I end up making a mess. That could be a flaw on my side. But I won't be making the same mess with BT.
I don't see how a FSM could avoid having transitions back and forth.
* Elevator is on level 3
* A person in the elevator wants to go to level 4
* A person waiting for down on level 5
* A person in the elevator wants to go to level 2
* A person waiting for down on level 2
FSM would need to track current floor and direction.
Would need guards/predicates on transitions for inputs
Could just be me, but I wouldn't be able to draw a pretty picture with those.
It's a cool programming problem to work on over a few courses. For example at the start when learning basic programming you just code a functional elevator (ie. a user presses a button, the elevator goes there, picks them up and delivers them).
Then you get to add more people, queuing of commands etc (helping you discover some different algorithms and data structures).
Then you can throw in some advanced predictive code and machine learning, taking into consideration usage vs time, locations people most travel to/from etc.
This is both cool and disappointing. I'm sure this is more challenging than it looks, and it's cool to see emergent complexity from a (seemingly) simply set of conditions to satisfy.
However, the reason I think about elevator programming isn't to make an elevator behave the way they do today. It's to make an elevator behave better than they do today.
For example:
* I don't want an elevator to close and reopen its doors on the same floor. That's horrible user experience.
* All the interesting problems arise when there are multiple elevators servicing the same set of floors. So let's control more than one elevator at the same time.
* If the elevator is on the ground floor, and has downward calls on both the 1st and 20th floors, then it is likely more efficient to service the 1st floor first rather than bypassing them just so you can keep travelling in the same direction.
I'd like to see a version of this that, rather than enforcing arbitrary rules, just has a lot of series of inputs and lets people compete to service those inputs in the shortest number of steps.
However, the criterion you're optimizing for is still unclear. Should it be:
a) the total number of steps the elevator takes
b) the average number of steps each user has to wait
c) the maximum number of steps each user has to wait
d) the 90th percentile of user waiting steps
Note: here, I'm counting the steps spent waiting for an elevator as well as the steps spent in the elevator till the destination as the same, but presumably you'd want to count steps spent inside the elevator as costlier, further complicating matters.
And this not even considering what happens if your algorithm answers 20 calls, without going to any destination floors, when the elevator capacity is only 10 people.
That's what makes this such an interesting problem.
This can be accomplished in a gamified way:
Game harness simulates people comming to an elevator, pressing destination button and waiting for some time (some wait longer, some wait shorter, should also depend on distance) before giving up and taking stairs.
The elevator could or could not know about it's capacity.
Assigning "price", optionally differentiated by input/output floors, to passenger, result would be €/time or €/level. Level - predetermined sequence of passengers.
Interesting thing here is that "price" does not have to depend on distance. Taking passengers travelling short distances might look cost effective, but that could have negative effect on number of people going to a 20th floor.
I guess we are looking at a trade-off in every case. Is speed, waiting time, or moves(energy saving) your priority. When you order a set of six to eight elevators for a 70 story building you probably are allowed to set your preferences of how your elevators want to perform. This is why I could not get constant (100%) success rate with one universal algorithm. I always had to change something.
Indeed. This seems like a good use case for a cost/utility function. Very long wait times should be very high cost, while short wait times should be disproportionately low cost, etc.
> Also, there might be more than one criteria to optimize for.. shortest travel time? fewest moves?
More fundamentally: do you optimise for the users of the service (lift passengers) or for the person paying for it (building owner)? Because I can imagine very different drivers there.
so are you saying that, similar to the elevator programming challenge itself, writing the elevator programming challenge was more difficult than it looked?
cool. that probably put a bigger smile on my face than it should've, but still cool.
Elevators enable skyscrapers. As you build taller skyscrapers, more and more of the floor space is given over to elevators. There must be a huge incentive to improve elevator routing. I'd love to peek behind that curtain.
> Modern elevators are strange and complex entities. The ancient electric winch and “maximum-capacity-eight-persons" jobs bear as much relation to a Sirius Cybernetics Corporation Happy Vertical People Transporter as a packet of mixed nuts does to the entire west wing of the Sirian State Mental Hospital.
> This is because they operate on the curious principle of “defocused temporal perception.” In other words they have the capacity to see dimly into the immediate future, which enables the elevator to be on the right floor to pick you up even before you knew you wanted it, thus eliminating all the tedious chatting, relaxing and making friends that people were previously forced to do while waiting for elevators.
> Not unnaturally, many elevators imbued with intelligence and precognition became terribly frustrated with the mindless business of going up and down, up and down, experimented briefly with the notion of going sideways, as a sort of existential protest, demanded participation in the decision-making process and finally took to squatting in basements sulking.
> An impoverished hitchhiker visiting any planets in the Sirius star system these days can pick up easy money working as a counselor for neurotic elevators.
The Hitchhiker's Guide to the Galaxy by Douglas Adams
Single-elevator control and group control are usually separate. In many systems, the group controller's authority is limited to remotely pushing the buttons in each elevator in each elevator. Thus, the group controller has no safety responsibilities.
All the hall calls (from the buttons outside the elevator) go to the group controller, which controls dispatch policy. Early systems, such as the Otis Autotronic, used analog computer components to set dispatch policy. The newest ones use machine learning.
If you set an elevator to "independent service" (this is a key switch in most elevators) it disconnects from the group controller and only obeys its own cab buttons. This is used when you need a service elevator, but not often enough to have a dedicated one. The group controller is not necessary for basic elevator operation.
i get angry at my building's elevators every damn day. They should park themselves at the ground floor before 10:30am and above ground after. I get to th building before 7am and there are times when 6 of us are waiting on one of 4 elevators for at least two minutes. It's inexplicable. They should be there waiting and ready. Ain't no on 11-21 trying to go DOWN before 7.
So yes I think I could program an elevator. And yes I think I could do it better than the shit it currently is.
Obviously you did not reach the level when you can program the behaviour of four elevators in the same time :) About the first and the 20th floor: How about if you've got 15 people on the 20th floor and one person on the 1st? Every button press is a request that could add more weight to the particular floor. After all the goal is to transport as many people as possible for a given time.
Someone should make a real contest (maybe a Kaggle contest), with real data and all. With well-chosen metrics I think it could be a lot of fun and a great success.
When I was teaching assistant at University for Real Time Safety Critical Systems class this was one of the star assignments in the class.
Instead of writing just a dummy program we built an actual elevator using servo motors and asked students to code using different logic
1. Single elevator
2. Double elevator
2. Double elevator with various kinds of optimizations (reduce the energy used v/s reduce the time for each passenger).
All had to be done using embedded C on an ATMEGA processor.
Then we let students do the exact same coding using Esterel where you essentially represent everything as the state diagram.
It was so much fun for bother teachers as well as students because when you deal with real hardware suddenly the scope of problems goes beyond merely getting the logic right.
This was one of my white board exercises during the interview for my current job. I found it interesting because it seems very easy when the question is asked but it allows for a lot of communication between the interviewer and interviewee as the edge cases are fleshed out.
An elevator once dropped me one and a half floors with open doors (both, floor station and cabin doors). I think the cable slipped over the transport wheel. Felt funny in the stomach, but we all kept standing when we hit the end-stop in the pit. "safest way of travel" huh!
One thought comes to mind. What if the button light is not working? Hit the N button once, and you are on your way to floor N. But if the light is busted, you would hit the light again, and now you have deselected your destination. I think button presses should be indempotent for this reason alone.
Seriously? Has anybody reading this ever done this? It seems to me that by the time the operator picks up and you tell them what you're trying to do and what elevator you are on it would be too late.
117 comments
[ 3.0 ms ] story [ 168 ms ] threadwhich introduces a whole new set of complexity.
I think this sort of elevator allocation is fairly common for tall buildings, because it's horribly inefficient for people going to the 44th floor to have to wait while people get on and off at all of the 42 floors in between!
It would be pretty fun if someone were to make a version that supported this. :)
http://play.elevatorsaga.com/
Which I'm now closing as I lost too much time to this the first time I saw it.
I think it's the programmer equivalent of https://xkcd.com/356/
This is how teaching should be...this exercise isn't at all about programming and more about how to think. This can be simplified into a drag and drop block language and given to grade school kids as a really good exercise.
Many programmers in the professional world today would really struggle with this because they never learned to actually think, they just "program" (copy paste, edit work already done by others). They don't actually create new things or find solutions themselves.
[0]: https://developers.google.com/blockly/?hl=en
http://slushsmackdown.com
http://www.codeandconquer.co/ is vaporware at this stage.
https://www.battlecode.org/ is also great fun each year. Not sure if it continues running after the competition is over.
http://aichallenge.org/ hasn't run either for awhile unfortunately.
Untrusted: https://alexnisnevich.github.io/untrusted/
It's the best one for doing challenges that use actual test cases. This challenge could easily be ported to that site (and I think there already are a few elevator ones)
It abstracts simple programming concepts (like loops, branches, etc) in a visual language.
- Why currentFloor() is a function not a property?
- Why both goingUpIndicator() and goingDownIndicator() instead of .direction property?
- Why name destinationDirection() instead of currentDirection?
- Why only floor_button_pressed but no in-door button press event?
I gave up.
Hilariously i missed the apply button on the first try, and wondered why it was still only moving between 0 and 1 after adding a few lines.
The site design could do with a tuneup as well. The actual page seems to only fit on widescreen, while the docs page becomes painful to read on same.
I think many developers have been waiting for an elevator thinking "Damn this thing is DUMB! I could do a way better job coding the logic for this..." Can finally test it out.
However, I do think this is a great exercise for people new to programming. It's a common enough scenario that most people can recite 80% of the requirements of an elevator from memory.
https://users.cs.duke.edu/~chase/cps310/lab3-elevator.html
It's a classic example of a problem that you think is appropriate to throw at new programmers but find out it goes terribly wrong because the hard part is designing a suitable state machine first. If you just start coding without a full model that covers all the edge cases, it quickly degenerates to a mess of ad-hoc heuristics and spaghetti.
My assignment involved writing assembly on some virtual machine with a weird byte/word size and dozens of addressing modes, as well as a (virtual) tape device. I think it was called CUSP but I can't find any references for it now.
GKRuleSystem[0] to the rescue!
Or any other Fuzzy Logic(?) framework.
Or maybe a behaviour tree, which is how I would have (tried) to design it with.
I hope I get something like this on an interview, instead of "reverse binary tree" like questions. This actually seems like a fun problem to solve. Knowing my defect brain, it would put a lot of effort into this because it's kinda fun. Also because I already have a ton of ideas on how to implement this - not that I already have.
Just off the top of my head. A BT that tracks current floor, direction, some predicates for inputs e.g ignore input 2 if direction is up and current floor is 3.
That would satisfy the current test conditions. HOWEVER.. a better style would be to keep that in queue with an indicator (UI) that it's on the queue after current direction has hit its highest floor. Could add another predicate that the elevator won't stop for 'caller' on third floor if it's filled (maxWeightReached) and everyone are going to bottom floor.
Eventually you could maximise the amount of people it moves based on space available and how many have called the elevator using their condo NFC tags.
Seriously, this what dev interviews should look like.
0: https://developer.apple.com/library/ios/documentation/Gamepl...
In any case, a well designed FSM would get you a long way. Since the input (pressed buttons) is finite, you can cover every single case and weight according to importance of floor and wait time.
A well designed FSM doesn't necessarily mean an easily read FSM.
I always try to draw states and transitions on paper, and I end up making a mess. That could be a flaw on my side. But I won't be making the same mess with BT.
I don't see how a FSM could avoid having transitions back and forth.
FSM would need to track current floor and direction. Would need guards/predicates on transitions for inputs Could just be me, but I wouldn't be able to draw a pretty picture with those.Then you get to add more people, queuing of commands etc (helping you discover some different algorithms and data structures).
Then you can throw in some advanced predictive code and machine learning, taking into consideration usage vs time, locations people most travel to/from etc.
Long story short: a simple, rules-based algorithm defeated my best efforts at having multiple elevators working together to coordinate their action.
[1]: https://clarkmoody.com/Moody_AgentBasedElevatorControl.pdf
However, the reason I think about elevator programming isn't to make an elevator behave the way they do today. It's to make an elevator behave better than they do today.
For example:
* I don't want an elevator to close and reopen its doors on the same floor. That's horrible user experience.
* All the interesting problems arise when there are multiple elevators servicing the same set of floors. So let's control more than one elevator at the same time.
* If the elevator is on the ground floor, and has downward calls on both the 1st and 20th floors, then it is likely more efficient to service the 1st floor first rather than bypassing them just so you can keep travelling in the same direction.
I'd like to see a version of this that, rather than enforcing arbitrary rules, just has a lot of series of inputs and lets people compete to service those inputs in the shortest number of steps.
However, the criterion you're optimizing for is still unclear. Should it be: a) the total number of steps the elevator takes b) the average number of steps each user has to wait c) the maximum number of steps each user has to wait d) the 90th percentile of user waiting steps
Note: here, I'm counting the steps spent waiting for an elevator as well as the steps spent in the elevator till the destination as the same, but presumably you'd want to count steps spent inside the elevator as costlier, further complicating matters.
And this not even considering what happens if your algorithm answers 20 calls, without going to any destination floors, when the elevator capacity is only 10 people.
That's what makes this such an interesting problem.
Interesting thing here is that "price" does not have to depend on distance. Taking passengers travelling short distances might look cost effective, but that could have negative effect on number of people going to a 20th floor.
More fundamentally: do you optimise for the users of the service (lift passengers) or for the person paying for it (building owner)? Because I can imagine very different drivers there.
cool. that probably put a bigger smile on my face than it should've, but still cool.
> This is because they operate on the curious principle of “defocused temporal perception.” In other words they have the capacity to see dimly into the immediate future, which enables the elevator to be on the right floor to pick you up even before you knew you wanted it, thus eliminating all the tedious chatting, relaxing and making friends that people were previously forced to do while waiting for elevators.
> Not unnaturally, many elevators imbued with intelligence and precognition became terribly frustrated with the mindless business of going up and down, up and down, experimented briefly with the notion of going sideways, as a sort of existential protest, demanded participation in the decision-making process and finally took to squatting in basements sulking.
> An impoverished hitchhiker visiting any planets in the Sirius star system these days can pick up easy money working as a counselor for neurotic elevators.
The Hitchhiker's Guide to the Galaxy by Douglas Adams
All the hall calls (from the buttons outside the elevator) go to the group controller, which controls dispatch policy. Early systems, such as the Otis Autotronic, used analog computer components to set dispatch policy. The newest ones use machine learning.
If you set an elevator to "independent service" (this is a key switch in most elevators) it disconnects from the group controller and only obeys its own cab buttons. This is used when you need a service elevator, but not often enough to have a dedicated one. The group controller is not necessary for basic elevator operation.
So yes I think I could program an elevator. And yes I think I could do it better than the shit it currently is.
Grumble grumble
Eg https://www.youtube.com/watch?v=59jW9dngt_c
PNs are a great way of modelling the concurrent state handling required for something like this.
[0]: https://news.ycombinator.com/user?id=silvamerica
Instead of writing just a dummy program we built an actual elevator using servo motors and asked students to code using different logic
1. Single elevator 2. Double elevator 2. Double elevator with various kinds of optimizations (reduce the energy used v/s reduce the time for each passenger).
All had to be done using embedded C on an ATMEGA processor.
Then we let students do the exact same coding using Esterel where you essentially represent everything as the state diagram.
It was so much fun for bother teachers as well as students because when you deal with real hardware suddenly the scope of problems goes beyond merely getting the logic right.
An elevator once dropped me one and a half floors with open doors (both, floor station and cabin doors). I think the cable slipped over the transport wheel. Felt funny in the stomach, but we all kept standing when we hit the end-stop in the pit. "safest way of travel" huh!