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. In designing a Library Management System, which component is best suited to handle the tracking of book loans and returns to ensure accurate availability status?

easy

A. A separate LoanManager class that manages all loan and return transactions

B. The Library class, which maintains a global list of all books and their statuses

C. The User class, which tracks the books currently borrowed by the user

D. The Book class itself, by maintaining a status flag indicating availability

Solution

1. Step 1: Understand Single Responsibility Principle

   Tracking loans and returns involves managing transactions and state changes, which is best encapsulated in a dedicated LoanManager to avoid bloating Book or User classes.

2. Step 2: Why not Book class?

   Embedding availability logic in Book violates SRP and complicates concurrency handling.

3. Step 3: Why not User class?

   User should track borrowed books but not manage loan state transitions globally.

4. Step 4: Why not Library class?

   Library manages collections but delegating loan logic to a specialized manager improves modularity and concurrency control.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   LoanManager centralizes loan logic, enabling better consistency and easier concurrency handling.

Hint: Separate transaction logic from data entities for clarity and concurrency [OK]

Common Mistakes:

• Putting loan logic inside Book class
• Letting User class handle global loan state
• Overloading Library class with transaction details

2. You are designing a system where multiple components need to be notified when certain events occur, but each component only wants to receive notifications for specific event types. Which design approach best ensures loose coupling and efficient event delivery to interested components only?

easy

A. Using a publish-subscribe pattern where components subscribe to event types and get notified only for those

B. Implementing a centralized event queue that all components read from regardless of event type

C. Polling each component periodically to check for event changes

D. Using a brute force approach where the subject notifies all components for every event

Solution

1. Step 1: Understand the problem constraints

   The system requires notifying multiple components selectively based on event types, ensuring loose coupling.

2. Step 2: Identify the design pattern that supports selective notification

   The publish-subscribe pattern allows components to subscribe to specific event types and receive notifications only for those, avoiding unnecessary updates and tight coupling.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Publish-subscribe enables selective, decoupled notifications [OK]

Hint: Selective notification requires publish-subscribe pattern [OK]

Common Mistakes:

• Assuming polling is efficient for event-driven updates

3. What is the time complexity of computing the cost() method when stacking k decorators on a core object using the Decorator Pattern with dynamic behavior injection?

medium

A. O(1) because each decorator adds a fixed cost

B. O(k) because each decorator delegates the call to the next one

C. O(k^2) because each decorator calls all previous decorators recursively

D. O(log k) because decorators form a balanced tree structure

Solution

1. Step 1: Identify call chain length

   Each decorator's cost() calls the wrapped object's cost(), forming a chain of length k.

2. Step 2: Calculate total calls

   Cost computation requires traversing all k decorators once, so time complexity is O(k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each decorator adds constant work, total linear in k [OK]

Hint: Decorator calls chain length equals number of decorators [OK]

Common Mistakes:

• Assuming O(1) because cost is a simple addition
• Mistaking recursive calls as quadratic

4. 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

5. In a large-scale system where behaviors need to be dynamically changed at runtime, what is a key design consideration when using composition to avoid pitfalls that inheritance-based designs face?

hard

A. Use deep inheritance hierarchies to capture all behavior variations upfront.

B. Ensure that composed behavior objects are immutable to prevent side effects.

C. Avoid using interfaces and rely on concrete classes to reduce complexity.

D. Design behavior interfaces and use delegation so behaviors can be swapped without modifying the main object.

Solution

1. Step 1: Understand dynamic behavior change

   To change behaviors at runtime, the design must support swapping behavior implementations easily.

2. Step 2: Analyze options

   Ensure that composed behavior objects are immutable to prevent side effects. is not practical; immutability limits dynamic changes. Avoid using interfaces and rely on concrete classes to reduce complexity. increases coupling and reduces flexibility. Use deep inheritance hierarchies to capture all behavior variations upfront. contradicts favoring composition and leads to rigid designs.

3. Step 3: Confirm best practice

   Design behavior interfaces and use delegation so behaviors can be swapped without modifying the main object. promotes defining behavior interfaces and delegating calls, enabling runtime swapping without modifying main objects.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Delegation with interfaces is key to flexible, dynamic composition.

Hint: Use interfaces and delegation to swap behaviors dynamically, not inheritance or concrete classes.

Common Mistakes:

• Thinking immutability aids dynamic behavior changes
• Relying on inheritance for runtime flexibility