DEV Community

Cover image for Advent of typescript 2023 day 22 : Reindeer Sudoku
ecyrbe
ecyrbe

Posted on

Advent of typescript 2023 day 22 : Reindeer Sudoku

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.

Image description

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;
Enter fullscreen mode Exit fullscreen mode

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 = [
  [['πŸ’¨', 'πŸ’ƒ', '🦌'], ['β˜„οΈ', '❀️', '🌩️'], ['🌟', '⚑', 'πŸ”΄']],
  [['🌟', '⚑', 'πŸ”΄'], ['πŸ’¨', 'πŸ’ƒ', '🦌'], ['β˜„οΈ', '❀️', '🌩️']],
  [['β˜„οΈ', '❀️', '🌩️'], ['🌟', '⚑', 'πŸ”΄'], ['πŸ’¨', 'πŸ’ƒ', '🦌']],
  /*------------------------------------------------------*/
  [['🦌', 'πŸ’¨', 'πŸ’ƒ'], ['⚑', 'β˜„οΈ', '❀️'], ['πŸ”΄', '🌩️', '🌟']],
  [['🌩️', 'πŸ”΄', '🌟'], ['🦌', 'πŸ’¨', 'πŸ’ƒ'], ['⚑', 'β˜„οΈ', '❀️']],
  [['⚑', 'β˜„οΈ', '❀️'], ['🌩️', 'πŸ”΄', '🌟'], ['🦌', 'πŸ’¨', 'πŸ’ƒ']],
  /*------------------------------------------------------*/
  [['πŸ’ƒ', '🦌', 'πŸ’¨'], ['❀️', '🌟', 'β˜„οΈ'], ['🌩️', 'πŸ”΄', '⚑']],
  [['πŸ”΄', '🌩️', '⚑'], ['πŸ’ƒ', '🦌', 'πŸ’¨'], ['❀️', '🌟', 'β˜„οΈ']],
  [['❀️', '🌟', 'β˜„οΈ'], ['πŸ”΄', '🌩️', '⚑'], ['πŸ’ƒ', '🦌', 'πŸ’¨']]
];
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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]>;
};
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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)