Donald Knuth's The Art of Computer Programming has, in its first volume, a lengthy section on simulating an elevator. It is a single regular elevator (nothing "special" going on as in the post here), but even so, as he tries to make things precise, you realize how much detail is involved, and get some appreciation for the task of programming.
It occupies about 15 pages (plus several pages of exercises and solutions). Knuth started working on TAOCP when he was a PhD student at Caltech:
> The program developed below simulates the elevator system in the Mathematics building of the California Institute of Technology. The results of such a simulation will perhaps be of use only to people who make reasonably frequent visits to Caltech; and even for them, it may be simpler just to try using the elevator several times instead of writing a computer program. […]
> The algorithm we will now study may not reflect the elevator’s true principles of operation, but it is believed to be the simplest set of rules that explain all the phenomena observed during several hours of experimentation by the author during the writing of this section. […]
> The elevator system described above is quite complicated by comparison with other algorithms we have seen in this book, but the choice of a real-life system is more typical of a simulation problem than any cooked-up “textbook example” would ever be.
It ends with:
> It is hoped that some reader will learn as much about simulation from the example above as the author learned about elevators while the example was being prepared.
And one of the exercises adds:
> It is perhaps significant to note that although the author had used the elevator system for years and thought he knew it well, it wasn’t until he attempted to write this section that he realized there were quite a few facts about the elevator’s system of choosing directions that he did not know. He went back to experiment with the elevator six separate times, each time believing he had finally achieved a complete understanding of its modus operandi. (Now he is reluctant to ride it for fear that some new facet of its operation will appear, contradicting the algorithms given.) We often fail to realize how little we know about a thing until we attempt to simulate it on a computer.
On one of the better teams I’ve worked with the water-cooler activity was trying to come up with an algorithm to describe the behaviour of the Coca Cola machine in the kitchen.
It was one of those clear plexiglass front machines where after punching in the coordinates of the item you wanted, a mechanical arm would move to the coordinates, take a drink, and place it in the delivery bay at the bottom.
While it would always get the drink you wanted, it would rarely go to the exact coordinates you specified. Ie, if there were three columns filled with coke, and you punched in the coordinates for the one on the far right, the arm may take a can from the center, or left column.
We would often wager a can of coke (“if I can’t find anything wrong in your PR, I’ll buy you a coke”), so we were perhaps drinking more soft drink than was medically advisable, but in our defence:
a) the machine was really cheap (AUD$1 or $1.5)
b) it was an excellent 10min break game
Eventually we thought they had it figured out we would gather and make our predictions, but occasionally there would be an upset that would throw a wrench into the model.
We got to a point where we just couldn’t reconcile the machine behaviour with any kind of coherent set of rules, then one morning we saw the delivery guy stocking it.
After chatting with him we learned our algorithm was more or less correct, but the internal state of the machine was prone to getting out of sync with the actual stock levels, so it would make the “wrong” choice near the end of the refill cycle. Then he gave the engineer talking to him a free energy drink (source of stock problems right there haha)
While we were no Knuths, I love that these kinds of games are so universal among engineers/devs. In fact, if I can get someone to tell me a similar story of theirs in an interview (for a technical
role) I’m much more likely to consider them for the position. Curiosity is a powerful trait for a developer.
…and the (simple) algorithm for the machine is:
Take from the column with the most stock, if there are multiple columns with the same stock level, take from the column furthest to the left.
> We often fail to realize how little we know about a thing until we attempt to simulate it on a computer.
"Programming is a good medium for expressing poorly understood and sloppily formulated ideas" is definitely on the list of my favourite programming quotes.
I recently tried to implement a simple version of an existing board game ... boy did all those "if you have this card and I have that card except for that special condition and also none of this matters if you play this card" bite me in the end ...
> We often fail to realize how little we know about a thing until we attempt to simulate it on a computer.
I'll often write out with pen and paper of how I think the flow of a model will go, it's always fascinating how much that diagram changes once I actually build the model. There are both drastic simplifications and increases in nuance based on experience with the system being modeled and where divergences occur.
Same here. And this also works for existing code. When I start diagramming some complex bit of flow, I'm often surprised by how little I actually understood it. I think translating to a different medium of expression forces you to actually read the code, instead of just skimming it and thinking you understand it.
Hm. I've always thought that the algorithm of operation of a single elevator is fairly simple? While passing each floor, if a button of that floor was pressed (is lit up), or if the button of the direction it's going on that floor is pressed, then stop. If the elevator is not in use and someone presses any call button, go to that floor. That's mostly it. At least that's how I have that algorithm in my head.
Now, if there are multiple elevators but a single set of up/down buttons for them on each floor, that's where things get really complex really fast.
What if you have, say, a 7 story building and someone on each floor presses the call button at around the same time? Do you send the elevator to each floor based on the time the button was pressed, or do you maybe go to the top floor and pick everyone up on the way down, or do something else? The algorithm probably also needs to consider max weight/occupancy. I think even for a single elevator it's quite complex, assuming you want operation to be both fair and efficient.
I'd assume that it would first go to the floor where the button was pressed first, and subsequently collect everyone in the direction it'll go from there. Because that's actually what I feel some elevators are doing because you wait for one for ages. Some certainly do work like that, but newer ones are probably indeed smarter.
Then there's the curiously simple system that you'd find in Soviet buildings, the kind built out of prefab concrete panels. The elevator doesn't allow to be called while it's in use, period. The call buttons on all floors light up while it's in use, and you have to wait for the light to go out before the button would do anything. The buttons inside also only work with doors open (I think?) and you could only press one at a time. The controller for these is most probably made out of relays or something similar.
Elevators in former Soviet Union (even those installed long after its disintegration) are quite dumb compared to Western and SE Asia installations in tall buildings.
I stayed in a tall hotel in Dubai (not sure how much of Asia UAE is) for a while and it still took a minute or two for an elevator to arrive. Though they were freakishly fast, Russian ones now feel like they're crawling.
- The elevator has a "home floor" (the lobby/ground floor) that it returns to by default, if it has nothing else to do. (Apparently many elevators do this; see "Up peak" in the linked post or on Wikipedia https://en.wikipedia.org/w/index.php?title=Elevator&oldid=10... .)
- To set up such a discrete event simulation on a computer, you also need to model timing (how much time it takes to open and close doors, to move between floors with acceleration/deceleration, etc), and users (how many arrive at each floor and when, and where they want to go to, how long they wait before giving up).
- So you end up with a fair amount of state (the "up" and "down" call buttons on each floor, the buttons inside the elevator, whether the elevator is going up or down or neither) and control (when to open or close doors: what to do if someone presses a button while the doors are closing, etc).
- The purpose of that section of TAOCP is to show in detail how to use doubly-linked lists to simulate such things on a computer (which here means getting down to the level of memory layout and assembly code: MIX/MMIX). So overall there are ~5.5 pages of describing the algorithm, ~1.5 pages for memory layout etc, ~7 pages of assembly code, and a page of higher-level stuff mentioning programming languages and profilers etc.
It occupies about 15 pages (plus several pages of exercises and solutions). Knuth started working on TAOCP when he was a PhD student at Caltech:
> The program developed below simulates the elevator system in the Mathematics building of the California Institute of Technology. The results of such a simulation will perhaps be of use only to people who make reasonably frequent visits to Caltech; and even for them, it may be simpler just to try using the elevator several times instead of writing a computer program. […]
> The algorithm we will now study may not reflect the elevator’s true principles of operation, but it is believed to be the simplest set of rules that explain all the phenomena observed during several hours of experimentation by the author during the writing of this section. […]
> The elevator system described above is quite complicated by comparison with other algorithms we have seen in this book, but the choice of a real-life system is more typical of a simulation problem than any cooked-up “textbook example” would ever be.
It ends with:
> It is hoped that some reader will learn as much about simulation from the example above as the author learned about elevators while the example was being prepared.
And one of the exercises adds:
> It is perhaps significant to note that although the author had used the elevator system for years and thought he knew it well, it wasn’t until he attempted to write this section that he realized there were quite a few facts about the elevator’s system of choosing directions that he did not know. He went back to experiment with the elevator six separate times, each time believing he had finally achieved a complete understanding of its modus operandi. (Now he is reluctant to ride it for fear that some new facet of its operation will appear, contradicting the algorithms given.) We often fail to realize how little we know about a thing until we attempt to simulate it on a computer.