# Advent of Typescript 2023
[Advent of TypeScript 2023](https://www.adventofts.com/events/2023) is a series of challenges related to type-level TypeScript. You can find the solutions & tests at [erhant/aot-2023](https://github.com/erhant/adventofts-2023).
## [Day 1. Christmas Cookies](https://www.adventofts.com/events/2023/1)
We simply have to provide a [Union](https://www.typescriptlang.org/docs/handbook/typescript-in-5-minutes-func.html#unions) type, as follows:
```ts
## [Day 2. Cookie Inventory](https://www.adventofts.com/events/2023/2)
We are required to return the keys in the given object, thankfully [`keyof`](https://www.typescriptlang.org/docs/handbook/2/keyof-types.html#the-keyof-type-operator) operator does just that!
```ts
type CookieSurveyInput<T> = keyof T;
```
## [Day 3. Gift Wrapper](https://www.adventofts.com/events/2023/3)
We have 3 parameters, and in the given order they must be assigned as values to keys `present`, `from` and `to`. Well, working with objects in the type-world is very similar to JS, as you can see:
```ts
type GiftWrapper<P, F, T> = {
present: P;
from: F;
to: T;
};
```
## [Day 4. Delivery Addresses](https://www.adventofts.com/events/2023/4)
Here, we need to change the values of a given object. We can access the keys of an object via `K in keyof T`; remember `keyof T` returns a union and `in` tells us that we want all the values in the union. Our solution is therefore:
```ts
type Address = { address: string; city: string };
type PresentDeliveryList<T extends Record<PropertyKey, any>> = {
[K in keyof T]: Address;
};
```
> We don't really need `T extends Record<PropertyKey, any>` here for the tests, but that provides a bit more type-safety where unsuitable parameters to `PresentDeliveryList` would cause an error.
## [Day 5. Santa's List](https://www.adventofts.com/events/2023/5)
Here we are asked to concatenate two arrays. We must remember that spread operator `...array` works in type-world too! So, if we have two arrays `A, B` we can spread them into a single array `[...A, ...B]` and the result will be as if we had called `A.concat(B)`.
```ts
type SantasList<A extends readonly any[], B extends readonly any[]> = [
...A,
...B,
];
```
## [Day 6. Filtering the Children I](https://www.adventofts.com/events/2023/6)
We are asked to **exclude** an item from a union. TypeScript has a built-in called `Exclude` just for that!
```ts
type FilterChildrenBy<T, E> = Exclude<T, E>;
```
## [Day 7. Filtering the Children II](https://www.adventofts.com/events/2023/7)
We have worked with changing the value of a record before in day 4; now, we are asked to change the keys! This is a bit more work, but we will make use of something called [key remapping](https://www.typescriptlang.org/docs/handbook/2/mapped-types.html#key-remapping-via-as) which allows one to re-map keys in a mapped type.
```ts
type GoodProperty<K extends PropertyKey> = K extends string
? `good_${K}`
: never;
type AppendGood<T extends Record<string, any>> = {
[K in keyof T as GoodProperty<K>]: T[K];
};
```
> One thing to notice here:
>
> ```ts
> type AppendGood<T extends Record<string, any>> = {
> [K in keyof T as `good_${K}`]: T[K];
> };
> ```
>
> The code above will not work because a string literal accepts things that can be stringified, however a property (via `keyof`) can return a `Symbol` which wouldn't be compatible with our string literal there.
> I didn't know about key-remapping until this challenge!
## [Day 8. Filtering the Children III](https://www.adventofts.com/events/2023/8)
In this challenge, we will filter out some of the keys based on how they fit a given string. We can use `Exclude` for this as well! If you hover over the built-in `Exclude` you will see that it is written as:
```ts
type Exclude<T, U> = T extends U ? never : T;
```
So if a given string `T` extends `U`, it will return `never`. If a mapped-key is `never` it is not included in the resulting object. With this in mind, our solution is:
```ts
type RemoveNaughtyChildren<T> = {
[K in Exclude<keyof T, `naughty_${string}`>]: T[K];
};
```
> Notice how we access the respective values of each key via `T[K]`
## [Day 9. Is Santa Dyslexic?](https://www.adventofts.com/events/2023/9)
We are asked to reverse a string, at type-level! Although this may sound scary at first, it is not so scary when you have knowledge of the `infer` keyword. Inferring is done within a conditional type, you can learn more about it [here](https://www.typescriptlang.org/docs/handbook/2/conditional-types.html#inferring-within-conditional-types).
We can ask if a type extends some other type, and infer parts of it based on whether that condition is true or not! In this challenge, we can ask if our type extends a string with two inferred parts: `T extends ${infer F}${infer S}`. It just turns out that `F` will be the first character here, and `S` will be the rest of the string.
So, we can extract `F` and `S` like that, and put `F` at the end of a new string, prefixed by `Reverse<S>` yet again to reverse the remaining string. In the end, there will be no characters left, and at that point we will return the string itself.
```ts
type Reverse<T extends string> = T extends `${infer F}${infer S}`
? `${Reverse<S>}${F}`
: T;
```
> When `T = 'a'`, that condition will result in `F = 'a'` and `S = ''`.
## [Day 10. Street Suffix](https://www.adventofts.com/events/2023/10)
In this challenge, we just need to make a suffix check, a job suited for the beloved condition-type together with a string literal.
```ts
type StreetSuffixTester<
T extends string,
S extends string,
> = T extends `${string}${S}` ? true : false;
```
The code is pretty self-explanatory in this one.
## [Day 11. Protect the List](https://www.adventofts.com/events/2023/11)
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`](https://www.typescriptlang.org/docs/handbook/utility-types.html#readonlytype) makes a type (not its children) `readonly`.
- [`ReadonlyArray`](https://www.typescriptlang.org/docs/handbook/2/objects.html#the-readonlyarray-type) 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:
```ts
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`:
```ts
// 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`:
```ts
type SantaListProtector<T> = DeepReadonly<T>;
```
## [Day 12. Find Santa I](https://www.adventofts.com/events/2023/12)
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`.
```ts
type FindSanta<T extends any[]> = T extends [...infer Rest, infer Last]
? Last extends "🎅🏼"
? Rest["length"]
: FindSanta<Rest>
: never;
```
## [Day 13. Count the Days](https://www.adventofts.com/events/2023/13)
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.
```ts
// 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`:
```ts
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](https://www.adventofts.com/events/2023/14)
Similar to day 9, in this challenge we can use a string literal with `infer`s in it.
```ts
// prettier-ignore
type DecipherNaughtyList<T extends string> =
T extends `${infer Head}/${infer Rest}`
```
## [Day 15. Box the Toys](https://www.adventofts.com/events/2023/15)
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"](https://www.typescriptlang.org/docs/handbook/2/conditional-types.html#distributive-conditional-types) 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:
```ts
// 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](https://www.adventofts.com/events/2023/16)
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.
```ts
// 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](https://www.adventofts.com/events/2023/17)
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:
```ts
// 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](https://www.adventofts.com/events/2023/18)
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.
```ts
// 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](https://www.adventofts.com/events/2023/19)
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:
```ts
// 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](https://www.adventofts.com/events/2023/20)
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:
```ts
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:
```ts
// 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:
```ts
// 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];
```
## [Day 21. Tic-Tac-Toe](https://www.adventofts.com/events/2023/21)
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:
```ts
// 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:
```ts
// 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:
```ts
// 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.
```ts
// 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:
```ts
// 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:
```ts
// 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](https://www.adventofts.com/events/2023/22)
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](https://typehero.dev/challenge/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!
```ts
// 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:
```ts
// 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](https://www.adventofts.com/events/2023/23)
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.
```ts
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.
```ts
// 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.
```ts
// 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:
```ts
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.
```ts
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`:
```ts
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:
```ts
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!
```ts
// 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.
```ts
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](https://www.adventofts.com/events/2023/24)
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:
```ts
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.
```ts
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:
```ts
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:
```ts
// 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:
```ts
// 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:
```ts
// 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!](https://www.adventofts.com/events/2023/25)
You know what to do!