Design Ludo

package com.androidinterview.ludo.game;

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

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveValidator;

// The turn loop, and it stays short because it delegates twice. The validator
// says what is legal and the strategy says what is played, so this class only
// owns turn order, extra turns and the win check.
public final class Game {

    private final MoveValidator validator;
    private final IntSupplier dice;
    private final Deque<Player> turnOrder = new ArrayDeque<>();
    private final List<Token> allTokens;

    private Player winner;

    public Game(MoveValidator validator, IntSupplier dice, List<Player> players) {
        this.validator = validator;
        this.dice = dice;
        this.turnOrder.addAll(players);
        this.allTokens = players.stream().flatMap(player -> player.tokens().stream()).toList();
    }

    public Player winner() {
        return winner;
    }

    public void play() {
        while (winner == null) {
            playTurn();
        }
    }

    // One player's whole turn, including any extra rolls a six or a capture
    // earns them.
    public void playTurn() {
        Player player = turnOrder.poll();
        int sixes = 0;
        boolean rollAgain = true;

        while (rollAgain) {
            int roll = dice.getAsInt();
            sixes = roll == 6 ? sixes + 1 : 0;
            if (sixes == 3) {
                // Three sixes forfeits the turn and the third roll is not
                // played at all.
                break;
            }
            List<Move> legal = validator.legalMoves(player.tokens(), allTokens, roll);
            if (legal.isEmpty()) {
                // No legal move is a normal outcome, not an error. Forgetting
                // this is the most common bug in a ludo implementation.
                break;
            }
            Move move = player.strategy().choose(legal);
            apply(move);
            if (player.hasWon()) {
                winner = player;
                return;
            }
            rollAgain = roll == 6 || move.isCapture();
        }
        turnOrder.add(player);
    }

    private void apply(Move move) {
        move.token().moveTo(move.toSteps());
        move.captured().forEach(Token::returnToYard);
    }
}

package com.androidinterview.ludo.game;

import java.util.List;
import java.util.stream.IntStream;

import com.androidinterview.ludo.model.Color;
import com.androidinterview.ludo.model.Token;
import com.androidinterview.ludo.rules.MoveSelectionStrategy;

// A player is a colour, four tokens and a way of choosing. The choosing is a
// strategy, so a person and three bots of different difficulty sit at the same
// table with no branching anywhere in the game.
public record Player(String name, Color color, List<Token> tokens, MoveSelectionStrategy strategy) {

    public static Player of(String name, Color color, MoveSelectionStrategy strategy) {
        return new Player(name, color, IntStream.range(0, 4).mapToObj(id -> new Token(color, id)).toList(), strategy);
    }

    public boolean hasWon() {
        return tokens.stream().allMatch(Token::isHome);
    }
}

package com.androidinterview.ludo.model;

import java.util.Set;

// The geometry, and nothing else. It answers one question that matters, which
// shared cell is this token standing on, and one that supports a rule variant,
// is that cell safe.
public final class Board {

    public static final int TRACK_CELLS = 52;

    // Steps 0 to 50 are the shared track, steps 51 to 56 are the private home
    // column, and step 56 is home. One number line for the whole journey.
    public static final int LAST_TRACK_STEP = 50;
    public static final int HOME_STEP = 56;

    private final Set<Integer> safeCells;

    public Board() {
        // The four entry cells and the four star cells eight ahead of them.
        this(Set.of(0, 8, 13, 21, 26, 34, 39, 47));
    }

    public Board(Set<Integer> safeCells) {
        this.safeCells = safeCells;
    }

    // The only place steps become a cell, and only for a token still on the
    // shared track. Two colours collide when this returns the same number.
    public int cellAt(Color color, int steps) {
        return (color.entryCell() + steps) % TRACK_CELLS;
    }

    public int cellOf(Token token) {
        return cellAt(token.color(), token.steps());
    }

    public boolean isSafe(int cell) {
        return safeCells.contains(cell);
    }
}

package com.androidinterview.ludo.model;

// A colour ties a player, four tokens, a yard and a home column together. It
// also carries where that colour joins the shared track, which is the only
// per colour number the rest of the design needs.
public enum Color {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39);

    private final int entryCell;

    Color(int entryCell) {
        this.entryCell = entryCell;
    }

    public int entryCell() {
        return entryCell;
    }
}

package com.androidinterview.ludo.model;

import java.util.List;

// A candidate move, already knowing what it would capture. The validator works
// that out once, so the game does not have to recompute it when it applies the
// move, and a bot can score the move without touching the board.
public record Move(Token token, int fromSteps, int toSteps, List<Token> captured) {

    public boolean isCapture() {
        return !captured.isEmpty();
    }
}

package com.androidinterview.ludo.model;

// A token stores how far it has travelled, not which cell it is standing on.
// Every colour enters the track at a different place, so an absolute cell
// would force per colour arithmetic into every rule. Steps travelled makes all
// four colours identical, and it makes the home column a continuation of the
// same number line rather than a special case.
public final class Token {

    public static final int YARD = -1;

    private final Color color;
    private final int id;
    private int steps = YARD;

    public Token(Color color, int id) {
        this.color = color;
        this.id = id;
    }

    public Color color() {
        return color;
    }

    public int id() {
        return id;
    }

    public int steps() {
        return steps;
    }

    // The four token states are derived, never stored. A stored state field is
    // a second source of truth that can disagree with the step count.
    public boolean isInYard() {
        return steps == YARD;
    }

    public boolean isHome() {
        return steps == Board.HOME_STEP;
    }

    public boolean isOnSharedTrack() {
        return steps >= 0 && steps <= Board.LAST_TRACK_STEP;
    }

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

    public void returnToYard() {
        this.steps = YARD;
    }

    @Override
    public String toString() {
        return color + " " + id;
    }
}

package com.androidinterview.ludo.rules;

import java.util.Comparator;
import java.util.List;

import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

// The choice, which is the whole thing that makes ludo harder than snake and
// ladder. The validator says which moves are legal, this says which one is
// played, and swapping a person for a bot changes nothing else.
@FunctionalInterface
public interface MoveSelectionStrategy {

    // The caller guarantees the list is not empty. An empty list is a passed
    // turn and the game loop deals with it, so no strategy has to.
    Move choose(List<Move> legalMoves);

    // Deterministic, so a game replays identically in a test. A bot that needs
    // a seeded random generator to be testable is a worse bot.
    static MoveSelectionStrategy firstLegal() {
        return moves -> moves.get(0);
    }

    // Take a capture, otherwise get a token out of the yard, otherwise push
    // the token that is furthest along. Three lines of heuristic, and it plays
    // a recognisable game.
    static MoveSelectionStrategy aggressive() {
        return moves -> moves.stream().max(Comparator.comparingInt(MoveSelectionStrategy::score)).orElseThrow();
    }

    private static int score(Move move) {
        if (move.isCapture()) {
            return 200 + move.captured().size();
        }
        if (move.fromSteps() == Token.YARD) {
            return 100;
        }
        return move.toSteps();
    }
}

package com.androidinterview.ludo.rules;

import java.util.ArrayList;
import java.util.List;

import com.androidinterview.ludo.model.Board;
import com.androidinterview.ludo.model.Move;
import com.androidinterview.ludo.model.Token;

// Every rule in the game is in this one class. Keeping it out of the game loop
// is the biggest structural decision in the design, because it turns a sixty
// line if chain into a list the caller can look at, score and choose from.
public final class MoveValidator {

    private final Board board;

    public MoveValidator(Board board) {
        this.board = board;
    }

    // The list may be empty, and that is a real outcome, not an error. All
    // four tokens in the yard and a roll of three means the turn simply passes.
    public List<Move> legalMoves(List<Token> playerTokens, List<Token> allTokens, int roll) {
        List<Move> moves = new ArrayList<>();
        for (Token token : playerTokens) {
            if (token.isHome()) {
                continue;
            }
            if (token.isInYard()) {
                // A six is the only way out of the yard, onto step zero, which
                // is this colour's entry cell.
                if (roll == 6) {
                    moves.add(candidate(token, 0, allTokens));
                }
                continue;
            }
            int destination = token.steps() + roll;
            // The exact finish rule. Overshooting home is not a legal move, so
            // it never reaches the player as an option at all.
            if (destination <= Board.HOME_STEP) {
                moves.add(candidate(token, destination, allTokens));
            }
        }
        return moves;
    }

    private Move candidate(Token token, int destination, List<Token> allTokens) {
        return new Move(token, token.steps(), destination, capturesAt(token, destination, allTokens));
    }

    private List<Token> capturesAt(Token mover, int destination, List<Token> allTokens) {
        // The home column is private, so nothing can be captured there.
        if (destination > Board.LAST_TRACK_STEP) {
            return List.of();
        }
        int cell = board.cellAt(mover.color(), destination);
        if (board.isSafe(cell)) {
            return List.of();
        }
        List<Token> captured = new ArrayList<>();
        for (Token other : allTokens) {
            if (other.color() != mover.color() && other.isOnSharedTrack() && board.cellOf(other) == cell) {
                captured.add(other);
            }
        }
        return captured;
    }
}

package com.androidinterview.ludo.game

import com.androidinterview.ludo.model.Color
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.rules.MoveSelectionStrategy
import com.androidinterview.ludo.rules.MoveValidator
import kotlin.random.Random

typealias Dice = () -> Int

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

// A player is a colour, four tokens and a way of choosing. Choosing is a
// strategy, so a person and three bots of different difficulty sit at one
// table with no branching in the game.
class Player(val name: String, val color: Color, val strategy: MoveSelectionStrategy) {
    val tokens = List(4) { id -> Token(color, id) }
    val hasWon get() = tokens.all { it.isHome }
}

// The turn loop, short because it delegates twice. The validator says what is
// legal and the strategy says what is played, so this class owns turn order,
// extra turns and the win check, and nothing else.
class Game(
    private val validator: MoveValidator,
    private val dice: Dice,
    players: List<Player>,
) {

    private val turnOrder = ArrayDeque(players)
    private val allTokens = players.flatMap { it.tokens }

    var winner: Player? = null
        private set

    fun play() {
        while (winner == null) playTurn()
    }

    // One player's whole turn, including any extra rolls a six or a capture
    // earns them.
    fun playTurn() {
        val player = turnOrder.removeFirst()
        var sixes = 0
        var rollAgain = true

        while (rollAgain) {
            val roll = dice()
            sixes = if (roll == 6) sixes + 1 else 0
            // Three sixes forfeits the turn and the third roll is not played.
            if (sixes == 3) break

            val legal = validator.legalMoves(player.tokens, allTokens, roll)
            // No legal move is a normal outcome, not an error. Forgetting this
            // is the most common bug in a ludo implementation.
            if (legal.isEmpty()) break

            val move = player.strategy(legal)
            apply(move)
            if (player.hasWon) {
                winner = player
                return
            }
            // A six or a capture earns one more roll, never two.
            rollAgain = roll == 6 || move.isCapture
        }
        turnOrder.addLast(player)
    }

    private fun apply(move: Move) {
        move.token.moveTo(move.toSteps)
        move.captured.forEach(Token::returnToYard)
    }
}

package com.androidinterview.ludo.model

// A colour ties a player, four tokens, a yard and a home column together, and
// carries the one per colour number the rest of the design needs, where that
// colour joins the shared track.
enum class Color(val entryCell: Int) {
    RED(0),
    GREEN(13),
    YELLOW(26),
    BLUE(39),
}

const val YARD = -1

// Steps 0 to 50 are the shared track, 51 to 56 are the private home column,
// and 56 is home. One number line for the whole journey.
const val LAST_TRACK_STEP = 50
const val HOME_STEP = 56
const val TRACK_CELLS = 52

// A token stores how far it has travelled, not the cell it stands on. Each
// colour joins the track somewhere different, so an absolute cell would push
// per colour arithmetic into every rule. Steps make all four colours identical
// and turn the home column into more of the same number line.
class Token(val color: Color, val id: Int) {

    var steps: Int = YARD
        private set

    // The four states are derived, never stored. A stored state field is a
    // second source of truth that can disagree with the step count.
    val isInYard get() = steps == YARD
    val isHome get() = steps == HOME_STEP
    val isOnSharedTrack get() = steps in 0..LAST_TRACK_STEP

    fun moveTo(steps: Int) {
        this.steps = steps
    }

    fun returnToYard() {
        steps = YARD
    }

    override fun toString() = "$color $id"
}

// A candidate move that already knows what it would capture. The validator
// works that out once, so the game does not repeat it and a bot can score a
// move without touching the board.
data class Move(val token: Token, val fromSteps: Int, val toSteps: Int, val captured: List<Token>) {
    val isCapture get() = captured.isNotEmpty()
}

// The geometry, and nothing else. Safe cells are a constructor argument
// because which cells are safe is exactly the rule that varies by region.
class Board(private val safeCells: Set<Int> = setOf(0, 8, 13, 21, 26, 34, 39, 47)) {

    // The only place steps become a cell, and only for a token still on the
    // shared track. Two colours collide when this returns the same number.
    fun cellAt(color: Color, steps: Int) = (color.entryCell + steps) % TRACK_CELLS

    fun cellOf(token: Token) = cellAt(token.color, token.steps)

    fun isSafe(cell: Int) = cell in safeCells
}

package com.androidinterview.ludo.rules

import com.androidinterview.ludo.model.Board
import com.androidinterview.ludo.model.HOME_STEP
import com.androidinterview.ludo.model.LAST_TRACK_STEP
import com.androidinterview.ludo.model.Move
import com.androidinterview.ludo.model.Token
import com.androidinterview.ludo.model.YARD

// The choice, which is the whole thing that makes ludo harder than snake and
// ladder. The validator says what is legal, this says what is played, and it
// is a function type because it has one job.
//
// The caller guarantees the list is not empty. An empty list is a passed turn
// and the game loop deals with it, so no strategy has to.
typealias MoveSelectionStrategy = (legalMoves: List<Move>) -> Move

// Deterministic, so a game replays identically in a test. A bot that needs a
// seeded random generator to be testable is a worse bot.
val FirstLegal: MoveSelectionStrategy = { moves -> moves.first() }

// Take a capture, otherwise leave the yard, otherwise push the token furthest
// along. Three lines of heuristic and it plays a recognisable game.
val Aggressive: MoveSelectionStrategy = { moves ->
    moves.maxBy { move ->
        when {
            move.isCapture -> 200 + move.captured.size
            move.fromSteps == YARD -> 100
            else -> move.toSteps
        }
    }
}

// Every rule in the game is in this one class. Keeping it out of the turn loop
// is the biggest structural decision here, because it turns a sixty line if
// chain into a list the caller can look at, score and choose from.
class MoveValidator(private val board: Board) {

    // The list may be empty, and that is a real outcome rather than an error.
    // Four tokens in the yard and a roll of three means the turn passes.
    fun legalMoves(playerTokens: List<Token>, allTokens: List<Token>, roll: Int): List<Move> =
        playerTokens.mapNotNull { token ->
            when {
                token.isHome -> null
                // A six is the only way out of the yard, onto step zero, which
                // is this colour's entry cell.
                token.isInYard -> if (roll == 6) token.candidate(0, allTokens) else null
                // The exact finish rule. Overshooting home is not legal, so it
                // never reaches the player as an option at all.
                token.steps + roll <= HOME_STEP -> token.candidate(token.steps + roll, allTokens)
                else -> null
            }
        }

    private fun Token.candidate(destination: Int, allTokens: List<Token>) =
        Move(this, steps, destination, capturesAt(destination, allTokens))

    private fun Token.capturesAt(destination: Int, allTokens: List<Token>): List<Token> {
        // The home column is private, so nothing can be captured there.
        if (destination > LAST_TRACK_STEP) return emptyList()
        val cell = board.cellAt(color, destination)
        if (board.isSafe(cell)) return emptyList()
        return allTokens.filter { it.color != color && it.isOnSharedTrack && board.cellOf(it) == cell }
    }
}