Connect 4 - Interview challenge solution

Content

What is Connect 4?
Implementation Overview
Implementation
Final thoughts and code

What is Connect 4?

Connect 4 is a classic two-player game where players take turns dropping colored tokens into a vertical grid. The goal is to be the first player to form a line of 4 tokens either horizontally, vertically, or diagonally.

The game mechanics are straightforward:

The game board is a 7x7 grid that starts empty
Players take turns selecting a column to drop their token
The token falls to the lowest empty position in that column
A player wins by connecting 4 of their tokens in a line:
- Horizontally (left to right)
- Vertically (up and down)
- Diagonally (at a 45 degree angle)
If the board fills up with no winner, the game is a draw

The key challenge in implementing Connect 4 is efficiently:

Managing the game state (board representation)
Handling token placement and gravity
Detecting winning combinations
Validating moves (full columns, out of bounds)
Switching between players

Let's look at how we can implement this in code...

Implementation Overview

The challenge starts with the following "base" code.

We need to implement three methods: play, checkWinner, and print (with print serving as a helper method). We can certainly implement additional methods or properties if needed.

/**
Connect4

Connect4 is a game where two players take turns placing a token on columns that drop to the bottom.
When a player forms 4 of his tokens in a line - horizontally, vertically,or diagonally - the player wins.

[Visualization](https://i.ebayimg.com/images/g/DzMAAOSwSjxj6m0e/s-l1600.jpg)

Implement Connect 4 with the class below.
*/

export const PLAYER_ONE = 1
export const PLAYER_TWO = 2

export class Connect4 {
  constructor() {}
  play(col) {}
  checkWinner() {}
  print() {}
}

Implementation

Initialize the board

We need to keep track of some stuff like the board, the current player and the winner. We can add the properties at class level.

export class Connect4 {
  board;
  currentPlayer;
  winner;
  
  constructor() {}
}

Then we need to create a base board where we have the "slots" so the "chip" or token can fall in. In this case is the player number.

As you might expect, we will work with 2D arrays. Something like this:

	0	1	2	3	4	5	6
0	○	○	○	○	○	○	○
1	○	○	○	○	○	○	○
2	○	○	○	○	○	○	○
3	○	○	○	○	○	○	○
4	○	○	○	○	○	○	○
5	○	○	○	○	○	○	○
6	○	○	○	○	○	○	○

So then we need to create the initial array with arrays (2D array). I made a mistake when using the fill() method. The error is pointed in code with a comment.

I was not able to see it at first but once I realized it was so obvious 😅.

Also currentPlayer is initialized.

constructor() {
    // ❌ Same array reference to all positions in the first array
    // this.board = Array(BOARD_SIZE).fill(Array(BOARD_SIZE).fill(""));

    // Init the board
    this.board = Array(BOARD_SIZE)
      .fill(null)
      .map(() => Array(BOARD_SIZE).fill(""));
    
    this.currentPlayer = PLAYER_ONE;
  }

The play method

The play method can be implemented in two ways:

Start from the bottom of the col -index 6- and go up until an empty slot is found
Start from the top of the col -index 0- and go until you find a non-empty slot and then put the chip/token in the previous slot

Option 2 is the more "natural way", but option 1 is easier to implement. Therefore, we'll implement option 1.

...
export const BOARD_SIZE = 7;
export const SLOTS_TO_WIN = 4;

export class Connect4 {
  ...

  play(col) {
    for (let row = BOARD_SIZE - 1; row >= 0; row--) {
      const valueAtPos = this.board[row][col];

      // If slot is empty, put a value and break
      if (!valueAtPos) {
        this.board[row][col] = this.currentPlayer;
        this.checkWinner(row, col);
        break;
      }
    }
  }
}

One of the most important parts in this section, is the break; call to stop the loop to continue.

The change of players need to be handled too.

play(col) {
  ...

  this.currentPlayer =
        this.currentPlayer === PLAYER_ONE ? PLAYER_TWO : PLAYER_ONE;
}

Using .table() to print a nice looking board

console.table() allows you to print arrays and objects in a nice looking way. Much easier than implementing 2x for loops to achieve almost the same result.

export class Connect4 {
...

  print() {
    console.table(this.board);
  }
}

The code above will look like:

The difficult part of checkWinner()

To check for a winner we need to consider that 4 chips in a row requires checking, in total, 4 cases:

Horizontally ↔
Vertically ↕
Diagonally from right to left ↖ and ↘ (RTL)
Diagonally from left to right ↗ and ↙ (LTR)

To check the 4 cases above there are many ways to do it:

Brute force. On every new check iterate the whole board and check for horizontal, vertical and diagonal coincidences.
- Too many loops, too much computational complexity.
Mini matrix. Check only the slots closer to the newly inserted chip.
- A smaller matrix means faster iteration but is still inefficient.
Starting from the recently inserted chip move around 3 more positions.
- The newly inserted chip + 3 positions to each side and 4 consecutive chips of the same player = win

From the options above, the third option is the most efficient. Certainly, there are other approaches, but for now, I think the third option is sufficient.

To implement it we need an offset, from the [row, col] coordinate we need to move in different directions.

To the left and right for horizontal checks
To top and bottom for vertical checks
To top-left and bottom-right for diagonal LTR checks
To top-right and bottom-left for diagonal RTL checks

For each direction, we need to check 3 positions from the newly inserted chip. For example, if we insert a chip at [3,3]:

Horizontal: Check positions [3,0], [3,1], [3,2], [3,3], [3,4], [3,5], [3,6]
Vertical: Check positions [0,3], [1,3], [2,3], [3,3], [4,3], [5,3], [6,3]
Diagonal LTR: Check positions [0,0], [1,1], [2,2], [3,3], [4,4], [5,5], [6,6]
Diagonal RTL: Check positions [0,6], [1,5], [2,4], [3,3], [4,2], [5,1], [6,0]

Make sure to avoid out of bounds indexes, especially for the rows part.

Since we are iterating based on the offset and not specifically on the board itself, we can check all directions in the same loop.

So, 4 arrays are created to store the findings when checking the surroundings of the newly inserted chip. The arrays will contain the values of the checked positions. Ex:

[undefined, "", 1, 1, 2, 2, ""]

Show me the code!

checkWinner(row, col) {
  const horizontals = [];
  const verticals = [];
  const diagonalLTR = [];
  const diagonalRTL = [];

  const offset = SLOTS_TO_WIN - 1;
  for (
    let currentOffset = -offset;
    currentOffset <= offset;
    currentOffset++
  ) {
    horizontals.push(this.board[row][col + currentOffset]);
    if (row + currentOffset > 0 && row + currentOffset < BOARD_SIZE) {
      verticals.push(this.board[row + currentOffset][col]);
      diagonalLTR.push(this.board[row + currentOffset][col + currentOffset]);
      diagonalRTL.push(this.board[row + currentOffset][col - currentOffset]);
    }
  }
}

For example, when checking positions [row + currentOffset][col + currentOffset] for diagonal checks, we need to validate that row + currentOffset is within the valid range (0 to BOARD_SIZE - 1). Otherwise we'll get undefined values or errors when trying to access positions outside the board boundaries.

That's why this condition exists:

if (row + currentOffset > 0 && row + currentOffset < BOARD_SIZE)

If we find 4 consecutive chips from the current player we have a winner 🎉.

To check for the 4 consecutive chips in the previously created arrays, we can implement a new function called hasAllNeededSlots() which receives the array.

hasAllNeededSlots(arr) {
    let consecutiveCount = 0;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === this.currentPlayer) {
        consecutiveCount++;
        if (consecutiveCount === SLOTS_TO_WIN) {
          return true;
        }
      } else {
        consecutiveCount = 0;
      }
    }

    return consecutiveCount === SLOTS_TO_WIN;
  }

Checking for if (consecutiveCount === SLOTS_TO_WIN) inside the loop is crucial in case we have something like [undefined, 1, 1, 1, 1, 2, 2].

If we don't the counter will reset to 0 and winner will not be found.

Final thoughts and code

Extra code not included in this article was added because of validations and readability. However, the core functionality has been thoroughly covered.

The final code for this Connect 4 implementation handles all the edge cases we discussed:

Validates column input is within bounds
Checks if column is full before playing
Detects horizontal, vertical and diagonal wins
Handles game ending in draw
Alternates between players
Prevents further moves after game ends

The core game logic demonstrates important programming concepts like:

2D array manipulation
Loop control flow
Win condition algorithms
State management
Input validation

You can find the complete code in the GitHub repository.

	0	1	2	3	4	5	6
0	○	○	○	○	○	○	○
1	○	○	○	○	○	○	○
2	○	○	○	○	○	○	○
3	○	○	○	○	○	○	○
4	○	○	○	○	○	○	○
5	○	○	○	○	○	○	○
6	○	○	○	○	○	○	○

	0	1	2	3	4	5	6
0	○	○	○	○	○	○	○
1	○	○	○	○	○	○	○
2	○	○	○	○	○	○	○
3	○	○	○	○	○	○	○
4	○	○	○	○	○	○	○
5	○	○	○	○	○	○	○
6	○	○	○	○	○	○	○

	0	1	2	3	4	5	6
0	○	○	○	○	○	○	○
1	○	○	○	○	○	○	○
2	○	○	○	○	○	○	○
3	○	○	○	○	○	○	○
4	○	○	○	○	○	○	○
5	○	○	○	○	○	○	○
6	○	○	○	○	○	○	○