Find the minimum number of die rolls necessary to reach the final cell of the given Snakes and Ladders board game.

Rules are as usual. Player starts from cell one, rolls a die and advances 1-6 (a random number of) steps at a time. Should they land on a cell where a ladder starts, the player immediately climbs up that ladder. Similarly, having landed on a cell with a snake’s mouth, the player goes down to the tail of that snake before they roll the die again. Game ends when the player arrives at the last cell.

Example One

Input: A board with 20 cells, two ladders 2->19 and 12->15 and a snake 9->2.

The two-dimensional view is for our visual convenience only: there are really just 20 cells, one after another, linearly. See below in the Notes how such a board is represented in the Input Parameters.

Output: 2

Having started from cell 1, player rolls 1 and moves to cell 2. The stair takes them from cell 2 to cell 19. They then roll 1 to arrive at the last, 20th cell. The player reached the end of the board in two rolls; that’s the fewest rolls possible.

Example Two:

Input: A board with eight cells, no snakes and no ladders:

Output: 2

There are several ways to reach the last cell from the first cell in two rolls: 6+1, 5+2, 4+3, 3+4, 2+5, 1+6. No way to reach it with any fewer rolls though.

Notes

Input Parameters: Function has two arguments:

1. n, size of the board, and

2. moves, array of integers defining the snakes and ladders:

● moves[i] = -1: no ladder or snake starts at i-th cell

● moves[i]  <  i: snake from i down to moves[i]

● moves[i]  >  i: ladder from i up to moves[i]

The indices and values in moves array are zero-based, for example moves[1]=18 means there is a ladder from cell 2 up to cell 19. moves for “Example One” above looks like this:

[-1, 18, -1, -1, -1, -1, -1, -1, 2, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1]

Output: Function must return an integer, the minimum number of dice rolls required to reach the last cell from the first. Return -1 if the last cell cannot be reached.

Constraints:

● 1

● 0

● No snake starts from the last cell and no ladder starts from the first cell.

No snake or ladder starts from a cell where another snake or ladder arrives.

‍

Solution

Optimal solution using BFS

Consider the entire board as a graph. All cells are nodes and there is an edge from every cell to the next 6 cells on the board, as there are 6 numbers on a dice. Whenever there is a snake or a ladder, we go to its respective ends with no cost instead of staying at its beginning. For instance, when we are at cell 24 and we roll 3 to reach cell 27, we would check if a snake or a ladder starts from cell 27: if there is, our graph would not have an edge from cell 24 to 27, but instead from 24 to the end of that snake or ladder.

We need to find the minimum distance (as measured by the number of edges) to the end cell from the start cell in the graph built like so. We can run a simple breadth first search (BFS) since we just need to count edges and don’t need to account for their length or weight. Note that we don't need to build entire graph upfront: to be more efficient the provided solution creates Node objects only as it visits cells. Once it reaches the last cell, the algorithm returns without necessarily building the entire graph of possible paths. Note that the algorithm ignores any paths to a particular node except the one that was found first. That’s because the first arrival to a node using BFS is guaranteed to use the fewest possible number of edges.

Auxiliary Space Used:

Auxiliary space is taken by array visited and linked list queue.

The visited array has n elements so it takes O(n) space.

Let’s see why the queue cannot ever have more than 6*n nodes (and therefore takes O(n) space too). Processing each node adds at most 6 new nodes to the queue, and no one node is processed more than once. Even if somehow all n nodes get processed before any nodes removed from the queue (not quite possible in practice as nodes get removed from the queue as algorithm processes them), we would have the queue with 6*n nodes and no more nodes could possibly be added to it (because visited[i] is true for all indices by then).

Total Auxiliary Space Used is O(n) + O(n) = O(n)

Space Complexity:

Auxiliary Space Used of O(n) plus input size of O(n) give us a total of O(n).

Time Complexity:

Using the same logic we used when calculating the Auxiliary Space Used we can conclude the Time Complexity of O(n).

// -------- START --------

    // An entry in queue used in BFS
    static class Node {
        int index; // Zero-based index of the cell.
        int dist; // Distance, measured in dice rolls, from the 0th cell.
    }

    static int minNumberOfRolls(int n, List moves) {
        boolean[] visited = new boolean[n]; // Java guarantees to initialize all with False.

        // Add the 0th cell to the queue as we start from there
        Queue queue = new LinkedList<>();
        Node node = new Node();
        node.index = 0;
        node.dist = 0;
        queue.add(node);
        
        // Run BFS from Node 0
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (visited[node.index]) {
                // If we visited this node before we must have reached it with
                // fewer dice rolls than we have done now. No need to consider it again.
                continue;
            }

            visited[node.index] = true;

            if (node.index == n-1) {
                // We arrived at the last cell. Since we advanced one dice roll at a time,
                // current distance (number of dice rolls) from the 0th is the smallest possible.
                return node.dist;
            }
            // Add all the neighbors to the queue.
            for (int dice = 1; dice <= 6; dice++) {
                int goingTo = node.index + dice;
                if (goingTo >= n) {
                    break; // No stepping beyond the board.
                }

                // Accounting for a snake or ladder if any:
                int snakeOrLadder = moves.get(goingTo);
                if (snakeOrLadder != -1) {
                    goingTo = snakeOrLadder;
                }

                Node newNode = new Node();
                newNode.index = goingTo;
                newNode.dist = node.dist + 1; // We used one dice roll to jump from node to newNode.
                queue.add(newNode);
            }
        }

        // No way to reach
        return -1;
    }

    // -------- END --------