[TS] Type-Challenges 스터디 16주차

[medium] 18220. Filter

View on github: https://tsch.js.org/18220

문제

Implement the type Filter<T, Predicate> takes an Array T, primitive type or union primitive type Predicate and returns an Array include the elements of Predicate.

문제 설명

• 배열을 받아, 배열의 요소중 Predicate(Primitive Type or Union Primitive Type)에 해당하는 요소만 반환

시도 1 (정답)

접근 방식

• 배열을 순회하면서 각 요소가 P에 extends 되는지 확인
• 해당 요소가 P에 extends 되면 리턴 배열에 포함

코드

type Filter<T extends any[], P> = T extends [infer First, ...infer Rest]
  ? First extends P
    ? [First, ...Filter<Rest, P>]
    : [...Filter<Rest, P>]
  : [];

코드 설명

• 배열을 순회하면서 각 요소가 P에 extends 되는지 확인
• 해당 요소가 P에 extends 되면 리턴 배열에 포함
• 해당 요소가 P에 extends 되지 않으면 무시
• 전체 순회가 끝나면 빈 배열 반환

[medium] 21104. Find All

View on github: https://tsch.js.org/21104

문제

Given a pattern string P and a text string T, implement the type FindAll<T, P> that returns an Array that contains all indices (0-indexed) from T where P matches.

문제 설명

• 텍스트 문자열 T와 패턴 문자열 P를 받아, P가 T에 존재하는 모든 인덱스를 배열로 반환

시도 1

접근 방식

• 템플릿 리터럴로 P가 존재하는지 확인, 존재할 경우 index를 구해서 리턴 배열에 추가
• index는 left 문자열의 길이를 재면 되지 않을까?
• 이후 P 뒷쪽의 rest 문자열을 재귀 처리

코드

type GetIndex<
  T extends string,
  LengthArr extends unknown[] = []
> = T extends `${infer _}${infer Rest}`
  ? GetIndex<Rest, [unknown, ...LengthArr]>
  : LengthArr["length"];

type FindAll<
  T extends string,
  P extends string
> = T extends `${infer Left}${P}${infer Rest}`
  ? [GetIndex<Left>, ...FindAll<Rest, P>]
  : [];

코드 설명

• ${infer Left}${P}${infer Rest}를 활용해 P가 존재하는지 확인
• P가 존재할 경우, Left의 길이를 리턴하고, 이후 Rest에 대해 재귀 처리
• P가 존재하지 않을 경우, 빈 배열 반환

실패 이유

• 뒷쪽의 rest 문자열만 재귀처리하니까, 두번째 요소에 대해서는 뒷쪽(rest 내)의 index를 구함
• 누적으로 더할 방법을 고민해봐야 함
• 하지만 결국 rest로 분리하게 되면, AAAA, AA를 통과를 못시킬듯

시도 2 (정답)

접근 방식

• T의 한 글자씩 순회하면서, P의 첫 글자와 같으면 비교
• 비교 성공시 index 리턴 배열에 추가

코드

type FindAll<
  T extends string,
  P extends string,
  IndexArr extends unknown[] = []
> = T extends `${infer TFirst}${infer TRest}`
  ? P extends `${TFirst}${infer PRest}`
    ? TRest extends `${PRest}${infer _}`
      ? [IndexArr["length"], ...FindAll<TRest, P, [...IndexArr, unknown]>]
      : [...FindAll<TRest, P, [...IndexArr, unknown]>]
    : [...FindAll<TRest, P, [...IndexArr, unknown]>]
  : [];

코드 설명

• ${infer TFirst}${infer TRest}를 활용해 T의 한 글자씩 순회
• P의 첫 글자와 같으면(${TFirst}${infer PRest}), TRest가 P 문자열을 포함하는지 확인
• 그럴 경우, 해당 index를 리턴 배열에 추가
• 아닐 경우, 해당 글자는 무시하고 다음 글자로 넘어감
• 모든 글자를 순회하면 빈 배열 반환

[medium] 21106. Combination Key Type

View on github: https://tsch.js.org/21106

문제

1. Combine multiple modifier keys, but the same modifier key combination cannot appear.
2. In the ModifierKeys provided, the priority of the previous value is higher than the latter value; that is, cmd ctrl is OK, but ctrl cmd is not allowed.

문제 설명

• 여러 키를 조합해서 새로운 키를 만들어야 함
• 조합된 키는 중복되지 않아야 함
• 조합된 키는 순서가 있어야 함(앞선 키가 우선 순위가 높음)

시도 1

접근 방식

• 기존 콤비네이션 코드 차용

코드

type MakeCombination<A extends string, B extends string> = `${A} ${B}`;

type UnionCombination<A extends string, B extends string = A> = [A] extends [
  never
]
  ? ""
  : A extends B
  ? MakeCombination<A, UnionCombination<Exclude<B, A>>>
  : never;

type Combs<T extends any[]> = UnionCombination<T[number]>;

실패 이유

• 조합이 아니라, 마치 순열처럼 모든 경우의 수가 합쳐져서 나옴

시도 2 (답지 참고)

코드

type Combs<T extends string[] = ModifierKeys> = T extends [
  infer F extends string,
  ...infer R extends string[]
]
  ? `${F} ${R[number]}` | Combs<R>
  : never;

코드 설명

• F와 나머지 R의 요소들을 묶은 string 리턴
• 이후 R를 순회하면서 계속 조합

[medium] 21220. Permutations of Tuple

View on github: https://tsch.js.org/21220

문제

Given a generic tuple type T extends unknown[], write a type which produces all permutations of T as a union.

예시

PermutationsOfTuple<[1, number, unknown]>;
// Should return:
// | [1, number, unknown]
// | [1, unknown, number]
// | [number, 1, unknown]
// | [unknown, 1, number]
// | [number, unknown, 1]
// | [unknown, number ,1]

문제 설명

• 튜플의 모든 조합을 반환하는 타입을 작성
• 조합들은 Union으로 반환

시도 1

접근 방식

• 기존 순열 코드 차용

코드

type Permutation<T, K = T> = [T] extends [never]
  ? []
  : K extends K
  ? [K, ...Permutation<Exclude<T, K>>]
  : never;

type PermutationsOfTuple<T extends unknown[]> = Permutation<T[number]>;

실패 이유

• any와 unknown 처리 실패

시도 2 (답지 참고)

코드

type PermutationsOfTuple<
  T extends unknown[],
  Prev extends unknown[] = []
> = T extends [infer First, ...infer Rest]
  ?
      | [First, ...PermutationsOfTuple<[...Prev, ...Rest]>]
      | (Rest extends [] ? never : PermutationsOfTuple<Rest, [...Prev, First]>)
  : [];

코드 설명

• T를 순회하며, First 및 Rest 분리
• First와 Prev, Rest를 조합
• Rest가 빈 배열일 경우 never 반환
• 아닐 경우, Rest와 ...Prev, First를 재귀 호출

[medium] 25170. Replace First

View on github: https://tsch.js.org/25170

문제

Implement the type ReplaceFirst<T, S, R> which will replace the first occurrence of S in a tuple T with R. If no such S exists in T, the result should be T.

문제 설명

• 튜플 T에서 첫 번째로 나타나는 S를 R로 대체
• 만약 T에 S가 없다면, 결과는 T

시도 1 (정답)

접근 방식

• 튜플을 순회하면서, S와 같은 요소를 찾아서 R로 대체

코드

type ReplaceFirst<
  T extends readonly unknown[],
  S,
  R,
  Result extends any[] = []
> = T extends [infer First, ...infer Rest]
  ? First extends S
    ? [...Result, R, ...Rest]
    : ReplaceFirst<Rest, S, R, [...Result, First]>
  : Result;

코드 설명

• 튜플을 순회하면서, S와 같은 요소를 찾음 (extends로 비교, IsEqual로 비교시 two와 string 비교 안됨)
• 찾으면, R로 대체
• 대체 후 나머지 요소들을 리턴

[medium] 25270. Transpose

View on github: https://tsch.js.org/25270

문제

The transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix A by producing another matrix, often denoted by AT.

예시

type Matrix = Transpose<[[1]]>; // expected to be [[1]]
type Matrix1 = Transpose<[[1, 2], [3, 4]]>; // expected to be [[1, 3], [2, 4]]
type Matrix2 = Transpose<[[1, 2, 3], [4, 5, 6]]>; // expected to be [[1, 4], [2, 5], [3, 6]]

문제 설명

• 행렬의 전치 연산을 수행
• 행렬의 행과 열을 바꾸어 새로운 행렬을 생성

시도 1

접근 방식

• 일단 눈물 좀 닦고...
• 행렬을 순회하면서, 각 행의 요소들을 모아서 새로운 행렬을 생성
• 이후 내부 행렬을 infer로 분리해서 같은 index로 모아서 새로운 행렬 생성

코드

type GetElementByIndex<
  T extends any[],
  Idx extends number,
  Cnt extends any[] = []
> = T extends [infer First, ...infer Rest]
  ? Cnt["length"] extends Idx
    ? First
    : GetElementByIndex<Rest, Idx, [...Cnt, unknown]>
  : never;

type PickColumn<M extends any[][], Idx extends number> = {
  [K in keyof M]: GetElementByIndex<M[K], Idx>;
};

type Transpose<M extends number[][]> = M extends [
  infer FirstRow extends any[],
  ...any
]
  ? { [K in keyof FirstRow]: PickColumn<M, Extract<K, number>> }
  : [];

코드 설명

• GetElementByIndex는 행렬의 요소를 인덱스로 조회하는 함수
• PickColumn은 행렬의 열을 추출하는 함수
• Transpose는 행렬의 전치 연산을 수행하는 함수

실패 이유

• 모두 never로 리턴

시도 2 (답지 참고)

접근 방식

코드

type Transpose<M extends number[][], R = M["length"] extends 0 ? [] : M[0]> = {
  [X in keyof R]: {
    [Y in keyof M]: X extends keyof M[Y] ? M[Y][X] : never;
  };
};

코드 설명

• 우선 R로 행렬의 첫 번째 행을 가져옴
• 이후 첫 번째 행을 순회하며, 각 키 값들을 바탕으로 새로운 열을 만듦
• 새로운 열에는 M[Y][X] 형식으로 값을 넣어줌
• 이후 새로운 열을 배열로 묶어서 리턴