Design Snake and Ladder Game - LLD End-to-End

▶

Steps

setup

Define the Player class

We start by defining the Player class, which represents a participant in the game. It has fields for the player's name and current position on the board.

💡 Defining Player first is crucial because players are the main actors whose positions change during the game.

Line:

class Player {
  private String name;
  private int position;
}

💡 Player encapsulates the state of a game participant, enabling position tracking.

setup

Add Player methods

We add methods to Player for getting the name and position, and for updating the position. These methods control access to the player's state.

💡 Encapsulation is key; methods allow controlled interaction with player data.

Line:

public String getName() { return name; }
public int getPosition() { return position; }
public void setPosition(int pos) { position = pos; }

💡 Methods provide safe access and modification of player state.

setup

Define the Board class

Next, we define the Board class which represents the game board. It holds the size of the board and mappings for snakes and ladders.

💡 Board is central to the game logic, storing the layout and special moves.

Line:

class Board {
  private int size;
  private Map<Integer, Integer> snakes;
  private Map<Integer, Integer> ladders;
}

💡 Board encapsulates the game layout and special jump rules.

setup

Add Board constructor and methods

We add a constructor to initialize the board size and empty maps for snakes and ladders. Also, methods to add snakes and ladders are defined.

💡 Initialization and modification methods allow flexible board setup.

Line:

public Board(int size) {
  this.size = size;
  snakes = new HashMap<>();
  ladders = new HashMap<>();
}
public void addSnake(int start, int end) { snakes.put(start, end); }
public void addLadder(int start, int end) { ladders.put(start, end); }

💡 Board can be configured dynamically with snakes and ladders.

setup

Define the Dice class

We define the Dice class to simulate dice rolls. It has a method to roll and return a random number between 1 and 6.

💡 Dice encapsulates randomness, a key part of game progression.

Line:

class Dice {
  public int roll() {
    return new Random().nextInt(6) + 1;
  }
}

💡 Dice abstracts the randomness needed for player moves.

setup

Define the Game class

We define the Game class which manages the overall game. It holds the board, dice, list of players, and tracks the current player index.

💡 Game orchestrates all components and controls game flow.

Line:

class Game {
  private Board board;
  private Dice dice;
  private List<Player> players;
  private int currentPlayerIndex;
}

💡 Game aggregates all components and manages player turns.

setup

Add Game constructor and addPlayer method

We add a constructor to initialize the board and dice, and an addPlayer method to add players to the game.

💡 Initialization and player management are essential for starting the game.

Line:

public Game(Board board, Dice dice) {
  this.board = board;
  this.dice = dice;
  this.players = new ArrayList<>();
  this.currentPlayerIndex = 0;
}
public void addPlayer(Player player) {
  players.add(player);
}

💡 Game can be configured with players and components before starting.

insert

Implement playTurn method in Game

We implement playTurn which rolls the dice, moves the current player, checks for snakes or ladders, and updates the player's position accordingly.

💡 This method encapsulates the core game logic for a single player's turn.

Line:

public void playTurn() {
  Player currentPlayer = players.get(currentPlayerIndex);
  int roll = dice.roll();
  int newPos = currentPlayer.getPosition() + roll;
  if (board.snakes.containsKey(newPos)) {
    newPos = board.snakes.get(newPos);
  } else if (board.ladders.containsKey(newPos)) {
    newPos = board.ladders.get(newPos);
  }
  currentPlayer.setPosition(Math.min(newPos, board.size));
  currentPlayerIndex = (currentPlayerIndex + 1) % players.size();
}

💡 Game logic handles position updates and turn rotation.

insert

Add method to check for winner

We add a method to Game to check if any player has reached the last cell, indicating a winner.

💡 Detecting game end is essential for stopping play and declaring a winner.

Line:

public Player getWinner() {
  for (Player p : players) {
    if (p.getPosition() == board.size) {
      return p;
    }
  }
  return null;
}

💡 Game can determine if the game is over and who won.

setup

Establish relationships between classes

We define the relationships: Game aggregates Board, Dice, and Players. Player is a standalone entity. This clarifies ownership and interaction.

💡 Understanding relationships helps visualize how classes collaborate.

Line:

// Relationships are implicit in fields and constructor parameters

💡 Game composes Board, Dice, and Players, showing aggregation.

reconstruct

Final design review

We review the final design showing all classes, their fields, methods, and relationships. This is the complete Snake and Ladder game design.

💡 Seeing the full design together helps consolidate understanding of class roles and interactions.

Line:

// Final class diagram with all components and relationships

💡 The design cleanly separates concerns and models the game accurately.

import random

# STEP 1 & 2
class Player:
    def __init__(self, name):
        self.__name = name
        self.__position = 0

    def get_name(self):
        return self.__name

    def get_position(self):
        return self.__position

    def set_position(self, pos):
        self.__position = pos

# STEP 3 & 4
class Board:
    def __init__(self, size):
        self.__size = size
        self.__snakes = {}
        self.__ladders = {}

    def add_snake(self, start, end):
        self.__snakes[start] = end

    def add_ladder(self, start, end):
        self.__ladders[start] = end

    def get_size(self):
        return self.__size

    def get_snakes(self):
        return self.__snakes

    def get_ladders(self):
        return self.__ladders

# STEP 5
class Dice:
    def roll(self):
        return random.randint(1, 6)

# STEP 6 & 7
class Game:
    def __init__(self, board, dice):
        self.__board = board
        self.__dice = dice
        self.__players = []
        self.__current_player_index = 0

    def add_player(self, player):
        self.__players.append(player)

    # STEP 8
    def play_turn(self):
        current_player = self.__players[self.__current_player_index]
        roll = self.__dice.roll()
        new_pos = current_player.get_position() + roll

        snakes = self.__board.get_snakes()
        ladders = self.__board.get_ladders()

        if new_pos in snakes:
            new_pos = snakes[new_pos]
        elif new_pos in ladders:
            new_pos = ladders[new_pos]

        new_pos = min(new_pos, self.__board.get_size())
        current_player.set_position(new_pos)

        self.__current_player_index = (self.__current_player_index + 1) % len(self.__players)

    # STEP 9
    def get_winner(self):
        for player in self.__players:
            if player.get_position() == self.__board.get_size():
                return player
        return None

📊

Design Snake and Ladder Game - LLD End-to-End - Watch the Algorithm Execute, Step by Step

Watching the design build step-by-step helps you understand how each class and relationship contributes to the overall game functionality, which is hard to grasp from code alone.

Defines the Player entity with name and position fields.

Player

−name: String

−position: int

Added accessor and mutator methods to Player for encapsulation.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Defines Board with size and mappings for snakes and ladders.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

Added constructor and methods to configure snakes and ladders.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Defines Dice class with roll method to simulate dice throw.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Defines Game class aggregating Board, Dice, and Players.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

Added constructor and addPlayer method to Game.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

+Game()

+addPlayer()

Implemented playTurn to handle dice roll, move, snakes/ladders, and turn rotation.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

+Game()

+addPlayer()

+playTurn()

Added getWinner method to detect game completion.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

+Game()

+addPlayer()

+playTurn()

+1 more

Established aggregation relationships from Game to Board, Dice, and Player.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

+Game()

+addPlayer()

+playTurn()

+1 more

Game ◇ Board (1:1)Game ◇ Dice (1:1)Game ◇ Player (1:0..*)

Complete design showing all classes and their relationships.

Player

−name: String

−position: int

+getName()

+getPosition()

+setPosition()

Board

−size: int

−snakes: Map<Integer, Integer>

−ladders: Map<Integer, Integer>

+Board()

+addSnake()

+addLadder()

Dice

+roll()

Game

−board: Board

−dice: Dice

−players: List<Player>

−currentPlayerIndex: int

+Game()

+addPlayer()

+playTurn()

+1 more

Game ◇ Board (1:1)Game ◇ Dice (1:1)Game ◇ Player (1:0..*)

Key Takeaways

✓ The design cleanly separates responsibilities into Player, Board, Dice, and Game classes.

This separation is hard to see from code alone but becomes clear when visualizing class roles and relationships.

✓ Aggregation relationships show how Game composes other components, centralizing control.

Understanding ownership and collaboration is easier when seeing explicit relationships.

✓ The playTurn method encapsulates the core game logic, including dice roll, movement, and special board rules.

Watching this method stepwise clarifies how game state changes each turn.

Practice

1. When a class implements an interface and also extends an abstract class, what is the sequence of abstraction enforcement and implementation that occurs during object instantiation?

easy

A. The abstract class constructor runs, but interface methods have no implementation to run.

B. Interface methods are implemented first, then the abstract class constructor runs.

C. The class must implement interface methods before the abstract class constructor runs.

D. The abstract class's constructor runs first, then interface methods are implemented by the class.

Solution

1. Step 1: Understand interface role

   Interfaces declare methods but provide no implementation or constructors.

2. Step 2: Abstract class constructor behavior

   Abstract class constructors run during instantiation to initialize shared state.

3. Step 3: Implementation of interface methods

   The class implementing the interface provides method bodies; no constructor or code runs from interface itself.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Interfaces define contracts only; abstract class constructors run during instantiation.

Hint: Interface methods have no constructor or implementation to run; abstract class constructors always run.

Common Mistakes:

• Thinking interface methods have constructors or code to execute.
• Believing interface implementation order affects constructor execution.
• Confusing interface method implementation with constructor invocation.

2. Trace the sequence of events when a user attempts to borrow a book that is currently checked out by another user in a concurrent environment. Which step correctly describes the system's behavior?

easy

A. The Library class queues the request and processes it after the current loan expires without immediate feedback

B. The system immediately updates the book status to 'borrowed' for the requesting user without checking current loans

C. The User class updates its borrowed books list first, then the system verifies availability asynchronously

D. The LoanManager checks the book's availability, detects it is loaned out, and denies the request atomically

Solution

1. Step 1: Check availability atomically

   LoanManager must verify the book is available before granting loan to prevent race conditions.

2. Step 2: Why not immediate update?

   The system immediately updates the book status to 'borrowed' for the requesting user without checking current loans risks data inconsistency by ignoring current loan state.

3. Step 3: Why not User updates first?

   The User class updates its borrowed books list first, then the system verifies availability asynchronously breaks transactional integrity and can cause stale or conflicting states.

4. Step 4: Why not queue without feedback?

   The Library class queues the request and processes it after the current loan expires without immediate feedback delays user feedback and complicates user experience; immediate denial is standard.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Atomic availability check and denial maintain consistency and user clarity.

Hint: Always verify resource availability atomically before state changes in concurrency [OK]

Common Mistakes:

• Assuming immediate state update without checks
• Updating user state before system validation
• Delaying feedback by queuing without immediate response

3. You have an object with nested mutable fields, and you need to create a new object instance such that changes to the nested fields in the new object do not affect the original. Which approach best guarantees this behavior?

easy

A. Manually copy only the top-level fields, sharing nested references to save memory

B. Use a greedy algorithm to selectively copy fields based on usage frequency

C. Serialize the object to JSON and deserialize it back to create a new instance

D. Recursively copy all nested objects to create independent duplicates

Solution

1. Step 1: Understand the problem requirement

   The goal is to create a new object where nested mutable fields are independent, so changes in the copy do not affect the original.

2. Step 2: Evaluate approaches

   Manual shallow copy (A) shares nested references, causing side effects. Greedy selective copying (B) is not a standard approach and risks missing nested objects. JSON serialization (D) can lose methods and fail on special objects. Recursive deep copy (C) ensures all nested objects are duplicated, preserving independence.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Deep copy duplicates nested objects -> no shared references [OK]

Hint: Deep copy duplicates nested objects fully [OK]

Common Mistakes:

• Assuming shallow copy suffices for nested mutable fields

4. Imagine a class responsible for both data persistence and data validation. When a change in validation rules occurs, trace the impact on the class and explain what happens step-by-step.

easy

A. Only the validation methods need modification; persistence remains unaffected, so SRP is maintained.

B. Changing validation rules forces modifying the entire class, risking unintended side effects on persistence logic.

C. Validation changes automatically propagate to persistence without code changes due to tight coupling.

D. Persistence logic will break because validation and persistence are tightly integrated and inseparable.

Solution

1. Step 1: Identify responsibilities

   The class handles both validation and persistence, two distinct reasons to change.

2. Step 2: Trace change impact

   Changing validation rules requires modifying validation code inside the class.

3. Step 3: Side effects

   Because persistence logic shares the class, changes risk affecting persistence unintentionally, increasing maintenance risk.

4. Step 4: SRP violation

   This coupling violates SRP, as one reason to change (validation) affects unrelated functionality (persistence).

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   One reason to change should not force changes in unrelated code -> SRP violation.

Hint: One reason to change means one place to modify.

Common Mistakes:

• Assuming changes affect only related methods without side effects.
• Believing tight coupling is harmless if code is in one class.
• Thinking validation and persistence are always linked.

5. What is the worst-case space complexity of the Composite pattern iterator when traversing a tree with n nodes and height h?

medium

A. O(n) because all nodes are stored in the stack at once.

B. O(1) since the iterator uses constant extra space.

C. O(log n) assuming a balanced tree reduces height.

D. O(h) because the stack stores nodes along the current path only.

Solution

1. Step 1: Understand iterator stack usage

   The iterator stack holds nodes along the current traversal path, not all nodes simultaneously.

2. Step 2: Relate stack size to tree height

   Maximum stack size corresponds to the height h of the tree, as children are pushed and popped during traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack size bounded by tree height h, not total nodes n [OK]

Hint: Iterator stack size bounded by tree height, not total nodes [OK]

Common Mistakes:

• Assuming stack holds all nodes at once
• Confusing height with log n for unbalanced trees