Advent of TypeScript 2023 - Part. III

Advent of TypeScript 2023 is a series of challenges related to type-level TypeScript.

This page provides walkthroughs for days 21 to 25.

You can find the solutions & tests at https://github.com/erhant/aot-2023

Day 21. Tic-Tac-Toe

In this challenge, we are asked to implement a Tic-Tac-Toe "state transition function" so to say, where we are given the current state of the game along with a position such that the current move will be played on that position.

Let us ask ourselves, what type of functions do we need?

• We need to translate a position (e.g. top-left) to indices on the 2D board.
• We need to get the value at a given 2D index.
• We need to set a value at a given 2D index.
• We need checker functions that can tell if a board has been won or there is a draw.

The first two are simple:

// prettier-ignore
type ToIndex = {
  top: 0; middle: 1; bottom: 2;
  left: 0; center: 1; right: 2;
};

// prettier-ignore
type Retrieve<T extends TicTacToeBoard, P extends TicTacToePositions> =
  P extends `${infer L extends TicTacToeYPositions}-${infer R extends TicTacToeXPositions}` 
  ? T[ToIndex[L]][ToIndex[R]]
  : never;

Setting a value at an index is a bit more work, but due to the small problem-size at hand we can hard-code it as such:

// prettier-ignore
type Put<T extends TicTactToeBoard, P extends TicTacToePositions, V extends TicTacToeCell> =
  // top
  P extends 'top-left' ?      [[V, T[0][1], T[0][2]], T[1], T[2]] : 
  P extends 'top-center' ?    [[T[0][0], V, T[0][2]], T[1], T[2]] : 
  P extends 'top-right' ?     [[T[0][0], T[0][1], V], T[1], T[2]] : 
  // middle
  P extends 'middle-left' ?   [T[0], [V, T[1][1], T[1][2]], T[2]] : 
  P extends 'middle-center' ? [T[0], [T[1][0], V, T[1][2]], T[2]] : 
  P extends 'middle-right' ?  [T[0], [T[1][0], T[1][1], V], T[2]] : 
  // bottom
  P extends 'bottom-left' ?   [T[0], T[1], [V, T[2][1], T[2][2]]] :
  P extends 'bottom-center' ? [T[0], T[1], [T[2][0], V, T[2][2]]] :
  P extends 'bottom-right' ?  [T[0], T[1], [T[2][0], T[2][1], V]] :
  never;

I found this to be more readable as well; of course, there is probably a way to do this in a more concise and generic way (which we will actually implement at a later challenge).

Winning conditions can be checked via hardcoding as well:

// prettier-ignore
type IsWinning<B extends TicTactToeBoard, C extends TicTacToeChip, CCC = [C, C, C]> = 
  [B[0][0], B[0][1], B[0][2]] extends CCC ? true : // top row
  [B[1][0], B[1][1], B[1][2]] extends CCC ? true : // middle row
  [B[2][0], B[2][1], B[2][2]] extends CCC ? true : // bottom row
  [B[0][0], B[1][0], B[2][0]] extends CCC ? true : // left col
  [B[0][1], B[1][1], B[2][1]] extends CCC ? true : // center col
  [B[0][2], B[1][2], B[2][2]] extends CCC ? true : // right col
  [B[0][0], B[1][1], B[2][2]] extends CCC ? true : // top-left bottom-right diag
  [B[0][2], B[1][1], B[2][0]] extends CCC ? true : // top-right bottom-left diag
  false;

For the drawing condition, I simply decided to spread the board into a 1D array and check if any cell includes the empty cell. If we are not winning, and with our move there are no empty cells left, then it is a draw.

// prettier-ignore
type IsDraw<B extends any[]> = 
  B extends [infer First, ...infer Rest]
  ? First extends TicTacToeEmptyCell
    ? false
    : IsDraw<Rest>
  : true

Our state transition is then defined like so:

// prettier-ignore
type NextState<B extends TicTacToeBoard, C extends TicTacToeChip> =
  IsWinning<B, C> extends true 
  ? {
    board: B,
    state: `${C} Won`
  }
  : IsDraw<[...B[0], ...B[1], ...B[2]]> extends true
  ? {
    board: B,
    state: 'Draw'
  }
  : {
    board: B,
    state: {
      "❌": "⭕";
      "⭕": "❌";
    }[C]
  }

For the solution, we must also take care of the case when a move is invalid, i.e. the cell to be played is not empty. With that said, here is the solution:

// prettier-ignore
type TicTacToe<T extends TicTacToeGame, P extends TicTacToePositions> = 
  Retrieve<T['board'], P> extends TicTacToeEmptyCell
  ? T['state'] extends TicTacToeChip 
    ? NextState<Put<T['board'], P, T['state']>, T['state']>
    : never // cant play a non-chip state
  : T; // invalid play does not change the state

Day 22. Sudoku

Here, we are asked to verify a given Sudoku solution, at type-level! For this, we need only one utility: a type that returns true if all its values are unique, and false otherwise.

Typehero actually has a challenge just like this: Unique. In that challenge, we return the unique values from a given array. To return a boolean whether an array is unique or not, we can retrieve the unique values in there and compare the lengths!

// prettier-ignore
type CheckAnyExtends<T, Arr extends any[]> = 
  Arr extends [infer First, ...infer Rest]
  ? T extends First
    ? true
    : CheckAnyExtends<T, Rest>
  : false;

// prettier-ignore
type Unique<T extends any[], Result extends any[] = []> = 
  T extends [infer First, ...infer Rest]
  ? CheckAnyExtends<First, Result> extends true
    ? Unique<Rest, Result>
    : Unique<Rest, [...Result, First]>
  : Result;

// prettier-ignore
type IsUnique<T extends any[]> = 
  T["length"] extends Unique<T>["length"] ? true : false;

With this in our hands, we can hardcode the Sudoku verifier as such:

// prettier-ignore
type Validate<T extends Reindeer[][][]> = 
    // check rows 
    IsUnique<[...T[0][0], ...T[0][1], ...T[0][2]]> extends false ? false :
    IsUnique<[...T[1][0], ...T[1][1], ...T[1][2]]> extends false ? false :
    IsUnique<[...T[2][0], ...T[2][1], ...T[2][2]]> extends false ? false :
    IsUnique<[...T[3][0], ...T[3][1], ...T[3][2]]> extends false ? false :
    IsUnique<[...T[4][0], ...T[4][1], ...T[4][2]]> extends false ? false :
    IsUnique<[...T[5][0], ...T[5][1], ...T[5][2]]> extends false ? false :
    IsUnique<[...T[6][0], ...T[6][1], ...T[6][2]]> extends false ? false :
    IsUnique<[...T[7][0], ...T[7][1], ...T[7][2]]> extends false ? false :
    IsUnique<[...T[8][0], ...T[8][1], ...T[8][2]]> extends false ? false :
    // check cols
    IsUnique<[T[0][0][0], T[1][0][0], T[2][0][0], T[3][0][0], T[4][0][0], T[5][0][0], T[6][0][0], T[7][0][0], T[8][0][0]]> extends false ? false :
    IsUnique<[T[0][0][1], T[1][0][1], T[2][0][1], T[3][0][1], T[4][0][1], T[5][0][1], T[6][0][1], T[7][0][1], T[8][0][1]]> extends false ? false :
    IsUnique<[T[0][0][2], T[1][0][2], T[2][0][2], T[3][0][2], T[4][0][2], T[5][0][2], T[6][0][2], T[7][0][2], T[8][0][2]]> extends false ? false :
    IsUnique<[T[0][1][0], T[1][1][0], T[2][1][0], T[3][1][0], T[4][1][0], T[5][1][0], T[6][1][0], T[7][1][0], T[8][1][0]]> extends false ? false :
    IsUnique<[T[0][1][1], T[1][1][1], T[2][1][1], T[3][1][1], T[4][1][1], T[5][1][1], T[6][1][1], T[7][1][1], T[8][1][1]]> extends false ? false :
    IsUnique<[T[0][1][2], T[1][1][2], T[2][1][2], T[3][1][2], T[4][1][2], T[5][1][2], T[6][1][2], T[7][1][2], T[8][1][2]]> extends false ? false :
    IsUnique<[T[0][2][0], T[1][2][0], T[2][2][0], T[3][2][0], T[4][2][0], T[5][2][0], T[6][2][0], T[7][2][0], T[8][2][0]]> extends false ? false :
    IsUnique<[T[0][2][1], T[1][2][1], T[2][2][1], T[3][2][1], T[4][2][1], T[5][2][1], T[6][2][1], T[7][2][1], T[8][2][1]]> extends false ? false :
    IsUnique<[T[0][2][2], T[1][2][2], T[2][2][2], T[3][2][2], T[4][2][2], T[5][2][2], T[6][2][2], T[7][2][2], T[8][2][2]]> extends false ? false :
    // check regions
    IsUnique<[...T[0][0], ...T[1][0], ...T[2][0]]> extends false ? false :
    IsUnique<[...T[0][1], ...T[1][1], ...T[2][1]]> extends false ? false :
    IsUnique<[...T[0][2], ...T[1][2], ...T[2][2]]> extends false ? false :
    IsUnique<[...T[3][0], ...T[4][0], ...T[5][0]]> extends false ? false :
    IsUnique<[...T[3][1], ...T[4][1], ...T[5][1]]> extends false ? false :
    IsUnique<[...T[3][2], ...T[4][2], ...T[5][2]]> extends false ? false :
    IsUnique<[...T[6][0], ...T[7][0], ...T[8][0]]> extends false ? false :
    IsUnique<[...T[6][1], ...T[7][1], ...T[8][1]]> extends false ? false :
    IsUnique<[...T[6][2], ...T[7][2], ...T[8][2]]> extends false ? false
    : true;

It is possible to do this without hardcoding, I didn't do it here due to time reasons :)

Day 23. Connect4

In this challenge, we will implement the logic for Connect4. In my opinion, this was the hardest challenge among all days! Looking at the game logic, we will need the following types:

• A type to find the index (row & column) to place a given piece
• A type to put a piece at a given index
• A type to check rows for winning conditions
• A type to check columns for winning conditions
• A type to check diagonals for winning conditions
• A type to check drawing condition

Finding the Index

We should make a really nice observation here: we already know the column to place a piece under, so we don't have to check others unless we really have to! For instance, we only need to find the correct row to place a piece, without checking the other rows.

There is a catch in finding the index though, we care about the last empty cell from the top, i.e. the first empty cell from the bottom! We can use this to our advantage, and iterate the rows starting from the bottom row and simply check if the corresponding column cell is empty.

type FindIndex2D<T extends Connect4Board, P extends number, Acc extends 0[] = []> =
  // start search from last row
  T extends [...infer Rest extends any[][], infer Last extends any[]]
    ? Last[P] extends "  "
      ? Acc["length"]
      : FindIndex2D<Rest, P, [0, ...Acc]>
    : never;

This returns us the row index with the first empty cell at column P.

Putting a Piece

We will implement a Replace type that lets us put a value at a given row & column. Both of these will keep track of the rows & cells that they have went over in doing so (in an accumulator Acc). However, we will go over the rows in reverse (due to our approach on finding the index) but the column indexing will be normal.

// prettier-ignore
type Replace2D<T extends any[][], IR extends number, IC extends number, V extends any, Acc extends any[][] = []> = 
  T extends [...infer Rest extends any[][], infer Last extends any[]]
    ? Acc["length"] extends IR
        ? [...Rest, Replace1D<Last, IC, V>, ...Acc]
        : Replace2D<Rest, IR, IC, V, [Last, ...Acc]>
    : T;

// prettier-ignore
type Replace1D<T extends any[], I extends number, V extends any, Acc extends any[] = []> = 
  T extends [infer First, ...infer Rest]
    ? Acc["length"] extends I
        ? [...Acc, V, ...Rest]
        : Replace1D<Rest, I, V, [...Acc, First]>
    : T;

Checking Rows

Checking if there is a winning row is straightforward: infer 4 elements in a row and see if they are equal to the currently placed piece.

// prettier-ignore
type CheckRows<T extends any[][], V extends Connect4Chips> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? CheckWin1D<First, V> extends true
        ? true
        : CheckRows<Rest, V>
    : false;

// prettier-ignore
type CheckWin1D<T extends any[], V extends any> = 
  T extends [infer I1, infer I2, infer I3, infer I4, ...infer Rest]
    ? [I1, I2, I3, I4] extends [V, V, V, V]
        ? true
        : CheckWin1D<[I2, I3, I4, ...Rest], V>
    : false;

Checking Columns

We only need to check the current column to see if it is winning for the column case:

type CheckCols<T extends any[][], V extends Connect4Chips, P extends number> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? [R1[P], R2[P], R3[P], R4[P]] extends [V, V, V, V]
    ? true
    : CheckCols<[R2, R3, R4, ...Rest], V, P>
  : false;

Checking Diagonals

Now this one is a bit more tricky. My idea was to offset rows so that the diagonal cells are all aligned, and then these 4 rows (each offset by one more than the previous) are checked together to see if at one index they all contain the same piece.

To do this, we write a utility type called CheckQuadRow that checks if there is a winning column in 4 rows stacked together.

type CheckQuadRow<
  R1 extends any[],
  R2 extends any[],
  R3 extends any[],
  R4 extends any[],
  V extends any,
  Acc extends 0[] = [],
  i extends number = Acc["length"]
> = R1["length"] extends i
  ? false
  : [R1[i], R2[i], R3[i], R4[i]] extends [V, V, V, V]
  ? true
  : CheckQuadRow<R1, R2, R3, R4, V, [...Acc, 0]>;

Now, we can simply check diagonals from top-left to bottom-right by offsetting each row by one, and passing in the resulting offset-rows to CheckQuadRow:

type CheckDiagLeftToRight<T extends any[][], V extends Connect4Chips> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? R2 extends [any, ...infer R2Rest]
    ? R3 extends [any, any, ...infer R3Rest]
      ? R4 extends [any, any, any, ...infer R4Rest]
        ? CheckQuadRow<R1, R2Rest, R3Rest, R4Rest, V> extends true
          ? true
          : CheckDiagLeftToRight<[R2, R3, R4, ...Rest], V>
        : false
      : false
    : false
  : false;

For the other diagonal from top-right to bottom-left, we can do almost the same but from the other way around:

type CheckDiagRightToLeft<T extends any[][], V extends Connect4Chips> = T extends [
  infer R1 extends any[],
  infer R2 extends any[],
  infer R3 extends any[],
  infer R4 extends any[],
  ...infer Rest extends any[][]
]
  ? R3 extends [any, ...infer R3Rest]
    ? R2 extends [any, any, ...infer R2Rest]
      ? R1 extends [any, any, any, ...infer R1Rest]
        ? CheckQuadRow<R1Rest, R2Rest, R3Rest, R4, V> extends true
          ? true
          : CheckDiagRightToLeft<[R2, R3, R4, ...Rest], V>
        : false
      : false
    : false
  : false;

Notice how that in both cases, the cells that are irrelevant to the diagonal are ignored. For example, the topmost & rightmost cell can't be in a winning diagonal from top-left to bottom-right, so that cell is not even included during these infer statements!

Checking the Draw

We also need to check for the drawing condition, which is to simply check if there is an empty cell or not in the entire board. If we are not winning in any case described so far, and there are no empty cells left, it is a draw!

// prettier-ignore
type CheckDraw<T extends any[][]> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? HasEmpty1D<First> extends true
        ? false
        : CheckDraw<Rest>
    : true;

// prettier-ignore
type HasEmpty1D<T extends any[]> = 
  T extends [infer First, ...infer Rest]
  ? First extends Connect4Empty
    ? true
    : HasEmpty1D<Rest>
  : false

The Solution

With all of these types, we are ready for the solution. We will follow the same order as described at the start of this challenge.

type Connect4<
  T extends Connect4Game, // current game
  C extends number, // column to place
  R extends number = FindIndex2D<T["board"], C>, // row to place (calculated)
  B extends Connect4Board = Replace2D<T["board"], R, C, T["state"]> // updated board
> = CheckRows<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckCols<B, T["state"], C> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDiagLeftToRight<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDiagRightToLeft<B, T["state"]> extends true
  ? { board: B; state: `${T["state"]} Won` }
  : CheckDraw<B> extends true
  ? { board: B; state: "Draw" }
  : { board: B; state: { "🔴": "🟡"; "🟡": "🔴" }[T["state"]] };

Notice that we store the index at R and the new board at B as parameters with defaults for our type. This is a common utility trick that allows us to use that same type in many places within the type definition.

In the final step of this type, we simply update the next state with the opposite chip.

Day 24. Santa in Forest

Santa is stuck in a forest, and we are tasked with building the type that navigates him out of there! The idea of my solution is as follows:

• Find the index of Santa, and return it as follows:
  • cur is the current index (row & column) of Santa
  • left is the left of cur
  • right is the right of cur
  • up is above the cur
  • down is below the cur

For each direction, if the index is out-of-bounds for either row or column, return that index as never instead of its number. This way, we can access the current index of Santa via cur, and know where to go using the direction parameter as a key for our index.

For example, if our direction is left, we will access the left property of our index to see where it leads. If either it's row or column is never then we are out of the maze.

Finding the Santa

Lets make a type for our indices:

type FullIndexType = {
  left: [number | never, number | never];
  right: [number | never, number | never];
  cur: [number, number];
  up: [number | never, number | never];
  down: [number | never, number | never];
};

To find these indices, we will implement two types: FindSanta2D and FindSanta1D. The latter will find the Santa in a row, and the former will keep record of the row index when that happens.

type FindSanta2D<
  T extends any[][],
  Acc extends 0[] = [],
  Idx extends [up: number | never, cur: number, down: number | never, max: number] = [never, 0, 1, T["length"]]
> = T extends [infer Row extends any[], ...infer Rest extends any[][]]
  ? FindSanta1D<Row> extends never
    ? FindSanta2D<Rest, [0, ...Acc], [Idx[1], [...Acc, 0]["length"], [...Acc, 0, 0]["length"], Idx[3]]>
    : ToIndex<Idx, FindSanta1D<Row>>
  : never;

type FindSanta1D<
  T extends any[],
  Acc extends 0[] = [],
  Idx extends [left: number | never, cur: number, right: number | never, max: number] = [never, 0, 1, T["length"]]
> = T extends [infer First, ...infer Rest]
  ? First extends Santa
    ? Idx
    : FindSanta1D<Rest, [0, ...Acc], [Idx[1], [...Acc, 0]["length"], [...Acc, 0, 0]["length"], Idx[3]]>
  : never;

To convert these index tuples to the FullIndexType we implement ToIndex as follows:

type ToIndex<
  RowIdx extends [up: number | never, cur: number, down: number | never, max: number],
  ColIdx extends [left: number | never, cur: number, right: number | never, max: number]
> = {
  // row left & right
  left: [RowIdx[1], ColIdx[0]];
  right: [RowIdx[1], ColIdx[2] extends ColIdx[3] ? never : ColIdx[2]];
  // current
  cur: [RowIdx[1], ColIdx[1]];
  // column up & down
  up: [RowIdx[0], ColIdx[1]];
  down: [RowIdx[2] extends RowIdx[3] ? never : RowIdx[2], ColIdx[1]];
};

Replacing a Value

Now, let us implement the logic to replace a value in the 2D array with a value that we want. This will do two things:

• When Santa moves, it's current index will be made empty
• Its new position will be made Santa

Similar to FindSanta types, we will implement two things: Replace2D and Replace1D. The first will find the correct row, and the second will find the correct column to replace. Both of these will keep track of the rows & cells that they have went over in doing so (in an accumulator Acc) and with that, replacing a value simply becomes: [...Acc, NewValue, ...Rest]. Let's look at these types:

// prettier-ignore
type Replace2D<T extends any[][], Row extends number, Col extends number, V extends any, Acc extends any[][] = []> = 
  T extends [infer First extends any[], ...infer Rest extends any[][]]
    ? Acc["length"] extends Row
        ? [...Acc, Replace1D<First, Col, V>, ...Rest]
        : Replace2D<Rest, Row, Col, V, [...Acc, First]>
    : T;

// prettier-ignore
type Replace1D<T extends any[], Col extends number, V extends any, Acc extends any[] = []> = 
  T extends [infer First, ...infer Rest]
    ? Acc["length"] extends Col
        ? [...Acc, V, ...Rest]
        : Replace1D<Rest, Col, V, [...Acc, First]>
    : T;

This is really similar to Replace type that we have implemented for day 23, but the array iteration logic is different; instead of taking Last in each step, we take the First.

Making Cookies

Finally, we will implement the type that turns the entire maze into cookies. These types will simply keep iterating over the array and replace each value with a cookie:

// prettier-ignore
type MakeCookies2D<T extends any[][], Acc extends DELICIOUS_COOKIES[][] = []> = 
  T["length"] extends Acc["length"]
  ? Acc
  : MakeCookies2D<T, [MakeCookies1D<T[Acc["length"]]>, ...Acc]>;

// prettier-ignore
type MakeCookies1D<T extends any[], Acc extends DELICIOUS_COOKIES[] = []> =
  T["length"] extends Acc["length"]
  ? Acc
  : MakeCookies1D<T, [DELICIOUS_COOKIES, ...Acc]>;

The Solution

With all of these, the actual solution is quite concise:

// prettier-ignore
type Move<
  T extends MazeMatrix,
  D extends Directions,
  I extends FullIndexType = FindSanta2D<T>
> = I[D][0] extends never
  ? MakeCookies2D<T> // row is out-of-bounds, santa exits!
  : I[D][1] extends never
  ? MakeCookies2D<T> // col is out-of-bounds, santa exits!
  : T[I[D][0]][I[D][1]] extends Tree
  ? T // there is a tree in the way
  : Replace2D<Replace2D<T, I[D][0], I[D][1], Santa>, I["cur"][0], I["cur"][1], Alley>;

Day 25. Merry Christmas!

You know what to do!