RSR

Every submission is public. That is the point — the interesting part is how somebody else solved it.

1// RSR — Relative System Response, the algorithm Otis patented.2//3// LOOK decides what order one car visits its stops in. RSR is a different kind of4// idea: it decides *which car goes*, by scoring every car against every lit button5// and taking the lowest score. The stop ordering underneath is still a LOOK sweep.6//7//   score = time to reach the caller8//         + penalty for how busy the car already looks9//         + penalty if another car is already going there the same way10//         - bonus if the car is already heading that way and the call is ahead of it11//         - bonus if the car is idle and nearby12//         - bonus if the car has nothing aboard13//14// Lower is better. The two penalties are what stop every car chasing the same call15// and arriving in a convoy, which is the failure mode of naive nearest-car.16//17// Nothing tells you how many people are in a lift, or how many are waiting. But a18// full car leaves a trace: it answers a call, and the button comes straight back on.19// This one watches for that and stops trusting a car for a while afterwards, which20// is most of what a load sensor would have bought it.21//22// The whole assignment is recomputed every few seconds rather than every tick, so a23// call can be handed to a better car as conditions change — but not so often that24// cars thrash between destinations and never arrive anywhere.2526const SECONDS_PER_FLOOR = 0.627const SECONDS_PER_STOP = 52829const BUSY_PENALTY = 1.8          // per floor already requested from inside30const BUNCHING_PENALTY = 22       // another car is already going there, the same way31const DIRECTION_BONUS = 9         // already sweeping that way, and the call is ahead32const IDLE_NEARBY_BONUS = 14      // sitting doing nothing within two floors33const EMPTY_BONUS = 6             // nothing aboard, so it will not fill up en route34const REOPTIMISE_EVERY = 5        // seconds35const DISTRUST_SECONDS = 12       // how long to doubt a car we think just filled up36const DISTRUST_PENALTY = 40       // heavy, but not a ban — it may still be the only car3738export default {39  setup(building) {40    this.top = building.floors - 141    this.heading = new Map()42    this.assigned = new Map()    // "floor:direction" -> car id43    this.served = new Map()      // car id -> the call it has just answered44    this.distrust = new Map()    // car id -> time until we stop believing it has room45    this.lastPass = -Infinity46  },4748  // Remember what this car just answered, so the next few ticks can tell us whether49  // it actually cleared the landing or filled up and left people standing.50  stop({ elevator, floor, car }, world) {51    this.served.set(elevator, { floor, direction: car.indicated, at: world.time })52  },5354  tick(world) {55    const cars = world.elevators.filter((car) => !car.outOfService)56    if (cars.length === 0) return5758    const byId = new Map(cars.map((car) => [car.id, car]))59    const live = new Set(world.calls.map((call) => call.floor + ':' + call.direction))6061    // Did anybody we just served put their button straight back on? If so that car62    // went away full, and we should stop offering it work for a bit.63    for (const [carId, stop] of [...this.served]) {64      if (world.time - stop.at > 2) {65        this.served.delete(carId)66        continue67      }68      if (stop.direction && live.has(stop.floor + ':' + stop.direction)) {69        this.distrust.set(carId, world.time + DISTRUST_SECONDS)70        this.served.delete(carId)71      }72    }7374    // Forget calls that have been answered, and cars that have gone out of service.75    for (const key of [...this.assigned.keys()]) {76      if (!live.has(key) || !byId.has(this.assigned.get(key))) this.assigned.delete(key)77    }7879    // A full re-optimisation clears the slate; otherwise only brand new calls get80    // assigned, and everything already promised to a car stays promised.81    const reoptimise = world.time - this.lastPass >= REOPTIMISE_EVERY82    if (reoptimise) {83      this.lastPass = world.time84      this.assigned.clear()85    }8687    for (const call of world.calls) {88      const key = call.floor + ':' + call.direction89      if (this.assigned.has(key)) continue9091      let best = null92      let bestScore = Infinity93      let fallback = null94      let fallbackLoad = Infinity9596      for (const car of cars) {97        const committed = car.pressed.length + this.promised(car.id)98        if (committed < fallbackLoad) {99          fallbackLoad = committed100          fallback = car101        }102        // Do not keep loading a car that has already promised a building's worth of103        // work. With no load reading, this cap is the only brake there is.104        if (committed >= car.capacity) continue105106        const score = this.score(car, call, cars, world)107        if (score < bestScore) {108          bestScore = score109          best = car110        }111      }112113      // Somebody has to go, even if everybody is busy.114      const chosen = best || fallback115      if (chosen) this.assigned.set(key, chosen.id)116    }117118    const work = new Map()119    for (const car of cars) work.set(car.id, [])120    for (const call of world.calls) {121      const carId = this.assigned.get(call.floor + ':' + call.direction)122      if (carId !== undefined && work.has(carId)) work.get(carId).push(call)123    }124125    for (const car of cars) this.drive(car, work.get(car.id), cars)126  },127128  // How many calls we have already promised this car in the current assignment.129  promised(carId) {130    let count = 0131    for (const id of this.assigned.values()) if (id === carId) count++132    return count133  },134135  score(car, call, cars, world) {136    const heading = this.heading.get(car.id)137    const floors = this.reach(car.floor, heading, call.floor, call.direction)138139    let score = floors * SECONDS_PER_FLOOR140141    // We watched this one answer a call and the button came straight back on, so we142    // think it went away full. A heavy penalty rather than a ban: in a quiet143    // building it may still be the only car that can go, and refusing outright144    // strands people rather than merely delaying them.145    if ((this.distrust.get(car.id) || 0) > world.time) {146      if (car.pressed.length === 0) this.distrust.delete(car.id)147      else score += DISTRUST_PENALTY148    }149    // Every floor already requested from inside is a stop this car has to make150    // before it gets anywhere else. It is the closest thing to a load reading you151    // are given, and it is a lower bound rather than a count.152    score += car.pressed.length * BUSY_PENALTY153154    // Anti-bunching: if somebody else is already going there the same way, a second155    // car usually buys nothing and costs a lift somewhere else in the building.156    //157    // Tempting to fade this out for calls that have been lit a long time, on the158    // theory that a persistent button means one car cannot cope. Measured: it makes159    // the morning peak markedly worse, because the cars pile into the lobby and the160    // rest of the building starves. Left alone deliberately.161    for (const other of cars) {162      if (other.id === car.id) continue163      const goingThere = other.queue.includes(call.floor)164      if (goingThere && this.heading.get(other.id) === call.direction) {165        score += BUNCHING_PENALTY166        break167      }168    }169170    // Already sweeping that way with the call ahead of it: nearly free to serve.171    const ahead =172      heading === 'up'173        ? call.floor >= car.floor174        : heading === 'down'175          ? call.floor <= car.floor176          : false177    if (heading === call.direction && ahead) score -= DIRECTION_BONUS178179    // An idle car two floors away is the best possible answer to a hall call.180    if (!heading && car.queue.length === 0 && Math.abs(car.floor - call.floor) <= 2) {181      score -= IDLE_NEARBY_BONUS182    }183184    // Empty, so it will not fill up before it gets there.185    if (car.pressed.length === 0) score -= EMPTY_BONUS186187    return score188  },189190  // How far this car has to travel, on its current sweep, to answer that call.191  reach(position, heading, floor, wants) {192    if (!heading) return Math.abs(position - floor)193194    if (heading === 'up') {195      if (floor >= position && wants === 'up') return floor - position196      if (wants === 'down') return this.top - position + (this.top - floor)197      return this.top - position + this.top + floor198    }199200    if (floor <= position && wants === 'down') return position - floor201    if (wants === 'up') return position + floor202    return position + this.top + (this.top - floor)203  },204205  // Everything below is the same LOOK sweep. RSR chooses the car; the car still has206  // to decide what order to visit things in, and LOOK is the right answer to that.207  drive(car, calls, cars) {208    const here = car.atFloor209    const loading = car.doors !== 'closed'210211    const stops = []212    for (const floor of car.pressed) stops.push({ floor, kind: 'car' })213    for (const call of calls) stops.push({ floor: call.floor, kind: call.direction })214    const pending = stops.filter((s) => !(loading && here !== null && s.floor === here))215216    if (pending.length === 0) {217      this.heading.delete(car.id)218      car.indicate(null)219      const lobbyCovered = cars.some(220        (other) => other.id !== car.id && (other.floor < 0.5 || other.queue[0] === 0),221      )222      if (!lobbyCovered && car.floor > 0.5) car.goTo(0)223      return224    }225226    let start = this.heading.get(car.id)227    if (!start) {228      let nearest = Infinity229      for (const stop of pending) {230        const distance = Math.abs(stop.floor - car.floor)231        if (distance < nearest) {232          nearest = distance233          start = stop.floor >= car.floor ? 'up' : 'down'234        }235      }236    }237238    const plan = this.sweep(car.floor, start, pending)239    this.heading.set(car.id, plan.heading)240    car.setQueue(plan.queue)241    car.indicate(this.lantern(here, loading, plan, pending))242  },243244  sweep(position, start, stops) {245    const left = stops.slice()246    const order = []247    let cursor = position248    let heading = start249    let leading = null250251    for (let leg = 0; leg < 4 && left.length > 0; leg++) {252      const floors = left.map((s) => s.floor)253      const reach = heading === 'up' ? Math.max(cursor, ...floors) : Math.min(cursor, ...floors)254255      const taken = left.filter((s) => {256        const wanted = s.kind === 'car' || s.kind === heading257        const onTheWay = heading === 'up' ? s.floor >= cursor - 0.001 : s.floor <= cursor + 0.001258        return wanted && onTheWay259      })260      taken.sort((a, b) => (heading === 'up' ? a.floor - b.floor : b.floor - a.floor))261262      if (taken.length > 0 && !leading) leading = heading263      for (const stop of taken) {264        left.splice(left.indexOf(stop), 1)265        if (!order.includes(stop.floor)) order.push(stop.floor)266      }267268      cursor = reach269      heading = heading === 'up' ? 'down' : 'up'270    }271272    for (const stop of left) if (!order.includes(stop.floor)) order.push(stop.floor)273    return { queue: order, heading: leading || start }274  },275276  lantern(here, loading, plan, stops) {277    const anchor = loading && here !== null ? here : plan.queue[0]278    if (anchor === undefined) return plan.heading279    if (anchor <= 0) return 'up'280    if (anchor >= this.top) return 'down'281282    const next = loading && here !== null ? plan.queue[0] : plan.queue[1]283    const onward = next !== undefined && next !== anchor ? (next > anchor ? 'up' : 'down') : null284285    const wanted = new Set()286    for (const stop of stops) {287      if (stop.floor === anchor && stop.kind !== 'car') wanted.add(stop.kind)288    }289    if (wanted.size === 1) return [...wanted][0]290291    return onward || plan.heading292  },293}