I can't solve a problem. We have an array. If we take a value, the index of it means port ID, and the value itself means the other port ID it is connected to. Need to find the start index of the longest sequential connection to element which value is -1.
I made a graphic explanation to describe the case for the array [2, 2, 1, 5, 3, -1, 4, 5, 2, 3]. On image the longest connection is purple (3 segments).

I need to make a solution by a function getResult(connections) with a single argument. I don't know how to do it, so i decided to return another function with several arguments which allows me to make a recursive solution.
function getResult(connections) {
return f(connections.findIndex(e => e === -1), connections, 0, []);
}
function f(index, cnx, counter, branches) {
counter++;
for (let i = 0; i < cnx.length; i++) {
if (cnx[i] === index) {
branches.push([i, counter]);
return f(i, cnx, counter, branches);
}
}
return branches.sort((a, b) => b[1] - a[1])[0][0];
}
console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6
Anyway, the code doesn't work completely properly. Would you please explain my mistakes? Is it possible to solve the problem by a function with just one original argument?
The code doesn't work completely properly. Would you please explain my mistakes?
You were quite close. The main problem is that the return keyword in front of the recursive calls terminates the for loop and the entire f function prematurely. This will cause it to visit only the nodes on the first possible branch, not all of them.
The other issue is that branches might be empty at the end of the function, yet you still access [0][0]. Instead return the entire array from f, and access the first tuple on in getResult.
These two small fixes already make the function work1:
function getResult(connections) {
return f(connections.findIndex(e => e === -1), connections, 0, [])[0][0];
}
function f(index, cnx, counter, branches) {
counter++;
for (let i = 0; i < cnx.length; i++) {
if (cnx[i] === index) {
branches.push([i, counter]);
f(i, cnx, counter, branches);
}
}
return branches.sort((a, b) => b[1] - a[1]);
}
console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6
getResult([]), it shouldn't throw an exception if branches is empty. This can be fixed by an specifically handling that case with an if condition, or by including the tuple [-1, 0] (no node, distance 0) in the branches.
Additional improvements would be to do also the sorting only once at the end in getResult, and starting the search directly with f(-1, connections, 0, []); instead of using findIndex.
Is it possible to solve the problem by a function with just one original argument? I don't know how to do it, so i decided to return another function with several arguments which allows me to make a recursive solution.
Introducing a helper function is a totally appropriate solution, this approach is good!
While it's always possible to write a recursive scheme as a loop with an explicit stack, that is usually unwieldy and incomprehensible. With the DFS approach you chose, a recursive function is the easiest and cleanest way to write it.
If you don't want to create an extra global variable, you can even declare your helper function inside getResult. This also allows accessing the connections directly from the upper scope, instead of passing it in as a function parameter. The same can be done to the branches variable:
function getResult(connections) {
const branches = [];
function f(index, distance) {
branches.push([index, distance]);
for (let i = 0; i < connections.length; i++) {
if (connections[i] === index) {
f(i, distance+1);
}
}
}
f(-1, 0);
branches.sort((a, b) => b[1] - a[1]);
return branches[0][0];
}
console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6
As for further alternatives and optimisations:
-1, with each child node pointing to its parent, never forming a circle (since there is no node -1 that points anywhere).connections array to find children of a node (the is referencing the current index), build an actual tree structure in a single iteration of the connections, then traverse that tree to find the deepest branch.