从起始节点查找分隔值 [英] Find separation values from a starting node
问题描述
我在一些在线编码练习中发现，这个看起来非常酷，我想试一试。
I found on some online coding exercises and this one looks really cool and I wanted to give it a shot.
问题陈述
奎因是一个非常受欢迎，非常谦虚的家伙。其他学生在称为QDist的单元中衡量他们的受欢迎程度。
Quinn is a pretty popular, and extremely modest guy. Other students measure their popularity in a unit called QDist.
可以通过查找他们自己和Quinn之间的分离程度来计算他们的QDist值。例如：
如果Quinn是Dave的朋友，而Dave是Travis的朋友，那么Dave的QDist值是1，而Travis是2.
One can calculate their QDist value by finding the degrees of separation between their self and Quinn. For example: If Quinn is friends with Dave, and Dave is friends with Travis, then Dave's QDist value is 1, and Travis is 2.
输出
按名称按字母顺序排序的每个人输入的名称QDist。
如果一个人无论如何都没有连接到Quinn，输出名称为uncool
name QDist for each person entered ordered alphabetically by name. In the event that a person is not connected to Quinn in anyway, output name uncool
给定一个友谊列表，列出每个人及其QDist值按字母顺序。
Given a list of friendships, list each person and their QDist value in alphabetical order.
样本输入/输出
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
我的方法
首先，我不希望回答我只是想要一个关于如何在javascript中解决问题的提示或指导（因为它是我最熟悉的语言）。我的想法是将程序分解为一个对象和数组，并尝试在每个名称之间创建一个族关系，作为嵌套对象或者数组。然后我可以使用某种递归来查找数组或对象的深度。
Firstly, I don't want the answer I just want a hint or some guidance on how I should approach the problem in javascript (as its the language i'm the most familiar with). My thought was to break the program into an object and arrays, and try to create a family relationship between each name, sort of as a nested object or perhaps an array. Then I could use some sort of recursion to find how deep the array or object goes.
什么是最好的方法？
推荐答案
从输入你可以创建一个人员列表。它可以是一个对象，其中每个键是一个人的名字，相应的值是一个名字数组，代表该人的朋友。当然你应该确保当你添加B作为A的朋友时，你还必须添加A作为B的朋友。
From the input you could create a list of persons. It could be an object, where each key is a person's name, and the corresponding value is an array of names, representing the friends of that person. Of course you should make sure that when you add B as a friend of A, you must also add A as a friend of B.
对于示例输入，以上结构看起来像这样：
For the example input, the above structure would look like this:
{
"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开始。
Then keep track of a list of names, starting with just Quinn, and also a distance, starting at 0.
然后，对于该列表中的每个名称，将当前距离指定为其QDist值。然后找到他们的朋友，把他们放在一起。删除已收到QDist值的名称。
Then for each name in that list, assign the current distance as their QDist value. Then find their friends and put them all together. Remove names that have already received a QDist value.
然后增加距离，并对新的名称列表重复上述步骤。
Then increase the distance, and repeat the above for that new list of names.
继续重复，直到名单列表为空。
Keep repeating until the list of names is empty.
请注意，如果按正确顺序执行操作，则可以替换朋友列表通过QDist值。所以上面的结构会在前两次迭代后发生变化：
Note that if you do things in the right order, you can replace a persons list of friends by the QDist value. So the above structure would change after the first two iterations to:
{
"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
}
现在剩余的朋友数组需要替换为uncool，显然相应的人们与奎因没有关系。此列表也需要排序。
Now the remaining friends arrays need to be replaced with "uncool", as apparently the corresponding people have no connection with Quinn. Also the list needs to be sorted.
这是一个工作片段：
// 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);
更详细，但更容易理解的版本：
And a more verbose, but easier to understand version:
// 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);
这篇关于从起始节点查找分隔值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
