stevensonmt

stevensonmt

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).
https://leetcode.com/problems/snakes-and-ladders/description/

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.

Showing Posts 1 to 2

sbuttgereit

sbuttgereit

A complete non-sequitur…

“Chutes and Ladders” is how the game is known in the U.S., but elsewhere (OK, the UK at least) it’s known as “Snakes and Ladders”. I guess snakes are just too scary for we Americans. :slight_smile:

stevensonmt

stevensonmt OP

Ah. I figured it was something like that, but conceptually chutes makes a lot more sense than snakes as a contrast to ladders.

— All posts loaded —

Where Next? Top

Trending in Challenges Top

Other Trending Topics Top

dominicletz
Hey there, I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first. ...
New
mudasobwa
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
New
KristerV
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
webofbits
With AI doing more of the implementation work, I’ve been wondering how much coding I should deliberately keep doing myself. My main conc...
#ai
New
OndrejValenta
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly) AI dream has many faces, but general...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews