Tic-Tac-Toe: Exploring a TypeScript Code Example

Hello, fellow code connoisseurs! I've recently decided to refresh my memory on data structures and algorithms. This current project is inspired by freecodecamp's tic-tac-toe example. Buckle up, and let's get started!

Heres the original blog.

This code snippet revolves around a Tic-Tac-Toe game but with some added features, such as the ability to change the board size and randomize the starting player. The core functionality of the game is handled by a reducer called interactionAreaReducer, which takes in the current state and an action and returns the updated state based on the action.

We'll only be exploring this file (as this is where the core logic of the game is handled). Feel free to explore the rest of the repository here: tic-tac-toe-example.

Here's also a reference to React reducers if you aren't familiar.

Let's Get Started!

1. Importing essential modules and types

This piece of art begins by importing various modules and types, such as InteractionAreaState, playerTypes, InteractionAreaAction, and toTitleCase. I'll explain each briefly.

import InteractionAreaState from "@/reducers/interactionArea/state";
import playerTypes from "@/types/playerTypes";
import {InteractionAreaAction} from "@/reducers/interactionArea/action";
import {toTitleCase} from "@/utils/general";
import PlayerTypes from "@/types/playerTypes";

1. InteractionAreaState - An interface describing what our interaction area will have. 'InteractionArea' here referes to the part of the board a user interacts with when playing a move.
2. PlayerTypes - Note the uppercase 'P'. Refers to the different types of players. In this case, I haven't defined a 'computer' type and is therefore by default 2 player mode ('player-1' and 'player-2').
3. playerTypes - Note the lowercase 'p'. Refers to an array of type 'PlayerTypes'.
4. InteractionAreaAction - Refers to the different types of actions you can perform on the interaction area. This maybe be: 'reset_game', 'start_game' etc. They have been defined in the repo if you'd like to explore further.
5. toTitleCase - Just a utility function that uppercases each first letter of every word in a sentence.

2. Defining the initial state

The interactionAreaInitialState object sets up the game's initial state.

export const interactionAreaInitialState: InteractionAreaState = {
  playedMoves: new Set<string>(),
  cellsPlayed: new Map<string, playerTypes>(),
  boardSize: 3,
  hasGameStarted: false,
}

playedMoves here is a set since we want constant time lookup when a move is made so as to improve performance. Our board (as defined by boardSize) can grow to any size and therefore this performance difference becomes noticable if, say we were to use an array, as the board size increases.
cellsPlayed is a map that stores the coordinates each player has played. i.e. if a player clicks on the coordinate '[2][1]', we save a key of '21' and the value becomes the player i.e. 'player-1'. We use this map when doing a lookup of whether the game has a winner, and who the winner actually is.

3. Crafting the reducer:

The interactionAreaReducer is a function that takes the current state and an action, then returns the updated state based on the action type. This is where the bulk of our logic for starting a game, checking for a winner, checking for a draw, checking for invalid moves and resetting the game. We'll go through our switch statement step by step.

const interactionAreaReducer = (state: InteractionAreaState, action: InteractionAreaAction): InteractionAreaState => {
  switch (action.type) {
    case "start_game":
      // randomize between 'computer' and 'player-1'. 'player-1' will be '1' and 'computer will be '2'
      const start = Math.round((Math.random() * 2));
      return {...state, hasGameStarted: true, currentPlayer: start === 1 ? "player-1" : "player-2"}
}

Here, we randomly select which player starts. We round off the number to the nearest whole number since generating random numbers returns a floating point number.

const interactionAreaReducer = (state: InteractionAreaState, action: InteractionAreaAction): InteractionAreaState => {
  switch (action.type) {
    case "show_reset_button":
      return {...state, shouldShowResetButton: true}
}

Here, when all moves are exhausted, or a winner has been found, this action is invoked to show the button that when clicked will reset state.

const interactionAreaReducer = (state: InteractionAreaState, action: InteractionAreaAction): InteractionAreaState => {
  switch (action.type) {
    case "hide_reset_button":
      return {...state, shouldShowResetButton: false}
}

This action here hides the reset button. i.e. when a new game has started.

const interactionAreaReducer = (state: InteractionAreaState, action: InteractionAreaAction): InteractionAreaState => {
  switch (action.type) {
      case "reset_game":
      return interactionAreaInitialState;
}

This action returns the initial state, basically resetting state.

   case "play_move":
      // check if the move being played is possible
      const player = action.payload?.player || "player-1"; // Can never be undefined
      const move = action.payload?.move || ""; // Can never be undefined
      const playedMoves = new Set(state.playedMoves);
      const cellsPlayed = new Map(state.cellsPlayed);
      const boardSize = state.boardSize;

      // 1. Check if this move is available. If not, throw error.
      if (playedMoves.has(`${move[0]}${move[1]}`)) {
        alert("This move is not available");
        return {...state};
      }

      // 2. Inject the current move (Play the move)
      playedMoves.add(move);
      cellsPlayed.set(move, player);


      // 3. Check for winner
      if (checkWinner(boardSize, cellsPlayed)) {
        return {...state, shouldShowResetButton: true, playedMoves, cellsPlayed}
      }

      // 4. If no winner was found, and there aren't any other moves, end game.
      if (cellsPlayed.size === (boardSize * boardSize)) {
        // No more moves to play
        alert(`Game over. No player has won. Click on the reset button to start over.`);
        return {...state, shouldShowResetButton: true, playedMoves, cellsPlayed}
      }

      // 3. Play the move.
      const newCurrentPlayer = player === "player-1" ? "player-2" : "player-1";
      return {...state, playedMoves, cellsPlayed, currentPlayer: newCurrentPlayer}

Here, I think the comments are self explanatory. we'll switch over to the checkWinner function as this is the function that handles logic for selecting a winner.

const checkWinner = (boardSize: number, cellsPlayed: Map<string, playerTypes>): boolean => {

This function takes 2 arguments: boardSize which we'll use in our for...loop to traverse all cells in our grid and cellsPlayed which we'll use to identify which player made that move when traversing through each of our cells.

   // 1. Check rows
  let doesRowMatch = true;
  let rowCheck: PlayerTypes | undefined
  for (let i = 0; i < boardSize; i++) {
    rowCheck = cellsPlayed.get(`${i}${0}`) || "-";
    for (let j = 1; j < boardSize; j++) {
      if (rowCheck !== cellsPlayed.get(`${i}${j}`)) {
        doesRowMatch = false;
        break;
      }
    }
    if (doesRowMatch) {
      // exit, since we already found a winner.
      break;
    }
  }

Here, we loop through every single row in our array to check if there's a row where all cells match. The assumed state is that all cells will pass. If we run into a row with cells that do not pass, we break out of the inner loop since this entire row is already compromised. The if statement after the inner loop checks whether we did find a match. If we did, we do not need to traverse any other cells and instead we break out of loop. To better picture this, consider that the array we're working with is a matrix of boardSizeXboardSize and is a square. Here's an illustriong with indices: matrix.
The time complexity here is O(n*m) since we have a nested for...loop.

  let doesColumnMatch = true;
  let columnCheck: playerTypes | undefined;
  if (!doesRowMatch) {
    for (let i = 0; i < boardSize; i++) {
      columnCheck = cellsPlayed.get(`${0}${i}`) || "-";
      for (let j = 1; j < boardSize; j++) {
        if (columnCheck !== cellsPlayed.get(`${j}${i}`)) {
          doesColumnMatch = false;
          break;
        }
      }
      if (doesColumnMatch) {
        // exit, since we already found a winner.
        break;
      }
    }
  }

Here, we repeat the same logic for rows for columns. The only difference here is that we have inverted the indices when coming up with our keys. i.e. for the rows, originally it would have been [i][j] but for this we instead do [j][i]. Again, this is so much easier to picture if you consider our 2D array as a grid/matrix.
The time complexity here is O(n*m) since we have a nested for...loop.

 // 3. Check left diagonal
  let doesLeftDiagonalMatch = true;
  // Duplicate indices (i.e. 00, 11,22 ...) and you'll get your left diagonal.
  const leftDiagonalCheck = cellsPlayed.get(`${0}${0}`) || "-";
  if (!doesColumnMatch) {
    for (let i = 1; i < boardSize; i++) {
      let nextLeftDiagonalCheck = cellsPlayed.get(`${i}${i}`);
      if (leftDiagonalCheck !== nextLeftDiagonalCheck) {
        doesLeftDiagonalMatch = false;
        break;
      }
    }
  }

For left diagonals, as long as the matrix/grid is a square, the indices will always behave such that i and j will always be the same. As such, we need only a single loop and we infer the value of j from i.
The time complexity here is O(n) since we have a single for...loop.

  // 4. Check right diagonal.
  let doesRightDiagonalMatch = true;
  const rightDiagonalCheck = cellsPlayed.get(`${0}${boardSize - 1}`) || "-";
  if (!doesLeftDiagonalMatch) {
    for (let i = 1; i < boardSize; i++) {
      let nextRightDiagonalCheck = cellsPlayed.get(`${i}${boardSize - 1 - i}`);
      if (rightDiagonalCheck !== nextRightDiagonalCheck) {
        doesRightDiagonalMatch = false;
        break;
      }
    }
  }

For right diagonals, the behaviour is such that when value of i increase by 1, the value of j decrease by 1. As such, we also need only one loop here and we subtract the value of i from the total - 1 (boardSize - 1) to get indices of j.
The time complexity here is O(n) since we have a single for...loop.

let currentWinner: playerTypes | undefined;
  if (doesRowMatch) {
    currentWinner = rowCheck;
  } else if (doesColumnMatch) {
    currentWinner = columnCheck;
  } else if (doesRightDiagonalMatch) {
    currentWinner = rightDiagonalCheck;
  } else if (doesLeftDiagonalMatch) {
    currentWinner = leftDiagonalCheck;
  }
  if (currentWinner) {
    alert(`Game over. ${toTitleCase(currentWinner)} has won! Click on the reset button to start over.`);
    return true;
  }

Lastly, if we did find any columns,rows or diagonals matching, we print out the winner. This function returns a boolean to indicate whether a winner was found or not. This return value is used when no more moves are left and there was no winner.

In conclusion, due to the performance implications of nested for loops (when traversing cells in a 2D array), we have used maps and sets to store the values so that we get sublinear time complexity (O(log n)) or linear time (O(n)) since this is based on javascript but ideally a map and set lookup should be constant time (O(1)).

That's all for the tic-tac-toe game. Feel free to reach out if there's anything that's unclear, you have improvements or you'd just like to chat!