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

Sort by

recency

|

251 Discussions

|

  • zoyashah41306
     + 0 comments

    Branded merchandise can make your Snakes and Ladders game even more exciting! Just like the game, where players take the quickest route up the ladder or face setbacks with snakes, these items add a fun twist to your promotional strategy. Whether it's a custom board or unique game pieces, incorporating your brand ensures that every move is remembered and creates lasting impressions. Elevate your branding with a playful, engaging touch!

  • mah_shamim
     + 0 comments

    "Snakes and Ladders: The Quickest Way Up" problem, we can use the Breadth-First Search (BFS) algorithm. Below is the PHP solution for this problem:

    <?php

function quickestWayUp($ladders, $snakes) {
    $board = array_fill(1, 100, 0);

    // Set up ladders
    foreach ($ladders as $ladder) {
        $board[$ladder[0]] = $ladder[1] - $ladder[0];
    }

    // Set up snakes
    foreach ($snakes as $snake) {
        $board[$snake[0]] = $snake[1] - $snake[0];
    }

    // BFS to find the shortest path
    $queue = [[1, 0]];
    $visited = array_fill(1, 100, false);
    $visited[1] = true;

    while (!empty($queue)) {
        list($current, $moves) = array_shift($queue);

        for ($dice = 1; $dice <= 6; $dice++) {
            $next = $current + $dice;
            if ($next <= 100) {
                $next += $board[$next];

                if ($next == 100) {
                    return $moves + 1;
                }

                if (!$visited[$next]) {
                    $visited[$next] = true;
                    array_push($queue, [$next, $moves + 1]);
                }
            }
        }
    }

    return -1;
}

?>

    Explanation:

    1. Initialization:

      • The board array stores the effect of ladders and snakes on each cell.
      • queue is used for BFS, initialized with the starting position (1, 0) representing the start of the board and 0 moves.
      • visited array keeps track of visited cells to avoid revisiting them.

    2. Setup Ladders and Snakes:

      • For ladders, the board at the start cell of the ladder has the value of the end cell minus the start cell.
      • Similarly, for snakes, the board at the start cell of the snake has the value of the end cell minus the start cell.

    3. BFS to Find Shortest Path:

      • Dequeue the current position and number of moves.
      • For each dice roll (1 to 6), calculate the next position.
      • Apply any ladder or snake effect.
      • Check if the next position is 100 (end of the board).
      • If not visited, mark it as visited and enqueue it with incremented move count.

    4. Handling Input:

      • The readInput function reads the input from standard input and processes it.
      • For each test case, read the number of ladders and snakes, and their respective positions.
      • Call the quickestWayUp function for each test case and print the result.

  • wgcv92
     + 0 comments

    Pthon

    BFS

    def bfs(node, squares):
    visited = set()
    q = []
    q.append(node)
    sentinel = None
    q.append(sentinel)
    movement = 0
    while(len(q)>0):
        n = q.pop(0)
       
        if(n is sentinel):
            if(q):
                movement += 1
                q.append(sentinel)
                continue
            else:
                return -1
        if (n.finish):
            return movement
        if(n in visited):
            continue
        visited.add(n)
        for i in n.edges:
            q.append(squares[i])
            
def quickestWayUp(ladders, snakes):
    squares = {}
    dladders = {}
    dsnakes = {}
    for i in ladders:
        s1 = i[0]
        s2 = i[1]
        dladders[s1] = s2
    for i in snakes:
        s1 = i[0]
        s2 = i[1]
        dsnakes[s1] = s2
    for i in range(100, 0, -1):
        n = Node(i)
        squares[i] = n
        for j in range(i+1, i+7):
            if (j<=100):
                if(j in dladders):
                    n.edges.append(dladders[j])
                elif (j in dsnakes):
                    n.edges.append(dsnakes[j])
                else:
                    n.edges.append(j)  
    # for i in range(1,101):
    #     print("n", squares[i].val)
    #     print(squares[i].edges)
    squares[100].finish=True
    return bfs(squares[1], squares)

  • marcioreisjr
     + 0 comments

    Rust is generally a bit verbose. The execution time is nice, though. time ./target/release/rust < input_1.txt (test case #1) real 0m0.016s user 0m0.006s sys 0m0.008s

    use std::collections::HashMap;
const BOARD_LEN: usize = 100;

fn quickest_way_up_dp(ii: usize, memo: &mut HashMap<usize, i32>, st: &Vec<i32>) -> Option<i32> {
    if memo.contains_key(&ii) {
        return Some(*memo.get(&ii).unwrap());
    }
    if ii == BOARD_LEN {
        return Some(0);
    }
    if ii > BOARD_LEN || st[ii] > (BOARD_LEN as i32) || st[ii] < 0 || st[ii] == ii as i32 {
        return None;
    }
    if st[ii] != 0 {
        return quickest_way_up_dp(st[ii] as usize, memo, st);
    }
    memo.insert(ii, i32::MAX);
    let mut min = i32::MAX;
    for dice in 1..=6 {
        let next = ii + dice;
        if let Some(res) = quickest_way_up_dp(next, memo, st) {
            min = min.min(res);
        }
    }
    if min != i32::MAX {
        memo.insert(ii, 1 + min);
        return Some(*memo.get(&ii).unwrap());
    }
    None
}

fn quickestWayUp(ladders: &[Vec<i32>], snakes: &[Vec<i32>]) -> i32 {
    let mut steps: Vec<i32> = vec![0; 101];
    for v in ladders {
        steps[v[0] as usize] = v[1];
    }
    for v in snakes {
        steps[v[0] as usize] = v[1];
    }
    quickest_way_up_dp(1, &mut HashMap::new(), &steps).unwrap_or(-1)
}

  • 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)