5 ms·

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 c

by arnarbi 11y ago

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.

noir_lord 11y ago
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 :).
nosequel 11y ago
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.
- philsnow 11y ago
  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.
mshang0 11y ago
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.
seivan 11y ago
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/GameplayKit/Reference/GKRuleSystem_Class/index.html#//apple_ref/occ/instp/GKRuleSystem/facts https://developer.apple.com/library/ios/documentation/Gamepl...
- seivan 11y ago
  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.
  - hvidgaard 11y ago
    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.
    - seivan 11y ago
animal531 11y ago
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.

by arnarbi 11y ago

noir_lord 11y ago

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

nosequel 11y ago

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.

philsnow 11y ago
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.

mshang0 11y ago

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.

seivan 11y ago

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/GameplayKit/Reference/GKRuleSystem_Class/index.html#//apple_ref/occ/instp/GKRuleSystem/facts https://developer.apple.com/library/ios/documentation/Gamepl...

seivan 11y ago
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.
- hvidgaard 11y ago
  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.
  - seivan 11y ago

animal531 11y ago

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.