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 |
Last active
December 10, 2021 21:07
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
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. | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment