Problem 453752 · hard · Level 04 Non-Linear Data Structures

A Bank of Lifts

py-classes · py-composition · state machines · simulation

An office building has n_lifts lifts serving floors 0 to floors - 1. Every lift starts at floor 0 with no stops and no direction. Write a class Building(floors, n_lifts) (you will want a second class for a single lift) with three methods:

call(f) asks for a lift to stop at floor f and returns the index of the lift that will serve it (a floor outside the building raises ValueError):

  1. If some lift already has f among its stops, nothing changes; return the lowest such index.
  2. Otherwise the candidates are the lifts that are free for f: lifts with no direction, lifts already at floor f, lifts going up with f above them and lifts going down with f below them. If no lift is free for f, every lift is a candidate.
  3. The nearest candidate (fewest floors away) gets f as a new stop; ties go to the lowest index.

step() moves time on by one tick: every lift, in index order, does one of these and reports it as a string, and step returns the list of reports:

  • if its current floor is one of its stops, it removes that stop and opens its doors: "open 4";
  • otherwise, if it has no direction, it waits: "idle";
  • otherwise it moves one floor in its direction: "up 5" or "down 3" (the floor it arrives at).

where() returns a list of (floor, direction) pairs, one per lift, where the direction is "up", "down" or None.

A lift's direction is updated after every change to its stops or position (a new stop, an opening, a move), from its stops other than its current floor:

  • no such stops: None;
  • it is going up and one of them is above it: stay "up"; going down and one is below: stay "down";
  • it has no direction: head towards the nearest of them (towards the one above on a tie);
  • otherwise it turns round.

The tests drive the building with run_ops(Building, ops, args), and raises(fn, *args) returns the name of the exception a call raises (or None); the setup's office_day(floors, n_lifts, n, seed) makes a long random (ops, args) day.

Examples

ops:  ["Building", "call", "step", "step", "call", "call", "step", "step", "step", "where"]
args: [[8, 2], [4], [], [], [1], [6], [], [], [], []]
Output: [None, 0, ['up 1', 'idle'], ['up 2', 'idle'], 1, 0, ['up 3', 'up 1'],
         ['up 4', 'open 1'], ['open 4', 'idle'], [(4, 'up'), (1, None)]]
Explanation: both lifts are idle at floor 0, so lift 0 (the lower index) takes floor 4.
When floor 1 calls, lift 0 is at floor 2 going up, so it is not free for floor 1; lift 1 is.
Floor 6 is above both lifts and both are going up: lift 0 is nearer (4 floors against 6).
After opening at floor 4, lift 0 still has floor 6 ahead, so it keeps going up.

Constraints

  • 2 <= floors <= 60, 1 <= n_lifts <= 8; up to 4000 operations.

Goals

  • Split a simulation into objects: a building that has lifts, each lift with its own state
  • Keep a lift's direction consistent with its remaining stops after every change
  • Let the building decide which lift serves a call by asking the lifts about themselves
Starting Python…