Which I'm now closing as I lost too much time to this the first time I saw it.
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.
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.
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.
I think it's the programmer equivalent of https://xkcd.com/356/
- Why currentFloor() is a function not a property?
- Why both goingUpIndicator() and goingDownIndicator() instead of .direction property?
- Why name destinationDirection() instead of
- 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.
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.
* 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.
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.
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.
> 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
So yes I think I could program an elevator. And yes I think I could do it better than the shit it currently is.
cool. that probably put a bigger smile on my face than it should've, but still cool.
PNs are a great way of modelling the concurrent state handling required for something like this.
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.
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.
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.
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 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.
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.
* 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
Long story short: a simple, rules-based algorithm defeated my best efforts at having multiple elevators working together to coordinate their action.
which introduces a whole new set of complexity.
It would be pretty fun if someone were to make a version that supported this. :)
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!
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!
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.
Because, you know, I really have no work I need to accomplish this year...
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.
If you know a bit about boolean algebra, it is easy to learn ladder and program an elevator the real way. :)
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.