Sort 211 Discussions, By:
Please Login in order to post a comment
For those that are new to Graph Theory (i.e. myself), take a bit of time to firmly understand the construction of a Graph using an adjacency list, and how to explore the adjacency list using a "Breadth First Search" algorithm. Only then you'll be able to comprehend why this problem was categorized as "easy". I know there are people here succesfully solving it through "Dynamic Programming", and it's a valid method, but if you take that route, you'll miss out on an elegant and simple "Graph Theory" solution that I would argue is the purpose of this challenge. Admins, perhaps it might not be the worse idea to include "Adjacency List" and "Breadth First Search" as topics for this problem.
At any rate, if you are struggling as much as I was, take a look at this: http://theoryofprogramming.com/2014/12/25/snakes-and-ladders-game-code/
It's a bigger challenge getting the input right, than solving the problem :P
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.
This problem is sort of unintuitive for people who've never heard of Snakes and Ladders. I feel like the problem description and the example problem can be improved to explain the rules of the game more clearly.
Why can't this problem use the usual space and newline separated format?