Hacker News Reader

Comment by arnarbi | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com