[Type-challenges] 난이도 Medium - (8)

Github 챌린지 문제들을 풀고 관련된 내용을 정리하면서, 부족했던 타입스크립트 기본지식을 다지고자 한다. (주 1-2회)

 

https://github.com/type-challenges/type-challenges

GitHub - type-challenges/type-challenges: Collection of TypeScript type challenges with online judge

 

---

📘 목차 - Medium

1. Fibonacci Sequence
2. AllCombinations
3. Greater Than
4. Zip
5. IsTuple
6. Chunk
7. Fill

 

 

📘 문제 및 풀이

 

1. Fibonacci Sequence

Implement a generic Fibonacci<T> that takes a number T and returns its corresponding Fibonacci number.

The sequence starts: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

For example

type Result1 = Fibonacci<3> // 2
type Result2 = Fibonacci<8> // 21

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Fibonacci<1>, 1>>,
  Expect<Equal<Fibonacci<2>, 1>>,
  Expect<Equal<Fibonacci<3>, 2>>,
  Expect<Equal<Fibonacci<8>, 21>>,
]

 

🖌 풀이

type Fibonacci<T extends number, N extends unknown[] = [1], Cur extends unknown[] = [1], Pre extends unknown[] = [1]> =
  N['length'] extends T
  ? Cur['length']
  : Fibonacci<T, [...N, 1], Pre, [...Pre, ...Cur]>

N(인덱스), Cur(현재값), Pre(이전 Cur값) 3가지 배열 인자를 추가적으로 활용해서 풀 수 있는 문제이다.

Typescript 에서는 숫자 연산이 제한되므로, 이처럼 배열을 연장하여 이 길이로 연산하는 것이 일반적인 듯 하다.

 

---

2. AllCombinations

Implement type AllCombinations<S> that return all combinations of strings which use characters from S at most once.

For example:

type AllCombinations_ABC = AllCombinations<'ABC'>;
// should be '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<AllCombinations<''>, ''>>,
  Expect<Equal<AllCombinations<'A'>, '' | 'A'>>,
  Expect<Equal<AllCombinations<'AB'>, '' | 'A' | 'B' | 'AB' | 'BA'>>,
  Expect<Equal<AllCombinations<'ABC'>, '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'>>,
  Expect<Equal<AllCombinations<'ABCD'>, '' | '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'>>,
]

 

🖌 풀이

type AllCombinations<S, U extends string = ''> = S extends `${infer SF}${infer SR}` ? 
  U extends `${infer UF}${infer UR}` ? 
    AllCombinations<SR, U | `${SF}${UR}${UF}` | `${UF}${SF}${UR}` | `${UR}${SF}${UF}` | `${UR}${UF}${SF}`> 
  : AllCombinations<SR, U | `${SF}${U}` | `${U}${SF}`> 
: U

문자열의 모든 조합을 반환해야 한다. U 인자에는 모든 조합을 유니온으로 저장한다.

S가 문자열일 때, U의 앞뒤에 SF(첫글자)를 붙여주고 SR(나머지 글자)에 유틸리티를 재귀적으로 적용한다.

단, U가 이미 한 번 실행된 문자열인 경우에, 문자열들을 모두 섞은 조합이 필요하므로 U를 다시 UF, UR로 나눠서 유니온에 반영해준다.

( SF + UF + UR 은  SF + U 와,  UF + UR + SF  는  U + SF 와 같으므로 이는 제외해도 에러가 발생하지 않음)

 

---

3. Greater Than

In This Challenge, You should implement a type GreaterThan<T, U> like T > U
Negative numbers do not need to be considered.

For example

GreaterThan<2, 1> //should be true
GreaterThan<1, 1> //should be false
GreaterThan<10, 100> //should be false
GreaterThan<111, 11> //should be true

 

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<GreaterThan<1, 0>, true>>,
  Expect<Equal<GreaterThan<5, 4>, true>>,
  Expect<Equal<GreaterThan<4, 5>, false>>,
  Expect<Equal<GreaterThan<0, 0>, false>>,
  Expect<Equal<GreaterThan<10, 9>, true>>,
  Expect<Equal<GreaterThan<20, 20>, false>>,
  Expect<Equal<GreaterThan<10, 100>, false>>,
  Expect<Equal<GreaterThan<111, 11>, true>>,
  Expect<Equal<GreaterThan<1234567891011, 1234567891010>, true>>,
]

 

🖌 풀이

type GreaterThan<A extends number, B extends number, N extends any[] = []> = N['length'] extends A
  ? false
  : N['length'] extends B
  ? true
  : GreaterThan<A, B, [...N, any]>;

N이라는 배열에 요소를 하나씩 추가해가면서, 이 길이(length)가 A, B 중 어느 값에 먼저 도달하는지에 따라 true/false 를 반환한다.

 

단, 마지막 케이스는 숫자가 커서 에러가 발생하는 듯 한데,

A, B를 string화 후 비교해서 같은 경우 앞자리부터 하나씩 자른 뒤 남은 숫자만 위 유틸리티를 적용하는 방법으로 풀 수 있을 것 같다.

 

---

4. Zip

In This Challenge, You should implement a type Zip<T, U>, T and U must be Tuple

type exp = Zip<[1, 2], [true, false]> // expected to be [[1, true], [2, false]]

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Zip<[], []>, []>>,
  Expect<Equal<Zip<[1, 2], [true, false]>, [[1, true], [2, false]]>>,
  Expect<Equal<Zip<[1, 2, 3], ['1', '2']>, [[1, '1'], [2, '2']]>>,
  Expect<Equal<Zip<[], [1, 2, 3]>, []>>,
  Expect<Equal<Zip<[[1, 2]], [3]>, [[[1, 2], 3]]>>,
]

 

🖌 풀이

type Zip<T, U> = T extends [infer TF, ...infer TR] ? U extends [infer UF, ...infer UR] ? [[TF, UF], ...Zip<TR, UR>] : [] : []

T, U 각각에 첫 인자가 있으면 이를 튜플로 만들고 남은 TR, UR에 대해 Zip을 재귀적으로 이어간다.

각각이 없는 경우 더 이상 진행이 불가하여 빈 배열을 반환한다.

 

---

5. IsTuple

Implement a type IsTuple, which takes an input type T and returns whether T is tuple type.

For example:

type case1 = IsTuple<[number]> // true
type case2 = IsTuple<readonly [number]> // true
type case3 = IsTuple<number[]> // false

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<IsTuple<[]>, true>>,
  Expect<Equal<IsTuple<[number]>, true>>,
  Expect<Equal<IsTuple<readonly [1]>, true>>,
  Expect<Equal<IsTuple<{ length: 1 }>, false>>,
  Expect<Equal<IsTuple<number[]>, false>>,
  Expect<Equal<IsTuple<never>, false>>,
]

 

🖌 풀이

type IsTuple<T> = [T] extends [never] ? 
  false
: T extends [] | readonly [any] ? true : false

T를 먼저 never인 경우를 구분하기 위해 첫 줄을 작성했는데, 많은 경우가 패스되었다.

에러가 발생한 경우를 확인하면, T가 빈 배열이거나 readonly 배열인 경우에 대해서 분기 처리를 해주면 된다.

 

---

6. Chunk

Do you know lodash? Chunk is a very useful function in it, now let's implement it. Chunk<T, N> accepts two
required type parameters, the T must be a tuple, and the N must be an integer >=1

type exp1 = Chunk<[1, 2, 3], 2> // expected to be [[1, 2], [3]]
type exp2 = Chunk<[1, 2, 3], 4> // expected to be [[1, 2, 3]]
type exp3 = Chunk<[1, 2, 3], 1> // expected to be [[1], [2], [3]]

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Chunk<[], 1>, []>>,
  Expect<Equal<Chunk<[1, 2, 3], 1>, [[1], [2], [3]]>>,
  Expect<Equal<Chunk<[1, 2, 3], 2>, [[1, 2], [3]]>>,
  Expect<Equal<Chunk<[1, 2, 3, 4], 2>, [[1, 2], [3, 4]]>>,
  Expect<Equal<Chunk<[1, 2, 3, 4], 5>, [[1, 2, 3, 4]]>>,
  Expect<Equal<Chunk<[1, true, 2, false], 2>, [[1, true], [2, false]]>>,
]

 

🖌 풀이

type Chunk<T extends any[], N extends number = 1, C extends any[] = []> = 
  T extends [infer R, ...infer U]
    ? C['length'] extends N
      ? [C, ...Chunk<T, N>]
      : Chunk<U, N, [...C, R]>
    : C extends []
      ? []
      : [C]

T(배열), N(chunk 길이)에 C(chunk한 배열) 인자까지 추가하여 유틸리티를 실행한다.

 

우선 T가 배열일 때, C의 길이가 N과 같으면 이 C를 유지하고 다음 Chunk를 재귀적으로 실행시킨다.

길이가 아직 부족하다면, 남은 배열(U)에 대해 실행하며 이 때 C에는 기존 C + 현재 R을 넣어준다.

마지막으로 C가 빈 배열일 때 처리를 해주면 끝난다.

 

---

7. Fill

Fill, a common JavaScript function, now let us implement it with types. Fill<T, N, Start?, End?>, 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.

type exp = Fill<[1, 2, 3], 0> // expected to be [0, 0, 0]

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Fill<[], 0>, []>>,
  Expect<Equal<Fill<[], 0, 0, 3>, []>>,
  Expect<Equal<Fill<[1, 2, 3], 0, 0, 0>, [1, 2, 3]>>,
  Expect<Equal<Fill<[1, 2, 3], 0, 2, 2>, [1, 2, 3]>>,
  Expect<Equal<Fill<[1, 2, 3], 0>, [0, 0, 0]>>,
  Expect<Equal<Fill<[1, 2, 3], true>, [true, true, true]>>,
  Expect<Equal<Fill<[1, 2, 3], true, 0, 1>, [true, 2, 3]>>,
  Expect<Equal<Fill<[1, 2, 3], true, 1, 3>, [1, true, true]>>,
  Expect<Equal<Fill<[1, 2, 3], true, 10, 0>, [1, 2, 3]>>,
  Expect<Equal<Fill<[1, 2, 3], true, 10, 20>, [1, 2, 3]>>,
  Expect<Equal<Fill<[1, 2, 3], true, 0, 10>, [true, true, true]>>,
]

 

🖌 풀이

type Fill<
  T extends unknown[],
  N,
  Start extends number = 0,
  End extends number = T['length'],
  A extends unknown[] = []
> = T extends [infer F, ...infer R] ?
  A['length'] extends Start ? Fill<R, N, Start, End, [...T, N]> :
    A['length'] extends End ? Fill<R, N, Start, End, [...A, F]> :
  Fill<R, N, Start, End, [...A, N]>
: []

이는 내가 풀다가 실패한 풀이며, 정답은 우측 링크를 참고하면 된다. (정답링크)

축적하고 있는 A 배열의 길이를, Start, End 등에 따라 다소 노가다성으로 분기해줘야 하는 문제이다.