Hacker News new | past | comments | ask | show | jobs | submit login
So You Think You Can Program an Elevator (github.com)
407 points by mshang0 on Jan 12, 2016 | hide | past | web | favorite | 112 comments



Very similar immediately playable JavaScript version.

http://play.elevatorsaga.com/

Which I'm now closing as I lost too much time to this the first time I saw it.


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.


Plenty of programmers think, they just don't consider the use case and the user.


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.


This would be a great Blockly[0] demo

[0]: https://developers.google.com/blockly/?hl=en


Indeed. Example of a similar game using Blockly, with the option to switch to JavaScript:

http://slushsmackdown.com


This is fantastic. Are there other good programming challenge / games like this? I'd love to see a collection of other similar games.



https://codecombat.com/ maybe?

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.


Check out http://www.CodeWars.com

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)


"Human Resources Machine" from Tomorrow Corporation (it's a proper indie game, you can find it on Steam).

It abstracts simple programming concepts (like loops, branches, etc) in a visual language.


ruby warrior https://www.bloc.io/ruby-warrior is another good one


Robocode is another one: http://robocode.sourceforge.net/


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.


Stockfighter.io and microcorruption


This game is basically what I set out to make, not knowing it existed at the time.


Oh no. My work day has been seriously threatened.


Which 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/


Nice link! The problem has been solved, by the way: http://physics.stackexchange.com/questions/2072/on-this-infi...


That is hilarious. If elevators always malfunctioned like that imagine how many calories some people would burn.


This makes me want a hackable version of SimTower.


Also came here to post this link. Ought to come with a warning label.


I stuck at challenge #10, can anybody help?


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.


This is fun! Thanks for sharing.


Well I can report just straight random is only good enough for the first level.


Somehow I find this API counter-intuitive and painful to use.

- 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.


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') ?


What i found the most annoying was that it had both a save and a apply button.

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.


Is there a solution "Attach R2D2 to computer terminal"? ;)


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.


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.


THIS.

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.


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.


I think they use machine learning now.


> 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


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.

Grumble grumble


Either your building has old/cheap/shitty elevators or they are misconfigured. This is already standard feature in our elevators.


My building is from 1983. I would wager five bucks that more than half of office tower elevators are old/cheap/shitty/misconfigured.


Totally agree. That's basically the challenge that I wanted to make, but I found that I bit off more than I could chew.


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.


Yeah, but that can't be surprising. Software estimation is hard.


indeed it is. i think i'm especially bad at it, but a lot of people probably feel that way.


I believe the afore-mentioned http://play.elevatorsaga.com/ let's you experiment with optimizing algorithms.


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.


Elevator simulation is used often as a case study for petri nets. There is quite a bit of PN material using elevators.

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.


Also, there might be more than one criteria to optimize for.. shortest travel time? fewest moves?


> 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.


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.


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 :).


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.


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.


I 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.


Don'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/Gamepl...


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.


A 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


This looks really funny. Is it a spoiler if I haven't done the posted link yet? If so I'll read it later :)


Not related to the posted link, so no spoilers :-)


Then 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

which introduces a whole new set of complexity.


As 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. :)


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.


What if you need to visit someone on another floor?


There's touchscreens in the lift lobbies where you can select an override floor before scanning your pass.


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).


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.


Over 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.


On 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


thx.

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!


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


I 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.



Awesome, my favorite game when I was younger.


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.


There'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


Nice. 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/eleva... ) or Double-decker elevators ( https://en.wikipedia.org/wiki/Double-deck_elevator )?

Because, you know, I really have no work I need to accomplish this year...


I'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?


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.


Or in a crowded elevator a 'malicious' user blocking the view to the buttons deselects all but their own floor.


This is why the standard practice of picking up the elevator phone and requesting a floor cancellation exists.


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.


Most modern elevators already do this ...


This 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


Nice! They shoot for automated grading. I wish I had that when I was a TA.


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.


I think traffic signal optimization would be another neat game.


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.


Elevators 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.


Wow, 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!


This post reminded me of this classic Apple //c commercial:

https://www.youtube.com/watch?v=B3rKBw5ZNL4


Usually 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. :)


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.


Maybe an elevator but I very much doubt a Wonkavator!


I actually wonder how the space and time complexity of the algorithm would increase as the number of possible dimensions of travel increases.


They've removed the elevator buttons inside the carriage at my work; now one can only select a single floor from outside the elevator.


The buttons are still there, just hidden under a cover. If not your building has a serious fire safety problem.


I can't exactly remember why I found it, but there is a book about this very topic! Elevator Traffic Handbook, by Gina Barney


Good challenge. I've thought myself many times what would be elevator logic, and it's not trivial.


This would be fun as an html5 game. I'm not sure how you'd enter the logic though.


Elevator and vending machine are two good examples for learning about state machine.


Funny they refer to it as "business logic."


what no elevator recall?


>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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: