Advent of Typescript 2023 Day 21 : TIC TAC TOE

Hello Typescript Wizards, i hope you are having fun with the Advent of Typescript 2023.
With Trash we created some awesome challenges for you to solve this year.
I'm starting to do Blog posts to explain the solutions to the challenges since they are getting more and more complex.

Description

This challenge is about creating a Tic Tac Toe game in typescript type system.
For this we are working with some simple primitives types to describe the game.

The game

type TicTacToeChip = '❌' | '⭕';
type TicTacToeEndState = '❌ Won' | '⭕ Won' | 'Draw';
type TicTacToeState = TicTacToeChip | TicTacToeEndState;
type TicTacToeEmptyCell = '  ';
type TicTacToeCell = TicTacToeChip | TicTacToeEmptyCell;

type TicTactToeBoard = TicTacToeCell[][];

type TicTacToeGame = {
  board: TicTactToeBoard;
  state: TicTacToeState;
};

The game is played on a 3x3 board, each player has a chip, the first player has the ❌ chip and the second player has the ⭕ chip.
The game is won when a player has 3 chips in a row, column or diagonal.
The game is a draw when the board is full and no player has won.

The Game is represented by a TicTacToeGame object, which has a board Matrix and a state.

The board is a 3x3 matrix of TicTacToeCell which can be either a TicTacToeChip or a TicTacToeEmptyCell.

The challenge

Playing the game is done by calling the TicTacToe Utility type with the current game state and the next move.
The utility type will return the next game board and state.

Example

  Expect<
    Equal<
      TicTacToe<NewGame, 'top-center'>,
      {
        board: [
          [ '  ', '❌', '  ' ],
          [ '  ', '  ', '  ' ],
          [ '  ', '  ', '  ' ]
        ];
        state: '⭕';
      }
    >
  >

Solution to place a chip on the board

Here we will follow a step by step approach to solve this challenge.

Step 1: Map move to board position

The board can be described as a 3x3 matrix of TicTacToeCell.
Row and column are 0 based index, starting from the top left corner.

Here a mapping of the board position to the row and column index, keeping the index as string. This will come in handy later.

type PositionMap = {
  'top-left': ['0', '0'];
  'top-center': ['0', '1'];
  'top-right': ['0', '2'];
  'middle-left': ['1', '0'];
  'middle-center': ['1', '1'];
  'middle-right': ['1', '2'];
  'bottom-left': ['2', '0'];
  'bottom-center': ['2', '1'];
  'bottom-right': ['2', '2'];
};

Step 2: Set the chip on the board

Now that we have a mapping of the board position to the row and column index, we can set the chip on the board using Object Mapping.
Indeed we learned in previous challenges that we can use the Object Mapping to do a For Loop on Tuples.

We can divide the problem in 2 parts:

• Set the chip on the row
• Set the row on the board

We are also carreful to not override an existing chip on the board.
In such case we keep the existing board state.

Notice that we use K extends index to only set the chip on the row index. K is a string, that's why the mapping is done with string index.

type PlaceChipOnTuple<
  T extends TicTacToeCell[],
  X,
  Chip extends TicTacToeChip
> = {
  [K in keyof T]: K extends X ? 
    T[K] extends '  ' ?  // set only if the cell is empty
      Chip : 
      T[K] : 
    T[K];
};

type PlaceChipOnMatrix<
  Board extends TicTactToeBoard,
  Position extends [string, string],
  Chip extends TicTacToeChip,
  $y = Position[0], // alias for row index
  $x = Position[1]  // alias for column index
> = {
  [K in keyof Board]: K extends $y
    ? PlaceChipOnTuple<Board[K], $x, Chip>
    : Board[K];
};

We are not done yet, we can create a utility type to set the chip on the board given the current state. If the state is a win or a draw, we keep the current board.

Notice a trick here, we use Extract to cast the result to TicTactToeBoard since typescript has a hard time to infer the type.

type PlaceChip<
  Board extends TicTactToeBoard,
  Position extends [string, string],
  State extends TicTacToeState
> = State extends TicTacToeChip
  ? Extract<PlaceChipOnMatrix<Board, Position, State>, TicTactToeBoard>
  : Board;

Solution to check if the game is won

Now that we can place a chip on the board, we can check if the game is won.
For this we need to check if we have 3 same chips is in a row, column or diagonal.

Step 1: Check if rows are won

Enabler

We can check if a row is won by checking if all the chips in the row are the same.
We create a utility type to check if a row is won, given a Tuple.
This will come in handy for other checks.

type CheckCells<T extends TicTacToeCell[]> = 
  T extends [infer A, ...infer B]
  ? B[number] extends A
    ? A extends '  '
      ? false
      : A
    : false
  : false;

here we check that the first cell is the same as the rest of the cells in the row. We also check that the first cell is not empty to be sure that it's a Chip.
Note that we return the Chip if the row is won, this will come in handy later.

Check one row

So to check if a row is won, we can use the CheckCells utility type on the Board

type CheckRow<Board extends TicTactToeBoard, Row extends number> = 
  CheckCells<Board[Row]>;

Check all rows

Here we use a trick to check all the rows, we use typescript Distributive Conditional Types to iterate over the rows.

type CheckRows<
  Board extends TicTactToeBoard,
  $iter extends number = 0 | 1 | 2
> = $iter extends number
  ? CheckRow<Board, $iter> extends infer Chip extends TicTacToeChip
    ? Chip
    : never
  : never;

Step 2: Check if columns are won

Check one column

We can reuse the CheckCells utility type to check if a column is won.

type CheckColumn<
  Board extends TicTactToeBoard,
  Column extends number
> = CheckCells<[Board[0][Column], Board[1][Column], Board[2][Column]]>;

Check all columns

It's the same as rows now :

type CheckColumns<
  Board extends TicTactToeBoard,
  $iter extends number = 0 | 1 | 2
> = $iter extends number
  ? CheckColumn<Board, $iter> extends infer Chip extends TicTacToeChip
    ? Chip
    : never
  : never;

Step 3: Check if a diagonal is won

Enabler

We can reuse the CheckCells utility type to check if a diagonal is won.
But first we create a Map to get the diagonal cells from the board.

type DiagonalMap = [
  [[0, 0], [1, 1], [2, 2]], 
  [[0, 2], [1, 1], [2, 0]]
];

Check one diagonal

Now we can use the DiagonalMap to get the diagonal cells from the board and check if the diagonal is won.

type CheckDiagonal<
  Board extends TicTactToeBoard,
  N extends number
> = CheckCells<
  [
    Board[DiagonalMap[N][0][0]][DiagonalMap[N][0][1]],
    Board[DiagonalMap[N][1][0]][DiagonalMap[N][1][1]],
    Board[DiagonalMap[N][2][0]][DiagonalMap[N][2][1]]
  ]
>;

Check all diagonals

It's the same as rows and columns now :

type CheckDiagonals<
  Board extends TicTactToeBoard,
  $iter extends number = 0 | 1
> = $iter extends number
  ? CheckDiagonal<Board, $iter> extends infer Chip extends TicTacToeChip
    ? Chip
    : never
  : never;

Step 4: Check if the game is won

We can combine the previous checks to check if the game is won by using all the checks in a union.

type Winner<Board extends TicTactToeBoard> = CheckRows<Board> | CheckColumns<Board> | CheckDiagonals<Board>;

Step 5: Check if the game is a draw

checking if the game is a draw is simple, we just check if the board is full. And it's full if there is no empty cell.

type CheckFilled<Board extends TicTactToeBoard> =
  '  ' extends Board[number][number] ? false : true;

Implementing the TicTacToe Utility type

Step 1: Next game state

Now that we have all the utilities to check if the game is won or a draw, we can implement a GameNextState utility type, so that after a move we can check if the game is won or a draw.

type NextGameState<
  Board extends TicTactToeBoard,
  State extends TicTacToeState,
  $winner = Winner<Board>
> = [$winner] extends [never]
  ? CheckFilled<Board> extends false
    ? State extends '❌'
      ? '⭕'
      : '❌'
    : 'Draw'
  : `${$winner & string} Won`;

Step 2: Implement the TicTacToe Utility type

Now that we have all the utilities to place a chip on the board and check if the game is won or a draw, we can implement the TicTacToe utility type.

Notice 1 that we use PositionMap[Position] to get the row and column index from the position.
Notice 2 that we use PlaceChip to place the chip on the board.
Notice 3 that we use NextGameState to get the next game state.

And we use $ default variables to simplify the logic.

type TicTacToe<
  Game extends TicTacToeGame,
  Position extends TicTacToePositions,
  $Position extends [string, string] = PositionMap[Position],
  $nextBoard extends TicTactToeBoard = PlaceChip<
    Game['board'],
    $Position,
    Game['state']
  >
> = {
  board: $nextBoard;
  state: $nextBoard extends Game['board']
    ? Game['state']
    : NextGameState<$nextBoard, Game['state']>;
};

Conclusion

We have seen how to create a Tic Tac Toe game in typescript type system.
We have seen how to use Object Mapping to iterate over Tuples.
We have seen how to use Distributive Conditional Types to iterate over a range of numbers.
We have seen how to use Extract to cast a type.
We have seen how to use $ default variables to simplify the logic.

You can check the full solution on TS Playground.

Hope you enjoyed this challenge, see you next time.