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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Snakes and Ladders: The Quickest Way Up
  5. Discussions

Snakes and Ladders: The Quickest Way Up

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 226 Discussions, By:

votes

Please Login in order to post a comment

  • m_a_r_c_e_li_n_o
    6 years ago+ 16 comments

    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/

    164|
    Permalink
    View more Comments..
  • sidprasad
    7 years ago+ 0 comments

    It's a bigger challenge getting the input right, than solving the problem :P

    40|
    Permalink
  • AKSaigyouji
    5 years ago+ 6 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.

    26|
    Permalink
    View more Comments..
  • mtanida
    6 years ago+ 1 comment

    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.

    17|
    Permalink
  • ziggystar
    8 years ago+ 1 comment

    Why can't this problem use the usual space and newline separated format?

    13|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature