Advent of TypeScript 2023 - Part. II

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

This page provides walkthroughs for days 11 to 20.

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

Day 11. Protect the List

Here is a chunky challenge, a DeepReadonly (which is a popular type-challenge on its own) that works on any nested object. Before we move on, let us remember the two built-ins:

• Readonly makes a type (not its children) readonly.
• ReadonlyArray makes an array readonly, kind of like using as const in normal code.

In this challenge, we will consider our types to be objects or arrays.

• If there is an object, we must make their keys readonly and their values readonly as well.
• If there is an array, we must make each element readonly.
• Otherwise, we can simply make that type readonly.

With this logic in mind, let us construct our solution:

type DeepReadonly<T> =
  // check if T is an object
  T extends Record<any, unknown>
    ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
    : // check if T is an array
    T extends Array<unknown>
    ? DeepReadonlyArray<T>
    : // otherwise, just return T
      T;

Just as we described, we can use the conditionals to see if we have an object or array, or none of them. Now, let's define DeepReadonlyArray:

// prettier-ignore
type DeepReadonlyArray<
  T extends ReadonlyArray<unknown>,
  Acc extends ReadonlyArray<unknown> = []
> = 
  T["length"] extends Acc["length"] 
  ? Acc 
  : DeepReadonlyArray<T, readonly [...Acc, DeepReadonly<T[Acc["length"]]>]>;

This is a really common method of iterating over an array and mapping its values, and we will see much more of this throughout the challenges. We start with an accumulator Acc that is initialized as []. Then, we check the length property of these arrays and see if they are equal. This condition will only be true when we have exhausted the array, at which point we return the resulting Acc.

Now, another magic here is T[Acc['length']], where we use the length of the accumulator as our index to access the elements of T. As Acc grows, we will have accessed all elements within the array T!

With these in our hand, our solution is simply forwarding the input to DeepReadonly:

type SantaListProtector<T> = DeepReadonly<T>;

Day 12. Find Santa I

In this challenge, we are asked to find the index of an element in a tuple. This is a perfect opportunity to use the spread-infer operation! In type-world, one can iterate over an array using infer in two ways:

• T extends [infer First, ...infer Rest] will return the first element in First and the rest of the array in Rest.
• T extends [...infer Rest, infer Last] will return the last element in Last and the rest of the array in Rest.

One particular advantage of using the latter is that you always know the index of Last, it is given by Rest['length'].

For this challenge, we can keep looking at Last to see if it is santa, and return Rest['length'] if that is true; otherwise, we can recurse with the Rest of the array. If this condition no longer works, then it means our array is exhausted (empty) so we can return never.

type FindSanta<T extends any[]> = T extends [...infer Rest, infer Last]
  ? Last extends "🎅🏼"
    ? Rest["length"]
    : FindSanta<Rest>
  : never;

Day 13. Count the Days

Here, we are asked to construct a union of consecutive numbers with the given limits. Although the tests only start with 1, our solution works for any limits.

Our solution will have two parts, assuming the inputs DayCounter<L, R> where both are numbers:

• GotoLeft will construct an array of length L with values [0, 1, ..., L-1] and then call GotoRight
• GotoRight will construct an array of length R, while keeping track of the values in each step.

// prettier-ignore
type GotoLeft<L extends number, R extends number, Ctr extends number[] = []> = 
    Ctr['length'] extends L 
    ? GotoRight<R, Ctr>
    : GotoLeft<L, R, [...Ctr, Ctr['length']]>;

// prettier-ignore
type GotoRight<R extends number, Ctr extends number[], Acc extends number[] = []> =
    Ctr['length'] extends R 
    ? [...Acc, Ctr['length']][number]
    : GotoRight<R, [...Ctr, Ctr['length']], [...Acc, Ctr['length']]>;

The two parts look very similar, with one difference being that GotoRight keeps a separate accumulator for the answer. Then, in the end, we convert a tuple to union using [number] as the index.

The actual solution is to simply connect the type to GotoLeft:

type DayCounter<L extends number, R extends number> = GotoLeft<L, R>;

This solution has the following property that:

• DayCounter<N, N> results in N.
• DayCounter<N, M> where N > M results in an error due to infinite recursion.

Day 14. Naughty List

Similar to day 9, in this challenge we can use a string literal with infers in it.

// prettier-ignore
type DecipherNaughtyList<T extends string> = 
  T extends `${infer Head}/${infer Rest}`
  ? Head | DecipherNaughtyList<Rest>
  : T;

Day 15. Box the Toys

The solution is rather straightforward in this challenge, keep an accumulator until its length equals the number of toys, right? Well, yes, but we must support the number of items being a union type as well!

The trick here is to know that union types "distribute" when they are used in a conditional, so it will be as if our conditional is looped over each item in the union. Our solution is the following:

// prettier-ignore
type BoxToys<T extends string, N extends number, Acc extends string[] = []> = 
    N extends Acc['length']
    ? Acc
    : BoxToys<T, N, [...Acc, T]>;

Day 16. Find Santa II

We have a 2D array, and we would like to find the santa in there somewhere & returns its index! The solution is actually similar to Find Santa I at day 12, we just have to do it for each row in an array of rows.

// prettier-ignore
type CheckRow<T extends any[], Acc extends 0[] = []> = 
    T['length'] extends Acc['length']
    ? never
    : T[Acc['length']] extends '🎅🏼'
        ? Acc['length']
        : CheckRow<T, [...Acc, 0]>

// prettier-ignore
type FindSanta<T extends any[][], Acc extends 0[] = []> = 
    T['length'] extends Acc['length']
    ? never
    : CheckRow<T[Acc['length']]> extends never
        ? FindSanta<T, [...Acc, 0]>
        : [Acc['length'], CheckRow<T[Acc['length']]>]

I use the type 0[] for my accumulators sometimes. I do that so that I dont mistakenly give some other type to my accumulator, and explcitly force myself to write 0 to make them stand out a bit more. You are free to use any other type of course.

Day 17. Rock Paper Scissors

In this challenge, we implement a type that can determine the winner & loser of a "Rock, Paper, Scissors" game! It is actually rather straightforward using a chain of conditional types:

type RockPaperScissors = "👊🏻" | "🖐🏾" | "✌🏽";

// prettier-ignore
type WhoWins<L extends RockPaperScissors, R extends RockPaperScissors> = 
    // winning cases
    [L, R] extends ['👊🏻', '🖐🏾'] ? 'win' :
    [L, R] extends ['🖐🏾', '✌🏽'] ? 'win' :
    [L, R] extends ['✌🏽', '👊🏻'] ? 'win' :
    // losing cases
    [L, R] extends ['🖐🏾', '👊🏻'] ? 'lose' :
    [L, R] extends ['✌🏽', '🖐🏾'] ? 'lose' :
    [L, R] extends ['👊🏻', '✌🏽'] ? 'lose' :
    // otherwise draw
    'draw';

Day 18. Remaining Deliveries

This challenge is a classic use-case of an accumulator: to keep count! We will simply keep an array that gets a new element every time we find the element that we seek. In the end, the length of this accumulator results in the number of times that element has been seen.

// prettier-ignore
type Count<T extends any[], V, Acc extends 0[] = []>  = 
    T extends [infer First, ...infer Rest]
    ? First extends V
        ? Count<Rest, V, [...Acc, 0]>
        : Count<Rest, V, Acc>
    : Acc['length'];

Day 19. Embezzle Funds

Here, we will actually make use of two accumulators: one to keep track of all items, and one to keep track of the current item's count. We also need a small utility type to map a given toy to another toy, which will be used when we move on the next item.

Here is the solution:

// map a given item to another item
type Items = { "🛹": "🚲"; "🚲": "🛴"; "🛴": "🏄"; "🏄": "🛹" };

type Rebuild<
  T extends any[],
  Cur extends keyof Items = "🛹", // current item
  Acc extends (keyof Items)[] = [], // accumulator (for our result)
  Ctr extends 0[] = [] // counter
> = T extends [infer First, ...infer Rest]
  ? First extends Ctr["length"]
    ? Rebuild<Rest, Items[Cur], Acc, []>
    : Rebuild<[First, ...Rest], Cur, [...Acc, Cur], [0, ...Ctr]>
  : Acc;

Day 20. ASCII Art

In this challenge, we convert a string to ASCII art; quite a cool thing to do at type-level! First things first, we must extend the Letters type to include lowercase letters as well:

type AllLetters = Letters & {
  [K in keyof Letters as K extends string ? Lowercase<K> : never]: Letters[K];
};

It also seems that we will be working with triples (tuples of length 3) quite a bit, so let us write a utility to concatenate two triples of strings at element level:

// prettier-ignore
type Append<T extends [string, string, string], N extends [string, string, string]> =
  [`${T[0]}${N[0]}`, `${T[1]}${N[1]}`, `${T[2]}${N[2]}`]

With these in our hand, the solution is actually quite simple! One thing that we must tackle first is to detect newlines. Similar to day 10, we can find a string with prefix \n and infer the rest to get the "next line".

If we are not in a new line, we will get the ASCII art triple form AllLetters and append it to an accumulator for the current line. When the line is finished, we add our accumulator to a more general accumulator that keeps track of all lines. We will denote the former as Cur and the latter as Acc.

With these, our solution becomes:

// prettier-ignore
type ToAsciiArt<
    S extends string,
    Acc extends string[] = [],
    Cur extends [string, string, string] = ["", "", ""],
> = 
  S extends `\n${infer Rest}`
  ? ToAsciiArt<Rest, [...Acc, ...Cur], ["", "", ""]>
  : S extends `${infer First extends keyof AllLetters}${infer Rest}` 
    ? ToAsciiArt<Rest, Acc, Append<Cur, AllLetters[First]>>
    : [...Acc, ...Cur];