DEV Community is a community of 867,901 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

dev.to staff

Posted on

Daily Challenge #105 - High-Sum Matrix Drop

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!

Discussion (6)

Craig McIlwrath

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

``````data Move = D | DL | DR deriving (Show)

type Size = Int
type Row = Int
type Col = Int
type Pos = (Row, Col)

isInSquare :: Size -> Pos -> Bool
isInSquare n (r, c) = all id
[ r >= 0
, r < n
, c >= 0
, c < n
]

executeMove :: Move -> Pos -> Pos
executeMove D  (r, c) = (r + 1, c)
executeMove DL (r, c) = (r + 1, c - 1)
executeMove DR (r, c) = (r + 1, c + 1)

validMove :: Size -> Pos -> Move -> Bool
validMove n p m = isInSquare n \$ executeMove m p

possibleMoves :: Size -> Pos -> [Move]
possibleMoves n p = filter (validMove n p) [D, DL, DR]

generatePaths :: Size -> Pos -> [[Move]]
generatePaths n p
| fst p == n - 1 = [[]]
| otherwise      = possibleMoves n p >>= nextMoves
where nextMoves :: Move -> [[Move]]
nextMoves m = generatePaths n (executeMove m p) >>= \ms -> [m : ms]

-- Middle spot of an even array is defined as the right middle for simplicity.
middle n
| odd n     = n `div` 2
| otherwise = n `div` 2

access :: [[a]] -> Pos -> a
access xss (r, c) = xss !! r !! c

sumIn :: (Num a) => [[a]] -> Pos -> [Move] -> a
sumIn xss start path = let ps = scanl (flip executeMove) start path
in  sum \$ map (access xss) ps

maxBy :: (Ord b) => (a -> b) -> [a] -> a
maxBy f = foldl1 maxOf
where maxOf m x = if (f x > f m) then x else m

bestPath :: (Ord a, Num a) => Size -> [[a]] -> ([Move], a)
bestPath n xss = let start = (0, middle n)
paths = generatePaths n start
in  maxBy snd \$ zip paths \$ map (sumIn xss start) paths
``````
sinx

My solution using queue. Should be o(n).

``````
import string

def get_steps(i, j, row, col):
left = j - 1
right = j + 1
down = i + 1

if down >= row:
return []

steps = []
if left >= 0:
steps.append((down, left))

steps.append((down, j))

if right < col:
steps.append((down, right))

return steps

def make_and_fill(row, col, fill):
ret = []
for _ in range(row):
row_ = [fill] * col
ret.append(row_)

return ret

def find_max_index(xs):
max_ = max(xs)
return xs.index(max_)

def get_path(i, j, backtraces):
ret = []
queue = [(i, j)]

while queue:
pos = queue.pop(0)
if pos:
ret.append(pos)
i, j = pos
backtrace = backtraces[i][j]
queue.append(backtrace)

ret.reverse()
ret = [f'{string.ascii_letters[j]}/{i}' for (i, j) in ret]
return ', '.join(ret)

def solve(xs):
row, col = len(xs), len(xs[0])
sums = make_and_fill(row, col, 0)
sums[0][:] = xs[0]
backtraces = make_and_fill(row, col, 0)
queue = [(0, col//2)]

while queue:
pos = queue.pop(0)
i, j = pos
for step in get_steps(i, j, row, col):
step_i, step_j = step
acc = sums[i][j] + xs[step_i][step_j]
if sums[step_i][step_j] < acc:
queue.append((step_i, step_j))
sums[step_i][step_j] = acc
backtraces[step_i][step_j] = pos

max_index = find_max_index(sums[-1])
print(sums[-1][max_index])

path = get_path(row-1, max_index, backtraces)
print(path)

if __name__ == '__main__':
matrix = [
[2, 1, 4, 5, 3],
[5, 2, 1, 4, 3],
[1, 3, 2, 5, 4],
[1, 5, 2, 3, 4],
[3, 2, 1, 5, 4],
]
solve(matrix)
``````
Zohar Peled

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

Michael Tharrington

Ah jeez... my bad here. 🤦‍♂️

You are absolutely right, Zohar!

Michael Tharrington

Thanks for pointing this out, David! This was a mistake.