Find separation values from a starting node

Question

I found on some online coding exercises and this one looks really cool and I wanted to give it a shot.

Problem Statement

Quinn is a pretty popular, and extremely modest guy. Other students measure their popularity in a unit called QDist.

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.

Output

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

Given a list of friendships, list each person and their QDist value in alphabetical order.

Sample Input/output

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

Output

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

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.

What would be the best approach?

Answer 1

If i had to solve this problem,

First I would create an array and initialise it with student who are 1 with Quinn by finding rows (elements) studentX ←→ Quinn in original array.

Then I would search recursively those who are level n with quinn by finding rows studentX ←→ student(n-1)FromQuinn

Answer 2

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"]
}

Then keep track of a list of names, starting with just Quinn, and also a distance, starting at 0.

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.

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
}

When the algorithm finishes, you have:

{
  "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
}

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.

Spoiler warning!

Here is a working snippet:

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

Answer 3

My attempt to understand

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

},{});

First input.split(/\s+/).slice(1) Gives us an array with all of the names in it. Now

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

obj is set by default to due to {} according to the reduce method property.

name is current value which is basically going from Alden all the way to Ally. i will go from 1-10 and names is the array

Now we are saying set obj[name] = obj[name].concat([names[i%2 ? i-1 : i+1]]),obj); IF this is possible. If this isn't possible set obj[name] = [].concat([names[i%2 ? i-1 : i+1]]),obj);. This is my interpretation from reading up on ||

Example iteration

first obj = {}, and name will be Alden so the type Alden i.e persons = { Alden: ..} will be obj[Alden].concat(names[2],obj), it will be 2, since 1 mod 2 doesn't get reached.

Now there is where I am a bit confused... what exactly is the ,obj doing here..? am I interpreting this right?