Getting the closest path of target from an array

Lets say I have an array like this:

const array = [
   ['a', [[19], [2]]],
   ['b', [[3], [4]]],
   ['c', [[15], [6]]],
];

And now I want to create a function which will take two things as arguments 1. the target 2. the array

const getClosestPath = (array, target) => {
// logic will be here to find the path    
return closestPath;
}

// sample input
getClosestPath(array, 19) // should return a - 19
getClosestPath(array, 4) // should return b - 4

Any idea how can I achieve this, thanks!

You’ll want to set up some variables:

  1. for the closest key (or index, either is fine).
  2. for the closest value.
  3. for the current smallest difference (start at Infinity or some arbitrarily high number).

Then loop through the array. Check what the difference between the target and each of the numbers is in turn (you would use Math.abs for this). If the difference is less than the smallest difference, then set closest key to the key, closest value to the value, current smallest difference to that difference.

Because you have two values, that would be two if statements in the loop (not if…else, needs to run one then the other).

Return the string you want , which will be closestKey + " - " + closestValue

This operation can be done via an imperative loop (for…of is probably most sensible), or via reduce – what you want means some faffy logic so the imperative loop is likely to be easier to write and to read afterwards.

Note that it’s a bit difficult to provide help here without context: there may be a better way, but what you’ve posted is bit abstract (eg what is the weird data structure, why do you need to return that specific value)

Actually I wanted to find out the shortest path of a single target node from the root.

Now I want something like this:

findPath(rootObject, 'VV') // which will return D => F => VV
const array = [
   ['a', [[19], [2]]],
   ['b', [[30], [4]]],
   ['c', [[15], [6]]],
];

function closestPath(target, array){
    let closest = array[0];
    let closestDistance = Infinity;
    for(let i = 0; i < array.length; i++){
        let distance = Math.abs(target - array[i][1][0]);
        if(distance < closestDistance){
            closest = array[i];
            closestDistance = distance;
        }
    }
    return closest;
}

console.log(closestPath(30, array));

This code seems working, can you explain a bit for me? thanks!

Ok, can you explain the two values: that gives you the closest first value, the second one is ignored? And do you have a description of what you’re trying to achieve and what the data structures look like?

What you want is probably a depth-first or breadth-first search (your choice), which is easiest to implement using a recursive function, but how you do that & what you need is easier to advise on with the above info.

Anyhoo, that code is fine for getting that closest path:

So you set what the closest node is (that could just be let closest; but makes sense to set it as the first node, can assume there is always at least that). You set what the distance is to Infinity, because everything is < that – means that the first check in the loop (if (distance < closestDistance)) is always going to return true.

The distance has to be target - theCurrentValueYouAreComapring. And because you don’t care what that current value is, just what the difference is between it and the target value, you use abs to give you the absolute value (if it’s negative, it strips the sign, so you always get a positive number). Then you can compare distance to the closestDistance. On the first run of the loop, that’s Infinity, so distance will always be less than that.

For reference I had something like:

function getClosestPath (nodes, target) {
  let closestKey = nodes[0][0];
  let closestTarget = 0;
  let diff = Infinity;

  for (const [k, [[x], [y]]] of nodes) {
    const currDiffX = Math.abs(target - x);
    const currDiffY = Math.abs(target - y);

    if (currDiffX < diff) {
      closestKey = k;
      closestTarget = x;
      diff = currDiffX;
    }

    if (currDiffX < diff) {
      closestKey = k;
      closestTarget = y;
      diff = currDiffY;
    }

    console.log(`Closest node key is ${closestKey}, closest target in that node is ${closestTarget}`);
  }
  return `${closestKey} - ${closestTarget}`;
}

But not quite sure how that fits in now – you probably don’t want your closestPath function in its current form, you’ll need to integrate some of the logic of it into a [likely recursive] function that walks the tree

1 Like