You have a square matrix of unsigned integer values. Say, 5 + 5.
Each row of that matrix contains numbers from 1 to 5 (or to whatever length of the matrix), randomly sorted.
You can move through the matrix only one step at the time - either straight down, left-down or right-down.
Your challenge is to write a code that will start at the middle of the top row, and find the path down with the highest sum.
Example:
For the following matrix, you start in c/0. For this matrix the best path would be: c/0, d/1, d/2, e/3, d/5 which scores 4+4+5+4+5 = 22.
+---+---+---+---+---+---+ | | a | b | c | d | e | +---+---+---+---+---+---+ | 0 | 2 | 1 | 4 | 5 | 3 | +---+---+---+---+---+---+ | 1 | 5 | 2 | 1 | 4 | 3 | +---+---+---+---+---+---+ | 2 | 1 | 3 | 2 | 5 | 4 | +---+---+---+---+---+---+ | 3 | 1 | 5 | 2 | 3 | 4 | +---+---+---+---+---+---+ | 4 | 3 | 2 | 1 | 5 | 4 | +---+---+---+---+---+---+
Good luck!
This challenge comes from peledzohar here on DEV. Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (5)
I didn't do #90, so I'll put my answer here. This is a really stupid, slow, "just works" algorithm. It checks every single possible path. I guess it's around O(n3)?
(Language is Haskell).
My solution using queue. Should be o(n).
Thanks for pointing this out, David! This was a mistake.
Hey guys, Someone got mixed up a bit here. That was the 90# challenge, this one was suppose to be the one I've sent you later, with the bottles... :-)
Ah jeez... my bad here. 🤦♂️
You are absolutely right, Zohar!