Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Elevator dispatch algorithm in javascript
/*
Elevator algorithm
by Ben Buckman, for a job interview process 7/18/12
*/
// == INSTRUCTIONS ==
// Iterate through the elevators list and return the elevator that is:
// closest, AND
// moving in the right direction (or idle),
// - [ben] this could mean 2 things:
// 1) moving toward the passenger.
// - but then could overshoot. we don't know w/o the elevator's current *destination*, which is not available.
// 2) previous + moving in the SAME direction as the passenger wants to go
// - going with #2 for this. has to be approaching and already heading in the same direction.
// - (result is, dispatched elevator will often not actually be the most efficient, if the current destination were known)
// AND hasn't passed the requestFloor
//
var DOWN = -1;
var IDLE = 0;
var UP = 1;
function Elevator(floor, direction)
{
this.floor = floor;
this.direction = direction;
}
var elevators = [
new Elevator(1, IDLE),
new Elevator(7, DOWN),
new Elevator(9, UP),
new Elevator(10, DOWN)
];
function findElevator(requestFloor, requestDirection)
{
// holder for integer pointing to position of elevator in the array.
// this is for best fit, approaching passenger & going in same direction
// (given unknown destination. see above)
var bestFit = null;
// fallback, simply the closest.
// start w/ a random one, so in the event that all are equally good/bad, it distributes evenly.
var closest = Math.floor(Math.random() * elevators.length);
// for each elevator, check if it's an efficient dispatch and how far away it is
elevators.forEach(function(elevator, elevatorInd) {
// is elevator approaching the passenger?
// (implies, not yet overshot)
// if going down, want elevator floor to be > passenger floor. (P - E < 0)
// if going up, want elevator floor to be < passenger floor. (P - E > 0)
// same floor (=) is also ok. (assuming elevator records the next floor as soon as it starts moving toward it.)
var approachingPassenger = (
(elevator.direction === UP && elevator.floor <= requestFloor) ||
(elevator.direction === DOWN && elevator.floor >= requestFloor) ||
elevator.direction === IDLE ); // requestDirection doesn't matter if it's idle
// (we're not worrying about additional energy/inefficiency from the accelaration of an idle elevavor.)
// already going in the same direction as the passenger wants to go?
// (not neces most efficient, but w/o knowing the current destination, it's the best available.)
var sameDirection = requestDirection === elevator.direction || elevator.direction === IDLE;
// how far away? all else being equal, closer is better.
var distance = Math.abs(requestFloor - elevator.floor);
// best fit so far (good & closest) or first good fit
if (approachingPassenger && sameDirection &&
(bestFit === null || distance < Math.abs(requestFloor - elevators[bestFit].floor)) ) {
bestFit = elevatorInd;
}
// fallback, closest regardless of efficiency.
if (distance < Math.abs(requestFloor - elevators[closest].floor)) {
closest = elevatorInd;
}
}); //each
return bestFit !== null ? bestFit : closest;
}
////////////////////////////////////////////////////////
// test
Elevator.prototype.toString = function(){
return "Elevator at floor " + this.floor + " " + (this.direction === IDLE ? "idle" : (this.direction > 0 ? "going up" : "going down"));
};
console.log("For 2 going up:", elevators[ findElevator(2, UP) ].toString() ); // 1-idle
console.log("For 2 going down:", elevators[ findElevator(2, DOWN) ].toString() ); // 1-idle
console.log("For 12 going down:", elevators[ findElevator(12, DOWN) ].toString() );
// the close ones aren't both approaching and going in the same direction,
// so 1-idle is actually the best fit
console.log("For 12 going up:", elevators[ findElevator(12, UP) ].toString() ); // 9-up (perfect)
console.log("For 5 going up:", elevators[ findElevator(5, UP) ].toString() ); // 1-idle (same as 12-down)
console.log("For 5 going down:", elevators[ findElevator(5, DOWN) ].toString() ); // 7-down (perfect)
console.log("For 8 going up:", elevators[ findElevator(8, UP) ].toString() ); // 1-idle
console.log("For 8 going down:", elevators[ findElevator(8, DOWN) ].toString() ); // 10-down (perfect)
console.log("For 7 going up:", elevators[ findElevator(7, UP) ].toString() ); // 1-idle
console.log("For 7 going down:", elevators[ findElevator(7, DOWN) ].toString() ); // 7-down (perfect)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment