CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 4 of 6 · 4 min read

The code

Validate once, then play.

The dice and the board:

interface Dice { int roll(); }

class ScriptedDice implements Dice {
    private final int[] v; private int i;
    ScriptedDice(int... v) { this.v = v; }
    public int roll() { return v[i++ % v.length]; }
}

class Board {
    private final int size; private final Map<Integer, Integer> jumps;

    Board(int size, Map<Integer, Integer> jumps) {
        if (size < 10) throw new IllegalArgumentException("size");
        for (var e : jumps.entrySet()) {
            int from = e.getKey(), to = e.getValue();
            if (from < 2 || from >= size || to < 1 || to > size || from == to)
                throw new IllegalArgumentException("bad jump " + from + "->" + to);
        }
        for (int to : jumps.values())
            if (jumps.containsKey(to)) throw new IllegalArgumentException("chained jump at " + to);
        this.size = size; this.jumps = Map.copyOf(jumps);
    }
    int size() { return size; }
    int resolve(int square) { return jumps.getOrDefault(square, square); }
}

The checks keep out jumps that start at square 1 or at the last square, jumps that start and end on the same square, and jumps that end outside the board. They also forbid a jump that ends on the start of another jump. Without that rule a ladder that ends on a snake head would force a chain, and two jumps could even form a loop. Forbidding chains is the simplest answer. Resolving chains is a possible rule, but then cycles must be detected, so say which you chose.

The game:

class Game {
    private final Board board; private final Dice dice;
    private final List<Player> players; private final int[] pos;
    private int turn; private Player winner;

    void step() {
        if (winner != null) throw new IllegalStateException("game over");
        int i = turn, roll = dice.roll(), target = pos[i] + roll;
        if (target <= board.size()) pos[i] = board.resolve(target);   // else stay
        if (pos[i] == board.size()) { winner = players.get(i); return; }
        turn = (turn + 1) % players.size();
    }
}

step rolls once, moves, applies a jump if any, checks for a win and passes the turn. A turn is not passed after a win, so the state stays correct.

A run with the jumps 4 to 25, 27 to 5, 99 to 10 and 50 to 90, and a scripted die that gives 4, 3, 2, 6 (made up):

Turn Player Roll Result
1 A 4 lands on 4, ladder to 25
2 B 3 lands on 3
3 A 2 lands on 27, snake to 5
4 B 6 lands on 9

After four turns A is on 5 and B is on 9. Because the die is scripted, this table is the same on every run. That is the point of the interface.

A second run uses RandomDice with a fixed seed of 7, three players and no jumps. The game finishes with player A winning after 79 steps. Fixing the seed makes even a random game repeatable. A third run, on a board of 10, shows the exact-finish rule: with rolls 6, 6, 6, 6, 4, both players reach 6, then each is refused a roll of 6 (it would reach 12), and A's roll of 4 lands on 10 and wins.

Bad boards are refused when built: the jumps 4 to 25 and 25 to 3 give "chained jump at 25", and a jump from 100 to 3 on a 100-square board gives "bad jump 100->3".

Check yourself: 1. After the first four turns, where are A and B? 2. What does a seeded random die give that an unseeded one does not? 3. Why is the turn not passed after a win?