Car lane assignment algorithm

user_13673943 0
Viewed 190

I have an array of car objects (sorted in ascending order by start) expressed as follows:

var cars = [
  {"name": "car0blue", "start": 0, "end": 3},
  {"name": "car1red", "start": 1, "end": 4},
  {"name": "car2yellow", "start": 3, "end": 7},
  {"name": "car3green", "start": 3, "end": 6},
  {"name": "car4purple", "start": 4, "end": 7},
  {"name": "car5grey", "start": 5, "end": 11},
]

The start and end describes where the cars are located on an x-axis.

I'm trying to assign the cars to lanes, always striving to put the car in the lowest numbered lane possible without bumping into another car.

This is the result I'm trying to achive

enter image description here

carsWithLanes = [
  {"name": "car0blue", "start": 0, "end": 3, "lane": 0},
  {"name": "car1red", "start": 1, "end": 4, "lane": 1},
  {"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
  {"name": "car3green", "start": 3, "end": 6, "lane": 2},
  {"name": "car4purple", "start": 4, "end": 7, "lane": 1},
  {"name": "car5grey", "start": 5, "end": 11, "lane": 3},
]

This is the logic

To fit into a given lane the start value has to be greater than or equal to the end value of the car in the given lane.

"car0blue": since this is the first car it is assigned to lane 0.

{"name": "car0blue", "start": 0, "end": 3, "lane": 0}

"car1red": since it won't fit into lane 0 it's assigned to lane 1.

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},

"car2yellow": since it will fit into lane 0 it's assigned to lane 0.

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane":0},

"car3green": since it won't fit into lane 0 or lane 1 it's assigned to lane 2.

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},

"car4purple": since it won't fit into lane 0 but will fit into lane 1 it's assigned to lane 1.

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},
{"name": "car4purple", "start": 4, "end": 7, "lane": 1},

"car5grey": since it won't fit into lane 0, lane 1 or lane 2 it's assigned to lane 3

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},
{"name": "car4purple", "start": 4, "end": 7, "lane": 1},
{"name": "car5grey", "start": 5, "end": 11, "lane": 3},

What I've tried

I figured I would need some sort of array containing the current end values of each lane to compare against but realize I'm stuck and looking for some help.

      var laneBuffer = [];

      cars.forEach((item, i) => {
        if (i === 0) {
          item.lane = 0;
          laneBuffer.push(item);
        }
        else{
          //Brain freeze...
          });
        }
      });
javascript
3 Answers

Fun problem. This algorithm should work in all cases.

const cars = [
    { name: "car0blue", start: 0, end: 3 },
    { name: "car1red", start: 1, end: 4 },
    { name: "car2yellow", start: 3, end: 7 },
    { name: "car3green", start: 3, end: 6 },
    { name: "car4purple", start: 4, end: 7 },
    { name: "car5grey", start: 5, end: 11 },
];

const lanes = [];
cars.forEach(placeInFreeLane);
console.log( cars );

// Algorithm:

function placeInFreeLane(car) {
    let lane = 0;
    while (!tryFitInLane(car, lane)) lane++;
    car.lane = lane;
}

function tryFitInLane(car, laneNumber) {
    const lane = lanes[laneNumber];
    if (lane === undefined) {
        lanes[laneNumber] = [car];
        return true;
    } else {
        const intersectsWithAny = lane.some(otherCar => intersects(car, otherCar));
        if (!intersectsWithAny) {
            lane.push(car);
            return true;
        }
    }
    return false;
}

function intersects(a, b) { return a.start < b.end && a.end > b.start; }

Output given your case (matches the desired output):

[
  { "name": "car0blue", "start": 0, "end": 3, "lane": 0 },
  { "name": "car1red", "start": 1, "end": 4, "lane": 1 },
  { "name": "car2yellow", "start": 3, "end": 7, "lane": 0 },
  { "name": "car3green", "start": 3, "end": 6, "lane": 2 },
  { "name": "car4purple", "start": 4, "end": 7, "lane": 1 },
  { "name": "car5grey", "start": 5, "end": 11, "lane": 3 }
]

EDIT: for the fun of it here is another version written in a more functional manner. This one is self contained and doesn't mutate the original or global state. It copies the input data and has no side effects.

// Algorithm:

const intersects = (a, b) => a.start < b.end && a.end > b.start;
const hasNoIntersectionsWith = (car) => (lane) => !lane.some((other) => intersects(car, other));
const getPacked = (cars) => {
    const lanes = [];
    return cars.map((car) => {
        let freeLaneIndex = lanes.findIndex(hasNoIntersectionsWith(car));
        if (freeLaneIndex < 0) freeLaneIndex = lanes.push([]) - 1;
        lanes[freeLaneIndex].push(car);
        return { ...car, lane: freeLaneIndex };
    });
};

// Example:

var cars = [
    { name: "car0blue", start: 0, end: 3 },
    { name: "car1red", start: 1, end: 4 },
    { name: "car2yellow", start: 3, end: 7 },
    { name: "car3green", start: 3, end: 6 },
    { name: "car4purple", start: 4, end: 7 },
    { name: "car5grey", start: 5, end: 11 },
];

console.log(getPacked(cars));

user_13964800

You need to check each lane if the last end is smaller or equal to the current car start.

If you find a lane then you can add the car, if not you create a new lane.

var cars = [
  {"name": "car0blue", "start": 0, "end": 3},
  {"name": "car1red", "start": 1, "end": 4},
  {"name": "car2yellow", "start": 3, "end": 7},
  {"name": "car3green", "start": 3, "end": 6},
  {"name": "car4purple", "start": 4, "end": 7},
  {"name": "car5grey", "start": 5, "end": 11},
]

const carLanes = [];

cars.forEach(car=>{
  const availableLane = carLanes.find(lane=>
    lane[lane.length-1].end <= car.start
  );
  if (availableLane) {
    availableLane.push(car);
  } else {
    carLanes.push([car]);
  }
})

console.log(carLanes);

user_1281650

You need to convert cars into lanes e.g.

[ car0
  car1
  car2
  car3
  car4
  car5
]

[ [car0, car2] // lane 0
  [car1, car4] // lane 1
  [car3]       // lane 2
  [car5]       // lane 3
]

This allows us to find a free lane simply by checking the last car of each lane. When you add a car to a lane, add the lane number to the car. Once you're done doing that flatten lanes:

const assign_cars = cars => {
  const lanes = [];
  for (let i = 0; i < cars.length; i += 1) {
    const car = cars[i];
    const idx = lanes.findIndex(lane => lane[lane.length-1].end <= car.start);
    const free = idx > -1;
    const lane = free ? idx : lanes.length;
    if (free) lanes[lane].push({...car, lane});
    else lanes.push([{...car, lane}]);
  }
  return lanes.flat();
}

console.log(assign_cars(cars));
<script>
const cars = [
  {"name": "car0blue", "start": 0, "end": 3},
  {"name": "car1red", "start": 1, "end": 4},
  {"name": "car2yellow", "start": 3, "end": 7},
  {"name": "car3green", "start": 3, "end": 6},
  {"name": "car4purple", "start": 4, "end": 7},
  {"name": "car5grey", "start": 5, "end": 11},
]
</script>

user_12448840
Related