Design Snake and Ladder

package com.androidinterview.snakeandladder.game;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.function.Consumer;

import com.androidinterview.snakeandladder.model.Board;
import com.androidinterview.snakeandladder.model.Dice;
import com.androidinterview.snakeandladder.model.Player;

// The whole game. A queue for turn order, one roll, one move, one win check.
// There is no snake handling and no ladder handling in here, because the board
// already resolved both into a destination.
public final class Game {

    private final Board board;
    private final Dice dice;
    private final Deque<Player> turnOrder = new ArrayDeque<>();
    private final Consumer<String> log;

    private Player winner;

    public Game(Board board, Dice dice, List<Player> players) {
        this(board, dice, players, System.out::println);
    }

    // The commentary goes to a listener rather than straight to stdout, so the
    // same game runs behind a socket, in a test or in a UI without anyone
    // capturing a stream.
    public Game(Board board, Dice dice, List<Player> players, Consumer<String> log) {
        this.board = board;
        this.dice = dice;
        this.log = log;
        this.turnOrder.addAll(players);
    }

    public boolean isOver() {
        return winner != null;
    }

    public Player winner() {
        return winner;
    }

    public void play() {
        while (!isOver()) {
            playTurn();
        }
        log.accept(winner.name() + " wins the game");
    }

    // One player's whole turn. A six earns another roll, and three sixes in a
    // row cancels the turn, which is why the starting cell is kept.
    public void playTurn() {
        Player player = turnOrder.poll();
        int startedAt = player.position();
        int sixes = 0;
        boolean rollAgain = true;

        while (rollAgain) {
            int roll = dice.roll();
            sixes = roll == 6 ? sixes + 1 : 0;
            if (sixes == 3) {
                player.moveTo(startedAt);
                break;
            }
            move(player, roll);
            if (player.position() == board.size()) {
                winner = player;
                // The winner is not pushed back on the queue. Keeping the rest
                // going until one player is left is what turns this into a
                // ranking, and it costs this one return.
                return;
            }
            rollAgain = roll == 6;
        }
        turnOrder.add(player);
    }

    private void move(Player player, int roll) {
        int from = player.position();
        int target = from + roll;
        // The exact finish rule, and the requirement most people miss. A roll
        // that would overshoot the last cell does not move the player at all.
        int to = target > board.size() ? from : board.destinationFrom(target);
        player.moveTo(to);
        log.accept(player.name() + " rolled a " + roll + " and moved from " + from + " to " + to);
    }
}

package com.androidinterview.snakeandladder.model;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Cell to destination, one map. A list of snakes and a list of ladders would
// mean scanning both on every move, so the entities are flattened into a
// lookup once at construction and never scanned again.
public final class Board {

    private final int size;
    private final Map<Integer, Integer> jumps = new HashMap<>();

    public Board(int size, List<BoardEntity> entities) {
        this.size = size;
        for (BoardEntity entity : entities) {
            requireOnBoard(entity.start());
            requireOnBoard(entity.end());
            if (entity.start() == size) {
                throw new IllegalArgumentException("Nothing may start on the last cell, " + entity.start());
            }
            if (jumps.put(entity.start(), entity.end()) != null) {
                throw new IllegalArgumentException("Two entities start at cell " + entity.start());
            }
        }
    }

    // The board is the only object that knows how big it is, so the range check
    // belongs here rather than on the entity. A ladder to 105 leaves a player on
    // a cell that never equals the last one, so they can never win, and a snake
    // head on the last cell makes the game unwinnable for everybody.
    private void requireOnBoard(int cell) {
        if (cell < 1 || cell > size) {
            throw new IllegalArgumentException("Cell " + cell + " is off a board of " + size + " cells");
        }
    }

    public int size() {
        return size;
    }

    // Jumps chain, because a ladder can land you on a snake head. Follow them
    // until the cell is quiet. The hop cap turns a badly built board into an
    // error instead of a program that never returns.
    public int destinationFrom(int cell) {
        int current = cell;
        for (int hop = 0; jumps.containsKey(current) && hop <= jumps.size(); hop++) {
            current = jumps.get(current);
        }
        if (jumps.containsKey(current)) {
            throw new IllegalStateException("Jumps loop forever starting at " + cell);
        }
        return current;
    }
}

package com.androidinterview.snakeandladder.model;

// One type for both. A snake goes down and a ladder goes up, and that is the
// entire difference between them. Two classes would carry no extra behaviour,
// and they would push a snake branch and a ladder branch into the turn loop
// forever. With one type the loop only ever asks where a cell leads.
public record BoardEntity(int start, int end) {

    public static BoardEntity snake(int head, int tail) {
        if (tail >= head) {
            throw new IllegalArgumentException("A snake has to go down, " + head + " to " + tail);
        }
        return new BoardEntity(head, tail);
    }

    public static BoardEntity ladder(int bottom, int top) {
        if (top <= bottom) {
            throw new IllegalArgumentException("A ladder has to go up, " + bottom + " to " + top);
        }
        return new BoardEntity(bottom, top);
    }
}

package com.androidinterview.snakeandladder.model;

import java.util.Random;

// The number of dice is a field, which is the whole reason the two dice
// variant is a one line change rather than a rewrite.
public final class Dice {

    private final int count;
    private final Random random;

    public Dice(int count, Random random) {
        this.count = count;
        this.random = random;
    }

    public int roll() {
        int total = 0;
        for (int die = 0; die < count; die++) {
            total += random.nextInt(6) + 1;
        }
        return total;
    }
}

package com.androidinterview.snakeandladder.model;

// A name and a cell. Everything else about a turn belongs to the game, because
// a player that knows the rules is a player you edit when the rules change.
public final class Player {

    private final String name;
    private int position;

    public Player(String name) {
        this.name = name;
    }

    public String name() {
        return name;
    }

    public int position() {
        return position;
    }

    public void moveTo(int position) {
        this.position = position;
    }
}

package com.androidinterview.snakeandladder.game

import com.androidinterview.snakeandladder.model.Board
import com.androidinterview.snakeandladder.model.Dice
import com.androidinterview.snakeandladder.model.Player

// The whole game. A deque for turn order, one roll, one move, one win check.
// There is no snake handling and no ladder handling here, because the board
// already resolved both into a destination.
//
// The commentary goes to a listener that defaults to println, so the same game
// runs behind a socket, in a test or in a UI without anyone capturing stdout.
class Game(
    private val board: Board,
    private val dice: Dice,
    players: List<Player>,
    private val log: (String) -> Unit = ::println,
) {

    private val turnOrder = ArrayDeque(players)

    var winner: Player? = null
        private set

    val isOver: Boolean get() = winner != null

    fun play() {
        while (!isOver) playTurn()
        log("${winner?.name} wins the game")
    }

    // One player's whole turn. A six earns another roll, and three sixes in a
    // row cancels the turn, which is why the starting cell is kept. The do
    // while condition can read the roll declared inside the body, so there is
    // no flag variable.
    fun playTurn() {
        val player = turnOrder.removeFirst()
        val startedAt = player.position
        var sixes = 0
        do {
            val roll = dice()
            sixes = if (roll == 6) sixes + 1 else 0
            if (sixes == 3) {
                player.moveTo(startedAt)
                break
            }
            move(player, roll)
            if (player.position == board.size) {
                winner = player
                // The winner is not pushed back on the queue. Keeping the rest
                // going until one player is left is what turns this into a
                // ranking, and it costs this one return.
                return
            }
        } while (roll == 6)
        turnOrder.addLast(player)
    }

    private fun move(player: Player, roll: Int) {
        val from = player.position
        val target = from + roll
        // The exact finish rule, and the requirement most people miss. A roll
        // that would overshoot the last cell does not move the player at all.
        val to = if (target > board.size) from else board.destinationFrom(target)
        player.moveTo(to)
        log("${player.name} rolled a $roll and moved from $from to $to")
    }
}

package com.androidinterview.snakeandladder.model

// Cell to destination, one map. Two lists would mean scanning both on every
// move, so the entities are flattened into a lookup once and never scanned.
class Board(val size: Int, entities: List<BoardEntity>) {

    private val jumps = entities.associate { it.start to it.end }

    init {
        require(jumps.size == entities.size) { "Two entities start on the same cell" }
        // The board is the only object that knows how big it is, so the range
        // check belongs here rather than on the entity. A ladder to 105 leaves
        // a player on a cell that never equals the last one, so they can never
        // win, and a snake head on the last cell makes the game unwinnable for
        // everybody.
        jumps.forEach { (start, end) ->
            require(start in 1..size && end in 1..size) {
                "$start to $end is off a board of $size cells"
            }
            require(start != size) { "Nothing may start on the last cell, $start" }
        }
    }

    // Jumps chain, because a ladder can drop you on a snake head. Follow them
    // until the cell is quiet. The hop count turns a badly built board into an
    // error rather than a program that never returns.
    tailrec fun destinationFrom(cell: Int, hops: Int = 0): Int {
        check(hops <= jumps.size) { "Jumps loop forever starting at $cell" }
        val next = jumps[cell] ?: return cell
        return destinationFrom(next, hops + 1)
    }
}

package com.androidinterview.snakeandladder.model

// One type for both. A snake goes down and a ladder goes up, and that is the
// entire difference. Two classes would carry no extra behaviour and would push
// a snake branch and a ladder branch into the turn loop forever.
data class BoardEntity(val start: Int, val end: Int)

fun snake(head: Int, tail: Int): BoardEntity {
    require(tail < head) { "A snake has to go down, $head to $tail" }
    return BoardEntity(head, tail)
}

fun ladder(bottom: Int, top: Int): BoardEntity {
    require(top > bottom) { "A ladder has to go up, $bottom to $top" }
    return BoardEntity(bottom, top)
}

package com.androidinterview.snakeandladder.model

import kotlin.random.Random

// A die is only something that produces a number, so it is a function type.
// The count is captured in the lambda, which is what makes the two dice
// variant one line instead of a new class.
typealias Dice = () -> Int

fun dice(count: Int = 1, random: Random = Random.Default): Dice =
    { (1..count).sumOf { random.nextInt(1, 7) } }

package com.androidinterview.snakeandladder.model

// A name and a cell. Everything else about a turn belongs to the game, because
// a player that knows the rules is a player you edit when the rules change.
//
// The cell moves through moveTo and nowhere else, so nothing outside the game
// can teleport a player.
class Player(val name: String) {

    var position: Int = 0
        private set

    fun moveTo(cell: Int) {
        position = cell
    }
}