从起始节点查找分离值

Question

我在一些在线编码练习中发现，这个看起来很酷，我想试一试。

问题陈述

奎恩是个很受欢迎而且非常谦虚的人。其他学生则在一个名为QDist的单元中测量他们的受欢迎程度。

我们可以通过找出他们自己和奎恩之间的分离程度来计算他们的QDist值。例如:如果Quinn是Dave的朋友，Dave是Travis的朋友，那么Dave的QDist值是1，Travis是2。

输出

输入的每个人的名称QDist按名称按字母顺序排列。如果一个人在任何情况下都没有连接到Quinn，那么输出名称就不酷了。

给出一份友谊清单，按字母顺序列出每个人及其QDist值。

样本输入/输出

10
Alden Toshiko
Che Kortney
Che Dorian
Ronda Lindell
Sharon Alden 
Dorian Quinn
Owen Sydnee
Alden Che
Dorian Tyra
Quinn Ally

输出

Alden 3
Che 2
Dorian 1
Kortney 3
Lindell uncool
Ally 1
Owen uncool
Quinn 0
Ronda uncool
Sharon 4
Sydnee uncool
Toshiko 4
Tyra 2

My Approach

首先，我不想要答案--我只想知道如何在javascript中处理这个问题(因为它是我最熟悉的语言)。我的想法是将程序分解为一个对象和数组，并尝试在每个名称之间创建一个家族关系，类似于嵌套对象或数组。然后，我可以使用某种递归来查找数组或对象的深度。

什么是最好的方法？

Answer 1

从输入中可以创建一个人员列表。它可以是一个对象，其中每个键都是一个人的名字，而对应的值是一个名称数组，表示该人的朋友。当然，当你把B加为A的朋友时，你也必须把A加为B的朋友。

对于示例输入，上面的结构如下所示：

{
  "Alden": ["Toshiko","Sharon","Che"],
  "Toshiko": ["Alden"],
  "Che": ["Kortney","Dorian","Alden"],
  "Kortney": ["Che"],
  "Dorian": ["Che","Quinn","Tyra"],
  "Ronda": ["Lindell"],
  "Lindell": ["Ronda"],
  "Sharon": ["Alden"],
  "Quinn": ["Dorian","Ally"],
  "Owen": ["Sydnee"],
  "Sydnee": ["Owen"],
  "Tyra": ["Dorian"],
  "Ally": ["Quinn"]
}

然后跟踪一个名字列表，从Quinn开始，还有一个距离，从0开始。

然后，对于列表中的每个名称，将当前距离指定为它们的QDist值。然后找到他们的朋友，把他们聚在一起。删除已经收到QDist值的名称。

然后增加距离，并对新的名称列表重复上面的内容。

继续重复，直到名称列表为空。

请注意，如果您按正确的顺序进行操作，则可以用QDist值替换朋友的个人列表。因此，在前两次迭代之后，上述结构将更改为：

{
  "Alden": ["Toshiko","Sharon","Che"],
  "Toshiko": ["Alden"],
  "Che": ["Kortney","Dorian","Alden"],
  "Kortney": ["Che"],
  "Dorian": 1,
  "Ronda": ["Lindell"],
  "Lindell": ["Ronda"],
  "Sharon": ["Alden"],
  "Quinn": 0,
  "Owen": ["Sydnee"],
  "Sydnee": ["Owen"],
  "Tyra": ["Dorian"],
  "Ally": 1
}

当算法完成时，您有：

{
  "Alden": 3,
  "Toshiko": 4,
  "Che": 2,
  "Kortney": 3,
  "Dorian": 1,
  "Ronda": ["Lindell"],
  "Lindell": ["Ronda"],
  "Sharon": 4,
  "Quinn": 0,
  "Owen": ["Sydnee"],
  "Sydnee": ["Owen"],
  "Tyra": 2,
  "Ally": 1
}

现在剩下的朋友数组需要替换为“不酷”，因为显然对应的人与Quinn没有关联。此外，列表需要排序。

扰流板警告！

下面是一个工作片段：

​

// Get input as text
var input = `10
Alden Toshiko
Che Kortney
Che Dorian
Ronda Lindell
Sharon Alden 
Dorian Quinn
Owen Sydnee
Alden Che
Dorian Tyra
Quinn Ally`;

// Build persons list with friends list
var persons = 
    // Take the input string
    input
    // Split it by any white-space to get array of words
    .split(/\s+/)
    // Skip the word at position 0: we don't need the line count
    .slice(1)
    // Loop over that array and build an object from it 
    .reduce(
        // Arguments: obj = result from previous iteration
        //            name = current name in names array
        //            i = index in that array
        //            names = the whole array being looped over
        (obj, name, i, names) => (
               // Get the list of friends we already collected for this name.
               // Create it as an empty array if not yet present.
               obj[name] = (obj[name] || [])
               // Add to that list the previous/next name, depending
               // whether we are at an odd or even position in the names array
               .concat([names[i%2 ? i-1 : i+1]])
               // Use the updated object as return value for this iteration
               , obj)
        // Start the above loop with an empty object
        , {});

// Now we have a nice object structure: 
//    { [name1]: [friendName1,friendName2,...], [name2]: ... }
// Start with Quinn as the only person we currently look at.
var friends = ['Quinn'];
// Increment the distance for each "generation" of friends 
// until there are none left.
for (var i = 0; friends.length; i++) {
    // Replace the friends list with a new list, 
    // while giving the friends in the current list a distance
    friends = 
        // Start with the current list of friends
        friends
        // Loop over these friends. 
        // Only keep those that still have a friends array (object) assigned to them,
        // since the others were already assigned a distance number.
        .filter(friend => typeof persons[friend] === "object")
        // Loop over those friends again, building a new list of friends
        .reduce((friends, friend, k) => [
                // Add this friends' friends to the new list
                friends.concat(persons[friend]),
                // ... and then replace this friends' friend list 
                // by the current distance we are at.
                persons[friend] = i
                // Return the first of the above two results (the new list)
                // for the next iteration.
                ][0]
            // Start with an empty array for the new friends list
            , []);
}

// Now we have for each person that connects to Quinn a number: 
//    { [name1]: number, ... }

// Convert this to a format suitable to output
var result = 
    // Get list of names from the object (they are the keys)
    Object.keys(persons)
    // Sort that list of names
    .sort()
    // Loop over these names to format them
    .map(name =>
        // Format as "name: distance" or "name: uncool" depending on whether there
        // still is an array of friends (object) in this entry
        name + ': ' + (typeof persons[name] == 'object' ? 'uncool' : persons[name]));

// Output the result in the console
console.log(result);

​

还有一个更详细，但更容易理解的版本：

​

// Get input as text
var input = `10
Alden Toshiko
Che Kortney
Che Dorian
Ronda Lindell
Sharon Alden 
Dorian Quinn
Owen Sydnee
Alden Che
Dorian Tyra
Quinn Ally`;

// Build persons list with friends list
// Take the input string
var persons = input;
// Split it by any white-space to get array of words
persons = persons.split(/\s+/)
// Skip the word at position 0: we don't need the line count
persons = persons.slice(1)
// Loop over that array and build an object from it 
var obj = {}; // Start loop with an empty object
for (var i = 0; i < persons.length; i++) {
    var name = persons[i]; // name = current name in names array
    // Get the list of friends we already collected for this name.
    // Create it as an empty array if not yet present.
    if (obj[name] === undefined) obj[name] = [];
    // Add to that list the previous/next name, depending
    // whether we are at an odd or even position in the names array
    obj[name].push(persons[i%2 === 1 ? i-1 : i+1]);
}
// Assign result to persons
persons = obj;
// Now we have a nice object structure: 
//    { [name1]: [friendName1,friendName2,...], [name2]: ... }
// Start with Quinn as the only person we currently look at.
var friends = ['Quinn'];
// Increment the distance for each "generation" of friends 
// until there are none left.
for (var i = 0; friends.length !== 0; i++) {
    // Loop over those friends, building a new list of friends
    // Start with an empty array for the new friends list
    var newFriends = [];
    for (var k = 0; k < friends.length; k++) {
        var friend = friends[k];
        // Only consider those that still have a friends array (object) assigned to them,
        // since the others were already assigned a distance number.
        if (typeof persons[friend] === "object") {
            // Add this friends' friends to the new list
            newFriends = newFriends.concat(persons[friend]);
            // ... and then replace this friends' friend list 
            // by the current distance we are at.
            persons[friend] = i;
        }
    };
    // Make the new list the current list:
    friends = newFriends;
}

// Now we have for each person that connects to Quinn a number: 
//    { [name1]: number, ... }

// Convert this to a format suitable to output
// Get list of names from the object (they are the keys)
var result = Object.keys(persons);
// Sort that list of names
result.sort();
// Loop over these names to format them
for (var i = 0; i < result.length; i++) {
    var name = result[i];
    // Format as "name: distance" or "name: uncool" depending on whether there
    // still is an array of friends (object) in this entry
    if (typeof persons[name] == 'object') {
        result[i] = name + ': uncool';
    } else {
        result[i] = name + ': ' + persons[name];
    }
}

// Output the result in the console
console.log(result);

​

Answer 2

如果我要解决这个问题，

首先，我将创建一个数组，并通过在原始数组中查找行(元素)、、studentX、、、←→、Quinn 等行(元素)，与1的学生一起初始化它。

然后，通过查找student(n-1)FromQuinn studentX←→，递归地搜索那些级别为n的quinn。

Answer 3

我试图理解

var persons = input.split(/\s+/).slice(1).reduce(function(obj,name,i,names){
    return (obj[name] = (obj[name] || []).concat([names[i%2 ? i-1 : i+1]]), obj);

},{});

首先，input.split(/\s+/).slice(1)给出了一个数组，其中包含所有的名称。现在

(obj[name] = (obj[name] || []).concat([names[i%2 ? i-1 : i+1]]), obj);

在默认情况下，obj将根据{}属性设置为reduce方法。

名称是当前值，它基本上从Alden一直到Ally。i将离开1-10，而names是数组

现在我们要说的是，如果可能的话，设置obj[name] = obj[name].concat([names[i%2 ? i-1 : i+1]]),obj);。如果这是不可能的，那么设置obj[name] = [].concat([names[i%2 ? i-1 : i+1]]),obj);。这是我对||的解读

示例迭代

第一个obj = {}，名称将是Alden，所以Aldeni.e persons = { Alden: ..}类型将是obj[Alden].concat(names[2],obj)，它将是2，因为没有到达1 mod 2。

现在我有点困惑..。,obj到底在这里做什么..？我解释得对吗？