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.
Top comments (2)
day 22
There's a post about it here:
dev.to/ecyrbe/advent-of-typescript...