Trying to get more facility with dynamic programming concepts on Leetcode and having an issue I can’t find a way around. It’s a chutes and ladders game (that they call snakes and ladders for some reason).
My intuition for this problem was to start at the end and work backwards since it’s easier to know that the last square before the end will only take one dice roll to get to the end than to know how many it would take to get to the end from the second square. So working backwards goes great except that when I encounter a snake head the value for number of rolls from the snake tail is not known yet. I addressed this by not storing integers but rather functions to get the correct integer value once the entire board has been traversed. This also works great but introduces too much complexity when trying to find the minimum value for a square that is not a ladder bottom or snake head. For those squares I have to assess the next six squares and take the smallest value plus one. I think it’s fair to assume any square that is not a ladder bottom or snake head will not beat out a maximum roll of 6 but not sure. Anyway the trouble I have with this solution below is this error:
eheap_alloc: Cannot allocate 255489152 bytes of memory (of type “heap”). Crash dump is being written to: erl_crash.dump…
EDIT: by changing some Enum calls to Stream calls the above error resolves and now it just times out b/c infinite recursion over a few values (see below).
I’m guessing that all those function calls are piling up recursively? Anyone have suggestions on how to adapt my approach?
defmodule Solution do
@spec snakes_and_ladders(board :: [[integer]]) :: integer
def snakes_and_ladders(board) do
n = length(board)
last = n * n
dp = do_dp(%{last => fn _ -> 0 end}, flat_board(board, last), last)
dp[1].(dp) |> IO.inspect()
end
@spec flat_board([[integer]], integer) :: map
defp flat_board(board, last) do
board
|> Enum.with_index()
|> Enum.map(fn {row, i} when rem(i, 2) == 0 -> row
{row, i} -> Enum.reverse(row)
end)
|> List.flatten()
|> Enum.with_index()
|> Map.new(fn {v,k} -> {last - k, v} end)
end
defp do_dp(seen, _board, last) when last <= 1, do: seen
defp do_dp(seen, board, last) do
1..6
|> Enum.map(fn i -> last - i end)
|> Enum.reduce(seen, fn i, sn ->
fun =
cond do
# not a snake head or ladder bottom, just tack on one to last
board[i] == -1 ->
fn cache ->
next =
1..6
|> Stream.filter(fn j -> Map.get(board, i + j, -1) != -1 end)
|> Stream.map(fn j -> cache[i + j].(cache) end)
|> Stream.concat([cache[last].(cache)])
Enum.min(next)
|> Kernel.+(1)
end
# bottom of ladder, add one to distance to end from top of ladder
Map.get(sn, board[i], false) -> fn cache -> cache[board[i]].(cache) end
# head of snake, add one to distance from tail of snake but this not calculated yet.
board[i] < i -> fn cache -> cache[board[i]].(cache) end
# should only be reachable when i < 1 b/c board[i] does not exist
true -> fn _ -> 0 end
end
Map.put(sn, i, fun)
end)
|> do_dp(board, last - 6)
end
end
If I inspect the case where a space is not a snake head or ladder bottom I see that it ends up looping over these conditions infinitely:
last=36
i=30
: 0
last=30
i=24
: 1
last=24
i=18
: 2
last=36
i=35
: 0
I’m an idiot. I’m decrementing over 1…6 and then incrementing each value over 1…6 in the same loop so of course it’s going to infinity.
