Javascript: build possible paths through an object tree

Question

I have an object: {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]} which I would like to loop/traverse through.

• Each key of this object is like a point or location (eg location 1 or location 2).
• And each location is linked to one or two other locations, allowing you to jump from one to the next. These "links" are defined by the array-property of each key. For example, I can jump from location 1 to location 2, or from location 3 to location 8.

Now I would like to map out these links in the form of a 2D array. The 2D array should contain all possible paths, with each path starting with location 1 and ending with location End (defined only in the array of key 8).


I have the following code so far:

let paths_list;
function find_paths(obk, data={}) {
    paths_list = data?.paths_list || [];
    let newest_path = data?.newest_path || [1];
    let current_number = data?.current_number || 1;
    let next_possible_numbers_iteration = (data.next_possible_numbers_iteration || 0);

    if((current_number == "End" || current_number == undefined) && next_possible_numbers_iteration >= obk[1].length) {
        return paths_list;
    }

    let next_possible_numbers;
    let next_number;

    for(let i = 0; i < 2; i++) {
        if(current_number == "End" || current_number == undefined) {
            next_possible_numbers_iteration++;
            current_number = 1;
            paths_list.push(newest_path);
            newest_path = [1];
        }
        next_possible_numbers = obk[current_number]; // [2,2]
        next_number = next_possible_numbers[next_possible_numbers_iteration];
        newest_path.push(next_number);
        current_number = next_number;
    }
    

    if(current_number != "End" && current_number != undefined) {
        find_paths(obk, {
            paths_list,
            newest_path,
            current_number,
            next_possible_numbers_iteration
        });
    } else {
        next_possible_numbers_iteration++;
        paths_list.push(newest_path);
        find_paths(obk, {
            paths_list,
            current_number,
            next_possible_numbers_iteration
        });
    }
}


let my_obk = {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]};
find_paths(my_obk);
console.log(paths_list);

Problem

But there is a slight problem: The function returns only some of the possible paths. Specifically, it returns these correctly:

• 1,2,3,4,8,End
• 1,3,8,End

But does not return other paths such as:

• 1,2,3,8,End

This is because the function only searches in the same position in each array-property and does not fluctutate the position at which it searches (defiend by next_possible_numbers_iteration).

In short, my question is how would I make the func look at different positions in each array (or property) instead of just one in all arrays. This probably does not make sense when you read it, but if you look at how the variable next_possible_numbers_iteration is used, you'll see what I mean. Feel free to change my function if it is hopeless.

Answer 1

The recursive solution by @Nina looks great

If you want a iterative way of solving the same you can check this

Keep on creating new paths until all paths end : )

const obj = { 1: [2, 3], 2: [3, 3], 3: [4, 8], 4: [8, 8], 8: ['End', 'End'] };

let paths = obj[1].map((x) => [1, x]);
let complete = false;

while (!complete) {
  complete = true;
  
  const result = [];
  paths.forEach((path) => {
    const lastElementOfPath = path[path.length - 1];
    const nextPathDirections = obj[lastElementOfPath];
    if (nextPathDirections) {
      Array.from(new Set(nextPathDirections)).forEach((nextPathElement) => {
        result.push([...path, nextPathElement]);
        if (nextPathElement !== 'End' && !!obj[nextPathElement]) {
          complete = false;
        }
      });
    } else {
      result.push([...path]);
    }
  });
  
  paths = result;
}


// Paths will be your desired result
paths.forEach(path => console.log(...path))