Hello Typescript Wizards, i hope you are having fun with the Advent of Typescript 2023.
This is the second article in the series of blog posts explaining the solutions to the challenges for advent of typescript 2023.
Description
This challenge is about creating a special Sudoku checker in typescript type system.
For this we are given some simple types to describe a game of Reindeer Sudoku.
type Dasher = '💨';
type Dancer = '💃';
type Prancer = '🦌';
type Vixen = '🌟';
type Comet = '☄️';
type Cupid = '❤️';
type Donner = '🌩️';
type Blitzen = '⚡';
type Rudolph = '🔴';
type Reindeer = Dasher| Dancer| Prancer| Vixen| Comet| Cupid| Donner| Blitzen| Rudolph;
The challenge
The challenge is to create one utility type that checks if a given Sudoku board is valid.
The utility type should take a Sudoku board and return a boolean indicating if the board is valid.
A valid board is a board where each row, column and 3x3 square contains all 9 reindeers.
Here is an example of a valid Sudoku board:
type SudoKu = [
[['💨', '💃', '🦌'], ['☄️', '❤️', '🌩️'], ['🌟', '⚡', '🔴']],
[['🌟', '⚡', '🔴'], ['💨', '💃', '🦌'], ['☄️', '❤️', '🌩️']],
[['☄️', '❤️', '🌩️'], ['🌟', '⚡', '🔴'], ['💨', '💃', '🦌']],
/*------------------------------------------------------*/
[['🦌', '💨', '💃'], ['⚡', '☄️', '❤️'], ['🔴', '🌩️', '🌟']],
[['🌩️', '🔴', '🌟'], ['🦌', '💨', '💃'], ['⚡', '☄️', '❤️']],
[['⚡', '☄️', '❤️'], ['🌩️', '🔴', '🌟'], ['🦌', '💨', '💃']],
/*------------------------------------------------------*/
[['💃', '🦌', '💨'], ['❤️', '🌟', '☄️'], ['🌩️', '🔴', '⚡']],
[['🔴', '🌩️', '⚡'], ['💃', '🦌', '💨'], ['❤️', '🌟', '☄️']],
[['❤️', '🌟', '☄️'], ['🔴', '🌩️', '⚡'], ['💃', '🦌', '💨']]
];
Solution
Here we will follow a step by step approach to solve this challenge.
Step 1: Enabler, flatten the board
The first step is to create a utility type that flattens the board.
Indeed, we will need to check each column and it's easier to do it with a flat array.
Flatten a matrix into a tuple
Here is a utility type that flattens a matrix into a tuple, doing it recursively:
type Flatten<T extends any[][], $acc extends any[] = []> = T extends [
infer Head extends any[],
...infer Tail extends any[][]
]
? Flatten<Tail, [...$acc, ...Head]>
: $acc;
Flatten a Sudoku board
To flatten a Sudoku board, we just need to flatten each row of the board.
For this we use a mapped type:
type FlattenSudoku<Sudoku extends Reindeer[][][]> = {
[Row in keyof Sudoku]: Flatten<Sudoku[Row]>;
};
Step 2: Check if a row is valid
Now that we have a flat array, we can check if a row is valid.
For this we need to check if the row contains all the reindeers.
Get a row as a union
To check if a row is valid, we need to get the row. This is done with a simple indexed type:
type GetRow<Sudoku extends Reindeer[][], Row extends number> = Sudoku[Row][number];
Check one row
Now we just need to transform the row into a union of all the cells and checking if the union contains all the reindeers.
type CheckRow<
Sudoku extends Reindeer[][],
Row extends number,
$Items = GetRow<Sudoku, Row> // Union of all the cells
> = Reindeer extends $Items ? true : false;
Step 3: Check if a column is valid
Get a column as a union
To check if a column is valid, we need to get the column. We can do that with a mapped type:
type GetColumn<Sudoku extends Reindeer[][], Column extends number> = {
[Row in keyof Sudoku]: Sudoku[Row][Column];
}[number];
Check one column
Now we just need to transform the column into a union of all the cells and checking if the union contains all the reindeers.
type CheckColumn<
Sudoku extends Reindeer[][],
Column extends number,
$Items = GetColumn<Sudoku, Column> // Union of all the cells
> = Reindeer extends $Items ? true : false;
Step 4: Check if a 3x3 square is valid
Map of 3x3 squares
Checking if a 3x3 square is valid is a bit more complicated.
We need to get the 3x3 square from the board and check if it contains all the reindeers.
For that we need a map of all the 3x3 squares.
type MapBox<N extends number> = [
[[0, 0], [1, 0], [2, 0]],
[[3, 0], [4, 0], [5, 0]],
[[6, 0], [7, 0], [8, 0]],
[[0, 1], [1, 1], [2, 1]],
[[3, 1], [4, 1], [5, 1]],
[[6, 1], [7, 1], [8, 1]],
[[0, 2], [1, 2], [2, 2]],
[[3, 2], [4, 2], [5, 2]],
[[6, 2], [7, 2], [8, 2]]
][N];
Get one 3x3 square as a union
Now we can use the MapBox to get the 3x3 square cells from the board and check if the 3x3 square is valid.
type GetBox<
Sudoku extends Reindeer[][][],
N extends number,
$Map extends number[][] = MapBox<N>
> =
| Sudoku[$Map[0][0]][$Map[0][1]][number]
| Sudoku[$Map[1][0]][$Map[1][1]][number]
| Sudoku[$Map[2][0]][$Map[2][1]][number];
Check one 3x3 square
type CheckBox<
Sudoku extends Reindeer[][][],
N extends number,
$Items = GetBox<Sudoku, N>
> = Reindeer extends $Items ? true : false;
Step 5: Check if the board is valid
Now that we have all the utilities to check if a row, column or 3x3 square is valid, we can check if the board is valid.
Helper to convert a number literal to a number
We need a helper to convert a number literal to a number. That is to check all the rows, columns and 3x3 squares.
type ToInt<T> = T extends `${infer N extends number}` ? N : never;
Check all rows
We use a trick to check all the rows at once using Distributive Conditional Types.
type CheckRows<
Sudoku extends Reindeer[][],
$Iter extends number = ToInt<keyof Sudoku> // Distributive Conditional Types
> = $Iter extends infer N extends number ? CheckRow<Sudoku, N> : false;
Check all columns
type CheckColumns<
Sudoku extends Reindeer[][],
$Iter extends number = ToInt<keyof Sudoku>
> = $Iter extends infer N extends number ? CheckColumn<Sudoku, N> : false;
Check all 3x3 squares
type CheckBoxes<
Sudoku extends Reindeer[][][],
$Iter extends number = ToInt<keyof Sudoku>
> = $Iter extends infer N extends number ? CheckBox<Sudoku, N> : false;
Check the board
type Validate<
Sudoku extends Reindeer[][][],
$flattenSudoku extends Reindeer[][] = FlattenSudoku<Sudoku>
> = CheckRows<$flattenSudoku> extends true
? CheckColumns<$flattenSudoku> extends true
? CheckBoxes<Sudoku> extends true
? true
: false
: false
: false;
Conclusion
We have created a utility type that checks if a given Sudoku board is valid.
This is a very complex type, but it's possible to do it in typescript.
You can find the full solution on Typescript Playground
Hope you enjoyed this challenge, see you tomorrow for the next one.
SOCIAL SHARE CARD GENERATOR