CODEWITHSUNDEEP
javascriptarraysalgorithmdynamic-programminggraph-algorithm
Micael Illos
Micael Illos

Reputation: 492

Find Maximum Path thats divisible by 3 in 2D array

Given a two-dimensional array of numbers.

Find the "snake path" whereas:

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

Upvotes: 0

Views: 685

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50797

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))

I don't have the time now to write up a long explanation of this code, but a brief synopsis is that this is using dynamic programming, following the algorithm described by Ehsan Gerayli. We start with an array the width of each row, each entry containing an array of three copies of {n: 0, p: ''}, one each for the 0, 1, and 2 modulus results for 3.

Starting with the bottom row, we calculate, for each cell, the results found by moving down and either left or right from the cell, storing the total and the path in the correct modulo bucket if the total is bigger than the current value for the bucket.

At the end, we have the maximum for each bucket stored. We can now remove the 1 and 2 buckets, renaming variables and including the index to start at. (.map (([{n, p}], startIndex) => ({total: n, path: p, startIndex})))

That will give us something like this:

[
  {path: "RLRRR", startIndex: 0, total: 24}, 
  {path: "RRRLL", startIndex: 1, total: 39}, 
  {path: "LRRRL", startIndex: 2, total: 27}, 
  {path: "LRRRR", startIndex: 3, total: 45}, 
  {path: "RLRLL", startIndex: 4, total: 42}, 
  {path: "RLLRR", startIndex: 5, total: 51}, 
  {path: "LRLLL", startIndex: 6, total: 39}
]

Then, the reduce call in the final line chooses the one with the largest total.

I think I have the requirements right. But if a path can also drop straight down, you could also add this in the obvious place:

      ...(prev [  i  ] || []).map(({n, p}) => ri == 0 ? {n, p} : ({n, p: 'D' + p})),

which would now yield the result

{path: "RRDRD", startIndex: 3, total: 57}

Finally, if your grid can contain negative numbers, then you should replace all the {n: 0} instances with {n: -Infinity}. (This isn't thoroughly tested, but it looks as though it will work.)

I would like to hear if this matches the requirements.

Upvotes: 1

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

First of all the statement I calculated that there are n^3 potential snake paths is wrong, there are lot lot more situations and it's actually of O(2^n)

You can use following dynamic approach which is O(n^2)

  • At the beginning just keep last row of array and in each step add rows from bottom one by one
  • In each Step suppose you keep these 3 values for each cell of Current_Array
    • Max path with SUM % 3 ==0 , Max path with SUM % 3==1 and ...==2
    • For the new added row, you can easily calculate these 3 parameters from it's bottom row as , for example for index (i,j) just check 3 parameters of (i+1,j+1) and (i+1,j-1) and according to the value of index(i,j)%3 calculate it's parameters
  • At the end find maximum value of (SUM % 3 ==0) parameter in the array with O(n^2)

Upvotes: 0

Related Questions