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
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]>;
};
Check duplicate reindeers
We need to check if a row, column or 3x3 square contains all the reindeers.
We can handle all the cases with a simple utility type:
type CheckDuplicates<Cells extends Reindeer> = Reindeer extends Cells
? true
: false;
Step 2: Check if rows are 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 rows
Now we just need to use the CheckDuplicates utility type to check if the row contains all the reindeers.
And we use Distributive Conditional Types to check all the rows at once.
type CheckRows<
Sudoku extends Reindeer[][],
$Iter extends number = ToInt<keyof Sudoku>,
> = $Iter extends number ? CheckDuplicates<GetRow<Sudoku, $Iter>> : false;
Step 3: Check if columns are valid
Get a column as a union
To check if a column is valid, we need to get the column. We simply use indexed types again:
type GetColumn<
Sudoku extends Reindeer[][],
Column extends number
> = Sudoku[number][Column];
Check columns
Same logic as rows, we use Distributive Conditional Types to check all the columns at once.
type CheckColumns<
Sudoku extends Reindeer[][],
$Iter extends number = ToInt<keyof Sudoku>
> = $Iter extends number ? CheckDuplicates<GetColumn<Sudoku, $Iter>> : false;
Step 4: Check if 3x3 squares are 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.
Again we use indexed types with the Map to get the 3x3 square.
type GetBox<
Sudoku extends Reindeer[][][],
N extends number,
$Map extends number[][] = MapBox<N>
> = Sudoku[$Map[number][0]][$Map[number][1]][number];
Check 3x3 squares
Same logic as rows and columns, we use Distributive Conditional Types to check all the 3x3 squares at once.
type CheckBoxes<
Sudoku extends Reindeer[][][],
$Iter extends number = ToInt<keyof Sudoku>
> = $Iter extends number ? CheckDuplicates<GetBox<Sudoku, $Iter>> : 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 the board
One thing to note here, if the board is valid, all tests return true else it returns true|false, so we just need to check for truthyness of all cases.
type Validate<
Sudoku extends Reindeer[][][],
$flattenSudoku extends Reindeer[][] = FlattenSudoku<Sudoku>
> =
| CheckRows<$flattenSudoku>
| CheckColumns<$flattenSudoku>
| CheckBoxes<Sudoku> extends true
? true
: false;
Conclusion
We have created a utility type that checks if a given Sudoku board is valid.
You can find the full solution on Typescript Playground
Hope you enjoyed this challenge, see you tomorrow for the next one.
Top comments (0)