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