Machine coding · Games and state machines

Snake and ladder board game

Reported once
SDE-1 (backend)
Strategy
State
Factory
1 source

One candidate write-up. Treat it as a single data point.

The prompt

Implement the board game snake and ladder in an object-oriented way. The basic rules must work, and extra requirements are to be supported by extension: any board size, any number of players, a ladder that begins where a snake ends, a snake that begins where a ladder ends, and play that continues until every player has finished.

Restated in our own words, not a quote from Swiggy or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

Questions to ask first:

How big is the board and how many dice? Assume a configurable size, default 100, and one die that returns a value from an injected source.
Which rules are mandatory? The report does not list them. Assume the standard game: players start off the board, roll one die in turn, and snakes and ladders move them.
Can a player overshoot the last cell? The source does not say. Assume an exact roll is needed, and make that rule swappable.
If a snake tail is the bottom of a ladder, or a ladder top is a snake head, do both fire in one move? Assume yes, followed to the end of the chain, and reject chains that loop.
Does the game stop at the first winner? Assume not: it continues until every player has finished and produces a ranking.
Extra turn on a six, capturing another player? Out of scope.

Entities and relationships

Who owns what, and who talks to whom.

Game runs turns. It has one Board, one Dice, one finish rule, a list of players, a queue of players still waiting to finish, a ranking and a status (playing or finished).
Board holds the size and a map from a start cell to an end cell. A snake is a jump whose end is lower than its start, a ladder is the opposite, so the board needs one concept, not two classes.
Player holds a name and a position, where 0 means not yet on the board.
Dice is an interface with roll(). SequenceDice replays a fixed list in tests; a random one has the same shape.
FinishRule is a strategy: ExactFinish keeps a player in place when the roll overshoots, OvershootFinishes clamps to the last cell.
createGame is the factory that builds a Game from a plain config and picks the finish rule by name.

The design

The class map, the main flow and the patterns that earn their place.

Snake and ladder class mapGame runs turns. Board, dice and the finish rule sit behind small seams, and a factory builds it all.

The factory builds the board, validates the jumps and picks the finish rule by name.
Each turn looks at the first player in the waiting queue.
The injected dice returns the roll; a bad roll throws before anything changes.
The finish rule decides where the player lands, keeping them still if the roll overshoots.
The board follows any snake or ladder chain from the landing cell.
The final cell is stored on the player, who is ranked or put back in the queue.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

The design keeps every rule that might change behind a small seam. The Board validates its jump map when it is built: a jump may not start on cell 1 or on the last cell, may not start where another jump starts, and must stay on the board. It also rejects a board smaller than two cells, and the game rejects duplicate player names. It then walks every chain with a visited set, so a loop such as 2 to 5 and 5 to 2 is rejected immediately with a clear message rather than hanging a game later. settle(cell) follows a chain until the cell has no jump, which gives the optional rule for free: a ladder that starts at a snake's tail, or a snake that starts at a ladder's end, is just two entries in the same map.

Dice is injected. Production code supplies a random die, tests supply SequenceDice, and a loaded die for a demo is the same interface. FinishRule is a Strategy for the one rule the prompt leaves open, so switching from exact finish to overshoot is a config value, not an edit to Game.

Turn flow in playTurn():

Reject the call if the game is already finished.
Look at the player at the front of the waiting queue.
Roll the dice. A roll that is not a whole number of at least 1 throws here, before anything has changed, so a failed roll never costs the player their place. Then take the player off the queue and ask the finish rule where they land from the current cell.
Ask the board to settle that cell through snakes and ladders and store the result as the player's position.
If the position is the last cell, append the player to the ranking. Otherwise put the player at the back of the queue.
When the queue is empty the status becomes finished. The method returns a record with the roll, the cell landed on and the final cell, which a UI or a test can print.

The status field is a small state machine: playing to finished only when the last player reaches the end, and no turn is accepted afterwards. Because finished players leave the queue, "play until everyone finishes" needs no special loop, and a game with any number of players or any board size uses the same code.

Trade-off: snakes and ladders are one kind of entry in a single jump map. If you later add obstacles with different behaviour, such as skip a turn, replace the map value with a cell effect object that has an apply(player) method.

The code

Runnable JavaScript, with the checks it passes.

swiggy-snake-and-ladder.js

class SequenceDice {
  constructor(values) {
    this.values = values.slice();
    this.index = 0;
  }
  roll() {
    if (this.index >= this.values.length) throw new Error("dice script exhausted");
    this.index += 1;
    return this.values[this.index - 1];
  }
}

class Board {
  constructor(size, jumps) {
    if (!Number.isInteger(size) || size < 2) throw new Error("board size must be an integer of at least 2");
    this.size = size;
    this.jumps = new Map();
    for (const [from, to] of jumps) {
      const valid = from >= 2 && from < size && to >= 1 && to <= size && from !== to && !this.jumps.has(from);
      if (!valid) throw new Error("invalid jump " + from + " to " + to);
      this.jumps.set(from, to);
    }
    for (const from of this.jumps.keys()) this.settle(from);
  }
  settle(cell) {
    const seen = new Set();
    let at = cell;
    while (this.jumps.has(at)) {
      if (seen.has(at)) throw new Error("jump cycle at " + at);
      seen.add(at);
      at = this.jumps.get(at);
    }
    return at;
  }
}

class ExactFinish {
  land(position, roll, size) {
    return position + roll > size ? position : position + roll;
  }
}

class OvershootFinishes {
  land(position, roll, size) {
    return Math.min(position + roll, size);
  }
}

const FINISH_RULES = { exact: () => new ExactFinish(), overshoot: () => new OvershootFinishes() };

class Game {
  constructor(board, names, dice, finishRule) {
    if (names.length < 1) throw new Error("at least one player is needed");
    if (new Set(names).size !== names.length) throw new Error("player names must be unique");
    this.board = board;
    this.dice = dice;
    this.finishRule = finishRule;
    this.players = names.map((name) => ({ name, position: 0 }));
    this.waiting = this.players.slice();
    this.ranking = [];
    this.status = "playing";
  }
  playTurn() {
    if (this.status === "finished") throw new Error("game is over");
    const player = this.waiting[0];
    const roll = this.dice.roll();
    if (!Number.isInteger(roll) || roll < 1) throw new Error("the dice returned " + roll);
    this.waiting.shift();
    const from = player.position;
    const landed = this.finishRule.land(from, roll, this.board.size);
    player.position = this.board.settle(landed);
    if (player.position === this.board.size) this.ranking.push(player.name);
    else this.waiting.push(player);
    if (this.waiting.length === 0) this.status = "finished";
    return { player: player.name, roll, from, landed, to: player.position };
  }
  playToEnd(maxTurns) {
    let turns = 0;
    while (this.status === "playing" && turns < maxTurns) {
      this.playTurn();
      turns += 1;
    }
    return this.ranking;
  }
}

function createGame(config) {
  const makeRule = FINISH_RULES[config.finish || "exact"];
  if (!makeRule) throw new Error("unknown finish rule " + config.finish);
  return new Game(new Board(config.size, config.jumps || []), config.players, config.dice, makeRule());
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

How would you give a player another turn after rolling a six, and cancel the turn after three sixes in a row?
How would you support two dice, or a loaded die that is used only in tests?
How would you add a trap cell that makes the player skip the next turn?
What changes if landing on an occupied cell sends the other player back to the start?
How would you stop the game when only one player is left, or when the first player finishes?

Where candidates slip

The mistakes this problem punishes.

This problem punishes these slips:

Writing separate Snake and Ladder classes with duplicated logic, then having no clean way to add a third obstacle.
Resolving a jump only once, so the optional chain rule fails, or resolving it with no cycle check so a bad board loops for ever.
Calling a random number generator inside the game, which makes every test flaky.
Declaring the first finisher the winner and stopping, when the prompt asks that play continue until all have finished.
Forgetting the overshoot rule, or letting a player move past the last cell.
Mixing printing into the rules, so the game cannot be tested without capturing output.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Candidate write-up · 2021Swiggy Interview Experience for SDE-1, off-campus 2021 (GeeksforGeeks)

Now make it stick

Where this was reported

More on games and state machines