Advent of typescript 2023 day 22 : Reindeer Sudoku
Tags: typescript, adventofcode, adventoftypescript
Published: 2023-12-22 14:12:26

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](https://typehero.dev/challenge/day-22).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pq902o89cv8vbt78msxi.png)

## 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.

```ts
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:

```ts
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:

```ts
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:
 
```ts
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:

```ts
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:

```ts
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.

```ts
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:

```ts
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.

```ts
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.

```ts
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.

```ts
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.

```ts
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.

```ts
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.

```ts
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](https://tsplay.dev/NDJg1W)

Hope you enjoyed this challenge, see you tomorrow for the next one.