Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Dwarfs standing on the shoulders of giants

Original Problem

The Goal

The saying "Dwarfs standing on the shoulders of giants" refers to the importance of being able to build upon the work of our predecessors.
When we read texts, we often only get a small glance of this dependence: this person influenced that person. Thereafter, we learn that the second person, in turn influenced a third and so on. In this exercise we’re interested in the chain of influence and more precisely in finding the longest possible chain.​

Rules

We choose to represent each person by a distinct integer. If person #1 has influenced persons #2 and #3 and person #3 has influenced #4 then there is a succession of thoughts between #1, #3 and #4. In this case, it’s the longest succession and the expected result will be 3, since it involves 3 people.

If we were to complete this example when we learn that person #2also influenced persons #4 and #5, then the longest succession will still have a length of 3, but there will now be several of them.

If we now add that person #10 influenced person #11, the result remains 3. However, as soon as we learn that #10 also influenced #1and #3, then the result becomes 4, since there is now a succession involving 4 people, which is #10, #1, #2, #5.

Note: It takes time for a thought to influence others. So, we will suppose that it is not possible to have a mutual influence between people, i.e. If A influences B (even indirectly through other people), then B will not influence A (even indirectly). Also, you can not influence yourself.

Game Input

Input

Line 1: The number N of relationships of influence.

N following lines: a relationship of influence between two people in the form of X (whitespace) Y, which indicates that X influences Y. The relationships of influence are listed in any order.

Output
The number of people involved in the longest succession of influences.
Constraints
0 < N < 10000
0 < X, Y < 10000

Solution

We need some way to store the graph. I decided to store the graph as key-value mapping, with the key the number of the node and the value an array of all adjacent nodes. In the first step we duplicate in a path and a root mapping:

var path = {};
var root = {};

var n = readline();

for (var i = 0; i < n; i++) {

    var t = readline().split(" ");

    if (undefined === path[t[0]]) {
        path[t[0]] = [t[1]];
        root[t[0]] = [t[1]];
    } else {
        path[t[0]].push(t[1]);
        root[t[0]].push(t[1]);
    }
} 

In the next step, we go over all nodes in the root mapping and delete every node from it, which occurs as a node. The idea is that only the real root nodes will remain in root:

for (var i in root) {
    for (var j = 0; j < root[i].length; j++) {
        delete root[root[i][j]];
    }
}

The only remaining thing left is looping over all root nodes and find the maximum diameter of the graph:

var s = 0;
for (var i in root) {
    s = Math.max(s, diameter(path, i));
}
print(s);

The only missing piece is the diameter calculation. Let's define this recursively. If a node does not have a certain element, the recursion needs to end. Otherwise we loop in a depth-first-search manner over all adjacent elements. The maximum depth we can find this way is the depth of the current node. But hold on. When we calculate the depth this way, a lot of nodes will be computed over and over again, when they're visited via another node. Introducing a memory which stores nodes we've already seen can help here. The diameter implementation then looks like this:

var hash = {};
function diameter(path, node) {

    if (!path[node]) {
        return 1;
    }

    if (hash[node]) {
        return hash[node];
    }

    var max_d = 0;
    for (var i = 0; i < path[node].length; i++) {
        max_d = Math.max(max_d, diameter(path, path[node][i]));
    }
    return hash[node] = 1 + max_d;
}

Go to overview

All images are copyright to Codingame