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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Snakes and Ladders: The Quickest Way Up
  5. Discussions

Snakes and Ladders: The Quickest Way Up

  • marcos_matcomp
     + 0 comments

    I noticed HackerRank is passing on all cases for a code that is incorrect.

    To solve this problem, I implemented the following code:

    class SnakesAndLadders:

    def __init__(self, ladders, snakes):

        self.ladders = {a: b for a, b in ladders}
        self.snakes = {a: b for a, b in snakes}
        self.adj = self._construct_graph()

    def _construct_graph(self):

        adj = {x: [] for x in range(101)}
        for node in range(1,101):
            if node in self.ladders:
                adj[node].append((0, self.ladders[node]))
            elif node in self.snakes:
                adj[node].append((0, self.snakes[node]))
            else:
                for dice in range(1,7):
                    if node+dice <= 100:
                        adj[node].append((1, node+dice))
        return adj

    def quickest_way(self):

        visited = set()
        queue = [(0, 1)]
        while len(queue) > 0:
            rolls, node = queue.pop(0)
            if node == 100:
                return rolls
            if node in visited:
                continue
            for w, adj in self.adj[node]:
                if adj not in visited:
                    queue.append((rolls+w, adj))
            visited.add(node)
        return -1

    But it resulted in a wrong answer for the following input:

    1
5
7 12
24 29
41 46
58 63
75 80
0

    You can notice I have a set of visited nodes, and that I will process each node of the graph only once. Also, I'm processing the nodes in the order they are being added to the queue.

    When processing node 1, I will add to the queue nodes from 2 to 7 with one roll. When processing node 6, I will add node 12 in the queue with two rolls. But I can arrive in node 12 with only one roll, by falling on node 7 after the first roll and use the ladder. Since node 12 was first added to the queue with 2 rolls, I will process it using two rolls, and will not process it again with 1 roll (I have a continue on the code).

    For the input I provided, it will result in an answer of 18. And HackerRank is accepting the solution.

    But I can arrive on node 100 with only 13 rolls. The following method is correct and generates the answer of 13.

    def quickest_way(self):

        shortest_dist = {}
        queue = [(0, 1)]
        shortest_dist[1] = 0
        while len(queue) > 0:
            rolls, node = queue.pop(0)
            for w, adj in self.adj[node]:
                if rolls+w < shortest_dist.get(adj, 1e12):
                    queue.append((rolls+w, adj))
                    shortest_dist[adj] = rolls+w
										
        return shortest_dist.get(100, -1)