We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'm seeing some pretty crazy solutions for this problem (Dijkstra's, Bellman Ford, dynamic programming, etc.)
This is a straightforward BFS, and doesn't even require the explicit construction of a graph, just an array with 100 (or 101) slots. For each slot, place either the index of that slot (i.e. 5th spot has a 5 in it), or, if it has the head of a snake or start of a ladder, the endpoint of that snake/ladder.
The slots form an implicit graph where the connected vertices from a given slot are the 6 slots after the current one.
Running a BFS on this implicit graph will get you the solution.
The reason you don't need dijkstra's is that you're only measuring the number of die rolls: you don't care about distance travelled (edge weights). Similarly, you don't need bellman ford as that is an algorithm needed to handle negative edge weights.
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
I'm seeing some pretty crazy solutions for this problem (Dijkstra's, Bellman Ford, dynamic programming, etc.)
This is a straightforward BFS, and doesn't even require the explicit construction of a graph, just an array with 100 (or 101) slots. For each slot, place either the index of that slot (i.e. 5th spot has a 5 in it), or, if it has the head of a snake or start of a ladder, the endpoint of that snake/ladder.
The slots form an implicit graph where the connected vertices from a given slot are the 6 slots after the current one.
Running a BFS on this implicit graph will get you the solution.
The reason you don't need dijkstra's is that you're only measuring the number of die rolls: you don't care about distance travelled (edge weights). Similarly, you don't need bellman ford as that is an algorithm needed to handle negative edge weights.