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.
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
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.
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.
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.
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.
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:
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.
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:
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 :
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.
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.
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
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.
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.
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.
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.
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
This was a fun challenge. I hope you enjoyed it as much as i did.
We will continue with the next challenge tomorrow.
Top comments (1)
Haha, I wasn't prepared for this, I thought it's going to be coded in typescript, but I didn't expect this to be actually solved in types rather than the code 😅 Incredible what you can do with typescript 👍