Allocate Bikes To People - First Priority (closest Bike To Closest Person)
Solution 1:
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:
functionfindBikesForPeople(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;
functiondistance(a, b) {
returnMath.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.
Solution 2:
I will outline the steps for you
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]];
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
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)]
- Sort the array by increasing value of
dist
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]
Iterate through the array. If for the current
Distance
objectperson_used[person_id] == false && bike_used[bike_id] == false
assign this person to this bike and set bothperson_used[person_id] and bike_used[bike_id] to true
. If either isfalse
you can ignore it.- Stop when each person is assigned a bike.
Post a Comment for "Allocate Bikes To People - First Priority (closest Bike To Closest Person)"