Как определить шаблоны в многомерном массиве и разбить данные на полезные типы, такие как Карты или Наборы

Question

Я предполагаю, что это довольно открытый и не совсем конкретный вопрос, но я думаю, что это хороший пример того, что может легко сделать наш мозг, что может быть трудно кодировать.Решение было бы круто, но Меня действительно больше интересует, каков ваш потенциальный подход .

Этот конкретный вопрос из раздела теории графов CodeSignal, и просит нас написать функциюэто определяет, если из заданной матрицы смежности (не важно знать для этого примера), если граф напоминает бабочку .

Вы можете представить центральную вершину с двумя парами 'дорог'(или градусов), каждая пара разделяет эксклюзивную "дорогу" между двумя другими своими вершинами.

Я сделал несколько других из этих проблем, но эта из нового набора, состоящего из определенных форм, и намного легче для определения шаблонов для передачи ввода.Я использовал тонны методов Array.prototype для создания и преобразования многомерных массивов. Каждая проблема занимала у меня довольно болезненное время. Я действительно изо всех сил пытаюсь найти эффективный способ обработки этих данных в целом.

Вот список 'дорог'(или градусы) в качестве контрольного примера. (я для удобства превратил матрицу смежности в массив дорог.) Каждая цифра представляет узел или вершину (их будет всего пять, если это проще) ...

[ [ '0', '1' ],
  [ '0', '2' ],
  [ '1', '0' ],
  [ '1', '2' ],
  [ '2', '0' ],
  [ '2', '1' ],
  [ '2', '3' ],
  [ '2', '4' ],
  [ '3', '2' ],
  [ '3', '4' ],
  [ '4', '2' ],
  [ '4', '3' ] ]

(примечание: центральная вершина не будет указана в массиве, и это только один пример.)

Даже без графикаВ течение нескольких секунд мы можем сказать, что это действительный "галстук-бабочка".

Примечание: некоторые дороги повторяются, но я сделал это нарочно ... Я подумал, если этолегче увидеть, легче кодировать.

Мы хотим прочитать из такого массива и определить (вернуть true), образуют ли дороги bowtie .|> <|</p>

Я спрашиваю, потому что держу пари, что есть некоторые особенности JavaScript, о которых я даже не подозревал.Я знаю, что такое Карты и Наборы, и я думал, что Карта может помочь, но мне не хватает опыта программирования.Заранее спасибо !!!

Answer 1

Поиск алгоритмов для эффективного выполнения подобных задач может быть очень сложным - я не могу обязательно дать вам совет по этому вопросу, но могу предложить несколько советов по кодированию.

1) Преобразовать массив -> Объект

Простой JavaScript object или Map может быть полезным типом данных для графического содержимого. Это действительно похожие (немного отличающиеся) типы данных, которые хранят вещи в соответствии с парами ключ-значение. Одна стратегия: вы можете превратить каждый узел в ключ, а массив связанных узлов в значение. Это похоже на немного более полезную структуру для этой информации. Примерно так:

/**
 * Convert array of arrays into object
 * where {key=node, val=[array of connected nodes]}
 */
function arrayToObj(roadsArr) {
  // start with empty object
  var obj = {};

  // iterate over each pair in roads array
  // initialize new {key: [val]} entry if none exists
  // otherwise add to existing list of values
  roadsArr.forEach(function(pair) {
    var key = pair[0];
    var val = pair[1];
    if (obj[key] === undefined) {
      obj[key] = [val];
    } else {
      obj[key].push(val);
    }
  });
  return obj;
}


roadsArr = [
  ["0", "1"],
  ["0", "2"],
  ["1", "0"],
  ["1", "2"],
  ["2", "0"],
  ["2", "1"],
  ["2", "3"],
  ["2", "4"],
  ["3", "2"],
  ["3", "4"],
  ["4", "2"],
  ["4", "3"]
];

var roadsObj = arrayToObj(roadsArr);
console.log(roadsObj);

2) Условия графика испытаний

Далее, я бы подумал об условиях, которые вам нужно проверить, чтобы подтвердить, что это галстук-бабочка, и проверить их по одному.

Пять узлов

Вы упомянули, что должно быть ровно пять узлов: мы можем проверить это, проверив, что ровно пять ключей.

/**
 * Check there are exactly five nodes
 * Returns true if 5 keys in roadsObj, false otherwise
 */
function hasFiveNodes(roadsObj) {
  var keys = Object.keys(roadsObj); // -> [0, 1, 2, 3, 4]
  return keys.length === 5;
}

Количество соединений

Вы упомянули, что один узел должен иметь четыре соединения, в то время как другие должны иметь два соединения. Вот один из способов проверить это:

/**
 * Check that each node has two connections, except one node with 4
 */
function hasValidNumConnections(roadsObj) {
  // extract array of values from object
  var valuesArr = Object.values(roadsObj); // -> [[0,1], [0,2] ... [2,3]]

  // map list of values into list of lengths
  var lenArr = valuesArr.map(x => x.length); // -> [2, 2, 4, 2, 2]

  // sort array of lengths
  var sortedLenArr = lenArr.sort(); // -> [2, 2, 2, 2, 4]

  // compare to desired string (because comparing arrays is tricky in JS)
  return sortedLenArr.toString() === "2,2,2,2,4";
}

Другие условия ??

Возможно, вам придется проверить и некоторые другие условия - например, вам может потребоваться проверить не только количество соединений, которые имеет каждый узел, но , какие соединений, чтобы обеспечить структуру bowtie.

3) Собираем все вместе

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

// ---------- helper function ----------

/**
 * Convert array of arrays into object
 * where {key=node, val=[array of connected nodes]}
 */
function arrayToObj(roadsArr) {
  var obj = {};
  roadsArr.forEach(function(pair) {
    var key = pair[0];
    var val = pair[1];
    if (obj[key] === undefined) {
      obj[key] = [val];
    } else {
      obj[key].push(val);
    }
  });
  return obj;
}

// ---------- validator functions ----------

/**
 * Check there are exactly five nodes
 * Returns true if 5 keys in roadsObj, false otherwise
 */
function hasFiveNodes(roadsObj) {
  var keys = Object.keys(roadsObj); // -> [0, 1, 2, 3, 4]
  return keys.length === 5;
}

/**
 * Check that each node has two connections, except one node with 4
 */
function hasValidNumConnections(roadsObj) {
  var valuesArr = Object.values(roadsObj); // -> [[0,1], [0,2] ... [2,3]]
  var lenArr = valuesArr.map(x => x.length);
  var sortedLenArr = lenArr.sort();
  return sortedLenArr.toString() === "2,2,2,2,4";
}

// ---------- main function ----------

/**
 * Check if given array represents a bowtie graph.
 */
function isBowtie(roadsArr) {
  // convert array to object
  var roadsObj = arrayToObj(roadsArr);

  // has exactly 5 nodes?
  if (!hasFiveNodes(roadsObj)) {
    return false;
  }
  console.log("> has 5 nodes");

  // has one node with 4 connections
  if (!hasValidNumConnections(roadsObj)) {
    return false;
  }
  console.log("> has valid number connections");

  // other checks??
  // ... insert here

  // if all pass, return true
  return true;
}

// ---------- testing ----------

roadsArr = [
  ["0", "1"],
  ["0", "2"],
  ["1", "0"],
  ["1", "2"],
  ["2", "0"],
  ["2", "1"],
  ["2", "3"],
  ["2", "4"],
  ["3", "2"],
  ["3", "4"],
  ["4", "2"],
  ["4", "3"]
];

var result = isBowtie(roadsArr);
console.log(result);