Javascript 2D Matrix traversal

[Osiris]

Hello, I have a 2D square matrix that looks something like this for example:

const exampleGridB = [
  [9,    32,  12,  14],
  [21,   20,  3,   0],
  [4,    0,   1,   2],
  [0,    5,   13,  1]
];

The idea is that you have to find several paths and return the largest sum along with the path used, following this rule:
You can only move diagonally one square up or one square down and only start from the first column but you can choose the row (by moving diagonally one square up/down you can only move like in examples below but you cannot do something like: 9, 0 , 5 so you cannot skip that far so it s a bit like chess).

In other words you can have paths like this:
9, 20, 1, 1
21, 0, 13
4, 5
or something like this (zig zag or check mark)
9, 20, 12, 0
9, 20, 1, 0
21, 0, 13, 2

Can anyone help with an idea is there an algorithm that can be applied for this case?
It looks like a recursion should be involved.
Any idea is welcome.

[danfly09]

You could call a for loop with different starting points for the iterator, and the high bound, with an offset of the matrix length.

Inside the loop, check if the iterator is greater than the length of the matrix, then, when calling the elements in the matrix, if the iterator is greater than the matrix length, subtract the length but only for calling the matrix element, don’t modify the iterator.

Starting from 3 for example, your i = 3; i < 7; i++
on your second pass… i = 4… because that is greater than the matrix length, you will then subtract 4, and check matrix[ i - 4]

PS: I misread… I thought you had to move all the way and then overflow to the next row.
Like 9, 20, 1, 1 or 12, 0, 4, 5

[michaelnicol]

Could you specify more details in the question?

Are you given the path coordinates and need to figure out the largest cell value out of all of them? The total values for the all of the cells combined? Or are you trying to write a function, that given a starting coordinate, can determine the path highest possible sum?

For example, start at cell 21 (1,0) and determine the highest value path until you hit the edge of the matrix? This is a difficult problem if this is the case, because every time you traverse a cell you branch 3 other diagonal cells you didn’t use in your path. The number of possible paths goes up exponentially as you check paths.

[Osiris]

It always starts at column 1(so always left side), but you decide which row to start with so for example u can start with number 21. The idea is that you should traverse from left to right and you sum all cell values you go through

[michaelnicol]

How is the user actually going to command where they are going? Are they going input a 2D array into the function defining what cells to traverse for the entire path.

traverse([[0,0],[1,1],[2,2]]) … etc