Advent of typescript 2023 day 23 : Connect 4
Tags: typescript, adventofcode, adventoftypescript
Published: 2023-12-23 15:56:55

Hello Typescript Wizards, i hope you are having fun with the Advent of Typescript 2023.
This is the third article in the series of blog posts explaining the solutions to the challenges
for [advent of typescript 2023](https://typehero.dev/challenge/day-23).


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b9ewp8h3zo82h29dvbwd.png)

## The challenge

Playing the game is done by calling the `Connect4` Utility type with the current game state and the next row position for the chip color of the current player.
The utility type will return the next game board and state.

**Example**
```ts
  Expect<
    Equal<
      Connect4<NewGame, 0>,
      {
        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: Find the first empty row in a column

To place a chip on the board we first need to find the first empty row in the column.
Then we can replace the empty cell with the chip color of the current player.

```ts
type FindEmptyRow<
  board extends Connect4Cell[][],
  column extends number
> = board extends [
  ...infer rows extends Connect4Cell[][],
  infer row extends Connect4Cell[]
]
  ? row[column] extends '  '
    ? rows['length']
    : FindEmptyRow<rows, column>
  : never;
```
### Step 2: Replace a cell in a matrix

This is much like the `Tic-Tact-Toe` challenge where we had to replace a cell in a matrix.

```ts
type ArrayReplaceAt<Array extends any[], X extends number, value> = {
  [key in keyof Array]: key extends `${X}` ? value : Array[key];
};

type MatrixReplaceAt<
  Matrix extends any[][],
  Position extends [number, number],
  value
> = {
  [key in keyof Matrix]: key extends `${Position[1]}`
    ? ArrayReplaceAt<Matrix[key], Position[0], value>
    : Matrix[key];
};
```

### Step 3: Place a chip on the board

We can now place a chip on the board by combining the previous steps.
**Notice 1:** We use `chip extends Connect4Chips` to check that the chip is not a win or a draw.
**Notice 2:** We use `Extract` to cast the result to `Connect4Cell[][]` since typescript has a hard time to infer the type.

```ts
type PlaceChip<
  board extends Connect4Cell[][],
  column extends number,
  chip extends Connect4State
> = chip extends Connect4Chips
  ? FindEmptyRow<board, column> extends infer row extends number
    ? Extract<MatrixReplaceAt<board, [column, row], chip>, Connect4Cell[][]>
    : board
  : 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.
This is a lot like the previous days challenges.

We will first create small utility types to get a row, column or diagonal from the board.
Then we will check if there is a winner in the rows, columns or diagonals.

### Step 1: Enabler

The first step is to create a common type to check if a tuple contains 4 same chips in a row.
For that we use recusion and accumulate the chips in a tuple until we have 4 chips.
If we switch to a different chip, we reset the accumulator.

```ts
type Check4<
  Board extends Connect4Cell[],
  $acc extends Connect4Chips[] = []
> = $acc['length'] extends 4
  ? $acc[0]
  : Board extends [infer head, ...infer tail extends Connect4Cell[]]
  ? head extends Connect4Chips
    ? [$acc[0]] extends [head]
      ? Check4<tail, [...$acc, head]> // continue accumulating the same chips
      : Check4<tail, [head]> // reset accumulator to the new chip
    : Check4<tail> // reset accumulator
  : never;
```

### Step 2: Check if rows are won

#### Get a row as a tuple

To check if a row is won, we need to get the row. This is done with a simple indexed type:

```ts
type GetRow<
  Board extends Connect4Cell[][],
  Row extends number
> = Board[Row];
```

#### Find winner in rows

Now that we can get a row, we can check if all the rows are won by iterating with the `Check4` type over the rows.
For that we use Distributive conditional types.

```ts
type WinnerInRows<
  Board extends Connect4Cell[][],
  $rows = ToInt<keyof Board>
> = $rows extends number ? Check4<GetRow<Board, $rows>> : never;
```
### Step 3: Check if columns are won

#### Get a column as a tuple

To check if a column is won, we need to get the column. This is done by using a Mapped type:

```ts
type GetColumn<Board extends Connect4Cell[][], column extends number> = {
  [key in keyof Board]: Board[key][column];
};
```

#### Find winner in columns

It's the same as rows now :

```ts
type WinnerInColumns<
  Board extends Connect4Cell[][],
  $columns = ToInt<keyof Board[0]>
> = $columns extends number ? Check4<GetColumn<Board, $columns>> : never;
```

### Step 4: Check if diagonals are won

This is a lot like the previous days challenges. We will create a Map to get the diagonal cells from the board.
Then we will check if there is a winner in the diagonals.

#### Map of diagonals

We can see that we have 12 diagonals in the board. We can create a map of all the diagonals.

```ts
type DiagonalMap = [
  [[0, 3], [1, 2], [2, 1], [3, 0]],
  [[0, 4], [1, 3], [2, 2], [3, 1], [4, 0]],
  [[0, 5], [1, 4], [2, 3], [3, 2], [4, 1], [5, 0]],
  [[0, 6], [1, 5], [2, 4], [3, 3], [4, 2], [5, 1]],
  [[1, 6], [2, 5], [3, 4], [4, 3], [5, 2]],
  [[2, 6], [3, 5], [4, 4], [5, 3]],
  [[2, 0], [3, 1], [4, 2], [5, 3]],
  [[1, 0], [2, 1], [3, 2], [4, 3], [5, 4]],
  [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5]],
  [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]],
  [[0, 2], [1, 3], [2, 4], [3, 5], [4, 6]],
  [[0, 3], [1, 4], [2, 5], [3, 6]]
];
```

#### Get a diagonal as a tuple

This a now a lot like the previous days challenges. We will use the map to get the diagonal cells from the board.

```ts
type GetDiagonal<
  Board extends Connect4Cell[][],
  N extends number,
  $map extends [number, number][] = DiagonalMap[N]
> = Extract<
  {
    [key in keyof $map]: Board[$map[key][0]][$map[key][1]];
  },
  Connect4Cell[] // cast
>;
```

#### Find winner in diagonals

This is straight forward now, same as rows and columns

```ts
type WinnerInDiagonals<
  Board extends Connect4Cell[][],
  $diags = ToInt<keyof DiagonalMap>
> = $diags extends number ? Check4<GetDiagonal<Board, $diags>> : never;
```

### Step 5: Check if the game is won

We can now check if the game is won by combining the previous steps.

```ts
type Winner<Board extends Connect4Cell[][]> =
  | WinnerInRows<Board>
  | WinnerInColumns<Board>
  | WinnerInDiagonals<Board>;
```

## Solution to check if the game is a draw

To check if the game is a draw, we need to check if there is an empty cell in the board.
That's it.

```ts
type CheckDraw<Board extends Connect4Cell[][]> =
  '  ' extends Board[number][number] ? false : true;
```

## Implementing the Connect4 Utility type

### Step 1: Next game state

Now that we have all the utilities to check if there is a winner or a draw, we can check the next game state.

```ts
type NextGameState<
  Board extends Connect4Cell[][],
  State extends Connect4State,
  $winner extends Connect4Chips = Winner<Board>
> = [$winner] extends [never]
  ? CheckDraw<Board> extends false
    ? State extends '🔴'
      ? '🟡'
      : '🔴'
    : 'Draw'
  : `${$winner} Won`;
```

### Step 2: Implement the Connect4 Utility type

Now that we have can place a chip on the board and get the next game state, we can implement the Connect4 Utility type.

```ts
type Connect4<
  Game extends { board: Connect4Cell[][]; state: Connect4State },
  Column extends number,
  $NewBoard extends Connect4Cell[][] = PlaceChip<
    Game['board'],
    Column,
    Game['state']
  >,
  $NewState = NextGameState<$NewBoard, Game['state']>
> = {
  board: $NewBoard;
  state: $NewState;
};
```

## Conclusion

We used the same approach as the previous days challenges. 
One thing to remember, don't hesitate to build Map types to simplify your code.
Take advantage of Distributive conditional types to iterate over a tuple.

You can find the full solution on [Ts Playground](https://tsplay.dev/Wozbjm)

This was a fun challenge. I hope you enjoyed it as much as i did.
We will continue with the next challenge tomorrow.