11 ms·
So You Think You Can Program an Elevator
- mattlong 11y agohttp://codelift.org/ http://codelift.org/ is an elevator challenge a friend of mine[0] built that'll throw scenarios of various numbers of floors and elevators at you. [0]: https://news.ycombinator.com/user?id=silvamerica https://news.ycombinator.com/user?id=silvamerica
- n0us 11y agoThen there is the alternative system where you do not request UP or DOWN but you request the floor, otherwise known as destination dispatch https://en.wikipedia.org/wiki/Destination_dispatch https://en.wikipedia.org/wiki/Destination_dispatch which introduces a whole new set of complexity.
- Zikes 11y agoI 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.
- The_Magistrate 11y agoTaller 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.
- caf 11y agoI'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.
- Raticide 11y agoWhat if you need to visit someone on another floor?
- caf 11y agoThere's touchscreens in the lift lobbies where you can select an override floor before scanning your pass.
- rodgerd 11y agoWhenever 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.
- jleader 11y agoI 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!
- caf 11y agoIn 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).
- verbatim 11y agoAs a programmer who works in a building with one of these -- I've often been quite sure I could code a more efficient system. It would be pretty fun if someone were to make a version that supported this. :)
- torkable 11y agoor just play this: http://play.elevatorsaga.com/ http://play.elevatorsaga.com/
- noir_lord 11y agoVery similar immediately playable JavaScript version. http://play.elevatorsaga.com/ http://play.elevatorsaga.com/ Which I'm now closing as I lost too much time to this the first time I saw it.
- hodwik 11y agoOh no. My work day has been seriously threatened.
- noir_lord 11y agoWhich is why I closed it once I'd copied the link, it's very very addictive. I think it's the programmer equivalent of https://xkcd.com/356/ https://xkcd.com/356/
- Luyt 11y agoNice link! The problem has been solved, by the way: http://physics.stackexchange.com/questions/2072/on-this-infinite-grid-of-resistors-whats-the-equivalent-resistance http://physics.stackexchange.com/questions/2072/on-this-infi...
- kevindeasis 11y agoThat is hilarious. If elevators always malfunctioned like that imagine how many calories some people would burn.
- oliv__ 11y agoThis is fun! Thanks for sharing.
- Cshelton 11y agoThis 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.
- phibit 11y agoThis 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.
- exelius 11y agoNo, 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.
- flippyhead 11y agoMaybe an elevator but I very much doubt a Wonkavator!
- n0us 11y agoI actually wonder how the space and time complexity of the algorithm would increase as the number of possible dimensions of travel increases.
- avodonosov 11y agoGood challenge. I've thought myself many times what would be elevator logic, and it's not trivial.
- aaronkrolik 11y agoThis is a lot like an assignment for my operating systems class to introduce threads/lock (each elevator and rider is a thread). https://users.cs.duke.edu/~chase/cps310/lab3-elevator.html https://users.cs.duke.edu/~chase/cps310/lab3-elevator.html
- monksy 11y agoNice! They shoot for automated grading. I wish I had that when I was a TA.
- arnarbi 11y agoThis 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.
- noir_lord 11y agoThat 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 :).
- nosequel 11y agoSame 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.
- philsnow 11y agoSame 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.
- mshang0 11y agoI had no idea that it was a common problem assigned to students, but it makes sense. Somebody on reddit also mentioned that Knuth also covers it.
- seivan 11y agoDon't go for a FSM. 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/GameplayKit/Reference/GKRuleSystem_Class/index.html#//apple_ref/occ/instp/GKRuleSystem/facts https://developer.apple.com/library/ios/documentation/Gamepl...
- clarkmoody 11y agoA project during my graduate work was to solve this problem. You can read my write up, which includes pseudo-code for the best algorithm I found[1]. 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 https://clarkmoody.com/Moody_AgentBasedElevatorControl.pdf
- wodenokoto 11y agoThis looks really funny. Is it a spoiler if I haven't done the posted link yet? If so I'll read it later :)
- clarkmoody 11y agoNot related to the posted link, so no spoilers :-)
- mrfusion 11y agoThis would be fun as an html5 game. I'm not sure how you'd enter the logic though.
- mrfusion 11y agoI think traffic signal optimization would be another neat game.
- phasmantistes 11y agoThis 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.
- neil_s 11y agoTHIS. 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.
- friendzis 11y agoThis 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.
- joelthelion 11y agoSomeone 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.
- deleted 11y ago[deleted]
- tn13 11y agoWhen 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.
- southphillyman 11y agoThis 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.
- brk 11y agoOn the topic of elevators, opening this link will cause you to (happily) lose an hour of productivity: https://m.youtube.com/watch?v=1Uh_N1O3E4E https://m.youtube.com/watch?v=1Uh_N1O3E4E
- anotheryou 11y agothx. 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!
- platz 11y agoThey've removed the elevator buttons inside the carriage at my work; now one can only select a single floor from outside the elevator.
- ben_bai 11y agoThe buttons are still there, just hidden under a cover. If not your building has a serious fire safety problem.
- sfall 11y agowhat no elevator recall?
- kneel 11y agoI've always wanted to see the option to deselect a floor if you press a button twice. Is there a good reason why this doesn't happen?
- amorphid 11y agoOne 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.
- Skunkleton 11y agoThis is why the standard practice of picking up the elevator phone and requesting a floor cancellation exists.
- jandrese 11y agoSeriously? 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.
- glitcher 11y agoOr in a crowded elevator a 'malicious' user blocking the view to the buttons deselects all but their own floor.
- kenshaw 11y agoMost modern elevators already do this ...
- swehner 11y agoFunny they refer to it as "business logic."
- cranium 11y agoI can't exactly remember why I found it, but there is a book about this very topic! Elevator Traffic Handbook, by Gina Barney
- prutschman 11y agoI have a pet theory that Sim Tower came out of someone playing around with elevator algorithms for fun and then turning that into a game.
- andmarios 11y agoUsually elevators are controlled by PLCs which can be programmed using ladder. If you know a bit about boolean algebra, it is easy to learn ladder and program an elevator the real way. :)
- valgaze 11y agoThere's an old legend in the construction world that the fastest way to reduce complaints about slow elevators in an office building is to add mirrors to the doors & hallways. The tenants (allegedly) spend so much time looking at themselves that they'll overlook an inefficient elevator system
- yeukhon 11y agoElevator and vending machine are two good examples for learning about state machine.
- timberburn 11y agoOver a phone interview with Segment.io, I was asked to program an elevator controller. It was described to perform like an HTTP server would handle requests... They were getting confused when I started writing code for a state machine. Glad I got a job offer somewhere else.
- gsam 11y ago>So You Think You Can Program an Elevator No, especially not in practice. I would never proclaim to have such a belief unless it was my job to do so. Even then, I wouldn't be convinced I was doing a good job of it. The amount of unforeseen complexity in most systems is no joke.
- danbolt 11y agoElevators are a great exercise to get people started in writing organized programs. My university's introductory assembly class had us do it in ARM, and it really taught me a lot about being structured. I'm happy to see this sort of stuff on the front page.
- chrissnell 11y agoThis post reminded me of this classic Apple //c commercial: https://www.youtube.com/watch?v=B3rKBw5ZNL4 https://www.youtube.com/watch?v=B3rKBw5ZNL4
- lotask 11y agoWow, how thoughts can be materialised easily. I was thinking about elevator simulation for the past year, but didn't get into implementing anything.. Think this is a good challenge for me to start doing this. Nice!
- nekopa 11y agoNice. To the author, is there anyway to change the simulation to try programming 2 elevators in the same shaft ( http://www.thyssenkruppelevator.co.uk/new-installation/elevators/passenger-elevators/twin/ http://www.thyssenkruppelevator.co.uk/new-installation/eleva... ) or Double-decker elevators ( https://en.wikipedia.org/wiki/Double-deck_elevator https://en.wikipedia.org/wiki/Double-deck_elevator )? Because, you know, I really have no work I need to accomplish this year...
- amydav27 11y agoHAWKHACK are Extraordinarily intelligent and smart Hacker,We are one of the rare gem of hackers who hack and build hacking software which most hackers can build on.We have an excellent record, recording 100% successes in all of our job.We are reliable and loyal to our clients and make the satisfaction and safety of our clients our priority.We render the following services at affordable price. UPGRADE UNIVERSITY GRADES HACK AND ADMIT YOU INTO ANY UNIVERSITY OF YOUR CHOICE HELP GET YOU A LEGIT AND ACCEPTABLE UNIVERSITY TRANSCRIPT TO APPLY FOR TRANSFER OR ADMISSION REMOVE CRIMINAL RECORDS HACKING SOFTWARES SOCIAL MEDIA HACK EMAIL ACCOUNTS PASSWORD HACK AND RECOVERY RETRIEVAL OF LOST FILE/DOCUMENTS BANK ACCOUNTS HACK BANK WIRE TRANSFERS TO ANY ACCOUNT OF YOUR CHOICE DATABASES HACK SALES OF VERIFIED CREDIT CARDS OF ALL KINDS UNTRACEABLE VPN CONTROL DEVICES REMOTELY HACK PHONE HACK AND SECRETLY READ TEXT MESSAGES AND WHATSAPP MESSAGE AND MONITOR CALLS VERIFIED PAYPAL ACCOUNTS HACK EMAIL INTERCEPTION HACK SKYPE HACK *CREDIT CARDS HACKER.NOTE NOTE...If you refer client to us as a result of the previous job done for you, you will stand a chance of getting any job of your choice hacked for you, free of charge. CONTACT US. WALTSTEPH82@GMAIL.COM + 1 601 866 5203