I have a function that should to build route from start to destination.

function solve(start, end, fetchRouts): Promise<string[] | string>; 

There also function that returns Promise with reachable points from current:

function fetchRouts(departurePoint: string): Promise<string[]>;

I'm trying to solve using a recursive function. But i can't return the value correctly. Second [*] then is visited 3 times, but returns first time, result is undefined here, so returns 'no ticket';

Inside solve:

const getRoute = (routes, stations) => {
    return routes.then((next) => {
        const temp = [...next];
        while (temp.length !== 0) {
            const current = temp[0];

            const copyStations = [...stations];
            copyStations.push(current);

            if (current === end)
                return Promise.resolve({ result: copyStations, end: true }); //how to throw result from here

            getRoute(fetchRouts(current), copyStations).then(result => {
                if (result && result.end)
                    return result;
            });
            temp.splice(0, 1); // delete station,  because they were on it
        }
    }).then(result => { // [*]
        if (result && result.end) {
            return Promise.resolve(result.result); // to here
        }
        return Promise.resolve('no ticket');
    })
}

return getRoute(fetchRouts(start), [start]);

a lil function description: first argument - Promise<string[]>, contains next stations, also accumulate route (second argument). I split the array and look for the next available one for each station. If available station exists, go to it. If station is destination, return Promise. idk how return its correctly.

CodePudding user response：

What you're doing is graph traversal. You can either do breadth-first or depth-first search, but since you want to do it recursively, depth-first makes sense. Any time you call a function that returns a promise, you need to return it and then process the return value in the then handler.

function solve(start, end, fetchRouts) {
  function getRoute(start, visited = new Set()) {
    visited.add(start);
    return fetchRouts(start).then(nexts => {
      for (const next of nexts) {
        if (next === end) {
          const route = Array.from(visited);
          route.push(end);
          return route;
        }
        if (!visited.has(next)) {
          return getRoute(next, visited);
        }
      }
    });
  }
  return getRoute(start);
}

Adapted from https://fireship.io/courses/javascript/interview-graphs/ depth-first search section.

Here's a runnable snippet:

function solve(start, end, fetchRouts) {
  function getRoute(start, visited = new Set()) {
    visited.add(start);
    return fetchRouts(start).then(nexts => {
      for (const next of nexts) {
        if (next === end) {
          const route = Array.from(visited);
          route.push(end);
          return route;
        }
        if (!visited.has(next)) {
          return getRoute(next, visited);
        }
      }
    });
  }
  return getRoute(start);
}

const dests = {"PHX":["LAX","JFK"],"BKK":["MEX","LIM"],"OKC":["JFK"],"JFK":["PHX","OKC","HEL","LOS"],"LAX":["PHX","MEX"],"MEX":["LAX","BKK","LIM","EZE"],"EZE":["MEX"],"HEL":["JFK"],"LOS":["JFK"],"LAP":[],"LIM":["MEX","BKK"]};
const fetchRoutes = async (station) => dests[station];

solve('PHX', 'BKK', fetchRoutes).then(route => console.log(route));

CodePudding user response：

solution:

function solve(start, end, fetchRouts) {

const getRoute = (start, visited = new Set()) => {

    const clone = new Set(visited);
    clone.add(start);

    return fetchRouts(start).then(nexts => {
        for (const next of nexts) {
            if (next === end) {
                const route = Array.from(clone);
                route.push(end);
                return route;
            }
            if (!clone.has(next)) {
                getRoute(next, clone);
            }
        }
    });
}

return getRoute(start).then(result =>
    result ? Promise.resolve(result) : Promise.resolve('no ticket')
);

};