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 232 Discussions, By:

recency

Please Login in order to post a comment

  • cweitay93
    1 week ago+ 0 comments
    def quickestWayUp(ladders, snakes):
        # Store snakes and ladders for lookup
        graph = {s[0]: s[1] for s in snakes}
        graph.update({l[0]: l[1] for l in ladders})
        
        visited = set([1])
        queue = [1]
        rolls = {}
        
        while queue:
            idx = queue.pop(0)
            for i in range(1, 7):
                # If neighbour is a snake/ladder, jump to its end point
                # else, increment as is
                neighbour = graph.get(idx + i, idx + i)
                if neighbour not in visited:
                    rolls[neighbour] = rolls.get(idx, 0) + 1
                    visited.add(neighbour)
                    queue.append(neighbour)
                if neighbour == 100:
                    return rolls[neighbour]
        return -1
    
    0|
    Permalink
  • karplucas
    2 months ago+ 0 comments

    C++ BFS Simple

    typedef unordered_map<int,int> graph;
     
    graph buildGraph(vector<vector<int>> &input){
        graph temp;
        for(const auto &x : input)
            temp[x[0]] = x[1];
        return temp;
    }
    
    
    int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) {
        graph ladders_graph = buildGraph(ladders);
        graph snakes_graph = buildGraph(snakes);
        vector<int> visited(101, INT_MAX/2);
        visited[1] = 0;
        queue<int> que;
        que.push(1);
        
        while(!que.empty()){
            auto idx = que.front();
            que.pop();
            for(int i = 1; i <= 6 && idx + i <= 100; i++){
                auto j = idx + i;
                if(snakes_graph.count(j))
                    j = snakes_graph[j];
                else if(ladders_graph.count(j))
                    j = ladders_graph[j];
                if(visited[idx] + 1 < visited[j]){
                    visited[j] = visited[idx] + 1; 
                    que.push(j);
                }
            }
        }
        return visited[100] == INT_MAX/2 ? -1 : visited[100];
    }
    
    0|
    Permalink
  • simone_riedi27
    6 months ago+ 0 comments

    Python 3:

    class Graph:
        def __init__(self, ladders, snakes):
            self.adj_list = {i:set() for i in range(100)}
            special = {v-1:w-1 for v, w in ladders}
            special.update({v-1:w-1 for v, w in snakes})
            for i in range(99):
                for j in range(i+1, min(100, i+7)):
                    if i in special:
                        continue
                    self.adj_list[i].add(special.get(j, j))
    
                
        def bfs(self):
            q = deque([(0, 0)])
            vis = set([0])
            while q:
                dist, v = q.popleft()
                if v == 99:
                    return dist
                for u in self.adj_list[v]:
                    if not u in vis:
                        vis.add(u)
                        q.append((dist+1, u))
            return -1
                        
                 
    def quickestWayUp(ladders, snakes):
        g = Graph(ladders, snakes)
        return g.bfs()
    
    0|
    Permalink
  • vgiargia
    6 months ago+ 0 comments

    it looks like a classical https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

    but on a second thought it is easier to do a https://en.wikipedia.org/wiki/Breadth-first_search

    and of course you don't need to construct the full graph, you can navigate it on the fly

    0|
    Permalink
  • vgiargia
    6 months ago+ 0 comments

    it looks like a classical https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

    but on a second thought it is easier to do a https://en.wikipedia.org/wiki/Breadth-first_search

    -1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy