Type Gymnastic - Part 8

Posted on:October 15, 2023 at 01:00 PM

This is part 8 of the series “Type Gymnastic”. If you haven’t already, go check out part 7. Let’s continue with more challenges today!

Table of contents

Open Table of contents

Intro

In this series of type challenges we do a walk through of all challenges that I used in my advent calender. We will continue from where we left off - challenge 21.

Basic maths 🤸

The next challenges can be difficult and are usually not just one or two lines of code, but hopefully this breakdown and explanation will be helpful.

Challenge 21

You are given the type

type Sum<A, B> = any;

and you want to construct a type which takes two (positive) numbers and returns the sum of the numbers. An example would be:

type A0 = Sum<1, 2>; // A0 = 3;
type A1 = Sum<11, 0>; // A1 = 11

Doing arithmetics with Typescript might seem a bit weird, but if you read the previous post I believe you can see how this can be solved. The main trick for these arithmetic challenges is to create arrays with a length based on the generics. Let’s create a helper type to create arrays:

type Enumerate<T extends number, Acc extends number[] = []> = Acc extends {
  length: infer L;
}
  ? T extends L
    ? Acc
    : Enumerate<T, [...Acc, 1]>
  : never;

This helper method will create a number array with the length of T:

type A0 = Enumerate<3>; // A0 = [1,1,1]

In this challenge we will have two different arrays, so we can concatinate them and then figure out the length of the concatinated array. Let’s create another helper type to concat two arrays and return the length of the array:

type ConcatLength<T extends any[], D extends any[]> = [...T, ...D]["length"];

Combining these two helpers type with the original Sum type we will get:

type Enumerate<T extends number, Acc extends number[] = []> = Acc extends {
  length: infer L;
}
  ? T extends L
    ? Acc
    : Enumerate<T, [...Acc, 1]>
  : never;
type ConcatLength<T extends any[], D extends any[]> = [...T, ...D]["length"];

type Sum<A extends number, B extends number> = ConcatLength<
  Enumerate<A>,
  Enumerate<B>
>;

Which is the solution to this challenge!

Challenge 22

You are given the type

type RotateMatrix = any;

And you want to construct a type that accepts a generic 2D matrix and rotate it. Some examples would be:

type Matrix1 = [[1, 2], [3, 4]];

type Result1 = RotateMatrix<Matrix1>;
//Result1 = [ [1,3], [2,4] ]

type Matrix2 = [[1, 2, 3], [4, 5, 6]];

type Result2 = RotateMatrix<Matrix2>;
// Result2 = [ [1,4], [2,5], [3,6]]

This takes challenge 11 to the next level. Let’s recap, because we will need that type to help us solve this challenge.

We have this type:

type MatrixColumn<T, I> = {
  [P in keyof T]: I extends keyof T[P]
    ? T[P][I] extends undefined
      ? never
      : T[P][I]
    : never;
};

Which can be used like this:

type Matrix1 = [[1, 2], [3, 4]];
type Column = MatrixColumn<Matrix1, 0>; // Column = [1,3]

Which selects one column, but for this challenge we want to do this for the whole matrix. So what’s left is to iterate over the whole matrix and use MatrixColumn to rotate it.

If we start off the easy way; We can use MatrixColumn twice and see what happens:

type RotateMatrix<T> = [MatrixColumn<T, 0>, MatrixColumn<T, 1>];

type Matrix1 = [[1, 2], [3, 4]];

type Result1 = RotateMatrix<Matrix1>;
// Result1 = [[1,3], [2,4]]
// That works.. But of course not with every matrix

It works, but we have to make it more generic. Right now it’s only handling a specific matrix. To be able to iterate over the whole matrix we got to make the type recursive and increment the index. Let’s add another generic to our type which can store the current index:

type RotateMatrix<T, N extends number[] = []> = [
  MatrixColumn<T, N["length"]>,
  MatrixColumn<T, N["length"]>,
];

We will use an array’s length to keep track of the current index. Before making the type recursive, let’s also add a conditional type to see that the array’s length is not greater than the matrix’ column length so we don’t end up with an index out of bounds:

type RotateMatrix<
  T extends number[][],
  N extends number[] = [],
> = N["length"] extends T[0]["length"]
  ? []
  : [MatrixColumn<T, N["length"]>, MatrixColumn<T, N["length"]>];

And for the last part we will switch out the last MatrixColumn<T, N["length"]> to instead be recursive, and also increment the index:

type RotateMatrix<
  T extends number[][],
  N extends number[] = [],
> = N["length"] extends T[0]["length"]
  ? []
  : [MatrixColumn<T, N["length"]>, ...RotateMatrix<T, [...N, 1]>];

Which is the solution to this challenge!

Challenge 23

You are given the type

type InsertionSort = any;

And you want to construct a type that accepts a generic array of numbers (only consider numbers 0-9) and sort it in a descending order. An example would be:

type A0 = [4, 3, 2, 5];
type Sorted0 = InsertionSort<A0>; // Sorted0 = [2,3,4,5]

type A1 = [8, 1, 1, 2];
type Sorted1 = InsertionSort<A1>; // Sorted1 = [1,1,2,8]

You are meant to use the insertion sort algorithm to solve this. You can read more about it here

The gist of it is to start at the beginning of the array and then look at one item at a time and sort it.

I will first create several helper types and them assemble them together in order for the insertion sort to function. We need to construct some types that can manipulate arrays.

type Pop<T extends any[]> = T extends [...infer R, any] ? R : never;

type T0 = Pop<[1, 2, 3, 4]>; // T0 = [1,2,3]
type Head<T extends any[]> = T extends [infer R, ...any] ? R : never;

type T0 = Head<[1, 2, 3, 4]>; // T0 = 1
type Tail<T extends any[]> = T extends [any, ...infer R] ? R : never;

type T0 = Tail<[1, 2, 3, 4]>; //T0 = [2,3,4]
type Unshift<T extends any[], N extends any> = [N, ...T];

type T0 = Unshift<[1, 2, 3, 4], 9>; // T0 = [9,1,2,3,4]
type Enumerate<N extends number, Acc extends number[] = []> = Acc extends {
  length: infer L;
}
  ? N extends L
    ? Acc
    : Enumerate<N, [...Acc, 1]>
  : never;

type T0 = Enumerate<3>; // T0 = [1,1,1]

That’s quite a lot of types… and there is more! When sorting the numbers, we need some way to compare them in order to see which one is greater than the other. One way to do this is by creating a new array for the two numbers being compared, removing one item at a time from the two arrays and seeing which one comes down to zero first. When one of the arrays comes down to zero, we can say that this number is the lower one.

With that in mind, let’s create a new type Lte which takes two numbers as generics and figures out if N is less than M:

type Lte<N extends number, M extends number> = N extends 0
  ? true
  : M extends 0
    ? false
    : Lte<Pop<Enumerate<N>>["length"], Pop<Enumerate<M>>["length"]>;

Here we are saying if N is zero, then that number will be considered the lower one and return true. If N is not 0, but M is, then M will be considered the lower number and the type will return false. If none of them are 0, we will have to create two new arrays of length M and N, but remove one item each time Lte is used.

If you were to try this in your own editor you would see that Typescript is complaining about Pop<Enumerate<N>> because “Type instantiation is excessively deep and possibly infinite.”. Typescript has its limitations, and inside the internals of Typescript you will find that there has been set a finite number of recursive type instantiations. If our type exceeds that limit, we will receive the said error. Let’s refactor the Enumerate type and try to bring the possible instantiiations down:

type Enumerate<N extends number, Acc extends 1[] = []> = Acc["length"] extends N
  ? Acc
  : Enumerate<N, [...Acc, 1]>;

Exact same functionality, and hopefully less recursive instantiations and no complaints from the Typescript compiler! Let’s continue with the refactoring and extract the Pop<Enumerate<N>>["length"] into its own type and call it SubtractOne:

type SubtractOne<T extends number> =
  Pop<Enumerate<T>> extends {
    length: infer R;
  }
    ? R
    : never;

type Lte<N extends number, M extends number> = N extends 0
  ? true
  : M extends 0
    ? false
    : Lte<SubtractOne<N> & number, SubtractOne<M> & number>;

// The Typescript compiler is not sure what type SubtractOne returns so let's just cast it to be a number type

Let’s summarize the types so far:

type Pop<T extends any[]> = T extends [...infer R, any] ? R : never;

type Head<T extends any[]> = T extends [infer R, ...any] ? R : never;

type Tail<T extends any[]> = T extends [any, ...infer R] ? R : never;

type Unshift<T extends any[], N extends any> = [N, ...T];

type Enumerate<N extends number, Acc extends 1[] = []> = Acc["length"] extends N
  ? Acc
  : Enumerate<N, [...Acc, 1]>;

type SubtractOne<T extends number> =
  Pop<Enumerate<T>> extends {
    length: infer R;
  }
    ? R
    : never;

type Lte<N extends number, M extends number> = N extends 0
  ? true
  : M extends 0
    ? false
    : Lte<SubtractOne<N> & number, SubtractOne<M> & number>;

Let’s continue with creating a type for inserting into an already sorted array: If the array is empty we insert the element into a new array, if the item is less than the first item in the array we insert the new item at index 0, if it’s greater than the first item we recursively use the type and go through the next items in the array:

type InsertArray<N extends number, Arr extends any[]> = Arr extends []
  ? [N]
  : Lte<N, Head<Arr> & number> extends true
    ? Unshift<Arr, N>
    : [Head<Arr>, ...InsertArray<N, Tail<Arr>>];

We now have all the tools to actually finish this challenge. Let’s construct the InsertionSort type.

type InsertionSort<T extends number[], Acc extends number[] = []> = T extends []
  ? Acc
  : InsertionSort<Tail<T>, InsertArray<Head<T>, Acc>>;

We have some unknown types that the Typescript compiler will complain about, let’s fix them and summarize all the types being used:

type Pop<T extends any[]> = T extends [...infer R, infer _] ? R : never;
type Head<T extends any[]> = T extends [infer R, ...infer _] ? R : never;
type Tail<T extends number[]> = T extends [infer _, ...infer R] ? R : never;
type Unshift<T extends any[], N extends any> = [N, ...T];

type Cast<T0, T1> = T0 extends T1 ? T0 : never; // New type instead of using i.e. '& number' to cast

type Enumerate<N extends number, Acc extends 1[] = []> = Acc["length"] extends N
  ? Acc
  : Enumerate<N, [...Acc, 1]>;
type SubtractOne<T extends number> =
  Pop<Enumerate<T>> extends {
    length: infer R;
  }
    ? R
    : never;

type Lte<N extends number, M extends number> = N extends 0
  ? true
  : M extends 0
    ? false
    : Lte<Cast<SubtractOne<N>, number>, Cast<SubtractOne<M>, number>>;

type InsertArray<N extends number, Arr extends any[]> = Arr extends []
  ? [N]
  : Lte<N, Cast<Head<Arr>, number>> extends true
    ? Unshift<Arr, N>
    : [Head<Arr>, ...InsertArray<N, Tail<Arr>>];
type InsertionSort<T extends number[], Acc extends number[] = []> = T extends []
  ? Acc
  : InsertionSort<
      Cast<Tail<T>, number[]>,
      InsertArray<Cast<Head<T>, number>, Acc>
    >;

Which is the solution to this challenge! Last part, and last challenge coming soon. Part 9