### re: Daily Challenge #105 - High-Sum Matrix Drop VIEW POST

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
``````
code of conduct - report abuse