Find sorting algorithm for an elevators floor travel schedule, starting from the current floor with preselected floors to reach and a travel direction

Question

I'm making an elevator in react, But I need to make a function that sorts an array to the nearest to the number X and also there is a condition if the elevator goes up or down,

so for example,

• There are in total 5 floors.
• X = Current Floor 3

You're now on floor 3 and click on the button UP and you click the numbers 2 -> 5 -> 4 -> 1

The array should be sorted so that it goes like this: 3 -> 4 -> 5 -> 2 -> 1.

Pseudocode:

let currentFloor = 3; 
let direction = "UP";
let clickedButtons = [2,5,4,1];

// ClickedButtons after sorted
 clickedButtons = [4,5,2,1]

Answer 1

I guess you need sth like this

Whenever you go up, you need to find all greater numbers and sort them in ascending order so elevator will stop at the next possible floor as it goes up.

Then find all lower numbers and sort them in reverse order.

The opposite procedure will be done if you choose to go down.

let arr = [10, 4, 8, 1, -2, 6];

let x = 3;

const goUp = (num, arr) => arr.filter(obj => obj > num).sort((a, b) => a - b)
const goDown = (num, arr) => arr.filter(obj => obj < num).sort((a, b) => b - a)

function printSequence(arr, initial, direction) {
  if (direction === 'up') {
    console.log(goUp(initial, arr).concat(goDown(initial, arr)))
  } else {
    console.log(goDown(initial, arr).concat(goUp(initial, arr)))
  }
}

printSequence(arr, 3, 'up')
printSequence(arr, 3, 'down')

Answer 2

You can separate the array into two arrays. One contains only higher numbers than the currentFloor other contains only lower numbers such as:

let lowerFloors = clickedButtons.filter(floor => floor > currnentFloor);
let upperFloors = clickedButtons.filter(floor => floor > currnentFloor);

Then sort each array lowerFloors would be descending, and higherFloors would be in ascending order.

upperFloors = upperFloors.sort((a, b) => {
  return a - b;
});

lowerFloors = lowerFloors.sort((a, b) => {
  return a - b;
});
lowerFloors = lowerFloors.reverse();

Then merge both arrays. If you going up upperFloors array would be first, else lowerFloors would be first.

let newArray;

if (direction === "UP") {
 newArray = upperFloors.concat(lowerFloors);
} else {
 newArray = lowerFloors.concat(upperFloors)
}

Answer 3

From both of my above comments ...

@Cedric ... 1/2 With this scenario the only sorting needed is e.g. an ascending sorting of all floor numbers ... [1, 2, 3, 4, 5] ... one find's the index of the current floor number 3 which is 2 ... 'up' will be translated into direction vector of 1, thus one takes 1st everything higher than index 2 or right from index 2 ... and 2nd everything left from index 2 ... result ... [4, 5, 2, 1].

@Cedric ... 2/2 One does likewise for 'down'/-1 where one 1st takes everything left from index 2 and 2nd everything right from index 2 ... result ... [2, 1, 4, 5]. There is no sorting magic since with the known preset of either 'up' or 'down' the floor travel schedule is obvious.

... but of cause one can cast the imperative recipe of my comments into a single sort formula.

function getFloorTravelSchedule(
  direction = 'up',
  floorNumber = 0,
  floorTravelList = [],
) {
  direction = ((direction === 'up') && 1) || -1;

  function getTravelPrecedence(a, b) {
    return (
      (a > floorNumber && b > floorNumber && a - b) ||
      (a < floorNumber && b < floorNumber && b - a) ||
      ((a > floorNumber && b < floorNumber && -1) || 1) * direction
    );
  }
  return Array
    .from(floorTravelList)
    .sort(getTravelPrecedence);
}
const currentFloorNumber = 3;
const selectedFloorNumbers = [2, 5, 4, 1];

const upwardFloorTravelSchedule =
  getFloorTravelSchedule('up', currentFloorNumber, selectedFloorNumbers);
const downwardFloorTravelSchedule =
  getFloorTravelSchedule('down', currentFloorNumber, selectedFloorNumbers);

console.log({
  currentFloorNumber,
  selectedFloorNumbers,
  upwardFloorTravelSchedule,
  downwardFloorTravelSchedule,
});

console.log(
  "getFloorTravelSchedule('up', 3, [10, 4, 8, 1, -2, 6]) ...",
  getFloorTravelSchedule('up', 3, [10, 4, 8, 1, -2, 6])
);
console.log(
  "getFloorTravelSchedule('down', 3, [10, 4, 8, 1, -2, 6]) ...",
  getFloorTravelSchedule('down', 3, [10, 4, 8, 1, -2, 6])
);

console.log(
  "getFloorTravelSchedule('up', 7, [10, 4, 8, 1, -2, 6]) ...",
  getFloorTravelSchedule('up', 7, [10, 4, 8, 1, -2, 6])
);
console.log(
  "getFloorTravelSchedule('down', 0, [10, 4, 8, 1, -2, 6]) ...",
  getFloorTravelSchedule('down', 0, [10, 4, 8, 1, -2, 6])
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Answer 4

First off, welcome to StackOverflow! My usual newcomers advice is that you take the tour, visit the help center and read up on asking good questions. After doing some research and searching for related topics on SO, try it yourself. If you're stuck, post a minimal, reproducible example of your attempt and note exactly where you're stuck.

But as there are already answers here, I won't wait for that and instead will make my own suggestion.

---

We can think of an elevator having a state. We can apply functions using that state to get a new state. For our purposes, the state might consist of the elevator's current floor, the direction it's traveling, and the list of scheduled stops.

We're looking for a function that takes an elevator that's still, but which already has a direction chosen, and a collection of floors to visit; it should return the entire new state. If we want just the list of scheduled stops, we can read that off this state.

We could build that off a function that calls an elevator to a given floor, just folding the list of floors and the initial state into a new state. So addStops will depend on call -- which would be useful in itself to call the elevator to a given floor.

In either case, we will need to sort the stops to be made based on our current floor and direction. So there is a function also for that. Putting these together, we can imagine a design like this:

const sortStops = (current, direction, stops) => {
  const floors = [... stops] .sort ((a, b) => a - b)
  const above = floors .filter ((f) => f > current)
  const below = floors .filter ((f) => f < current) .reverse ()
  return direction == 'UP' ? [... above, ...below] : [...below, ...above]
}

const call = ({current, direction, stops}, floor) => { 
  const newStops = sortStops ([... new Set ([...stops, floor])], direction, current)
  const newDirection = newStops .length ? (newStops [0] > current ? 'UP' : 'DOWN') : direction
  return {current, direction: newDirection, stops: newStops}
}

const addStops = ({current, direction, stops}, floors) =>
  sortStops (current, direction, stops) .reduce (call, elevator)


// our initial elevator state: on floor 3, headed up, with no stops scheduled
const elevator = {current: 3, direction: 'UP', stops: []}

console .log (addStops (elevator, [2, 5, 4, 1]))

This will return

{current: 3, direction: "UP", stops: [4, 5, 2, 1]}

The advantage of this is that we can write other functions on this same data structure to perform other actions of the elevator, like making its next stop:

const stop = ({current, stops, direction}) => stops .length
  ? {
      current: stops [0], 
      stops: stops .slice (1), 
      direction: stops .length > 1 ? stops [1] > stops [0] ? 'UP' : 'DOWN' : 'N/A'
    }
  : {current, stops, direction: 'N/A'}

const elevator = {current: 3, stops: [], direction: 'UP'}

If we call stop on {current:3, direction: "UP", stops:[4,5,2,1]}, we will get

{current:4, direction: "UP", stops:[5,2,1]}

And if we called it again that result, we would get

{current:5, direction: "DOWN", stops:[2,1]}

And then

{current:2, direction: "DOWN", stops:[1]}

and

{current:1, direction: "N/A", stops:[]}

at which point another call won't do anything, returning again:

{current:1, direction: "N/A", stops:[]}

And we could write other functions -- maybe a cancelAllStops in case of a fire alarm. The point is that we can work with immutable state objects with some simple functions. In an object-oriented system, these would be methods on a mutable object. Here they're just plain functions. This can be a very useful way of structuring your data.

Answer 5

• The list of floors can be divided into two group, one group contains all floors above the current floor & the other contains all floors below the current floor.

• The group that contains higher floors, always needs to be sorted in ascending order irrespective of the direction.

• The group that contains lower floors, always needs to be sorted in descending order irrespective of the direction.

• If the direction is "UP", then the higher floors group needs appear before the lower floors group.

• If the direction is "DOWN", then the lower floors group needs appear before the higher floors group.

function getRoute(dir, currFloor, floorList) {
  return floorList
    .reduce((g, f) => (g[+(dir === "UP" ? f < currFloor : f > currFloor)].push(f), g), [[], []])
    .flatMap((g, i) => g.sort((a, b) => (dir === "UP" ? 2 * i - 1 : 1 - 2 * i) * (b - a)));
}

console.log(getRoute("UP", 3, [5, 1, 4, 7, 2, 0]));
console.log(getRoute("DOWN", 3, [5, 1, 4, 7, 2, 0]));
console.log(getRoute("UP", 5, [1, 0, 2]));
console.log(getRoute("UP", 4, [7, 9, 5, 10]));
console.log(getRoute("DOWN", 5, [1, 0, 2]));
console.log(getRoute("DOWN", 4, [7, 9, 5, 10]));

.as-console-wrapper { min-height: 100% !important; top: 0; }

1. Using Array.prototype.reduce divide the floorList into groups and based on the dir decide which group appears first.

2. Using Array.prototype.flatMap sort the higher floors group in ascending order & the lower floors group in descending order.