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 arrayreadonly
, kind of like usingas 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 inFirst
and the rest of the array inRest
. -
T extends [...infer Rest, infer Last]
will return the last element inLast
and the rest of the array inRest
.
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 lengthL
with values[0, 1, ..., L-1]
and then callGotoRight
-
GotoRight
will construct an array of lengthR
, 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 inN
.DayCounter<N, M>
whereN > 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 infer
s 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];
Top comments (0)