0 - Design Connect Four

Design Connect Four

Background

Connect Four is a popular game played on a 7x6 grid. Two players take turns dropping colored discs into the grid. The first player to get four discs in a row (vertically, horizontally or diagonally) wins.

Connect Four

Requirements

Some possible questions to ask:

What are the rules of the game?
What size is the grid?
How many players are there? Player vs Computer? Player vs Player?
Are we keeping track of the score?

Basics

The game will be played by only two players, player vs player
The game board should be of variable dimensions
The target is to connect N discs in a row (vertically, horizontally or diagonally)
- N is a variable (e.g. connect 4, 5, 6, etc)
There should be a score tracking system
- After a player reaches the target score, they are the winner

Design

High-level

We will need a Grid class to maintain the state of the 2-D board
- The board cell can be empty, yellow (occupied by Player 1) or red (occupied by Player 2)
- The grid will also be responsible for checking for a win condition
We can have a Player class to represent the player's piece color
- This isn't super important, but encapsulating information is generally a good practice
The Game class will be composed of the Grid and Players
- The Game class will be responsible for the game loop and keeping track of the score

Code

We will use an enum to represent the GridPosition.

import enum

class GridPosition(enum.Enum):
    EMPTY = 0
    YELLOW = 1
    RED = 2

The Grid will maintain the state of the board and all of the pieces. It will also check for a win condition. Perhaps it would be more appropriate to name the checkWin method to checkNConnected, since the Grid itself shouldn't need to know what the rules of the game are.

class Grid:
    def __init__(self, rows, columns):
        self._rows = rows
        self._columns = columns
        self._grid = None
        self.initGrid()

    def initGrid(self):
        self._grid = [[GridPosition.EMPTY for _ in range(self._columns)] for _ in range(self._rows)]

    def getGrid(self):
        return self._grid

    def getColumnCount(self):
        return self._columns

    def placePiece(self, column, piece):
        if column < 0 or column >= self._columns:
            raise ValueError('Invalid column')
        if piece == GridPosition.EMPTY:
            raise ValueError('Invalid piece')
        for row in range(self._rows-1, -1, -1):
            if self._grid[row][column] == GridPosition.EMPTY:
                self._grid[row][column] = piece
                return row

    def checkWin(self, connectN, row, col, piece):
        count = 0
        # Check horizontal
        for c in range(self._columns):
            if self._grid[row][c] == piece:
                count += 1
            else:
                count = 0
            if count == connectN:
                return True

        # Check vertical
        count = 0
        for r in range(self._rows):
            if self._grid[r][col] == piece:
                count += 1
            else:
                count = 0
            if count == connectN:
                return True

        # Check diagonal
        count = 0
        for r in range(self._rows):
            c = row + col - r
            if c >= 0 and c < self._columns and self._grid[r][c] == piece:
                count += 1
            else:
                count = 0
            if count == connectN:
                return True

        # Check anti-diagonal
        count = 0
        for r in range(self._rows):
            c = col - row + r
            if c >= 0 and c < self._columns and self._grid[r][c] == piece:
                count += 1
            else:
                count = 0
            if count == connectN:
                return True

        return False

class Grid {
    private int rows;
    private int columns;
    private int[][] grid;

    public Grid(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        initGrid();
    }

    public void initGrid() {
        this.grid = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                grid[i][j] = GridPosition.EMPTY.ordinal();
            }
        }
    }

    public int[][] getGrid() {
        return this.grid;
    }

    public int getColumnCount() {
        return this.columns;
    }

    public int placePiece(int column, GridPosition piece) {
        if (column < 0 || column >= this.columns) {
            throw new Error("Invalid column");
        }
        if (piece == GridPosition.EMPTY) {
            throw new Error("Invalid piece");
        }
        // Place piece in the lowest empty row
        for (int row = this.rows - 1; row >= 0; row--) {
            if (this.grid[row][column] == GridPosition.EMPTY.ordinal()) {
                this.grid[row][column] = piece.ordinal();
                return row;
            }
        }
        return -1;
    }

    public boolean checkWin(int connectN, int row, int col, GridPosition piece) {
        // Check horizontal
        int count = 0;
        for (int c = 0; c < this.columns; c++) {
            if (this.grid[row][c] == piece.ordinal()) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check vertical
        count = 0;
        for (int r = 0; r < this.rows; r++) {
            if (this.grid[r][col] == piece.ordinal()) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check diagonal
        count = 0;
        for (int r = 0; r < this.rows; r++) {
            int c = row + col - r; // row + col = r + c, for a diagonal
            if (c >= 0 && c < this.columns && this.grid[r][c] == piece.ordinal()) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check anti-diagonal
        count = 0;
        for (int r = 0; r < this.rows; r++) {
            int c = col - row + r; // row - col = r - c, for an anti-diagonal
            if (c >= 0 && c < this.columns && this.grid[r][c] == piece.ordinal()) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }
        return false;
    }
}

class Grid {
private:
    int rows;
    int columns;
    vector<vector<int>> grid;
    
public:
    Grid(int rows, int columns) {
        this->rows = rows;
        this->columns = columns;
        initGrid();
    }

    void initGrid() {
        this->grid = vector<vector<int>>();
        for (int i = 0; i < rows; i++) {
            this->grid.push_back(vector<int>());
            for (int j = 0; j < columns; j++) {
                grid[i].push_back(GridPosition::EMPTY);
            }
        }
    }

    vector<vector<int>> getGrid() {
        return this->grid;
    }

    int getColumnCount() {
        return this->columns;
    }

    int placePiece(int column, GridPosition piece) {
        if (column < 0 || column >= this->columns) {
            throw "Invalid column";
        }
        if (piece == GridPosition::EMPTY) {
            throw "Invalid piece";
        }
        // Place piece in the lowest empty row
        for (int row = this->rows - 1; row >= 0; row--) {
            if (this->grid[row][column] == GridPosition::EMPTY) {
                this->grid[row][column] = piece;
                return row;
            }
        }
        return -1;
    }

    bool checkWin(int connectN, int row, int col, GridPosition piece) {
        // Check horizontal
        int count = 0;
        for (int c = 0; c < this->columns; c++) {
            if (this->grid[row][c] == piece) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check vertical
        count = 0;
        for (int r = 0; r < this->rows; r++) {
            if (this->grid[r][col] == piece) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check diagonal
        count = 0;
        for (int r = 0; r < this->rows; r++) {
            int c = row + col - r; // row + col = r + c, for a diagonal
            if (c >= 0 && c < this->columns && this->grid[r][c] == piece) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }

        // Check anti-diagonal
        count = 0;
        for (int r = 0; r < this->rows; r++) {
            int c = col - row + r; // row - col = r - c, for an anti-diagonal
            if (c >= 0 && c < this->columns && this->grid[r][c] == piece) {
                count++;
            } else {
                count = 0;
            }
            if (count == connectN) {
                return true;
            }
        }
        return false;
    }
};

class Grid {
    #rows;
    #columns;
    #grid;

    constructor(rows, columns) {
        this.#rows = rows;
        this.#columns = columns;
        this.initGrid();
    }

    initGrid() {
        this.#grid =
            Array(this.#rows).fill(0).map(
                () => Array(this.#columns).fill(GridPosition.EMPTY));
    }

    getGrid() {
        return this.#grid;
    }

    getColumnCount() {
        return this.#columns;
    }

    placePiece(column, piece) {
        if (column < 0 || column >= this.#columns) {
            throw new Error('Invalid column');
        }
        if (piece === GridPosition.EMPTY) {
            throw new Error('Invalid piece');
        }
        // Place piece in the lowest empty row
        for (let row = this.#rows - 1; row >= 0; row--) {
            if (this.#grid[row][column] === GridPosition.EMPTY) {
                this.#grid[row][column] = piece;
                return row;
            }
        }
    }

    checkWin(connectN, row, col, piece) {
        // Check horizontal
        let count = 0;
        for (let c = 0; c < this.#columns; c++) {
            if (this.#grid[row][c] === piece) {
                count++;
            } else {
                count = 0;
            }
            if (count === connectN) {
                return true;
            }
        }

        // Check vertical
        count = 0;
        for (let r = 0; r < this.#rows; r++) {
            if (this.#grid[r][col] === piece) {
                count++;
            } else {
                count = 0;
            }
            if (count === connectN) {
                return true;
            }
        }

        // Check diagonal
        count = 0;
        for (let r = 0; r < this.#rows; r++) {
            let c = row + col - r; // row + col = r + c, for a diagonal
            if (c >= 0 && c < this.#columns && this.#grid[r][c] === piece) {
                count++;
            } else {
                count = 0;
            }
            if (count === connectN) {
                return true;
            }
        }

        // Check anti-diagonal
        count = 0;
        for (let r = 0; r < this.#rows; r++) {
            let c = col - row + r; // row - col = r - c, for an anti-diagonal
            if (c >= 0 && c < this.#columns && this.#grid[r][c] === piece) {
                count++;
            } else {
                count = 0;
            }
            if (count === connectN) {
                return true;
            }
        }
        return false;
    }
}

A Player is only meant to encapsulate the player's information, more importantly the player's piece color.

class Player:
    def __init__(self, name, pieceColor):
        self._name = name
        self._pieceColor = pieceColor

    def getName(self):
        return self._name

    def getPieceColor(self):
        return self._pieceColor

class Player {
    private String name;
    private GridPosition piece;

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

    public String getName() {
        return this.name;
    }

    public GridPosition getPieceColor() {
        return this.piece;
    }
}

class Player {
private:
    string name;
    GridPosition piece;

public:
    Player(string name, GridPosition piece) {
        this->name = name;
        this->piece = piece;
    }

    string getName() {
        return this->name;
    }

    GridPosition getPieceColor() {
        return this->piece;
    }
};

class Player {
    #name
    #pieceColor;

    constructor(name, pieceColor) {
        this.#name = name;
        this.#pieceColor = pieceColor;
    }

    getName() {
        return this.#name;
    }

    getPieceColor() {
        return this.#pieceColor;
    }
}

The Game class will be used to play the game. It will keep track of the players, the score, and the grid. It will also be responsible for the game loop. The game parameters passed in via the constructor give us flexibility to play the game with slightly different rules and dimensions.
While we could instantiate the board within the Game class, it's preferred to pass it in via the constructor. This means the Game class does not need to know how to instantiate the board.
Even though we are only playing with two players, we can still use a list to store the players. This is not necessary, but it's easy enough and gives us flexibility to add more players in the future.

class Game:
    def __init__(self, grid, connectN, targetScore):
        self._grid = grid
        self._connectN = connectN
        self._targetScore = targetScore

        self._players = [
            Player('Player 1', GridPosition.YELLOW),
            Player('Player 2', GridPosition.RED)
        ]

        self._score = {}
        for player in self._players:
            self._score[player.getName()] = 0

    def printBoard(self):
        print('Board:\n')
        grid = self._grid.getGrid()
        for i in range(len(grid)):
            row = ''
            for piece in grid[i]:
                if piece == GridPosition.EMPTY:
                    row += '0 '
                elif piece == GridPosition.YELLOW:
                    row += 'Y '
                elif piece == GridPosition.RED:
                    row += 'R '
            print(row)
        print('')

    def playMove(self, player):
        self.printBoard()
        print(f"{player.getName()}'s turn")
        colCnt = self._grid.getColumnCount()
        moveColumn = int(input(f"Enter column between {0} and {colCnt - 1} to add piece: "))
        moveRow = self._grid.placePiece(moveColumn, player.getPieceColor())
        return (moveRow, moveColumn)

    def playRound(self):
        while True:
            for player in self._players:
                row, col = self.playMove(player)
                pieceColor = player.getPieceColor()
                if self._grid.checkWin(self._connectN, row, col, pieceColor):
                    self._score[player.getName()] += 1
                    return player

    def play(self):
        maxScore = 0
        winner = None
        while maxScore < self._targetScore:
            winner = self.playRound()
            print(f"{winner.getName()} won the round")
            maxScore = max(self._score[winner.getName()], maxScore)

            self._grid.initGrid() # reset grid
        print(f"{winner.getName()} won the game")

class Game {
    static Scanner input = new Scanner(System.in);
    private Grid grid;
    private int connectN;
    private Player[] players;
    private Map<String, Integer> score;
    private int targetScore;

    public Game(Grid grid, int connectN, int targetScore) {
        this.grid = grid;
        this.connectN = connectN;
        this.targetScore = targetScore;

        this.players = new Player[] {
            new Player("Player 1", GridPosition.YELLOW),
            new Player("Player 2", GridPosition.RED)
        };

        this.score = new HashMap<>();
        for (Player player : this.players) {
            this.score.put(player.getName(), 0);
        }
    }

    private void printBoard() {
        System.out.println("Board:");
        int[][] grid = this.grid.getGrid();
        for (int i = 0; i < grid.length; i++) {
            String row = "";
            for (int piece : grid[i]) {
                if (piece == GridPosition.EMPTY.ordinal()) {
                    row += "0 ";
                } else if (piece == GridPosition.YELLOW.ordinal()) {
                    row += "Y ";
                } else if (piece == GridPosition.RED.ordinal()) {
                    row += "R ";
                }
            }
            System.out.println(row);
        }
        System.out.println();
    }

    private int[] playMove(Player player) {
        printBoard();
        System.out.println(player.getName() + "'s turn");
        int colCnt = this.grid.getColumnCount();
        
        System.out.print("Enter column between 0 and " + (colCnt - 1) + " to add piece: ");
        int moveColumn = input.nextInt();
        int moveRow = this.grid.placePiece(moveColumn, player.getPieceColor());
        return new int[] { moveRow, moveColumn };
    }

    private Player playRound() {
        while (true) {
            for (Player player : this.players) {
                int[] pos = playMove(player);
                int row = pos[0];
                int col = pos[1];
                GridPosition pieceColor = player.getPieceColor();
                if (this.grid.checkWin(this.connectN, row, col, pieceColor)) {
                    this.score.put(player.getName(), this.score.get(player.getName()) + 1);
                    return player;
                }
            }
        }
    }

    public void play() {
        int maxScore = 0;
        Player winner = null;
        while (maxScore < this.targetScore) {
            winner = playRound();
            System.out.println(winner.getName() + " won the round");
            maxScore = Math.max(this.score.get(winner.getName()), maxScore);

            this.grid.initGrid(); // reset grid
        } 
        System.out.println(winner.getName() + " won the game");
    }
}

class Game {
private:
    Grid* grid;
    int connectN;
    vector<Player*> players;
    unordered_map<string, int> score;
    int targetScore;

public:
    Game(Grid* grid, int connectN, int targetScore) {
        this->grid = grid;
        this->connectN = connectN;
        this->targetScore = targetScore;

        this->players = vector<Player*> {
            new Player("Player 1", YELLOW),
            new Player("Player 2", RED)
        };

        this->score = unordered_map<string, int>();
        for (Player* player : this->players) {
            this->score[player->getName()] = 0;
        }
    }

    void printBoard() {
        cout << "Board:" << endl;
        vector<vector<int>> grid = this->grid->getGrid();
        for (int i = 0; i < grid.size(); i++) {
            string row = "";
            for (int piece : grid[i]) {
                if (piece == GridPosition::EMPTY) {
                    row += "0 ";
                } else if (piece == GridPosition::YELLOW) {
                    row += "Y ";
                } else if (piece == GridPosition::RED) {
                    row += "R ";
                }
            }
            cout << row << endl;
        }
        cout << endl;
    }

    vector<int> playMove(Player* player) {
        printBoard();
        cout << player->getName() << "'s turn" << endl;
        int colCnt = this->grid->getColumnCount();
        
        cout << "Enter column between 0 and " << (colCnt - 1) << " to add piece: ";
        int moveColumn = 0;
        cin >> moveColumn;
        
        int moveRow = this->grid->placePiece(moveColumn, player->getPieceColor());
        return vector<int> { moveRow, moveColumn };
    }

    Player* playRound() {
        while (true) {
            for (Player* player : this->players) {
                vector<int> pos = playMove(player);
                int row = pos[0];
                int col = pos[1];
                GridPosition pieceColor = player->getPieceColor();
                if (this->grid->checkWin(this->connectN, row, col, pieceColor)) {
                    this->score[player->getName()] = this->score[player->getName()] + 1;
                    return player;
                }
            }
        }
    }

    void play() {
        int maxScore = 0;
        Player* winner = nullptr;
        while (maxScore < this->targetScore) {
            winner = playRound();
            cout << winner->getName() << " won the round" << endl;
            maxScore = max(this->score[winner->getName()], maxScore);

            this->grid->initGrid(); // reset grid
        } 
        cout << winner->getName() << " won the game" << endl;
    }
};

const prompt = require('prompt-sync')({ sigint: true });

class Game {
    #grid;
    #connectN;
    #players;
    #score;
    #targetScore;

    constructor(grid, connectN, targetScore) {
        this.#grid = grid;
        this.#connectN = connectN;
        this.#targetScore = targetScore;

        this.#players = [
            new Player('Player 1', GridPosition.YELLOW),
            new Player('Player 2', GridPosition.RED)
        ];

        this.#score = {};
        for (const player of this.#players) {
            this.#score[player.getName()] = 0;
        }
    }

    #printBoard() {
        console.log('Board:\n');
        const grid = this.#grid.getGrid();
        for (let i = 0; i < grid.length; i++) {
            let row = '';
            for (let piece of grid[i]) {
                if (piece === GridPosition.EMPTY) {
                    row += '0 ';
                } else if (piece === GridPosition.YELLOW) {
                    row += 'Y ';
                } else if (piece === GridPosition.RED) {
                    row += 'R ';
                }
            }
            console.log(row);
        }
        console.log('');
    }

    #playMove(player) {
        this.#printBoard();
        console.log(`${player.getName()}'s turn`);
        const colCnt = this.#grid.getColumnCount();
        const moveColumn =
            Number(prompt(`Enter column between ${0} and ${colCnt - 1} to add piece: `));
        let moveRow = this.#grid.placePiece(moveColumn, player.getPieceColor());
        return [moveRow, moveColumn];
    }

    #playRound() {
        while (true) {
            for (const player of this.#players) {
                let [row, col] = this.#playMove(player);
                const pieceColor = player.getPieceColor();
                if (this.#grid.checkWin(this.#connectN, row, col, pieceColor)) {
                    this.#score[player.getName()]++;
                    return player;
                }
            }
        }
    }

    play() {
        let maxScore = 0;
        let winner = null;
        while (maxScore < this.#targetScore) {
            winner = this.#playRound();
            console.log(`${winner.getName()} won the round`);
            maxScore = Math.max(this.#score[winner.getName()], maxScore);

            this.#grid.initGrid(); // reset grid
        } 
        console.log(`${winner.getName()} won the game`);
    }
}

Finally, we can create the grid, set the game parameters, and play the game.

grid = Grid(6, 7)
game = Game(grid, 4, 2)
game.play()

Object-Oriented Design Interview

Design Connect Four

Design Blackjack

Design a Parking Lot

Design a Bank

Design a Movie Recommendation System

Design an Elevator System

Design Chess

0 - Design Connect Four

Design Connect Four

Background

Requirements

Basics

Design

High-level

Code