Created
February 7, 2019 16:34
-
-
Save nexdrew/f94497a8c6a6ffe3b83950f7d8d159ef to your computer and use it in GitHub Desktop.
See how bad I can fail the Elevator Saga: https://play.elevatorsaga.com/#challenge=18
This file contains 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) { | |
const numVators = elevators.length | |
// const numFloors = floors.length | |
const FILTER_BEFORE = true | |
const FILTER_AFTER = true | |
const AGGRESSIVE_FILTER = false | |
const STOP_ZERO = true | |
const IDLE_ZERO = true | |
const DIRECT_ZERO = true | |
const BEST_MATCH = false | |
const PITSTOP_REMOVAL = true | |
const VERBOSE = false | |
const JUNK = false | |
function getFloor (n) { | |
return floors[n] | |
} | |
function getDir (a, b) { | |
return a > b ? 'down' : 'up' | |
} | |
class Vator { | |
constructor (e, i) { | |
this.index = i | |
this.name = String.fromCharCode(65 + i) | |
this.e = e | |
e.on('idle', this.onIdle.bind(this)) | |
e.on('floor_button_pressed', this.onFBP.bind(this)) | |
e.on('passing_floor', this.onPassingFloor.bind(this)) | |
e.on('stopped_at_floor', this.onStopped.bind(this)) | |
this.goingNowhere() | |
// this.madeFirstMove = false | |
} | |
setOthers (vators) { | |
this.others = vators.filter(v => v !== this) | |
} | |
handleFloor (floorNum) { | |
this.gtf(floorNum, true) | |
this.others.forEach(v => v.onFloorHandledByOther(floorNum, this.ind)) | |
} | |
futureDir (n, q) { | |
q = q || this.q() | |
const i = q.findIndex(x => x === n) | |
if (i === -1) return null | |
let priorn = i === 0 ? this.cf() : q[i - 1] | |
return getDir(priorn, n) | |
} | |
onFloorHandledByOther (floorNum, ind) { | |
// potentially remove floorNum from q | |
if (!PITSTOP_REMOVAL) return null | |
const q = this.q() | |
if (!this.hasDestButtonPressed(floorNum) && q.includes(floorNum) && this.futureDir(floorNum, q) === ind) { | |
// console.log(`${this.name} removing floor ${floorNum} from queue`) | |
this.e.destinationQueue = q.filter(x => x !== floorNum) | |
this.e.checkDestinationQueue() | |
} | |
} | |
hasDestButtonPressed (n) { | |
return this.e.getPressedFloors().some(pf => pf === n) | |
} | |
hasSpace () { | |
return (1 - (1 / this.e.maxPassengerCount())) > this.e.loadFactor() | |
} | |
matchingInd (bs) { | |
return this.ind.includes(bs) | |
} | |
dir (q) { // check q.length BEFORE calling this! | |
q = q || this.q() | |
if (typeof q[0] !== 'number') return this.e.destinationDirection() | |
return getDir(this.cf(), q[0]) | |
} | |
isMovingToward (n, strict) { | |
const q = this.q() | |
if (!strict && !q.length) return true | |
const dir = this.dir(q) | |
if (dir === 'up' && this.cf() < n) return true | |
else if (dir === 'down' && this.cf() > n) return true | |
return false | |
} | |
goingNowhere () { | |
this.ind = 'up/down' | |
this.e.goingUpIndicator(true) | |
this.e.goingDownIndicator(true) | |
} | |
goingUp () { | |
this.ind = 'up' | |
this.e.goingUpIndicator(true) | |
this.e.goingDownIndicator(false) | |
} | |
goingDown () { | |
this.ind = 'down' | |
this.e.goingDownIndicator(true) | |
this.e.goingUpIndicator(false) | |
} | |
toggleInd () { | |
if (this.ind === 'up') this.goingDown() | |
else if (this.ind === 'down') this.goingUp() | |
} | |
q () { | |
return this.e.destinationQueue | |
} | |
gtf (n, direct) { | |
this.e.goToFloor(n, direct) | |
} | |
cf () { | |
return this.e.currentFloor() | |
} | |
nearestApex () { | |
const q = this.q() | |
if (q.length === 0) return null | |
if (q.length === 1) return 0 | |
let i = 1 | |
let pdir = getDir(q[i - 1], q[i]) | |
let ndir = pdir | |
while (i < q.length && pdir === ndir) { | |
i++ | |
pdir = ndir | |
ndir = getDir(q[i - 1], q[i]) | |
} | |
// let i = 0, pdir, ndir | |
// do { | |
// i++ | |
// pdir = ndir | |
// ndir = getDir(q[i - 1], q[i]) | |
// } while (pdir === ndir) | |
return i < q.length ? i - 1 : q.length - 1 | |
} | |
addPickup (n, bs, possiblyDeferToOthers) { | |
// this.madeFirstMove = true | |
if (this.ind === 'up/down') { | |
if (bs === 'up') this.goingUp() | |
else this.goingDown() | |
} | |
this.optimus(n, bs, possiblyDeferToOthers) | |
} | |
filterToActive (q) { | |
return q.filter(x => { | |
if (this.hasDestButtonPressed(x)) return true | |
const bss = getFloor(x).buttonStates | |
if (AGGRESSIVE_FILTER) { | |
// if (this.ind === 'up' && !bss.up) return false | |
// if (this.ind === 'down' && !bss.down) return false | |
const fd = this.futureDir(x, q) | |
if (!bss.up && fd === 'up') return false | |
if (!bss.down && fd === 'down') return false | |
} | |
// return bss.up || bss.down || this.hasDestButtonPressed(x) | |
return !!bss.up || !!bss.down | |
}) | |
} | |
optimus (n, bs, possiblyDeferToOthers) { | |
// TODO if possiblyDeferToOthers, see if n (with anticipated bs) is already on other q; if so, do not add n to this q | |
if (JUNK && possiblyDeferToOthers) { | |
let o = this.others.find(o => { | |
// let fd = o.futureDir(n) | |
return bs === o.futureDir(n) && o.q().includes(n) | |
}) | |
if (o) { | |
console.log(`${this.name} deferring floor ${n} ${bs} to vator ${o.name}: ${o.q().join('-')}`) | |
return | |
} | |
} | |
let q = this.q() | |
if (!q.length) return this.gtf(n) | |
if (this.isMovingToward(n) && this.matchingInd(bs)) { | |
// add n before the fold | |
const foldIndex = this.nearestApex() | |
const beforeFold = q.slice(0, foldIndex + 1) | |
const afterFold = q.slice(foldIndex + 1) | |
// const dir = this.dir(q) | |
this.e.destinationQueue = Array.from(new Set(beforeFold.concat(n))).sort((a, b) => { | |
if (bs === 'up') { | |
// sort asc | |
return a - b | |
} else { | |
// sort desc | |
return b - a | |
} | |
}).concat(afterFold) | |
if (FILTER_BEFORE) this.e.destinationQueue = this.filterToActive(this.e.destinationQueue) | |
// console.log(`${this.name} n: ${n}, q: ${q.join('-')}, bs: ${bs}, dir: ${dir}, fi: ${foldIndex}, bf: ${beforeFold.join('-')}, af: ${afterFold.join('-')}, dq: ${this.e.destinationQueue.join('-')}`) | |
this.e.checkDestinationQueue() | |
if (VERBOSE) console.log(`${this.name} ${this.ind} optimized: ${this.e.destinationQueue.join('-')}`) | |
} else { | |
// add n after the fold | |
this.e.destinationQueue = Array.from(new Set(this.e.destinationQueue.concat(n))) | |
if (FILTER_AFTER) { | |
this.e.destinationQueue = this.filterToActive(this.e.destinationQueue) | |
} | |
this.e.checkDestinationQueue() | |
if (VERBOSE) console.log(`${this.name} ${this.ind} NOT optimized: ${this.e.destinationQueue.join('-')}`) | |
} | |
} | |
onStopped (floorNum) { | |
// if bottom floor, make sure we're going up | |
// if top floor, make sure we're going down | |
if (floorNum === 0 && this.e.goingDownIndicator()) this.goingUp() | |
else if (floorNum === (floors.length - 1) && this.e.goingUpIndicator()) this.goingDown() | |
// detect other dir changes and set ind | |
const q = this.q() | |
if ( | |
q.length && | |
!this.matchingInd(getDir(floorNum, q[0])) | |
) { | |
// console.log(`${this.name} switch from ${this.ind} to ${getDir(floorNum, q[0])}`) | |
return this.toggleInd() | |
} | |
// if q is empty and no one getting on, treat as idle | |
const bss = getFloor(floorNum).buttonStates | |
if ( | |
// this.madeFirstMove && | |
this.ind !== 'up/down' && | |
q.length === 0 && | |
!bss.up && | |
!bss.down | |
) { | |
// do whatever idle would do | |
// console.log(`${this.name} going nowhere from stop`) | |
this.goingNowhere() | |
if (STOP_ZERO) this.gtf(0, DIRECT_ZERO) | |
} | |
} | |
onIdle () { | |
// if (!this.madeFirstMove) return false | |
if (this.ind !== 'up/down') this.goingNowhere() | |
// console.log(`${this.name} going nowhere from idle`) | |
// TODO try staggering floors ??? | |
if (IDLE_ZERO) this.gtf(0, DIRECT_ZERO) | |
} | |
onFBP (floorNum) { | |
// do not change ind, optimize q | |
// this.madeFirstMove = true | |
this.optimus(floorNum, this.ind, false) | |
} | |
onPassingFloor (floorNum, dir) { | |
/* | |
passing floor vator result | |
n dir bs cf ind result | |
- ---- ---- - ---- ------ | |
1 up up 0 up stop | |
1 up up 0 down pass | |
1 up down 0 up pass | |
1 up down 0 down pass | |
1 down up 2 up pass | |
1 down up 2 down pass | |
1 down down 2 up pass | |
1 down down 2 down stop | |
*/ | |
if ( | |
// dir === this.ind && | |
this.matchingInd(dir) && | |
this.hasSpace() && | |
// getFloor(floorNum).buttonStates[this.ind] | |
getFloor(floorNum).buttonStates[dir] | |
) { | |
// console.log(`${this.name} pit stop ${floorNum} ${dir}`) | |
this.handleFloor(floorNum) | |
} | |
} | |
} | |
const vators = elevators.map((e, i) => new Vator(e, i)) | |
vators.forEach(v => { | |
v.setOthers(vators) | |
}) | |
function randomBool () { | |
return Math.random() >= 0.5 | |
} | |
function getIdleVator () { | |
if (randomBool()) { | |
for (let i = 0; i < vators.length; i++) { // ascending | |
if (vators[i].ind === 'up/down') return vators[i] | |
} | |
} else { | |
for (let i = vators.length - 1; i >= 0; i--) { // descending | |
if (vators[i].ind === 'up/down') return vators[i] | |
} | |
} | |
return null | |
} | |
function getBestMatchVator (n, bs) { | |
// closest vator that has space with "ind containing bs" moving towards n | |
return vators.filter(v => { | |
// TODO how to anticipate future space ?? | |
return v.matchingInd(bs) && v.isMovingToward(n, true) && v.hasSpace() | |
}).sort((a, b) => { | |
return Math.abs(a.cf() - n) - Math.abs(b.cf() - n) // adist - bdist | |
})[0] | |
} | |
function getShortestQVator () { | |
return vators.sort((a, b) => { | |
return a.q().length - b.q().length | |
})[0] | |
} | |
function getClosestTailVator (n) { | |
return vators.sort((a, b) => { | |
const aq = a.q() | |
const bq = b.q() | |
const atail = aq.length ? aq[aq.length - 1] : a.cf() | |
const btail = bq.length ? bq[bq.length - 1] : b.cf() | |
return Math.abs(atail - n) - Math.abs(btail - n) | |
})[0] | |
} | |
function getClosestVator (n) { | |
return vators.sort((a, b) => { | |
return Math.abs(a.cf() - n) - Math.abs(b.cf() - n) | |
})[0] | |
} | |
function allVatorsBusy () { | |
const busy = vators.filter(v => v.q().length > 2) | |
return busy.length === numVators | |
} | |
function floorNeedsService (n, bs) { | |
let v, how | |
if (numVators === 1) v = vators[0] // 1. only | |
if (!v) { | |
v = getIdleVator() // 2. idle | |
if (v) how = 'idle' | |
} | |
if (!v && BEST_MATCH) { | |
v = getBestMatchVator(n, bs) // 3. best match | |
if (v) how = 'best' | |
} | |
// if (!v) v = allVatorsBusy() ? getClosestTailVator(n) : getShortestQVator() | |
// if (!v) v = allVatorsBusy() ? getShortestQVator() : getClosestTailVator(n) // 4. just pick one | |
if (!v) { | |
const allBusy = allVatorsBusy() | |
if (allBusy) v = getShortestQVator() | |
if (v) how = 'shortest' | |
if (!v) v = getClosestTailVator(n) | |
how = 'closest' | |
} | |
// if (!v && PREFER_CLOSEST_TAIL) v = getClosestTailVator(n) | |
// if (!v && PREFER_CLOSEST_CF) v = getClosestVator(n) | |
// if (!v) v = getShortestQVator() | |
console.log(`${n} ${bs} pressed, chose ${how} vator ${v.name}: ${v.q().join('-')}`) | |
v.addPickup(n, bs, true) | |
} | |
floors.forEach(f => { | |
f.on('up_button_pressed', () => { | |
floorNeedsService(f.floorNum(), 'up') | |
}) | |
f.on('down_button_pressed', () => { | |
floorNeedsService(f.floorNum(), 'down') | |
}) | |
}) | |
}, | |
update: function (dt, elevators, floors) {} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment