小镇做题家 - TypeScript 类型大挑战（中等篇 - 下）
## Medium 组（下）
### Reverse
> Implement the type version of ```Array.reverse```
```typescript
type Reverse = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, ['b', 'a']>>,
Expect, ['c', 'b', 'a']>>,
]
```
反转数组，这个也很简单：
```typescript
type Reverse = T extends [...infer R, infer L]
? [L, ...Reverse]
: T
```
### Flip Arguments
> Implement the type version of lodash's ```_.flip```.
>
> Type ```FlipArguments``` requires function type ```T``` and returns a new function type which has the same return type of T but reversed parameters.
```typescript
type FlipArguments = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect boolean>, () => boolean>>,
Expect number>, (foo: string) => number>>,
Expect void>, (arg0: boolean, arg1: number, arg2: string) => void>>,
]
type errors = [
// @ts-expect-error
FlipArguments<'string'>,
// @ts-expect-error
FlipArguments<{ key: 'value' }>,
// @ts-expect-error
FlipArguments<['apple', 'banana', 100, { a: 1 }]>,
// @ts-expect-error
FlipArguments,
]
```
首先需要对泛型加上约束解决 error cases：
```typescript
type FlipArguments any> = any
```
反转参数，这就和反转数组是一致的了：
```typescript
type Reverse = T extends [...infer R, infer L]
? [L, ...Reverse]
: T
type FlipArguments any> = T extends (...args: infer Args) => infer R
? (...args: Reverse) => R
: never
```
### FlattenDepth
> Recursively flatten array up to depth times.
```typescript
type FlattenDepth = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, [1, 2, 3, 4]>>,
Expect, [1, 2]>>,
Expect, [1, 2, 3, 4, [5]]>>,
Expect, [1, 2, 3, 4, [[5]]]>>,
Expect, [1, 2, 3, 4, [5]]>>,
Expect, [1, 2, 3, 4, 5]>>,
]
```
这题给的初始内容有点少得可怜，所以泛型这一块就需要我们自己补充上去了：
```typescript
type FlattenDepth = any
```
需要注意的是这里的 case 有一个比较大的层级数，所以我们不能够采用减法的形式来计算，再借助一个初始值做加法比对：
```typescript
type FlattenDepth
```
解题思路就比较简单了：
```typescript
type Plus = R['length'] extends T
? [...R, 0]['length']
: Plus
type FlattenDepth = S extends D
? T
: T extends [infer F, ...infer R]
? [
...(F extends any[]
? FlattenDepth>
: [F]
),
...FlattenDepth
]
: T
```
### BEM style string
> The Block, Element, Modifier methodology (BEM) is a popular naming convention for classes in CSS.
>
> For example, the block component would be represented as `btn`, element that depends upon the block would be represented as `btn__price`, modifier that changes the style of the block would be represented as `btn--big` or `btn__price--warning`.
>
> Implement `BEM` which generate string union from these three parameters. Where `B` is a string literal, `E` and `M` are string arrays (can be empty).
```typescript
type BEM = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 'btn__price'>>,
Expect, 'btn__price--warning' | 'btn__price--success' >>,
Expect, 'btn--small' | 'btn--medium' | 'btn--large' >>,
]
```
这题我们需要利用 `T[number]` 将数组转成 Union：
```typescript
type BEM = `${B}${E[number] extends '' ? '' : `__${E[number]}`}${M[number] extends '' ? '' : `--${M[number]}`}`
```
### InorderTraversal
> Implement the type version of binary tree inorder traversal.
```typescript
interface TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
}
type InorderTraversal = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
const tree1 = {
val: 1,
left: null,
right: {
val: 2,
left: {
val: 3,
left: null,
right: null,
},
right: null,
},
} as const
const tree2 = {
val: 1,
left: null,
right: null,
} as const
const tree3 = {
val: 1,
left: {
val: 2,
left: null,
right: null,
},
right: null,
} as const
const tree4 = {
val: 1,
left: null,
right: {
val: 2,
left: null,
right: null,
},
} as const
type cases = [
Expect, []>>,
Expect, [1, 3, 2]>>,
Expect, [1]>>,
Expect, [2, 1]>>,
Expect, [1, 2]>>,
]
```
这题我们需要注意的是它的取值顺序是 `left.val` 、`val`、`right.val`：
```typescript
type InorderTraversal = T extends TreeNode
? [
...T['left'] extends TreeNode ? InorderTraversal : [],
T['val'],
...T['right'] extends TreeNode ? InorderTraversal : []
]
: []
```
### Flip
> Implement the type of `just-flip-object`.
```typescript
type Flip = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect, NotEqual } from '@type-challenges/utils'
type cases = [
Expect>>,
Expect>>,
Expect>>,
Expect>>,
]
```
这题是把键值交换，需要注意的是，对象的键也就是 `PropertyKey` 他只能是 `string | number | symbol` ，如果不符合 `PropertyKey` 的约束，我们需要把它转成字符串：
```typescript
type Flip> = {
[P in keyof T as T[P] extends PropertyKey ? T[P] : `${T[P]}`]: P
}
```
### Fibonacci Sequence
> Implement a generic Fibonacci\ takes an number T and returns it's corresponding [Fibonacci number](https://en.wikipedia.org/wiki/Fibonacci_number).
```typescript
type Fibonacci = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 2>>,
Expect, 21>>,
]
```
我们需要了解什么是斐波那契数列：`1, 1, 2, 3, 5, 8, 13, ...`
然后从中取出指定索引的值，所以我们需要一些辅助类型来存储上一个值和当前值，并且让计算从第 2 项才开始：
```typescript
type NumberToTuple = R['length'] extends T
? R
: NumberToTuple
type Plus = [
...NumberToTuple,
...NumberToTuple
]['length'] & number
// 1, 1, 2, 3, 5, 8, ...
type Fibonacci<
T extends number,
Start extends number = 2,
Prev extends number = 0,
Last extends number = 1
> = T extends 0 | 1
? 1
: Start extends T
? Plus
: Fibonacci, Last, Plus>
```
### AllCombinations
> Implement type ```AllCombinations``` that return all combinations of strings which use characters from ```S``` at most once.
```typescript
type AllCombinations = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, ''>>,
Expect, '' | 'A'>>,
Expect, '' | 'A' | 'B' | 'AB' | 'BA'>>,
Expect, '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'>>,
Expect, '' | 'A' | 'B' | 'C' | 'D' | 'AB' | 'AC' | 'AD' | 'BA' | 'BC' | 'BD' | 'CA' | 'CB' | 'CD' | 'DA' | 'DB' | 'DC' | 'ABC' | 'ABD' | 'ACB' | 'ACD' | 'ADB' | 'ADC' | 'BAC' | 'BAD' | 'BCA' | 'BCD' | 'BDA' | 'BDC' | 'CAB' | 'CAD' | 'CBA' | 'CBD' | 'CDA' | 'CDB' | 'DAB' | 'DAC' | 'DBA' | 'DBC' | 'DCA' | 'DCB' | 'ABCD' | 'ABDC' | 'ACBD' | 'ACDB' | 'ADBC' | 'ADCB' | 'BACD' | 'BADC' | 'BCAD' | 'BCDA' | 'BDAC' | 'BDCA' | 'CABD' | 'CADB' | 'CBAD' | 'CBDA' | 'CDAB' | 'CDBA' | 'DABC' | 'DACB' | 'DBAC' | 'DBCA' | 'DCAB' | 'DCBA'>>,
]
```
首先要做的就是把字符串给转成联合类型：
```typescript
type StringToUnion = S extends `${infer F}${infer R}`
? F | StringToUnion
: never
```
然后利用分布式条件类型自动生成结果：
```typescript
type StringToUnion = S extends `${infer F}${infer R}`
? F | StringToUnion
: never
type Combinations = [T] extends [never]
? ''
: '' | { [K in T]: `${K}${Combinations>}` }[T]
type AllCombinations = Combinations>
```
分析结果可以看这里：[https://www.yuque.com/liaojie3/yuiou5/ogyeiz#giVmO](https://www.yuque.com/liaojie3/yuiou5/ogyeiz#giVmO)
### Greater Than
> In This Challenge, You should implement a type `GreaterThan` like `T > U`
>
> Negative numbers do not need to be considered.
```typescript
type GreaterThan = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, true>>,
Expect, true>>,
Expect, false>>,
Expect, false>>,
Expect, false>>,
Expect, false>>,
Expect, true>>,
]
```
这里的解题思路是：
1. 先过滤相等项；
```typescript
type GT = any
type GreaterThan = Equal extends true
? false
: GT
```
2. 然后递归地把第一项做 “减一” 操作，直到它和第二项相等，或者变为 0 为止。
```typescript
type NumberToTuple = Res['length'] extends T
? Res
: NumberToTuple
type MinusOne> = Res extends [infer F, ...infer R]
? R['length']
: never
type GT = T extends U
? true
: T extends 0
? false
: GT, U>
type GreaterThan = Equal extends true
? false
: GT
```
### Zip
> In This Challenge, You should implement a type `Zip`, T and U must be `Tuple`
```typescript
type Zip = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, [[1, true], [2, false]]>>,
Expect, [[1, '1'], [2, '2']]>>,
Expect, []>>,
Expect, [[[1, 2], 3]]>>,
]
```
根据题目要求，它需要两个泛型参数，并且都得是一个数组：
```typescript
type Zip = any
```
之后就是简单的数组操作了：
```typescript
type Zip = T extends []
? []
: T extends [infer TF, ...infer TR]
? U extends [infer UF, ...infer UR]
? [[TF, UF], ...Zip]
: []
: []
```
### IsTuple
> Implement a type ```IsTuple```, which takes an input type ```T``` and returns whether ```T``` is tuple type.
```typescript
type IsTuple = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, true>>,
Expect, true>>,
Expect, true>>,
Expect, false>>,
Expect, false>>,
Expect, false>>,
]
```
这题是比较简单的，我们可以使用 `[any?]` 来表示一个数组。当然，我们需要先排除掉 never：
```typescript
type IsTuple = [T] extends [never]
? false
: T extends readonly [any?]
? true
: false
```
### Chunk
> Do you know `lodash`? `Chunk` is a very useful function in it, now let's implement it.
>
> `Chunk` accepts two required type parameters, the `T` must be a `tuple`, and the `N` must be an `integer >=1`
```typescript
type Chunk = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, [[1], [2], [3]]>>,
Expect, [[1, 2], [3]]>>,
Expect, [[1, 2], [3, 4]]>>,
Expect, [[1, 2, 3, 4]]>>,
Expect, [[1, true], [2, false]]>>,
]
```
首先，根据题目要求把泛型以及约束加上：
```typescript
type Chunk = any
```
先实现一个用于取值的 Slice 类型，它会从指定的数组中取出指定长度的项：
```typescript
type GetItem = Res['length'] extends N
? Res
: T extends [infer F, ...infer R]
? GetItem
: Res
```
然后就是常规的数组操作了：
```typescript
type Slice = Res['length'] extends N
? Res
: T extends [infer F, ...infer R]
? Slice
: Res
type Chunk = T extends []
? []
: T extends [...Slice, ...infer R]
? R extends []
? [...Res, Slice]
: Chunk]>
: never
```
### Fill
> `Fill`, a common JavaScript function, now let us implement it with types.
>
> `Fill`, as you can see,`Fill` accepts four types of parameters, of which `T` and `N` are required parameters, and `Start` and `End` are optional parameters.
>
> The requirements for these parameters are: `T` must be a `tuple`, `N` can be any type of value, `Start` and `End` must be integers greater than or equal to 0.
```typescript
type Fill<
T extends unknown[],
N,
Start extends number = 0,
End extends number = T['length'],
> = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, []>>,
Expect, [1, 2, 3]>>,
Expect, [1, 2, 3]>>,
Expect, [0, 0, 0]>>,
Expect, [true, true, true]>>,
Expect, [true, 2, 3]>>,
Expect, [1, true, true]>>,
Expect, [1, 2, 3]>>,
Expect, [true, true, true]>>,
]
```
我们先排除 Start 和 End 相同，或者 End 为 0 的 case，然后再处理其它的：
```typescript
type Fill<
T extends unknown[],
N,
Start extends number = 0,
End extends number = T['length']
> = Start extends End ? T : End extends 0 ? T : FillRest
```
`FillReset` 利用一个计数器 Count 来决定什么时候开始对值进行替换：
```typescript
type PlusOne = Res['length'] extends T
? [...Res, 0]['length']
: PlusOne
type FillRest<
T extends unknown[],
N,
Start extends number = 0,
End extends number = T['length'],
Count extends number = 0,
Res extends unknown[] = []
> = Start extends End
? [...Res, ...T]
: T extends [infer F, ... infer R]
? Count extends Start
? FillRest, End, PlusOne, [...Res, N]>
: FillRest, [...Res, F]>
: Res
```
### Trim Right
> Implement `TrimRight` which takes an exact string type and returns a new string with the whitespace ending removed.
```typescript
type TrimRight = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 'str'>>,
Expect, 'str'>>,
Expect, 'str'>>,
Expect, ' str'>>,
Expect, ' foo bar'>>,
Expect, ''>>,
Expect, ''>>,
]
```
这和之前的 [TrimLeft](#TrimLeft) 一样的处理方式：
```typescript
type TrimRight = S extends `${infer R}${' ' | '\n' | '\t'}`
? TrimRight
: S
```
### Without
> Implement the type version of Lodash.without, Without takes an Array T, number or array U and returns an Array without the elements of U.
```typescript
type Without = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, [2]>>,
Expect, [4, 5]>>,
Expect, []>>,
]
```
就是过滤操作，首先我们把 U 转成联合类型：
```typescript
type ToUnion = T extends number
? T
: T extends any[]
? T[number]
: never
```
然后就是常规的对比操作了：
```typescript
type ToUnion = T extends number
? T
: T extends any[]
? T[number]
: never
type Without<
T,
U extends number | unknown[],
D = ToUnion,
Result extends unknown[] = []
> = T extends [infer F, ...infer R]
? F extends D
? Without
: Without
: Result
```
### Trunc
> Implement the type version of ```Math.trunc```, which takes string or number and returns the integer part of a number by removing any fractional digits.
```typescript
type Trunc = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, '0'>>,
Expect, '1'>>,
Expect, '12'>>,
Expect, '-5'>>,
Expect, '1'>>,
Expect, '-10'>>,
Expect, '10'>>,
]
```
移除小数位，直接字符串操作即可：
```typescript
type Trunc = `${T}` extends `${infer F}.${infer R}`
? `${F}`
: `${T}`
```
### IndexOf
> Implement the type version of Array.indexOf, indexOf takes an Array T, any U and returns the index of the first U in Array T.
```typescript
type IndexOf = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 1>>,
Expect, 2>>,
Expect, -1>>,
Expect, 2>>,
Expect, 4>>,
]
```
递归比对即可：
```typescript
type PlusOne = Res['length'] extends T
? [...Res, 0]['length']
: PlusOne
type IndexOf = T extends [infer F, ...infer R]
? Equal extends true
? I
: IndexOf>
: -1
```
### Join
> Implement the type version of Array.join, Join takes an Array T, string or number U and returns the Array T with U stitching up.
```typescript
type Join = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 'a-p-p-l-e'>>,
Expect, 'Hello World'>>,
Expect, '21212'>>,
Expect, 'o'>>,
]
```
我能想到的是先将 T 中所有项都和 U 拼接起来，然后再去除最后一个 U 便可以解开这道题：
```typescript
type RemoveLast = T extends `${infer R}${U}`
? R
: T
type FullJoin = T extends [infer F extends string, ...infer R extends string[]]
? FullJoin
: Result
type Join = RemoveLast, `${U}`>
```
### LastIndexOf
> Implement the type version of ```Array.lastIndexOf```, ```LastIndexOf``` takes an Array ```T```, any ```U``` and returns the index of the last ```U``` in Array ```T```
```typescript
type LastIndexOf = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, 3>>,
Expect, 7>>,
Expect, -1>>,
Expect, 4>>,
Expect, 5>>,
]
```
这题相对于 IndexOf 会更加简单，每一次取数组中最后一位作比对操作，如果相同，则数组中剩余项的个数即为 LastIndex：
```typescript
type LastIndexOf = T extends [...infer R, infer L]
? Equal extends true
? R['length']
: LastIndexOf
: -1
```
### Unique
> Implement the type version of Lodash.uniq, Unique takes an Array T, returns the Array T without repeated values.
```typescript
type Unique = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, [1, 2, 3]>>,
Expect, [1, 2, 3, 4, 5, 6, 7]>>,
Expect, [1, 'a', 2, 'b']>>,
Expect, [string, number, 1, 'a', 2, 'b']>>,
Expect, [unknown, any, never]>>,
]
```
通过 Includes 来判断是否已经取过该值即可：
```typescript
type Includes = T extends [infer F, ...infer R]
? Equal extends true
? true
: Includes
: false
type Unique = T extends [infer F, ...infer R]
? Includes extends true
? Unique
: Unique
: Res
```
### MapTypes
> Implement `MapTypes` which will transform types in object T to different types defined by type R which has the following structure
```typescript
type MapTypes = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, { stringToArray: [] }>>,
Expect, { stringToNumber: number }>>,
Expect, { stringToNumber: number; skipParsingMe: boolean }>>,
Expect, { date: null | Date }>>,
Expect, { date: null | Date }>>,
Expect }, { mapFrom: Record; mapTo: string[] }>, { fields: string[] }>>,
Expect, { name: string }>>,
Expect, { name: boolean; date: string }>>,
]
```
这题需要注意的是 U 有可能是一个联合类型，所以需要进一步判断：
```typescript
type Includes, U> = T extends {}
? T['mapFrom'] extends U
? T['mapTo']
: never
: T['mapTo']
type MapTypes> = {
[P in keyof T]: T[P] extends R['mapFrom']
? Includes
: T[P]
}
```
### Construct Tuple
> Construct a tuple with a given length.
```typescript
type ConstructTuple = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'
type cases = [
Expect, []>>,
Expect, [unknown, unknown]>>,
Expect['length'], 999>>,
// @ts-expect-error
Expect['length'], 1000>>,
]
```
生成一个指定长度的数组，这点在之前的挑战中已经多次实现过了，最后一个 case 是因为递归上限会导致出错：
```typescript
type ConstructTuple