How to find all possible paths in 2d array of numbers from the first to the last, where each step's value is greater than the previous step?

Question

The code I've got so far finds only 2 possible paths. How can I rework it to find all of them?

An example of a valid path would be, begin with the first array [1, 32]. Choose a number to step from, like 32.

Look at the next array immediately below: [11, 21, 24, 27, 35, 37, 65]. A valid step would be to any of these numbers that are greater than your current step. So 35, 37, and 65 would all be valid steps.

And continue constructing the path by taking steps onto the other arrays in order (top to bottom) until you reach the last.

'use strict';

const matrix = [
  [1, 32],
  [11, 21, 24, 27, 35, 37, 65],
  [17, 22, 25, 51, 57, 63],
  [18, 56]
];

function findPaths(arrays) {
  const paths = [];
  for (let i = 0; i < arrays[0].length; i++) {
    const path = [arrays[0][i]];
    for (let j = 1; j < arrays.length; j++) {
      for (let y = 0; y < arrays[j].length; y++) {
        if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
          path.push(arrays[j][y]);
          break;
        }
      }
    }
    paths.push(path);
  }
  return paths;
}

const result = findPaths(matrix);

console.log(result); // [ [ 1, 11, 17, 18 ], [ 32, 35, 51, 56 ] ]

Answer 1

I solved it. It's not the most efficient solution, but I'm working on it.

const data = [
  [1, 32],
  [11, 21, 24, 27, 35, 37, 65],
  [17, 22, 25, 51, 57, 63],
  [18, 56]
];

function findPaths(arrays) {
  const paths = [];
  const maxPaths = arrays.reduce((total, arr) => total *= arr.length || total, 1);
  for (let x = 0; x < maxPaths; x++) {
    for (let i = 0; i < arrays[0].length; i++) {
      const path = [arrays[0][i]];
      for (let j = 1; j < arrays.length; j++) {
        for (let y = 0; y < arrays[j].length; y++) {
          if (path[Math.max(0, path.length - 1)] < arrays[j][y]) {
            if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
              path.push(arrays[j][y]);
              break;
            }
          }
        }
      }
      paths.push(path);
    }
  }
  return paths.filter(path => path.length == arrays.length).sort();
}

const result = findPaths(data);

console.log(result);

/*
[
  [ 1, 11, 17, 18 ],  [ 1, 11, 17, 56 ],
  [ 1, 11, 22, 56 ],  [ 1, 11, 25, 56 ],
  [ 1, 11, 51, 56 ],  [ 1, 21, 22, 56 ],
  [ 1, 21, 25, 56 ],  [ 1, 21, 51, 56 ],
  [ 1, 24, 25, 56 ],  [ 1, 24, 51, 56 ],
  [ 1, 27, 51, 56 ],  [ 1, 35, 51, 56 ],
  [ 1, 37, 51, 56 ],  [ 32, 35, 51, 56 ],
  [ 32, 37, 51, 56 ]
]
*/