Allocate bikes to people - First Priority (Closest bike to closest person)

user_7427111 0
Viewed 1716

Passing in a grid to a function with bikes and person at locations

[ 'c' , '_' ,'A' ,'_', '_' , '_']
[ '_' , '_' ,'a' ,'_', '_' , '_']
[ '_' , '_' ,'_' ,'_', 'b' , '_']
[ '_' , '_' ,'_' ,'_', '_' , '_']
[ 'D' , 'd' ,'_' ,'_', '_' , 'B']
[ '_' , '_' ,'_' ,'C', '_' , '_']

Output: Something like this [A:1, B:3, C:8, D:1]

Where A is the person and 1 is the step required to travel to get to the bike.

Criterias:

  1. Closest person to the bike, get the bike at the first priority.
  2. Single bike can't be assigned to 2 individuals
  3. Distance of a bike from one individual will never be equal to distance of the same bike from a different individual.
  4. Distances can be equal, but 2 different bikes and 2 different individuals

I feel like Graphical representation might make more sense hence

enter image description here

My Approach:

  1. Find the location of Bikes and Person and store them in an Array.

    person = [[0,2],[4,0],[4,5],[5,3]], bikes = [[0,0],[1,2],[2,4],[4,1]];

  2. As shortest path will be 1, start removing the bikes and person from the Array who has the shortest path as 1 and keep incrementing the shortest path by 1. And store the person and bike into results array.

  3. Need to keep doing step # 2 till our Person's Array is empty

function findBikesForPeople(grid) {

  let row_length = grid.length;
  let col_length = grid[0].length;
  var bikes = [],
    person = [];

  for (var row = 0; row < row_length; row++) {
    for (var col = 0; col < col_length; col++) {
      if (grid[row][col] === 'B') {
        bikes.push([row, col]);
      }
      if (grid[row][col] === 'P') {
        person.push([row, col]);
      }
    }
  }

  var distances = (bikes, person) => {
    var dist = [];
    person.map((single) => {
      var inner = [];
      bikes.map((bike) => {
        inner.push(check_distance(single, bike));
      })
      dist.push(inner);
    })
    return dist;
  }


  //This isn't right
  var AllocateBikes = (distances) => {
    //var result = [];
    //var min = 1;
    //var increment = 0;
    //  let people = distances.length;
    //let bikeCount = distances[0].length;
    //while (people > 0) {
    //  if (Math.min(...distances[]))
    // }
    return distances;
  }

  function check_distance(a, b) {
    return Math.abs(b[1] - a[1]) + Math.abs(b[0] - a[0]);
  }

  let distance_between = distances(bikes, person);
  console.log(AllocateBikes(distance_between));

}
var grid = [
  ['P', '_', 'B', '_', '_'],
  ['_', '_', '_', '_', 'B'],
  ['_', '_', '_', '_', '_'],
  ['_', 'P', '_', '_', '_'],
  ['_', '_', '_', '_', 'B']
];

findBikesForPeople(grid);

data-structures algorithm javascript
2 Answers

If I understand correctly, you're almost there. What you need to do is indeed find all the combinations of people and bikes, and measure their distance. Then, you sort these based on distance, and then you can iterate over them and assign the bikes to the people whenever you come across a combination where the person doesn't have a bike yet and the bike is still free. This will assign a different bike to each person, and use the shortest distances first. In javascript that could look something like: 

function findBikesForPeople(grid) {
    var rows = grid.length, cols = grid[0].length;
    var bikes = [], people = [];
    for (var row = 0; row < rows; row++) {
        for (var col = 0; col < cols; col++) {
            if (grid[row][col] === 'B') {
                bikes.push({y: row, x:col});
            }
            if (grid[row][col] === 'P') {
                people.push({y:row, x:col});
            }
        }
    }
    var combis = [];
    for (var p in people) {
        for (var b in bikes) {
            var d = distance(people[p], bikes[b]);
            combis.push({person:p, bike:b, distance:d});
        }
    }
    combis.sort(function(a,b) {return a.distance - b.distance});
    var hasBike = [], isTaken = [], assignment = [];
    for (var c in combis) {
        var person = combis[c].person, bike = combis[c].bike;
        if (!hasBike[person] && !isTaken[bike]) {
            assignment.push({person:person, 
                             px:people[person].x, py:people[person].y,
                             bike:bike,
                             bx:bikes[bike].x, by:bikes[bike].y});
            hasBike[person] = true;
            isTaken[bike] = true;
        }
    }
    return assignment;

    function distance(a, b) {
        return Math.abs(b.x - a.x) + Math.abs(b.y - a.y);
    }
}

var grid = [['B', '_', 'P', '_', '_', '_'],
            ['_', '_', 'B', '_', '_', '_'],
            ['_', '_', '_', '_', 'B', '_'],
            ['_', '_', '_', '_', '_', '_'],
            ['P', 'B', '_', '_', '_', 'P'],
            ['_', '_', '_', 'P', '_', '_']];
document.write(JSON.stringify(findBikesForPeople(grid)));

Note: I'm interpreting the grid as displayed in the code, with x = horizontal and y = vertical, i.e. grid[y][x], with (0,0) being the top left corner.

user_49076040

I will outline the steps for you

  1. Find the location of Bikes and Person and store them in an Array.
    person = [[0,2],[4,0],[4,5],[5,3]], bikes = [[0,0],[1,2],[2,4],[4,1]];

  2. Define a Class ( lets call it Distance) having following variables:
    person_id: use person index (0, 1, 2, ...) bike_id: use bike index (0, 1, 2, ...) dist: distance between this person and bike

  3. Create an array of Distance objects for each pair of person and bike. So for the above example you will have object values
    [(0, 0, 2), (0, 1, 1), ...(3, 3, 3)]

  4. Sort the array by increasing value of dist

  5. Create two Boolean arrays person_used having same number of elements as number of persons and bike_used having same number of elements as number of bikes(both initialized as false).
    person_used = [false, false, false, false], bike_used = [false, false, false, false]

  6. Iterate through the array. If for the current Distance object person_used[person_id] == false && bike_used[bike_id] == false assign this person to this bike and set both person_used[person_id] and bike_used[bike_id] to true. If either is false you can ignore it.

  7. Stop when each person is assigned a bike.
user_51312870
Related