找到唯一的路径javascript？

Question

我需要帮助来解决这个编码挑战：

给出一个字符串数组，表示岛屿名称，n个查询次数，起始岛屿，结束岛屿。

考虑到从起点岛到终点岛只有一条路。输入格式：

第一行包含连接数 n。
第二行，包含两个岛屿名称，中间用 space 分隔。第一个是马里奥现在所在的位置，第二个是马里奥想去的地方。
n 行，每行包含两个岛屿名称（A 和 B），由 space 分隔。每条线表示A岛和B岛之间的连接

这是一个示例，可以更好地理解挑战：

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

过去 24 小时我都被困在这里！

Answer 1

我认为，这是基于@frithjof 的见解的可能解决方案：

1/ 从目标中提取所有连接。

2/ 创建一个遍历每个连接的递归函数

2-1/ if(destination is reached){
     return true; console.log(the result)
}
2-2/ if(not the destination && ,no more path){
   return false;
}
2-3/ else {
   return path;
 }

注意：这还没有在 JS 中测试过。

Answer 2

我想从我的电脑中删除这个文件:)希望你找到了自己的解决方案。

这不是最快的解决方案，因为它会尝试找到每条可能的路线。为了提高性能，它应该在找到有效路线时停止寻找路线。然而，这可用于查找跳数最少的路由。

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

找到唯一的路径javascript？

Find the only path javascript?

javascript

node.js

path-finding