Skip to content

Instantly share code, notes, and snippets.

@nexdrew
Created February 7, 2019 16:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nexdrew/f94497a8c6a6ffe3b83950f7d8d159ef to your computer and use it in GitHub Desktop.
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
{
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