Elevator Saga: An elevator programming game (2015) | Hacker News Reader

Elevator Saga: An elevator programming game (2015)

play.elevatorsaga.com

278 pointswarpech99 comments

Made me remember an interesting anecdote: During my PhD at Purdue I had the good luck to take the Pattern Recognition (nowadays would be called ML) course from Prof. Fukunaga, one of the pioneers in the field (https://en.m.wikipedia.org/wiki/Keinosuke_Fukunaga). In one of his classes he mentioned that years ago a company came to him, requesting his expertise in optimizing movement of a bank of elevators. He thought it would be trivial :-) After telling us that all his approaches failed miserably, he had one of his impish laughs and told us that he never worked on that problem again. Miss that guy. Get a copy of his book (https://books.google.com/books/about/Introduction_to_Statist...) if you can, it’s written in the “old style” but very informative.

Interesting fact: Gen Fukunaga (https://en.m.wikipedia.org/wiki/Gen_Fukunaga), founder of anime company Funimation, is his son.

I’ve always wondered if the main computer in Star Trek has to be so big just to manage the turbolifts. Three dimensional elevators with multiple exits per level, probably prioritizing routes dynamically based on the passengers and the military alert level. Imagine the algorithms.

I think it would fundamentally be a constraint based programming problem, eg the sudoku solvers, travelling salesman implementations, software that tells eg Amazon warehouses which parcels go in the van first based on both size and the route it’s planned so that the driver never had to dig all the parcels out to get the buried ones.

Boiler Up!

I had Prof Fukunaga for EE301 I think (Might have been EE202). I was too young and dumb to recognize his brilliance.

I started in physics before switching to CS. I'm glad the ECE department is good, because the CS department was terrible.

Awesome, it’s a small world. I was his teaching assistant during the times he taught EE301 (Signals & Systems) so chances are I’ve corrected your exams!

In my ML class some students did a project on using reinforcement learning to optimize elevators. They told me that after 100 years of operation the algorithm would have enough data to start working really well.

There is this anecdote in the text "Operations Research, An Introduction." by Hamdy Taha, which I consider to be a very good example of picking the right tools for the job. An OR group was hired to fix elevator wait times in an office building. After studying the problem they installed full-length mirrors at the entrance to the elevators. Complaints around elevator service disappeared as people were now engaged in watching themselves and others while waiting.

I first heard of this from Dr. Russell Ackoff's Systems Thinking Speech. I had a mini mind blown moment.

Reminds me a parable from Are your lights on by Gerald Weinberg.

I pounded my head on this problem in a multi-agent system course in graduate school. Needless to say, I could not outperform a simple naive algorithm however hard I tried.

During Covid, I've often wished I could reprogram the elevator of the apartment building I live in. The current rule is only 2 people can be in the elevator at a time.

Problems that arise:

* Elevator stopping frequently, but already at capacity, slowing down overall performance

* Elevator always goes to bottom (or top) first to pick up passengers going up (or down). This means if your waiting on the ground floor and it's a busy time, folks at the parking levels will repeatedly get picked up before you.

Possible solutions:

* First come, first served (need to remember order of what floor pushed button when)

* Ability to set elevator as "full". Even if abused by a single person, still better than multiple wasted stops.

Elevator could also make a decent guess at fullness just by recording the discrete changes in weight. It wouldn't be perfect but again it would probably be better than allowing user input.

i believe all elevators at least have a failsafe to refuse to run if they are overloaded. going from there to tracking and using the actual weight for its programming is not a big step

Oh, elevators know to some accuracy how many people-mass things are in it. It just rarely has reason to use that information.

During COVID I think it's totally reasonable for any person to be able to set the elevator as "full" - if you're returning from travel and quarantining, immunocompromised, etc. you might not want to travel with anyone.

Also,

* Elevator door closes when it's not in use - may as well stay open, get some ventilation, and use slightly less energy!

> any person to be able to set the elevator as "full"

Sadly, in an apartment building there are several people who are selfish. These types would use the feature to monopolize the elevator for moving.

> door closes - stay open?

Prob to reduce the time to travel to a floor. If the doors were open it would add another 15secs in addition to the travel time to reach the called floor.

Another failure: when there's a line, and you already know you'll need multiple cars, the elevator button will still only allow you to call one car at a time. Even if several cars are already on your level with the doors closed.

> Ability to set elevator as "full". Even if abused by a single person, still better than multiple wasted stops.

I'd add a couple of sensors (one for volume and one for weight) to let the elevator itself determine how full it is and act accordingly.

I would also still have a "full" button for people to press, but not have the button actually do anything, except maybe light up.

Would a first order approximation of "full" be "has two destinations"

You could but if passengers knew that it would result into single passengers pressing two car calls so they could get private elevator ride. Rather you would just use the normal passenger counting system i.e. correlating weight scale with photocell cuts.

I mean you aren't wrong, but also this is all logic tha has existed in elevators for decades, but if your building owner just slaps a piece of paper artificially creating a limit the elevator system won't be aware of it. On other hand they could have made an configuration order and paid to change the behavior of the elevator, to reduce its capacity. Then it wouldn't make extra stops since it would know that it is at max capacity.

Fun fact: all of the above things are features that exist on elevator controllers. Most buildings just never have their elevators configured correctly.

I always wished elevator buttons could toggle. If you accidentally press the wrong floor, just press it again to cancel. This may not work in all situations, but in some situations, it could be a time saver.

It works this way often in (north-east) Asia. Double-tap a selected floor and it unselects. Brilliant.

Yep. My office one does that. I first it was a joke, but it actually is indeed a brilliant scheme to avoid misclicks.

And as you seldom unselect, it's Huffman coding for the win ;-)

our elevator does that, and i noticed it is quite common in chinese elevators. i can undo all destinations which makes the elevator just stop.

living on the top floor of a highrise, i was occasionally able to use that when i realized that i forgot something at home (although most times it takes me longer to realize that than the elevator needs to make it all the way down)

it is also very useful when the kids are naughty and press all the buttons for fun

Many modern ones in high rise buildings require you to scan a key fob and/or enter the desired floor number, then it tells you which elevator to go wait at. The ones with the key fob often replace your previous selection automatically.

There are not buttons in this style of elevator other than door open door close and call for help.

In an office building near me, the security person at reception enters a destination floor and tells you which elevator to step into. There are no controls outside or in the elevator (other than emergency stuff).

A so-called "lobby system". Works well, IFF people understand that 1 passenger <=> 1 press, instead of having a group of (say) 5 having only one in the group press, then all of them piling in.

Used correctly, it can massively improve the elevator usage experience. Used incorrectly, it ends up being worse than a "indicate travel direction" system.

Having used it in 3 (I think) buildings with this system, it was definitely used correctly in one, definitely NOT used correctly in another and in the third, I was mostly present sufficiently outside normal working hours that I cannot with certainty state how it was used.

the thing is that elevators are these days way more complex than anybody would even imagine, but the thing also is that there are no tutorials given to people who use them. Also extra features cost extra money and building owners usually just want the very basic stuff for residentals.

I think the reason for this could be to prevent you cancelling other people's destinations. I can only imagine the public freakout that could unfold, even if it was accidental.

This is my top of the wish list feature as well! Then my 9yo son told me the feature exists, just double tap/press the desired floor button. I thought he was joking, but no! It works!! How he discovered it I will never know!

I always try this if I accidentally press a button, or enter an empty lift with a few buttons pressed. One glorious day in a hotel in Penang, I double-pressed a button and my dreams came true, lights out. That one experience will be enough to keep my dreams alive for decades to come

One past discussion, plus a one-commenter:

Elevator Saga: The Elevator Programming Game - https://news.ycombinator.com/item?id=21425054 - Nov 2019 (1 comment)

Elevator Saga – An elevator programming game - https://news.ycombinator.com/item?id=8929314 - Jan 2015 (104 comments)

And sadly it still has some unfixed bugs since 2015 where people don't consider the up/down indicators correctly, and will not enter the elevator even though the lights are on in the direction they want to go.

It uses the MIT license, and the git repo is here:

https://github.com/magwo/elevatorsaga

along with some pull requests which might fix those problems.

On the repo it says:

"For developers/contributors: This project is not actively maintained. The repo is used to serve github pages so I would like to keep it as is. Feel free to fork and host your own versions of Elevator Saga! But I would like to keep the domain name with the original version of the game."

I am sure someone on here has the chops to set up a clone of it.

Ah disk scheduling algorithms :) https://en.wikipedia.org/wiki/Elevator_algorithm

Call me weird, but I’ve been fascinated by elevator logic since I was a child. I had a math curiosities book that dedicated a chapter to it and after reading that I was hooked on knowing more.

I wish my knowledge of JavaScript was more than “programming language that’s not Java” so I could actually play this.

Could anyone recommend an online introduction to JS so I can attempt to play this?

I’m more of a bash guy.

If you know your way around any programming language, then hop on (https://learnxinyminutes.com) to quickly get the hang of any other language.

Also, to understand the asynchronous nature of Javascript, have a look at this excellent presentation and website:

http://latentflip.com/loupe/

https://www.codecademy.com

I didn't finish, but I recall enjoying their intro to JS, and managed to write a few working things hah

I don't remember the article but I remember reading about a building management game where the reviewer believed the entire game was based around the elevator management code and that writing that code was fun for the programmer but the game itself was not fun for the player.

It looks like this highlights the "fun for the programmer" part.

Maybe Sim Tower? The game was pretty boring, but building and managing elevators to keep people happy was a fun challenge.

Sim Tower and Sim Ant were both great network-building games. They seemed boring until you really delved into the details. Maxis was really genius up until EA bought them. Here's a pretty cool project they did that never came to light...

https://www.gamesradar.com/simrefinery-the-lost-oil-plant-ga...

As aidenn0 said, this sounds like SimTower and its sequel Yoot Tower. There's a section of the manual[1] called "A Message From Yoot Saito, Creator of Sim Tower" that describes how he started creating it because he was curious about elevator programming.

[1] https://archive.org/details/SimTower_-_Manual_-_PC/page/n7/m...

An interesting improvement over naive operation I thought long ago: idle elevators should go to 1/2 maximum floor! You easily cut average wait times in 1/2!

Problem is, it's also energy inefficient. If you get a passenger at floor 1 or 0, you've wasted a lot of movement. On-demand movement wastes minimally.

So I've learned of a tradeoff between energy and waiting time -- not just elevator speed, but in algorithms.

It's fun to consider a minimal energy solution (it takes a very long time to get anywhere ;) ).

I've also learned it's a classic under-specified problem. To solve it completely you need, for example:

1) distribution of arrival times and destinations of passengers;

(For example, if late evening people usually go up, it's best to idle on ground floor)

2) a "satisfaction function", giving a measure of performance of your system:

You can get low average waiting times and diverging maximum wait time for a busy elevator, simply trade time from a single passenger for others (by e.g. never going to a floor). As long as utilization is significant at all times, this phenomenon exists.

Clearly it's not only average we care about, but also maximum and minima of transit times.

---

It's a very illuminating modelling exercise.

Are real elevators ever coded with logic like mentioned in this thread? Or do they just keep it a simple as possible?

They can be. Express elevators and such. But mainly the programs are limited to what floor the elevators idle at because more complicated programs even if more efficient overall often piss people off.

>which floors the elevators idle at...

I recently spent 4 months in hospital which left me with an amount of time to kill in an attempt to stay sane. One of the games was trying to get places I was technically allowed but really shouldn't have been ("sod your 'no public access' signs, in not public, I'm an inpatient!"). Being confined to a wheelchair made the game a bit more difficult. One day one of the ward staff mentioned that the building used to have a 4th floor which got mothballed years ago. None of the elevators had a button for it and trying to get up a flight of stairs wasn't an option. After puzzling for a while, I finally realised that one of the elevators was still set to idle on the 4th floor. Get in the elevator, don't press any buttons, read a book for 10 minutes and bam - elevator returns itself to the 4th floor, opens the doors and goes ping. I wheel myself out to find I'm not just on the 4th floor, but also behind (on the inside of) the locked doors at the top of the stairs, which I counted as a double win ;)

That's amazing. I'll be trying that trick next time I have some time to kill in a building!

We also play the game sometimes of getting places we're not supposed to (as consultants). Walk around like you're from IT and are supposed to be there (technically both true), perhaps with a laptop under your arm, nobody will care what you do to any of the computers there. In schools and hospitals, and probably other places, try (variants of) the city you're in as password, perhaps combined with the postal code, and you usually get access to everything because of course the staff needs to actually help you. The username is pre-filled, don't worry about that (most of the time that's the field with more entropy).

It's honestly terrifying and short of locking rooms (because some of the personnel needs fast access to computers, preferably faster than plugging in and out smartcards all day long) there just isn't really a solution. I'm pretty sure we could have walked into a surgery room, we steered clear of any place that looked like it might head us into places with patients under actual operation. Why those aren't locked I don't know, probably there is a good reason so probably they can't change that...

I'm sure for surgery rooms (at least), needing someone to rush in to help and having them fumble with ID cards outweighs a bad party trying to, I guess, muck up a surgery or something.

“Men are better than gates” - Gandalf - the real security on the surgery rooms are those in them.

in the hospitals that i have been for visits usually the whole intensive care area and other sensitive areas were access controlled. so while the door to the actual surgery room might have been open, you are often not even allowed anywhere near.

Very rarely do you have people rushing in to surgery rooms. Despite TV dramas, most surgeries are not high risk, most surgical patients are not critically ill, and those that are tend to be pre-staffed for the risk. OR rooms are not usually locked but the surgical suite sure is. The bigger issue with the surgical suite is proper attire. ICUs are a different matter (where coincidentally I happen to be tonight). Generally all the staff you need is already on the locked side of the unit.

Hopefully you don’t have to spend the time again - but if you do it’s very easy to buy the fireman’s key on eBay. You didn’t hear that here.

Relevant video discussing fire keys and other common keys: https://www.youtube.com/watch?v=a9b9IYqsb_U

And since this thread is about elevators, I have to also mention another video of theirs: https://www.youtube.com/watch?v=ZUvGfuLlZus

our elevator allows undoing pressed buttons. if no buttons are pressed, then the elevator will stop. now you could play a game where you try to get the elevator to stop at a particular floor without pressing that floors button. the only downside is that our elevator does not open the doors if no button is pressed, so any off-limit floors would remain inaccessible

The logic to pick up passengers is the easy part of a real elevator. Some harder problems: a) Physics. How to drive the motors to move smoothly and efficiently to the desired floor and stop level with the landing. b) Safety and regulatory. There are lots of safety features that need to be implemented, e.g. control by fire fighters. c) Customization. There are lots of special cases, either for customer desires or laws in different states. d) Networking. How do you get the signals from the hall call buttons to the controller and from the controller to the hall lanterns? Tons of wires or a protocol? e) Diagnostics and failure handling. What do you do if something goes wrong? What do you log for maintenance?

I was thinking of creating this very thing on several occasions being in an elevator. The logic of elevators is very intriguing and more complicated than people realize.

I'm not sure if this is true. I think all elevators I've encountered followed the elevator/SCAN algorithm:

> the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction.

with the elevator staying on its last location if there are no new requests and there being no buffering time after a request, first come first served

https://en.wikipedia.org/wiki/Elevator_algorithm

That is true only for the single elevator system. If there are multiple elevators, the system could be extremely complicated.

Have you ever seen elevators where you select a floor from the outside and it gets assigned to one of multiple elevators? Those seem like they might be doing something more sophisticated.

I used to have those elevators where I worked and everybody hated them. I think the algorithm was tuned for efficiency, so you’d be waiting for an elevator for minutes as it tries to batch everyone up, while a dozen other elevators sit idle.

This was made worse through the need to specify the number of people who are travelling to a specific floor so the algorithm can allocate enough space in each elevator. Large groups often ignored this so you’d often find that an elevator you’ve waited minutes for is full, and start the dance all over again.

https://en.wikipedia.org/wiki/Destination_dispatch

This is the problem - if the system goes beyond “what floor should I idle at” and “do I idle door open” people get mad at it because of apparent unfairness and inefficiency even if it is actually more efficient overall.

Same thing happens with traffic lights.

This got downvoted, but I’m pretty sure it is objectively correct. I feel like the same sentiment occurs with one queue vs multiple queues.

Continued small motion in a long single queue feels “fairer” than multiple queues - and may actually be.

But I also know most people prefer a driving trip where they’re continually moving rather than one where they’re basically stopped - even if the second is shorter in time.

“Apparent fairness” is an important design criteria for dealing with the public. Even if the system is actually incredibly unfair.

This works if you have only a single elevator, but if you have a group of elevators that work together and serve same set of floors you can start optimizing the trips for example journey time vs wait time.

What am I doing wrong?

        for(elevator of elevators) {
            elevator.on('idle', () => {
                //do some logic with elevator
            })
        }

It only seems to run for the second elevator rather than both of them?

i likely ran into the same or a related issue. i dont know much about javascript though.

        for(var i = 0; i < elevators.length; i++) {
            elevators[i].on("idle", function() {
                for(var j = 0; j < floors.length; j++) {
                    elevators[i].goToFloor(j);
                }
            })
        }

it only works for "i < 1" and then only the second elevator moves... its kinda sad as i immediately enjoyed playing ...

I think this was discussed there: https://news.ycombinator.com/item?id=8933979

this did indeed help understanding and fixing the issue.

Just in case this is interesting, a potentially more elegant way to solve this with modern JS is to use 'for(let i' instead of 'for(var i'.

The reason is that 'let' gives 'i' 'block scope', meaning that each iteration of the loop block gets its own scope so that 'i' isn't overwritten each time, and each function you declare captures the value of 'i' at the time it was declared.

In other words - the way you originally expected 'var' to behave is how 'let' behaves!

Should be `for (let elevator of elevators)`

Oh my god you’re right, oops. I wouldn’t normally make that mistake but no IDE and coding at night apparently isn’t a good mix!

for (elevator ... Like that is making a new global variable called elevator which is getting overwritten on the next loop. You need to for(const elevator... (or let).

The other thread is the same answer but for a slightly different case

You should be able to accomplish the same with elevators.forEach((elevator) => {})

It could, but favouring FP I'd use for..of for imperative loops where I need to do side-effects, or use .map which is nicer anyway.

If you like these programming games, localmotion has one where you schedule taxis to pick up passengers between buildings.

https://www.getlocalmotion.com/code-challenge

We're building an API to monitor elevators and stuff inside buildings. There are smart and dumb elevators. In any case, no one is actively using the data yet to improve our experiences like mentioned on this thread...sometimes we just wish we knew when to take the stairs.

If you're curious to view the kind of data streaming from a building or basic elevator, see here: (https://onboarddata.io/), python SDK is on Github (https://github.com/onboard-data/client-py). Every building is different. Some elevators have data on flooding, weight, inspection, electricity usage, while others do not.

Most hotels I've stayed at seem to be significantly limited on speed; anything <=5 floors is almost always faster to just head for the stairs and not even bother waiting. After a week, it's 6 floors.

Oh, this reminds me of the elevator banks in my office. I’m sure there’s something going on there. It can let me know which of 8 elevators is coming to pick me up as soon as I press the button.

            elevator.goToFloor(0);
            elevator.goToFloor(1);
            elevator.goToFloor(2);
            elevator.goToFloor(3);
            elevator.goToFloor(4);

I used to interview programmers with an elevator programming problem. Neat to see it expanded so excellently and cleanly in this piece. Well done!

I had this question during a Google interview. The interviewer became annoyed when I suggested that an elevator that sometimes went backwards to pick ip someone on a just-missed floor could at least be interesting, if not perfectly efficient.

They had a preconceived idea that they wanted a stateless system and didn’t like my stateful approach, even if it was potentially better for end users.

That’s an example of a thing that may work well but would piss users off - it apparently reversing would annoy.

Not just annoy. Some users might think they accidentally got on the wrong elevator ("oops, I got on a down elevator instead of an up elevator") and leave the elevator at the next floor to ask for a new elevator.

Yeah, that's one reason I stopped doing like code-this-thing style of interviews. There's no point in contriving problems for someone, we could both be working on something useful. I think for me at least, the main attribute I look for in a candidate for a developer role is the ability-to-avoid-shitty-solutions-ness of someone. If they steer themselves from bad ideas well, the rest can be taught by presentation and practice with the rest of the team.

I've had a similar idea around measuring how many riders make calls over say the past 100 rides, and then trying to calculate how efficient it might be to deviate a few floors either direction to grab someone close-by. It's an interesting hole to climb into.

Did you get the gig at google?

the problem is having particular expectations at the outcome, which is wrong. even after hiring, if i have a particular expectation how problems are to be solved, then that will lead to disappointment, micromanagement and disempowerment of my developers. i did use elevatorsaga in interviews with good results. having someone making such an unusual suggestion in an interview would be a plus for me. this person is thinking out of the box. and it would lead to a discussion of the difference of optimizing solutions for overall performance vs user expectations.

I didn’t. I tried again later in my career but ended up taking up Facebook’s offer before the final Google round.

I really like just asking "how do elevators work"?

It's so open ended and they can talk about anything from the algorithm, to the mechanical design of elevators, to the UI, to a high-level discussion of all the different components.

Really lets you know quickly which parts of systems candidates are interested in.

It's annoying that it doesn't highlight syntax errors. It's even worse than that because it's intercepting the syntax error for logging purpose and loses any informations. You get unrelated errors in the app's code.

I've always been fascinated with elevator algorithms. This is awesome!

An advanced level of this game should have you implement your logic with mechanical relays. Those relay banks are always fascinating

There should be a checkbox here to add a mirror to the ground floor waiting area. If memory serves me correctly, this significantly reduces the amount people complain about waiting because they will look at themselves and it won't feel as long.

elevator.goToFloor(1); elevator.goToFloor(2); elevator.goToFloor(0);

That (or a slight variation) works for the first couple of levels. Then it gets harder.

I was happy that my solution for level 4 was also accepted for level 5 and 6. Only a small tweak was needed for level 7, as now moves were counted instead of time.

The next level required no passenger to wait longer that a certain amount of time, and I would have had to trash half my program, so I quit for now.

Reply on news.ycombinator.com