!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

This follows the same steps as every problem in this section. If you’ve read the tic-tac-toe walkthrough, some ideas will be familiar (a game as referee, one lock per game). This one adds three new things: validating data so impossible states can’t exist, rules as strategies when every family plays slightly differently, and what happens when you run a game millions of times on many threads.

Step 1Understand the problem

Picture the real thing first

A square board numbered 1 to 100, snaking back and forth. Everyone starts off the board. You roll a die and move that many squares. Land at the bottom of a ladder and you climb it. Land on a snake’s head and you slide down to its tail. First to reach 100 wins. And every family argues about the same two things: do you need the exact number to land on 100, and does rolling a six give you another go?

Hints in that story: board, square, roll, move, ladder, snake, climb, slide, first to 100, exact number, another go. And the argument at the end is the most useful hint of all: the rules vary.

Ask before you design

Group your questions: the board, the dice, the rules, the players, and how it’s played.

Functional requirements

1. FR1. A board has squares 1 to N (100 by default) and any number of snakes and ladders.
2. FR2. Players start off the board (square 0) and take turns rolling the dice and moving forward.
3. FR3. Landing on a ladder’s bottom moves you to its top. Landing on a snake’s head moves you to its tail.
4. FR4. The first player to reach exactly N wins.
5. FR5. What happens on overshooting N is a house rule: stay put, or bounce back.
6. FR6. Whether a six gives another roll is a house rule.
7. FR7. A board that could break the game is rejected when it’s created.

Non-functional requirements

1. NFR1: Easy to extend. New house rules, dice and boards mean new classes or new data, not edits.
2. NFR2: Correct online. A player can’t take two turns by sending two requests at once.
3. NFR3: Fast and correct under heavy simulation. Millions of games on many threads, with exact totals.
4. NFR4: Testable. A game that’s pure luck must still be testable move by move.

Assumptions we’ll write down

Step 2Break it into entities

Pull out the nouns

Board, square, snake, head, tail, ladder, bottom, top, die, dice, roll, player, counter, turn, house rule, winner, game.

Three questions that decide if a noun is a class

The trap: a class for snakes and a class for ladders

The tempting design:

class Snake { int head, tail; }
class Ladder { int bottom, top; }

class Cell {
    int number;
    Snake snake;      // maybe null
    Ladder ladder;    // maybe null
}

class Board { Cell[] cells = new Cell[101]; }

// and then, when a player lands:
if (cell.snake != null) pos = cell.snake.tail;
else if (cell.ladder != null) pos = cell.ladder.top;

Ask what a snake does differently from a ladder. Nothing. Both move a counter from one square to another. The only difference is the direction, and that’s already in the numbers: a snake goes down, a ladder goes up. Two classes means two fields on every cell, two null checks on every move, and a cell that could, by mistake, have both.

So model what they really are: a jump from one square to another.

record Jump(int from, int to) {
    boolean isLadder() { return to > from; }
}

And Cell has no data or rules of its own beyond its number. The board doesn’t need 100 objects to remember 15 jumps. It needs a map from start square to jump. Moving becomes one line: if there’s a jump where you landed, follow it.

Saying this out loud is worth a lot: ”Snakes and ladders behave identically; only the direction differs, and that’s in the data. So one class.” It’s the same lesson as one vehicle enum in the parking lot and one mark per player in tic-tac-toe.

Pull out the verbs

Roll, move, land, climb, slide, check the overshoot, pass the turn, roll again, win, validate the board.

Give each job to the class that knows the most

CRC cards

Find what will change

Note the fourth row. The layout changes all the time, but it’s data, so it doesn’t need an interface. A new board is a new list of jumps, not a new class.

Step 3Top-down or bottom-up?

Top-down: the server calls takeTurn(player). That needs dice (Dice.roll), a rule for the end (FinishRule.land), the board’s jumps (Board.resolve), and a rule for extra turns (TurnRule.rollsAgain).

Bottom-up: first a Jump that can’t jump to itself, then a Board that refuses broken layouts, then dice and rules, then the game.

Same conclusion as always: design from the outside in, code from the inside out.

Step 4Design each class

Game: the referee

Job: run one game. Whose turn it is, where everyone is, and who won.

takeTurn returns an Optional: a full record of what happened, or nothing if it wasn’t that player’s turn or the game is over. The Turn record makes the online UI easy (it animates exactly what’s in it), and makes tests easy (assert on the record).

Turn order is a queue: the player at the front plays, then goes to the back. With extra turns, they simply stay at the front.

Board: the layout, and its guard

Job: hold the jumps, answer “where does landing here send me?”, and refuse to exist if the layout is broken.

Putting validation in the constructor means a broken board can never exist. No other class has to wonder whether a board is valid. Step 8 lists exactly what “broken” means.

Jump: one snake or ladder

A record of from and to, which refuses to jump to its own square. isLadder() is there for the UI to draw it, not for the game: the game never needs to know.

Dice: where rolls come from

An interface with roll(). RandomDice rolls any number of six-sided dice from a random source passed in. ScriptedDice returns rolls from a list, for tests. The game can’t tell the difference, which is what makes a game of luck testable (NFR4).

FinishRule and TurnRule: the house rules

FinishRule.land(from, roll, last) returns where a move stops before any jump. ExactFinish stays put on an overshoot; BounceBack goes to the end and back by the extra amount.

TurnRule.rollsAgain(roll, rollsThisTurn) says whether the same player rolls again. OneRollPerTurn always says no; a six-rolls-again rule comes in step 11.

Turn and GameListener: what happened

Turn is a record: player, roll, from, the square they landed on, where they ended up, and whether they won. If landed and to differ, they hit a jump. GameListener hears every turn.

Step 5How the classes relate

That aggregation is worth a sentence in the interview. A board is immutable: once built and validated, it never changes. So a million simulated games can all share one board object, on any number of threads, with no locking at all.

Step 6The class diagram, built up

Version 1: the board

Version 2: the game and what varies

Version 3: the whole picture

ScriptedDice, BounceBack and OneRollPerTurn are left off; they sit next to their interfaces the same way.

Check it against the requirements

Step 7The patterns, and why each one is here

Why not an enum for the house rules?

You could write enum Overshoot { STAY, BOUNCE } and a switch inside Game. With two options that would work. But each new house rule would mean editing Game‘s switch, and the interviewer said boards and rules come from users. An interface lets a new rule be a new class, tested on its own. If you prefer the enum, say why: the set of rules is fixed and small. Either answer is fine with a reason.

Why not a Singleton board

“There’s one board”, until there are two. User-designed boards rule it out immediately, and simulations want many boards side by side. Pass the board in.

Patterns we deliberately didn’t use

• Factory for boards. A board is a size and a list of jumps. A static Board.classic() helper would be enough if we wanted a default.
• State for the game. It’s in progress or it has a winner; one if handles it.
• Command for turns. Turns can’t be undone here, and a Turn record already says what happened.

Step 8Walk the flows

A turn

1. Check first, roll second. A request out of turn never touches the dice, which matters for scripted dice in tests and for fairness online.
2. The finish rule decides where the move stops. Only then does the board apply a jump. Doing it in this order means a bounce back that lands on a snake’s head still slides, which is what players expect.
3. A jump is followed once. Our board doesn’t allow a jump to land on another jump, so there’s never a second one to follow.
4. The turn record keeps both the square landed on and the final square, so the UI can animate “moved to 27, then slid to 5”.

Checking a board

What could make a board break the game? Walk through every way a designer could get it wrong:

That last rule deserves a sentence. If jumps could chain, you’d need to follow them until you stop, and a loop would hang the game. You could detect loops instead, but the simple rule (no jump lands on another jump) makes loops impossible and is easy to explain to board designers. Real boards follow it anyway.

From real runs of the constructor:

100->20: off the board: Jump[from=100, to=20]
30->30: a jump must move: 30
4->25,4->10: two jumps start at 4
4->25,25->2: jump lands on a jump: Jump[from=4, to=25]
0->10: off the board: Jump[from=0, to=10]

What walking the flows taught us

When things go wrong

Step 9Write the code, bottom-up

Each class only uses those before it. This is complete Java that compiles and runs; every output on this page comes from running it.

9.1 Players and jumps

record Player(String name) { }

record Jump(int from, int to) {
    Jump {
        if (from == to) throw new IllegalArgumentException("a jump must move: " + from);
    }
    boolean isLadder() { return to > from; }
}

The block inside Jump with no brackets after the name is a compact constructor: it runs before the fields are set, so a jump to its own square can never be created.

9.2 The board

final class Board {
    private final int last;
    private final Map jumps = new HashMap<>(); 1

    Board(int last, List list) {
        if (last < 2) throw new IllegalArgumentException("board too small");
        this.last = last;
        for (Jump j : list) {
            if (j.from() < 1 || j.from() >= last || j.to() < 1 || j.to() > last)
                throw new IllegalArgumentException("off the board: " + j);   // (2)
            if (jumps.putIfAbsent(j.from(), j) != null)
                throw new IllegalArgumentException("two jumps start at " + j.from());
        }
        for (Jump j : list)
            if (jumps.containsKey(j.to()))
                throw new IllegalArgumentException("jump lands on a jump: " + j);  // (3)
    }

    int last() { return last; }
    Optional jumpAt(int square) { return Optional.ofNullable(jumps.get(square)); }
    int resolve(int square) {
        Jump j = jumps.get(square);
        return j == null ? square : j.to();
    }
    Collection jumps() {
        return Collections.unmodifiableCollection(jumps.values());
    }
}

1. The map answers “is there a jump here?” instantly, for a board of any size.
2. from >= last rejects a jump on the winning square.
3. The second loop runs after every jump is in the map, so the order of the list doesn’t matter.

Every field is final and nothing ever changes the map after the constructor, so a board is safe to share between games and threads.

9.3 Dice

interface Dice { int roll(); }

final class RandomDice implements Dice {
    private final int count;
    private final RandomGenerator random;
    RandomDice(int count, RandomGenerator random) {
        this.count = count;
        this.random = random;
    }
    public int roll() {
        int sum = 0;
        for (int i = 0; i < count; i++) sum += 1 + random.nextInt(6);
        return sum;
    }
}

final class ScriptedDice implements Dice {
    private final Deque rolls = new ArrayDeque<>();
    ScriptedDice(int... values) { for (int v : values) rolls.add(v); }
    public int roll() {
        Integer v = rolls.poll();
        if (v == null) throw new IllegalStateException("script ran out");
        return v;
    }
}

RandomGenerator is Java’s common interface for random sources. Taking it instead of Random means a caller can pass Random, SplittableRandom or ThreadLocalRandom. Step 10 shows why that choice matters a lot.

9.4 House rules

interface FinishRule {
    int land(int from, int roll, int last); 1
}

final class ExactFinish implements FinishRule {
    public int land(int from, int roll, int last) {
        int to = from + roll;
        return to > last ? from : to; 2
    }
}

final class BounceBack implements FinishRule {
    public int land(int from, int roll, int last) {
        int to = from + roll;
        return to > last ? last - (to - last) : to; 3
    }
}

interface TurnRule {
    boolean rollsAgain(int roll, int rollsThisTurn);
}

final class OneRollPerTurn implements TurnRule {
    public boolean rollsAgain(int roll, int rollsThisTurn) { return false; }
}

From real calls:

exact, 98 + 5 -> 98
bounce, 98 + 5 -> 97
bounce, 97 + 3 -> 100

9.5 Turns and listeners

record Turn(Player player, int roll, int from, int landed, int to, boolean won) {
    boolean jumped() { return landed != to; }
    @Override public String toString() {
        String s = player.name() + " rolls " + roll + ": " + from + " -> " + landed;
        if (jumped()) s += (to > landed ? " ladder to " : " snake to ") + to;
        return won ? s + ", wins" : s;
    }
}

interface GameListener {
    void turnTaken(Turn turn);
}

9.6 The game

final class Game {
    private final Board board;
    private final Dice dice;
    private final FinishRule finish;
    private final TurnRule turns;
    private final Deque order;
    private final Map position = new HashMap<>();
    private final List listeners = new CopyOnWriteArrayList<>();
    private Player winner;
    private int rollsThisTurn;

    Game(Board board, List players, Dice dice, FinishRule finish,
         TurnRule turns) {
        if (players.size() < 2) throw new IllegalArgumentException("need two players");
        if (new HashSet<>(players).size() != players.size())
            throw new IllegalArgumentException("duplicate player");
        this.board = board;
        this.dice = dice;
        this.finish = finish;
        this.turns = turns;
        this.order = new ArrayDeque<>(players);
        for (Player p : players) position.put(p, 0);                       // (1)
    }

    void subscribe(GameListener l) { listeners.add(l); }

    synchronized Optional takeTurn(Player p) {
        if (winner != null || !p.equals(order.peekFirst())) return Optional.empty();
        int roll = dice.roll();
        int from = position.get(p);
        int landed = finish.land(from, roll, board.last());
        int to = board.resolve(landed);
        position.put(p, to);
        boolean won = to == board.last();
        rollsThisTurn++;
        if (won) {
            winner = p;
        } else if (!turns.rollsAgain(roll, rollsThisTurn)) {
            order.addLast(order.pollFirst());                               // (2)
            rollsThisTurn = 0;
        }
        Turn t = new Turn(p, roll, from, landed, to, won);
        for (GameListener l : listeners) l.turnTaken(t);
        return Optional.of(t);
    }

    synchronized Player current() { return order.peekFirst(); }
    synchronized Optional winner() { return Optional.ofNullable(winner); }
    synchronized int positionOf(Player p) { return position.get(p); }
    Board board() { return board; }
}

1. Everyone starts on square 0, off the board.
2. The player at the front moves to the back. If they roll again, they stay at the front and rollsThisTurn keeps counting.

9.7 Putting it together

Two players, scripted dice, so this game is the same every time it runs:

public class Demo {
    public static void main(String[] args) {
        Board board = new Board(100, List.of(
            new Jump(4, 25), new Jump(13, 46), new Jump(33, 49), new Jump(42, 63),
            new Jump(50, 69), new Jump(62, 81), new Jump(74, 92),
            new Jump(27, 5), new Jump(40, 3), new Jump(43, 18), new Jump(54, 31),
            new Jump(66, 45), new Jump(76, 58), new Jump(89, 53), new Jump(99, 41)));
        Player meera = new Player("Meera"), kabir = new Player("Kabir");
        Game g = new Game(board, List.of(meera, kabir),
            new ScriptedDice(4, 6, 2, 5, 6, 2), new ExactFinish(), new OneRollPerTurn());
        g.subscribe(System.out::println);
        for (int i = 0; i < 6; i++) g.takeTurn(g.current());
        System.out.println("Kabir out of turn: " + g.takeTurn(kabir).isPresent());
    }
}

Meera rolls 4: 0 -> 4 ladder to 25
Kabir rolls 6: 0 -> 6
Meera rolls 2: 25 -> 27 snake to 5
Kabir rolls 5: 6 -> 11
Meera rolls 6: 5 -> 11
Kabir rolls 2: 11 -> 13 ladder to 46
Kabir out of turn: false

Meera’s ladder in the first turn, then the snake on 27 that sends her back to 5: exactly the kind of game a test should be able to replay. In a test, each line becomes an assertion on the Turn record.

Step 10Make it safe

There are two separate concurrency stories here, and it’s worth telling the interviewer you see both.

Online games: one lock per game

The online game has the same problem as tic-tac-toe: two requests from one player at the same instant could both pass the turn check and both roll. The fix is the same: takeTurn is synchronized, so the turn check, the roll, the move and passing the turn happen as one step. Each game has its own lock, so games never wait for each other. The board is immutable, so sharing it needs no lock at all.

Simulations: a million games on eight threads

The interviewer’s other use is checking new boards: run millions of games and look at how long they take. Each game is independent, so this is easy to spread across threads. Two things go wrong, and both are worth knowing.

The lost total

The first version kept one long totalRolls and every thread did totalRolls += rolls. That line looks like one step, but it’s three: read the total, add, write it back. Two threads can read the same old total, and one thread’s addition disappears.

Step through it:

We ran 2 million games on 8 threads and kept three totals side by side: the plain long, a LongAdder, and each thread’s own total added up at the end (the true answer):

run 1: true total=109893213, plain long=78024434 (lost 31868779), LongAdder=109893213
run 2: true total=109893213, plain long=79886059 (lost 30007154), LongAdder=109893213
run 3: true total=109893213, plain long=76983978 (lost 32909235), LongAdder=109893213

The plain long lost about 30% of all rolls, a different amount every run (in a later run it lost 24%), with no error and no warning. The average game length it reported would have been around 40 rolls instead of 55, and someone would have approved a board because of it.

LongAdder keeps several internal counters so threads rarely touch the same one, and adds them up when you ask. Even simpler, and what the true total above used: let each thread keep its own long, and add the eight numbers together once at the end. Nothing is shared until then.

The slow random

The second surprise: java.util.Random is thread-safe, so sharing one between threads gives correct results. But every call updates one shared value with an atomic compare-and-swap, so eight threads spend their time retrying against each other. From the same machine, same 2 million games:

one shared Random: 2M games in 16504 ms
SplittableRandom per thread: 2M games in 251 ms

Sixty-five times slower, from one shared object. Thread-safe is not the same as fast. Give each thread its own random source (SplittableRandom with its own seed, or ThreadLocalRandom.current()), and pass it to that thread’s RandomDice. Because RandomDice takes a RandomGenerator, nothing in the game changes to make this switch.

That’s the lesson to say in the interview: share only what never changes (the board), and give each thread its own copy of everything else.

Step 11Follow-ups, extended without editing

A six gives another turn

A new TurnRule. Game already counts rolls this turn and keeps the player at the front when the rule says so.

final class SixRollsAgain implements TurnRule {
    public boolean rollsAgain(int roll, int rollsThisTurn) {
        return roll == 6 && rollsThisTurn < 3; 1
    }
}

1. Without a limit, a lucky streak could go on for a long time. Many families send you back after three sixes; that would be another small rule.

Does the rule change who wins? We played 200,000 two-player games each way: the first player won 50.5% with one roll per turn and 50.7% with sixes rolling again. Going first is a tiny advantage, and the extra-turn rule barely changes it.

The fewest rolls to win

This is a famous coding question on its own. Think of each square as a point, and each roll (1 to 6) as a path from one point to another, after following any jump. The fewest rolls is the shortest path from 0 to 100, and when every step costs one roll, breadth-first search finds it: explore everything one roll away, then everything two rolls away, and so on.

Bad solutionTry every sequence of rolls

Six choices per roll, so 6²⁰ sequences of 20 rolls. Hopeless.

Good solutionBreadth-first search over squares

There are only 101 squares, and each has at most six next squares. The first time the search reaches a square, it has found the fewest rolls to get there.

Great solutionThe same search, using the game’s own rules

The search should use the same FinishRule and Board.resolve as the game, so the answer can never disagree with real play:

final class BoardAnalyzer {
    private final Board board;
    private final FinishRule finish;

    BoardAnalyzer(Board board, FinishRule finish) {
        this.board = board;
        this.finish = finish;
    }

    // Fewest rolls of one die to reach the last square, or -1 if it can't be reached.
    int fewestRolls() {
        int last = board.last();
        int[] dist = new int[last + 1];
        Arrays.fill(dist, -1);
        Deque queue = new ArrayDeque<>();
        dist[0] = 0;
        queue.add(0);
        while (!queue.isEmpty()) {
            int sq = queue.poll();
            if (sq == last) return dist[sq];
            for (int roll = 1; roll <= 6; roll++) {
                int next = board.resolve(finish.land(sq, roll, last));
                if (dist[next] == -1) { 1
                    dist[next] = dist[sq] + 1;
                    queue.add(next);
                }
            }
        }
        return -1;
    }

    // Expected rolls for one player to finish, from the start.
    double expectedRolls() {
        int last = board.last();
        double[] e = new double[last + 1]; 2
        for (int sweep = 0; sweep < 100_000; sweep++) {
            double change = 0;
            for (int sq = last - 1; sq >= 0; sq--) {
                if (sq != 0 && board.jumpAt(sq).isPresent()) continue;  // (3)
                double sum = 0;
                for (int roll = 1; roll <= 6; roll++)
                    sum += e[board.resolve(finish.land(sq, roll, last))];
                double v = 1 + sum / 6;
                change = Math.max(change, Math.abs(v - e[sq]));
                e[sq] = v;
            }
            if (change < 1e-9) break;
        }
        return e[0];
    }
}

1. Squares are visited in order of rolls needed, so the first visit is always the shortest.
2. Expected rolls, explained in the next section.
3. Nobody ever rests on a jump’s start square (they always follow it), so those squares are skipped.

On our board the fewest is 7 rolls, for example 1, 6, 6 (onto 13, ladder to 46), 4 (onto 50, ladder to 69), 5 (onto 74, ladder to 92), 2, 6. On an empty board it would be 17.

How long is a typical game?

Bad solutionPlay a few games by hand

Snakes and ladders is all luck, so a few games tell you almost nothing.

Good solutionSimulate a million games

Easy with our classes, and parallel as in step 10. One million single-player games on our board:

simulated 1M solo games: mean=55.02, longest=658

Great solutionWork it out exactly

Let E(s) be the expected rolls to finish from square s. From any square, you roll once and land on one of six squares, each with chance 1/6. So E(s) = 1 + the average of E over those six squares, and E(100) = 0. Start every E at zero and keep applying that formula to every square until nothing changes any more. That’s expectedRolls() above.

ExactFinish: fewest rolls=7, expected rolls=54.98
BounceBack: fewest rolls=7, expected rolls=72.24
no snakes or ladders: fewest=17, expected=33.33

The exact answer (54.98) matches the simulation (55.02), which is a good check that both are right. And it reveals something the designers would want to know: on this board, the bounce-back rule makes the average game 31% longer. Square 99 has a snake, and bouncing back from an overshoot can land you right on it (98 plus a roll of 3 bounces to 99, then slides to 41). The longest simulated game took 658 rolls, which says even more about the shape of the board: a game that long is a support ticket.

A random board generator

Generate random jumps, and let the Board constructor be the judge: if it throws, try again. Then use BoardAnalyzer to keep only boards whose expected length is in a range, say 25 to 45 rolls. Validation and analysis already exist; the generator is just a loop around them.

Two dice

new RandomDice(2, random), and the game works. But watch out: with two dice you can never roll a 1. With the exact-finish rule, a player on square 99 could never finish (on our board 99 has a snake, so nobody rests there, but on another board they could). And the analyzer assumes rolls of 1 to 6 with equal chance. So BoardAnalyzer should take the dice’s possible rolls and their chances instead of assuming one die. Spotting that a change in one place quietly breaks an assumption in another is exactly what this follow-up tests.

Mistakes people make on this one

• *Separate Snake and Ladder classes,* plus null checks on every square.
• *A Cell object per square* holding a possible snake and a possible ladder.
• *Calling Math.random() inside the game,* so no game can be tested.
• Hard-coding one house rule with no way for another family to play their way.
• No board validation, so a jump from 100 or a loop of jumps breaks games at runtime.
• Applying the jump before the finish rule, so a bounce back that lands on a snake doesn’t slide.
• Sharing a plain counter across simulation threads, and trusting the total.
• *Sharing one Random across threads,* and wondering why more threads made it slower.

How this answer gets scored

The whole design on one page

1. Data: a Board (last square plus a map of Jumps by start square) that validates itself and never changes.
2. A turn: check the turn, roll the Dice, let the FinishRule say where the move stops, follow a jump if there is one, check for a win, ask the TurnRule whether to pass the turn.
3. What varies: dice, finish rule and turn rule are strategies. Boards are data.
4. Testing: scripted dice make every game repeatable.
5. Concurrency: one lock per game online. For simulations, share only the immutable board; give each thread its own random source and its own total.
6. Analysis: breadth-first search for the fewest rolls; repeated averaging for the exact expected length.