Design Snake & Ladder

class Board {
    private final int size; // total cells, e.g. 100 for a 10x10 board
    // A single HashMap encodes BOTH snakes and ladders: cell -> destination cell.
    // Snake entries map head -> tail (destination < source).
    // Ladder entries map bottom -> top (destination > source).
    private final Map<Integer, Integer> jumpMap;
 
    Board(int size, List<Snake> snakes, List<Ladder> ladders) {
        this.size = size;
        this.jumpMap = new HashMap<>();
        for (Snake s : snakes) jumpMap.put(s.getHead(), s.getTail());
        for (Ladder l : ladders) jumpMap.put(l.getBottom(), l.getTop());
        validateNoOverlaps(snakes, ladders);
    }
 
    int getFinalCell() { return size; }
 
    /** Resolves chained jumps: a ladder top that is itself a snake head, etc. */
    int resolveJumps(int cell) {
        Set<Integer> visited = new HashSet<>(); // guards against a misconfigured infinite loop
        while (jumpMap.containsKey(cell)) {
            if (!visited.add(cell)) {
                throw new IllegalStateException("Cyclic snake/ladder configuration at cell " + cell);
            }
            cell = jumpMap.get(cell);
        }
        return cell;
    }
 
    private void validateNoOverlaps(List<Snake> snakes, List<Ladder> ladders) {
        // A cell cannot be both a snake head AND a ladder bottom — ambiguous rule.
        // A snake head cannot equal cell 1 (start) or the final cell (win cell).
        // Left as an exercise in a real implementation; called out here for interview credit.
    }
}

final class Snake {
    private final int head; // higher cell number
    private final int tail; // lower cell number
 
    Snake(int head, int tail) {
        if (tail >= head) throw new IllegalArgumentException("Snake tail must be below its head");
        this.head = head;
        this.tail = tail;
    }
 
    int getHead() { return head; }
    int getTail() { return tail; }
}
 
final class Ladder {
    private final int bottom; // lower cell number
    private final int top;    // higher cell number
 
    Ladder(int bottom, int top) {
        if (top <= bottom) throw new IllegalArgumentException("Ladder top must be above its bottom");
        this.bottom = bottom;
        this.top = top;
    }
 
    int getBottom() { return bottom; }
    int getTop() { return top; }
}

interface Dice {
    int roll();
}
 
class RandomDice implements Dice {
    private final int faces;
    private final Random random = new Random();
 
    RandomDice(int faces) { this.faces = faces; }
 
    public int roll() { return random.nextInt(faces) + 1; }
}
 
/** Test double: scripted rolls, so game-logic tests are 100% deterministic. */
class FixedSequenceDice implements Dice {
    private final Queue<Integer> scriptedRolls;
 
    FixedSequenceDice(List<Integer> rolls) {
        this.scriptedRolls = new LinkedList<>(rolls);
    }
 
    public int roll() {
        if (scriptedRolls.isEmpty()) throw new IllegalStateException("Dice script exhausted");
        return scriptedRolls.poll();
    }
}

class Player {
    private final String id;
    private final String name;
    private int position = 0; // 0 = not yet on the board; cell 1 is the first square
 
    Player(String id, String name) {
        this.id = id;
        this.name = name;
    }
 
    int getPosition() { return position; }
    void setPosition(int position) { this.position = position; }
    String getName() { return name; }
    String getId() { return id; }
}

interface OvershootRule {
    /** Returns the resolved position after applying a roll that may exceed the final cell. */
    int apply(int currentPosition, int roll, int finalCell);
}
 
/** Classic rule: a roll that overshoots is simply wasted — piece doesn't move. */
class StayInPlaceRule implements OvershootRule {
    public int apply(int currentPosition, int roll, int finalCell) {
        int target = currentPosition + roll;
        return target > finalCell ? currentPosition : target;
    }
}
 
/** Variant rule: overshoot bounces back by the excess amount. */
class BounceBackRule implements OvershootRule {
    public int apply(int currentPosition, int roll, int finalCell) {
        int target = currentPosition + roll;
        if (target <= finalCell) return target;
        int excess = target - finalCell;
        return finalCell - excess;
    }
}

interface GameObserver {
    void onMove(MoveEvent event);
    void onWin(WinEvent event);
}
 
record MoveEvent(Player player, int fromCell, int toCell, boolean snakeBite, boolean ladderClimb) {}
record WinEvent(Player winner) {}
 
class GameManager {
    private final Board board;
    private final List<Player> players;
    private final Dice dice;
    private final OvershootRule overshootRule;
    private final List<GameObserver> observers = new ArrayList<>();
    private int currentPlayerIndex = 0;
    private Player winner = null;
 
    GameManager(Board board, List<Player> players, Dice dice, OvershootRule overshootRule) {
        if (players.size() < 2) throw new IllegalArgumentException("Need at least 2 players");
        this.board = board;
        this.players = players;
        this.dice = dice;
        this.overshootRule = overshootRule;
    }
 
    void subscribe(GameObserver observer) { observers.add(observer); }
 
    void playTurn() {
        if (isGameOver()) throw new IllegalStateException("Game already over");
 
        Player current = players.get(currentPlayerIndex);
        int roll = dice.roll();
        int rawTarget = overshootRule.apply(current.getPosition(), roll, board.getFinalCell());
        int resolved = board.resolveJumps(rawTarget);
 
        boolean snakeBite = resolved < rawTarget;
        boolean ladderClimb = resolved > rawTarget;
 
        int from = current.getPosition();
        current.setPosition(resolved);
        notifyMove(new MoveEvent(current, from, resolved, snakeBite, ladderClimb));
 
        if (resolved == board.getFinalCell()) {
            winner = current;
            notifyWin(new WinEvent(current));
            return;
        }
        currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
    }
 
    boolean isGameOver() { return winner != null; }
    Player getWinner() { return winner; }
 
    private void notifyMove(MoveEvent e) { observers.forEach(o -> o.onMove(e)); }
    private void notifyWin(WinEvent e) { observers.forEach(o -> o.onWin(e)); }
}

int resolveJumps(int cell) {
    Set<Integer> visited = new HashSet<>();
    while (jumpMap.containsKey(cell)) {
        if (!visited.add(cell)) throw new IllegalStateException("Cyclic jump at cell " + cell);
        cell = jumpMap.get(cell);
    }
    return cell;
}

@Test
void playerWinsOnExactRoll() {
    Board board = new Board(100, List.of(), List.of());
    Player p1 = new Player("1", "Alice");
    Player p2 = new Player("2", "Bob");
    Dice scripted = new FixedSequenceDice(List.of(6, 6, /* ... */ 4)); // deterministic path to 100
    GameManager game = new GameManager(board, List.of(p1, p2), scripted, new StayInPlaceRule());
 
    while (!game.isGameOver()) game.playTurn();
 
    assertEquals("Alice", game.getWinner().getName());
}