LOOK

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

1// LOOK — the classic lift algorithm, and the one your office probably runs.2//3// Every car is sweeping in one direction. It serves each stop ahead of it on that4// leg, then turns round and sweeps back. The name is the important part: unlike5// SCAN, which runs to the end of the shaft whether or not anybody is up there, LOOK6// only goes as far as the furthest outstanding request before reversing.7//8// The rule that makes it work — and the one people miss — is that a hall call is9// only answered on the leg going the caller's way. Stopping for a down-call on the10// way up just opens the doors at somebody who does not want to get in.11//12// Note what you are not given: how many people are waiting anywhere, and how many13// are in any car. A lit button is a lit button. Working around that is the job.1415const SECONDS_PER_FLOOR = 0.616const SECONDS_PER_STOP = 517const CROWDING_PENALTY = 61819export default {20  setup(building) {21    this.top = building.floors - 122    this.heading = new Map()23  },2425  tick(world) {26    const cars = world.elevators.filter((car) => !car.outOfService)27    if (cars.length === 0) return2829    // Hand each lit button to whichever car reaches it soonest on the sweep it is30    // already committed to.31    const work = new Map()32    for (const car of cars) work.set(car.id, [])3334    for (const call of world.calls) {35      let best = null36      let bestCost = Infinity37      // If every car is over its cap the call still has to go somewhere, or in a38      // one-lift building nothing would ever be assigned and the car would sit39      // there while the lobby filled up.40      let fallback = null41      let fallbackCommitted = Infinity4243      for (const car of cars) {44        // Do not keep piling work onto a car that already has plenty. Without a load45        // reading this is the only brake there is, and without a brake one car ends46        // up promising the whole building while the others sit idle.47        const committed = this.busy(car) + work.get(car.id).length48        if (committed < fallbackCommitted) {49          fallbackCommitted = committed50          fallback = car51        }52        if (committed >= car.capacity) continue5354        const cost =55          this.reach(car.floor, this.heading.get(car.id), call.floor, call.direction) *56            SECONDS_PER_FLOOR +57          work.get(car.id).length * SECONDS_PER_STOP +58          committed * CROWDING_PENALTY5960        if (cost < bestCost) {61          bestCost = cost62          best = car63        }64      }6566      const chosen = best || fallback67      if (chosen) work.get(chosen.id).push(call)68    }6970    for (const car of cars) this.drive(car, work.get(car.id), cars)71  },7273  // How busy a car looks.74  //75  // Nothing anywhere tells you how many people are in a lift — that is the point of76  // the game. The closest honest signal is how many different floors the people77  // inside have already asked for: eight people all going to the fifth floor look78  // like one stop, and they are. It is a lower bound, and it is enough to stop you79  // loading every call onto the same car.80  busy(car) {81    return car.pressed.length82  },8384  // How far this car has to travel, on its current sweep, to answer that call.85  reach(position, heading, floor, wants) {86    if (!heading) return Math.abs(position - floor)8788    if (heading === 'up') {89      if (floor >= position && wants === 'up') return floor - position90      // We carry on up, turn round at the top of the run, and collect them coming back.91      if (wants === 'down') return this.top - position + (this.top - floor)92      // Behind us and going our way: they wait for the whole round trip.93      return this.top - position + this.top + floor94    }9596    if (floor <= position && wants === 'down') return position - floor97    if (wants === 'up') return position + floor98    return position + this.top + (this.top - floor)99  },100101  drive(car, calls, cars) {102    const here = car.atFloor103    const loading = car.doors !== 'closed'104105    // Two kinds of stop: somebody inside wants off here, or somebody outside wants106    // on. Only the second kind cares which way the car is going.107    const stops = []108    for (const floor of car.pressed) stops.push({ floor, kind: 'car' })109    for (const call of calls) stops.push({ floor: call.floor, kind: call.direction })110111    // Never re-queue the floor the car is standing at with its doors open. It would112    // shut them and immediately open them again for nobody.113    const pending = stops.filter((s) => !(loading && here !== null && s.floor === here))114115    if (pending.length === 0) {116      this.heading.delete(car.id)117      car.indicate(null)118      // An idle car is worth more at the lobby than wherever it happened to finish.119      // One car covers it; the rest stay put rather than all stampeding downstairs.120      const lobbyCovered = cars.some(121        (other) => other.id !== car.id && (other.floor < 0.5 || other.queue[0] === 0),122      )123      if (!lobbyCovered && car.floor > 0.5) car.goTo(0)124      return125    }126127    let start = this.heading.get(car.id)128    if (!start) {129      let nearest = Infinity130      for (const stop of pending) {131        const distance = Math.abs(stop.floor - car.floor)132        if (distance < nearest) {133          nearest = distance134          start = stop.floor >= car.floor ? 'up' : 'down'135        }136      }137    }138139    const plan = this.sweep(car.floor, start, pending)140    this.heading.set(car.id, plan.heading)141    car.setQueue(plan.queue)142    car.indicate(this.lantern(here, loading, plan, pending))143  },144145  // Order the stops into legs: everything this way, then everything back, and so on.146  sweep(position, start, stops) {147    const left = stops.slice()148    const order = []149    let cursor = position150    let heading = start151    let leading = null152153    for (let leg = 0; leg < 4 && left.length > 0; leg++) {154      // This is the LOOK part: turn round at the furthest request, not at the end155      // of the shaft.156      const floors = left.map((s) => s.floor)157      const reach = heading === 'up' ? Math.max(cursor, ...floors) : Math.min(cursor, ...floors)158159      const taken = left.filter((s) => {160        const wanted = s.kind === 'car' || s.kind === heading161        const onTheWay = heading === 'up' ? s.floor >= cursor - 0.001 : s.floor <= cursor + 0.001162        return wanted && onTheWay163      })164      taken.sort((a, b) => (heading === 'up' ? a.floor - b.floor : b.floor - a.floor))165166      if (taken.length > 0 && !leading) leading = heading167      for (const stop of taken) {168        left.splice(left.indexOf(stop), 1)169        if (!order.includes(stop.floor)) order.push(stop.floor)170      }171172      cursor = reach173      heading = heading === 'up' ? 'down' : 'up'174    }175176    for (const stop of left) if (!order.includes(stop.floor)) order.push(stop.floor)177    return { queue: order, heading: leading || start }178  },179180  // Which way to point the lantern: the direction the car will travel *from the stop181  // it is about to make*, not the direction it is travelling now.182  lantern(here, loading, plan, stops) {183    const anchor = loading && here !== null ? here : plan.queue[0]184    if (anchor === undefined) return plan.heading185186    // There is no down from the ground, and no up from the top.187    if (anchor <= 0) return 'up'188    if (anchor >= this.top) return 'down'189190    const next = loading && here !== null ? plan.queue[0] : plan.queue[1]191    const onward = next !== undefined && next !== anchor ? (next > anchor ? 'up' : 'down') : null192193    // If the car is going there to answer a hall call, it has to show that call's194    // direction — otherwise the people it came for will not get in, the call stays195    // lit, and it will keep coming back and keep not collecting them.196    const wanted = new Set()197    for (const stop of stops) {198      if (stop.floor === anchor && stop.kind !== 'car') wanted.add(stop.kind)199    }200    if (wanted.size === 1) return [...wanted][0]201202    return onward || plan.heading203  },204}