Snakes and Ladders: The Quickest Way Up

Sort by

recency

|

257 Discussions

|

  • + 0 comments
    def quickestWayUp(ladders, snakes):
        # Write your code here
        temp = {}
        for a, b in ladders + snakes:
            temp[a] = b
        
        queue = deque()
        queue.append((1, 0))
        visited = set()
        visited.add(1)
        
        while len(queue) > 0:
            current, roll_count = queue.popleft()
            if current == 100:
                return roll_count
                
            for i in range(1, 7):
                next_pos = current + i
                next_pos = temp.get(next_pos, next_pos)
                if next_pos not in visited:
                    queue.append((next_pos, roll_count+1))
                    visited.add(next_pos)
        return -1
    
  • + 0 comments
    def quickestWayUp(ladders, snakes):
        # Write your code here
        temp = {}
        for a, b in ladders + snakes:
            temp[a] = b
            
        graph = {}
        for i in range(1, 100):
            if i not in temp :
                graph[i] = []
                for roll in range(1, 7):
                    pos = i+roll
                    if pos <= 100:
                        pos = temp.get(pos, pos)
                        graph[i].append(pos)
        visited = set()          
        queue = deque()
        queue.append((1, 0))
        visited.add(1)
        while len(queue) > 0:
            current, roll_count = queue.popleft()
            if current == 100:
                return roll_count
            
            for n in graph[current]:
                if n not in visited:
                    queue.append((n, roll_count+1))
                    visited.add(n)
                    
        return -1
    
  • + 0 comments

    Java solution:

    public static int quickestWayUp(
        List<List<Integer>> ladders, List<List<Integer>> snakes) {
      int[] board = new int[101];
    
      for (int i = 0; i < 101; i++) {
        board[i] = i;
      }
    
      for (List<Integer> ladder : ladders) {
        board[ladder.get(0)] = ladder.get(1);
      }
    
      for (List<Integer> snake : snakes) {
        board[snake.get(0)] = snake.get(1);
      }
    
      Queue<int[]> queue = new LinkedList<>();
      boolean[] visited = new boolean[101];
      queue.offer(new int[] {1, 0});
    
      while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int currentSquare = current[0];
        int currentMove = current[1];
        
        if (currentSquare == 100) {
          return currentMove;
        }
    
        for (int i = currentSquare + 1; i <= currentSquare + 6; i++) {
          if (i <= 100 && !visited[board[i]]) {
            visited[i] = true;
            visited[board[i]] = true;
            queue.offer(new int[] {board[i], currentMove + 1});
            
          }
        }
      }
      return -1;
    }
    
  • + 0 comments

    Python Solution

    def quickestWayUp(ladders, snakes):
        n_moves = [-1]*101
        n_moves[1] = 0
        todo = [1]
        ladders_dict = {min(i,j): max(i,j) for i, j in ladders}
        snakes_dict = {max(i,j): min(i,j) for i, j in snakes}
        while todo:
            start = todo.pop()
            for x in range(start + 1, start + 7):
                x = ladders_dict.get(x, snakes_dict.get(x, x))
                if x > 100:
                    break
                if (n_moves[x] == -1) or (n_moves[x] > n_moves[start] + 1):
                    n_moves[x] = n_moves[start] + 1
                    todo.append(x)
        return n_moves[100]
    
  • + 0 comments

    Sheffield locksmith training equips you with essential skills, while Snakes and Ladders is a classic game that symbolizes life's ups and downs. In the game, players ascend ladders to progress quickly, but snakes can cause setbacks. Just like in life, success often requires patience and resilience. The key to winning, both in the game and in real life, is navigating challenges with determination and learning from each step along the way.