Snake and Ladders Problem

The problem, simply

A snakes and ladders board has N squares, numbered 0 to N - 1. You start on square 0 and want to reach square N - 1. Each throw of the die moves you 1 to 6 squares forward. If you land at the bottom of a ladder you climb to its top. If you land on a snake's head you slide down to its tail.

You get to pick every roll. Give back the smallest number of throws to reach the last square, or -1 if you never can. You may not move past the last square.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every sequence of rolls, like playing every possible game at once.

1. From the current square, try each roll from 1 to 6. Follow any ladder or snake.
2. Do not revisit a square already on this game's path, or a snake could loop forever.
3. When you reach the last square, keep the smallest number of throws.
4. Stop a game early when it has already used as many throws as the best so far.

class SnakesBrute {
    static int best;

    public static int minThrows(int n, int[] jump) {   // jump[i] = where square i sends you, or -1
        best = Integer.MAX_VALUE;
        play(0, n, jump, 0, new boolean[n]);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    static void play(int at, int n, int[] jump, int rolls, boolean[] onPath) {
        if (at == n - 1) { best = Math.min(best, rolls); return; }
        if (rolls + 1 >= best) return;                 // cannot beat the best game any more
        onPath[at] = true;
        for (int die = 1; die <= 6 && at + die < n; die++) {
            int next = at + die;
            int dest = jump[next] != -1 ? jump[next] : next;   // climb or slide
            if (!onPath[dest]) play(dest, n, jump, rolls + 1, onPath);
        }
        onPath[at] = false;
    }
}

How long it takes: up to 6 choices at every throw, and a game can wander over many squares, so it can take about O(6^N). Extra room: the path marks and the recursion, O(N).

Way 2: the clever way

Paint the board round by round. Every throw costs the same, so this is breadth first search: the first time a square is painted, it was reached with the fewest throws.

1. Put square 0 in a waiting line (a queue) with 0 throws, and mark it seen.
2. Take a square from the front. Try rolls 1 to 6. Follow any ladder or snake to find where you really end up.
3. If that is the last square, the answer is this square's throws plus 1.
4. Otherwise, if it is not seen yet, mark it and put it at the back of the line with one more throw.
5. If the line runs empty, the last square cannot be reached.

class SnakesBFS {
    public static int minThrows(int n, int[] jump) {  // jump[i] = where square i sends you, or -1
        if (n == 1) return 0;
        boolean[] seen = new boolean[n];
        int[] throwsTo = new int[n];
        Queue<Integer> line = new ArrayDeque<>();
        line.add(0);
        seen[0] = true;
        while (!line.isEmpty()) {
            int at = line.poll();
            for (int die = 1; die <= 6 && at + die < n; die++) {
                int next = at + die;
                int dest = jump[next] != -1 ? jump[next] : next;   // climb or slide
                if (dest == n - 1) return throwsTo[at] + 1;
                if (!seen[dest]) {
                    seen[dest] = true;                 // painted once, with the fewest throws
                    throwsTo[dest] = throwsTo[at] + 1;
                    line.add(dest);
                }
            }
        }
        return -1;                                     // the last square is never painted
    }
}

How long it takes: each square joins the line at most once and tries 6 rolls, O(6N), which is O(N). Extra room: the seen marks, the throw counts and the line, O(N).

Watch out for

• Snakes make loops. Without a seen mark, the search can go round and round forever.
• Rolls past the last square are not allowed. Stop the dice loop at n - 1.
• A ladder or snake that ends exactly on the last square still counts as reaching it. Check dest, not next.
• If the start square has a ladder on it, the usual rule is that you do not climb it before your first roll.

What interviewers ask next

• LeetCode 909 gives the board as an n by n grid numbered in the winding order, with -1 for plain squares. Turn a square number into a row and column first: the row from the bottom is (s - 1) / n, and every other row runs right to left.
• Print the actual rolls. Store the square you came from for every painted square, then walk back from the end.
• What is the expected number of throws with a real random die? Then it is a Markov chain. Solve a system of equations, or do value iteration, instead of BFS.
• Two players take turns. Who wins with perfect play? That becomes a game search with memo over both positions.

Remember this

Grown-up words: squares are nodes, a roll is an edge, the rounds of painting are BFS levels, the waiting line is a queue, and the number painted on the last square is the shortest path length.