Выделите велосипеды людям - Первый Приоритет (Ближайший велосипед к ближайшему человеку)

Question

Передача в сетке функции с велосипедами и персоной в локациях

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

Вывод: Примерно так [A:1, B:3, C:8, D:1]

Где A - это человек, а 1 - шаг, необходимый для того, чтобы добраться до велосипеда.

Характеристики:

1. Ближайший человек к велосипеду, возьмите велосипед на первом месте.
2. Один велосипед не может быть назначен 2 лицам
3. Расстояние велосипеда от одного человека никогда не будет равно расстоянию одного велосипеда от другого человека.
4. Расстояния могут быть одинаковыми, но 2 разных велосипеда и 2 разных человека

Мне кажется, что графическое представление может иметь больше смысла, следовательно

---

Мой подход:

1. Найдите расположение велосипедов и персонажа и сохраните их в массиве.

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

2. Поскольку кратчайший путь будет равен 1, начните удалять велосипеды и человека из массива. который имеет кратчайший путь как 1 и продолжает увеличивать кратчайший путь на 1. И сохранить человека и велосипед в массив результатов.

3. Нужно продолжать делать шаг # 2, пока наш массив не станет пустым

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);

Answer 1

Я обрисую шаги для вас

1. Найдите расположение велосипедов и человека и сохраните их в массиве.
   person = [[0,2],[4,0],[4,5],[5,3]], bikes = [[0,0],[1,2],[2,4],[4,1]];

2. Определите класс (назовем его Distance), имеющий следующие переменные:
   person_id: use person index (0, 1, 2, ...) bike_id: use bike index (0, 1, 2, ...) dist: distance between this person and bike

3. Создайте массив из Distance объектов для каждой пары человека и велосипеда. Так что для приведенного выше примера у вас будут значения объекта
   [(0, 0, 2), (0, 1, 1), ...(3, 3, 3)]

4. Сортировка массива по возрастанию значения dist
   

5. Создайте два логических массива person_used с тем же числом элементов, что и количество людей, и bike_used с таким же количеством элементов, что и количество велосипедов (оба инициализированы как false).
   person_used = [false, false, false, false], bike_used = [false, false, false, false]

6. Итерация по массиву. Если для текущего Distance объекта person_used[person_id] == false && bike_used[bike_id] == false назначьте этого человека на этот велосипед и установите оба person_used[person_id] and bike_used[bike_id] to true. Если любой из них false, вы можете игнорировать его.
   

7. Остановитесь, когда каждому человеку будет назначен велосипед.

Answer 2

Если я правильно понимаю, вы почти у цели. Что вам нужно сделать, так это найти все комбинации людей и велосипедов и измерить их расстояние. Затем вы сортируете их по расстоянию, а затем можете итерировать их и назначать велосипеды людям всякий раз, когда вы сталкиваетесь с комбинацией, в которой у человека еще нет велосипеда, а велосипед все еще свободен. Это назначит различный велосипед каждому человеку, и сначала будет использовать самые короткие расстояния В JavaScript это может выглядеть примерно так:

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)));

Примечание. Я интерпретирую сетку, как показано в коде, где x = горизонтальная и y = вертикальная, то есть сетка [y] [x], где (0,0) - верхний левый угол.