javascript - Find Maximum Path thats divisible by 3 in 2D array

Question

Given a two-dimensional array of numbers.

Find the "snake path" whereas:

• In a snake path there needs to be a element in each row, and in two adjacent rows the elements are in adjacent columns

• The sum of the "snake path" needs to be maximum and divisible by 3 (the elements itself don't necessary have to be divisible of 3)

I've been trying to solve this question for ages. What I've tried so far is:

I calculated that there are n^3 potential snake paths and the length of each snake path is n and then I'd just loop over the n^3 potential snake paths and check which one has a maximum sum and being divisible by 3.

The problem is this approach isn't so efficient it'll take O(n^4) which is pretty slow and this problem seems like one that can be solved using dynamic programming.

Any help would be greatly appreciated

Answer 1

I did find this an interesting problem to fiddle with. Here is a potential solution, which will find a path like the following:

Start at index 5 ---v
                    __       
 7   6   5   4   3 | 2|  1    (start)     2
                   '-- __               
 2   4   6   8  10  12 |14|   (right)  + 14 
                    __ /--' 
 2   7   1   8   2 | 8|  1    (left)   +  8
                __ /--'
 3   1   4   1 | 5|  9   2    (left)   +  5
               '-- __
 2   3   5   7  11 |13| 17    (right)  + 13
                   '-- __  
 8   6   7   5   3   0 | 9|   (right)  +  9
                       '--'            ----
                               total:    51

which would get reported like this:

{path: "RLLRR", startIndex: 5, total: 51}

The implementation looks like this:

const maxMod3Path = (grid) => 
  [...grid] .reverse () .reduce ((prev, row, ri) => row .map ((c, i) => 
    [
      ...(prev [i - 1] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'L' + p})), 
      ...(prev [i + 1] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'R' + p})), 
    ] 
      .map (({n, p}) => ({n: n + c, p}))
      .reduce (
        (a, {n, p}) => {a [n % 3] = (n > a [n % 3] .n ? {n, p} : a [n % 3]); return a}, 
        [{n: 0}, {n: 0}, {n: 0}]
      )
    ), 
    grid [0] .map ((c) => [{n: 0, p: ''}, {n: 0, p: ''}, {n: 0, p: ''}])
  ) 
  .map (([{n, p}], startIndex) => ({total: n, path: p, startIndex}))
  .reduce ((a, x) => x.total > a.total ? x : a, {total: 0})

const grid = [
  [ 7,  6,  5,  4,  3,  2,  1 ],
  [ 2,  4,  6,  8, 10, 12, 14 ],
  [ 2,  7,  1,  8,  2,  8,  1 ],
  [ 3,  1,  4,  1,  5,  9,  2 ],
  [ 2,  3,  5,  7, 11, 13, 17 ],
  [ 8,  6,  7,  5,  3,  0,  9 ],
]

console .log (maxMod3Path (grid))