Skip to content

Instantly share code, notes, and snippets.

@kalisjoshua
Last active December 10, 2021 21:07
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kalisjoshua/9c4b0246a2a339be2512 to your computer and use it in GitHub Desktop.
Save kalisjoshua/9c4b0246a2a339be2512 to your computer and use it in GitHub Desktop.
Elevator Saga - Solution for challenges 1 through 12; still need to work on better efficiency.
{
init: function(elevators, floors) {
var TOP_LEVEL = floors.length - 1;
floors.requestQueue = [];
/**/
function _padd(len, str, char) {
str = '' + str;
while(str.length < len) {str = str + char;}
return str;
}
// classic decorator pattern :)
elevators.forEach(function (elev) {
var original = elev.on;
elev.on = function (event, fn) {
original(event, function () {
console.log(
elev.indx,
' rQ [' + _padd(TOP_LEVEL, floors.requestQueue.join(), ' ') + ']' +
' btn [' +
floors.map(function (f, i) {
return [+!!f.buttonStates.down, +!!f.buttonStates.up].join('');
}).join() +
'] wait [' +
floors.map(function (f, i) {
return [_padd(2, f.waitTime.down, '0'), _padd(2, f.waitTime.up, '0')].join(' ');
}).join() +
'] elev [' +
elevators.map(function (e) {
return '{cur ' + e.currentFloor() +
' ind [' + [+!!e.goingDownIndicator(), +!!e.goingUpIndicator()].join('') + ']' +
' lF ' + _padd(6, e.loadFactor(), '0') +
' dQ [' + _padd(TOP_LEVEL, (e.destinationQueue.join() || ' '), ' ') + ']}';
}).join() + ']',
event,
arguments
);
fn.apply(elev, arguments);
});
};
});
floors.forEach(function (floor) {
var original = floor.on;
floor.on = function (event, fn) {
original(event, function () {
console.log(floor.level, event);
fn.apply(floor, arguments);
});
};
});
/**/
function _debugging() {
/** /
console.log.apply(console, arguments);
/**/
}
/** only add level if not already present in the queue
*/
function conditionalQueue(queue, level) {
if (queue.indexOf(level) === -1) {
queue.push(level);
}
return queue;
}
/** clean the requestQueue and return the nearest requested floor
*/
function dequeue(elev) {
/// optimization - find nearest floor to current in the requestQueue
floors.requestQueue = floors.requestQueue.reduce(function (a, f) {
if (floors[f].buttonStates.down || floors[f].buttonStates.up) {
a.push(f);
}
return a;
}, []);
if (elev) {
return floors.requestQueue.shift();
}
}
/** determine if the elevator is going in the direction
*/
function going(elev, direction, strict) {
var dn = elev.goingDownIndicator(),
up = elev.goingUpIndicator(),
// exclusive directions
x_dn = dn && !up && direction === 'down',
x_up = !dn && up && direction === 'up';
return x_dn || x_up || (!strict && dn && up);
}
function queueRequest(direction) {
var idle,
level = this.level;
this.waitTime[direction] = 1;
/// F OPTIMIZATION - (failed) add info about wait time to floor; allow skipping in passing_floor
/// 1. OPTIMIZATION - check to see if another elevator would satisfy this request as their next move
/*
1. down requested on floor 7
2. elevator 0 dispatched to 7
3. down requested on floor 6
4. elevator 1 dispatched to 6 (elevator 0 would be better off serving floor 6 down request)
*/
/// 2. OPTIMIZATION - find elevator with shortest destinationQueue and will stop closest to level
/// 3. OPTIMIZATION - get rid of requestQueue and use "live reads" from the floors to determine what to do
/// 4. optimization - look for elevators already going to floor with future direction
/// 5. optimization - look for nearby elevators
idle = elevators.reduce(function (a, e) {
/// optimization - factor in distance?
/// factor in loadFactor and direction
return !a && !e.destinationQueue.length && going(e, direction) && !e.loadFactor() ? e : a;
}, false);
if (idle) {
if (floors.requestQueue.length) {
conditionalQueue(floors.requestQueue, level);
level = floors.requestQueue.shift(); // bug - not necessarily the most efficient; could be the furthest from level
}
_debugging(level, 'pushed onto', idle.indx, 'because', this.level, 'requested');
idle.destinationQueue.push(level);
idle.checkDestinationQueue();
} else {
conditionalQueue(floors.requestQueue, level);
}
}
/** remove a the number from the queue
*/
function removeFrom(queue, num) {
return queue.filter(function (x) {return x !== num;});
}
elevators.forEach(function (elev, indx) {
elev.indx = indx;
elev.on('floor_button_pressed', function (level) {
conditionalQueue(elev.destinationQueue, level);
elev.trigger('queue_maintenance');
elev.trigger('update_indicators');
/// only remove from requestQueue if no more requests on floor
if (!floors[level].buttonStates.down && !floors[level].buttonStates.up) {
floors.requestQueue = removeFrom(floors.requestQueue, level);
}
if (!floors[level].buttonStates.down) {
floors[level].waitTime.down = 0;
}
if (!floors[level].buttonStates.up) {
floors[level].waitTime.up = 0;
}
});
elev.on('idle', function () {
var dest = dequeue(elev);
if (dest != null) {
_debugging(elev.indx, 'sent to', dest, 'from request queue');
elev.destinationQueue.push(dest);
elev.checkDestinationQueue();
elev.trigger('update_indicators');
} else {
/// OPTIMIZATION - go where the fewest elevators are to be ready for next request; add token to denote transitory destination
/** /
console.log(elevators.reduce(function (a, e) {
var cur = e.currentFloor(),
nxt;
nxt = cur +
(cur !== 0 && going(e, 'down', 'strict') ? -1 : 0) +
(cur !== TOP_LEVEL && going(e, 'up', 'strict') ? 1 : 0);
conditionalQueue(a, cur);
conditionalQueue(a, nxt);
return a;
}, []).sort());
/**/
/// optimization - go to defined range for elevator to wait for requests; prefer range of floors to pick up from
_debugging(elev.indx, 'idle with nowhere to go');
//elev.goToFloor(elev.indx % floors.length, true);
elev.trigger('update_indicators');
}
});
elev.on('passing_floor', function (level, direction) {
var availableCapacity = elev.loadFactor() < .50,
correctDirection = going(elev, direction),
passengersWaiting = !!floors[level].buttonStates[direction],
uniquelyVisiting;
/// only visit a floor if no other elevators are already scheduled to stop at that floor
uniquelyVisiting = elevators.every(function (e) {
return e.destinationQueue.indexOf(level) === -1 && going(e, direction);
});
_debugging('uniquelyVisiting', uniquelyVisiting);
if (!uniquelyVisiting) {
/// optimization, clear floor from other elevators with same destination and no loadFactor
uniquelyVisiting = !!elevators.reduce(function (a, e) {
if (e.destinationQueue[0] === level && e.loadFactor === 0) {
_debugging('needless stops', e);
e.destinationQueue.shift();
e.checkDestinationQueue();
a.push(e);
}
return a;
}, []).length;
}
/// OPTIMIZATION - check if elevator is closest to neighbor floor, beyond destination, with pending request in upcoming direction
if (passengersWaiting && correctDirection && availableCapacity && uniquelyVisiting) {
// optimization - check to make sure there isn't a request in the other direction before removing from requestQueue
//floors.requestQueue = removeFrom(floors.requestQueue, level); // handled in stopped_at_floor and floor_button_pressed
elev.trigger('queue_maintenance', level); // ensure level isn't in the queue more than once
elev.goToFloor(level, true);
}
});
elev.on('queue_maintenance', function (level) {
if (level != null) {
elev.destinationQueue = removeFrom(elev.destinationQueue, level);
}
elev.destinationQueue.sort();
if (elev.goingDownIndicator()) {
elev.destinationQueue.reverse();
}
elev.checkDestinationQueue();
});
elev.on('stopped_at_floor', function (level) {
elev.trigger('queue_maintenance', level);
elev.trigger('update_indicators');
if (going(elev, 'down') && going(elev, 'up')) {
floors[level].waitTime = {down: 0, up: 0};
floors.requestQueue = removeFrom(floors.requestQueue, level);
}
});
elev.on('update_indicators', function () {
var current = elev.currentFloor(),
emptyQueue = !elev.destinationQueue.length;
elev.goingUpIndicator(emptyQueue || current === 0 || current !== TOP_LEVEL && +elev.destinationQueue[0] > current);
elev.goingDownIndicator(emptyQueue || current === TOP_LEVEL || current !== 0 && +elev.destinationQueue[0] < current);
});
});
floors.forEach(function (floor, indx) {
floor.waitTime = {down: 0, up: 0};
floor.on('down_button_pressed', queueRequest.bind(floor, 'down'));
floor.on('up_button_pressed', queueRequest.bind(floor, 'up'));
});
},
update: function(dt, elevators, floors) {
floors.forEach(function (f) {
f.waitTime.down && ++f.waitTime.down;
f.waitTime.up && ++f.waitTime.up;
});
/// optimization - (cheat) check a waiting time for each floor and direction and if it
/// gets close to time threashhold find the nearest elevator and force it to pick people
/// up even if it isn't going in that direction; this may adversely affect performance.
}
}

Challenge 18 Stats

Stat Number
Speed 21x
Transported 2971
Elapsed time 2000s
Transported/s 1.49
Avg waiting time 14.5s
Max waiting time 54.6s
Moves 22460
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment