Find the only path javascript?

Question

I need help in trying to solve this coding challenge:

Giving an array of strings that represent the name of the island, n the number of queries, starting island, ending island.

Taking into consideration that there is ONLY one path that leads from starting island to ending island. Input Format:

• The first line contains the count of connections n.

• The second line, contains two islands name seprated by a space. The first is where Mario is right now and the second one is where Mario wants to go.

• n lines follow, each containing two islands name(A and B) separated by a space . Each line indicate a connection between the island A and the island B

This is a sample to understand better the challenge:

input sample: 
5// number of queries

yoshi donut // frist string is the starting island,second is the end

// this our table.
donut vanilla
donut twin
twin forest
choclate donut
forest yoshi

output sample:
forest twin donut

Explanation 
There are 5 connections, and Mario is currently at yoshi island, his hometown is donut island. So the path is forest -> twin -> donut 
Notice how the start island is not printed but the final island is.


function getMarioHome(n,pos,dest, arr) {

var arr = [{a:"donut",b:"vanilla"},{a:"donut",b:"twin"},{a:"twin",b:"forest"},{a:"choclate",b:"donut"},{a:"forest",b:"yoshi"}];


var uniqueArray = arr.filter(function(item) {
    return item.a === pos || item.b === pos;
}) // meaning that you created a temp table holding all possible connections from destination

console.log(uniqueArray);
}

I am stuck here for the past 24H!.

Answer 1

I wanted to delete this file from my computer:) I hope you found your own solution.

This is not the fastest solution since it will try to find every possible route. To improve performance it should stop looking for routes when a valid route is found. This could however be used to find the route with the least hops.

var arr = [{a:"donut",b:"vanilla"},{a:"donut",b:"twin"},{a:"twin",b:"forest"},{a:"choclate",b:"donut"},{a:"forest",b:"yoshi"}];

function gotoIsland(targetIsland, currentIsland, path) {
  path = path || []; // initialize path if not set
  if(targetIsland == currentIsland) {
    return path;
  }

  
  let connectedIslands = arr.filter(pair => pair.a == currentIsland || pair.b == currentIsland) // get pairs that are connected to current island 
  .map(pair => pair.a == currentIsland ? pair.b : pair.a) // get the connected islands name

  var possiblePaths = connectedIslands.map(nextIsland => {
    var hasTravelevedToIsland = path.filter(previousIsland => previousIsland == nextIsland);
    // if they have not been to the island go to the island
    if (hasTravelevedToIsland.length == 0) {
      // copy path so the path is not corrupted during branching paths
      var copyPath = path.slice();
      copyPath.push(nextIsland);
      return gotoIsland(targetIsland, nextIsland, copyPath);
    }
    return false
  }).filter((path) => path != false)
  if (possiblePaths.length) {
    if (possiblePaths.length == 1) {
      // if there is only a single path then flatten the array
      return possiblePaths[0];
    } else {
      // allow support for multiple paths :D
      // problem with this is that the output can wary depending on how many paths there are
      // if you only want 1 solution then just return the first element.
      return possiblePaths
    }
  } 
  
  // return false if there is no way to get to the island from the current island
  return false;
}

var path = gotoIsland("donut", "yoshi");
console.log("solution", path);