marbles.clj

(def max-marbles (memoize (fn [board x y i j]
  (let [tile-marbles (nth (nth board x) y)]
    (cond
      (and (= x i) (= y j)) tile-marbles
      (= x i) (+ tile-marbles (max-marbles board x (inc y) i j))
      (= y j) (+ tile-marbles (max-marbles board (inc x) y i j))
      :else (+ tile-marbles (max
        (max-marbles board x (inc y) i j)
        (max-marbles board (inc x) y i j))))))))

(def max-marbles-route (memoize (fn [board x y i j]
  (let [tile-marbles (nth (nth board x) y)]
    (cond
      (and (= x i) (= y j)) [tile-marbles (list [x y])]
      (= x i)
        (let [[max-marbles route] (max-marbles-route board x (inc y) i j)]
          [(+ tile-marbles max-marbles) (cons [x y] route)])
      (= y j)
        (let [[max-marbles route] (max-marbles-route board (inc x) y i j)]
          [(+ tile-marbles max-marbles) (cons [x y] route)])
      :else
        (let [[max-marbles-down route-down] (max-marbles-route board x (inc y) i j)
              [max-marbles-left route-left] (max-marbles-route board (inc x) y i j)]
          (if (> max-marbles-left max-marbles-down)
            [(+ tile-marbles max-marbles-left) (cons [x y] route-left)]
            [(+ tile-marbles max-marbles-down) (cons [x y] route-down)])))))))

(let [example-board [[0 0 12] [1 4 0] [9 0 1]]]
  (println (max-marbles example-board 0 0 2 2))
  (println (max-marbles-route example-board 0 0 2 2)))

marbles.hs

maxMarblesPath :: [[Int]] -> Int -> Int -> Int -> Int -> (Int, [(Int, Int)])
maxMarblesPath board x y i j
  -- Last step reached
  | x == i && y == j
  = (currentMarbleCount, [(x, y)])
  --- Horizontal edge reached, go upwards
  | x == i
  = let (maxMarbles, path) = maxMarblesPath board x (y + 1) i j
    in (currentMarbleCount + maxMarbles, (x, y) : path)
  -- Vertical edge reached, go left
  | y == j
  = let (maxMarbles, path) = maxMarblesPath board (x + 1) y i j
    in (currentMarbleCount + maxMarbles, (x, y) : path)
  -- Go both left and upwards and choose the best path
  | otherwise
  = let (maxMarbles1, path1) = maxMarblesPath board (x + 1) y i j
        (maxMarbles2, path2) = maxMarblesPath board x (y + 1) i j
    in (if maxMarbles1 > maxMarbles2
          then (currentMarbleCount + maxMarbles1, (x, y) : path1)
          else (currentMarbleCount + maxMarbles2, (x, y) : path2))

  where currentMarbleCount = board !! x !! y

exampleBoard :: [[Int]]
exampleBoard = [[0, 0, 12], [1, 4, 0], [9, 0, 1]]

main :: IO()
main = putStrLn $ show $ maxMarblesPath exampleBoard 0 0 2 2