Zenn
✍️

type-challengesのextremeレベルを解いてみた

2024/08/21に公開
TypeScript
tech

まえがき

チーム内でTypeScriptの学習法について話題に上がった際にこちらの問題集をメンバーからご共有頂きました。
type-challenges

普段はよく使うライブラリのソースコードを読んだり、OSSに参加したりしながら実践的にTypeScript力を鍛えているのですが、こういう問題集に挑戦するのも面白そう。
ということで、一番難しいレベルの「extreme」に記載されている問題について自分なりの解法と回答を記してみます。

あくまでも僕が個人的に考えたものなので最適な回答ではない可能性が高いです。
参考程度にお読みください。

5 - Get Readonly Keys

設問

オブジェクト型からreadonlyなプロパティのキーのみを抽出する汎用関数を作成する、という問題です。

解法

  1. 与えられた型引数 T から readonly であるプロパティのみを抜き出す
    1. 各プロパティが readonly であるかを判定する
      1. T のプロパティ K のみを readonly に置換したオブジェクトを作成する
        1. readonly な K を含むオブジェクトと K を除くオブジェクトの交差型を定義する
        2. 交差型を1つのオブジェクトとして統合する
      2. 作成したオブジェクトと T が完全に一致するかを比較する
  2. プロパティのキーを抽出する
// 1.1.1.1.
type GetReadonlyPropIntersection<T, U extends keyof T> = Readonly<Pick<T, U>> &
  Omit<T, U>

// 1.1.1.2.
type MergeIntersection<T> = {
  [K in keyof T]: T[K]
}

// 1.1.1.
type GetReadonlyPropObject<T, U extends keyof T> = MergeIntersection<
  GetReadonlyPropIntersection<T, U>
>

// 1.1.
type IsReadonlyProp<T, U extends keyof T> = Equal<
  T,
  GetReadonlyPropObject<T, U>
>

// 1.
type PickReadonlyProps<T> = {
  [K in keyof T as IsReadonlyProp<T, K> extends true ? K : never]: T[K]
}

// 2.
type GetReadonlyKeys<T> = keyof PickReadonlyProps<T>

回答

type Equal<A, B> = (<T>() => T extends A ? 1 : 2) extends <T>() => T extends B
  ? 1
  : 2
  ? true
  : false

type MergeIntersection<T> = {
  [K in keyof T]: T[K]
}

type GetReadonlyKeys<T> = keyof {
  [K in keyof T as Equal<
    T,
    MergeIntersection<Readonly<Pick<T, K>> & Omit<T, K>>
  > extends true
    ? K
    : never]: T[K]
}

151 - Query String Parser

設問

URLのクエリ文字列をオブジェクト型に変換する、という問題です。
要件として以下が追記されています。

  • クエリ文字列上で値を持たないキーについてはオブジェクトの値に true を設定する
  • クエリ文字列上に同一のキーで異なる値を持つものが存在する場合は、タプル型としてマージする
  • クエリ文字列中に1つだけ存在するキーの値はタプルではなく文字列型として設定する
  • 同一のキーが存在するが値も同じである場合はタプル化しない

解法

  1. クエリ文字列から重複するクエリを取り除く
    1. 入力文字列 T の先頭から "&" を検索し、1つ目のクエリ Q と残りの文字列 T1 に分割する
      1. "&" が存在する場合、 Q が出力済みクエリ U に含まれるかを判定する
        1. Q が出力済みの場合、 T1 に対して 1. の処理を再帰実行する
        2. Q が未出力の場合、 Q と T1 に対して 1. の処理を再帰実行したものを結合する
        3. 結合対象が空文字の場合は Q のみを、空文字以外の場合は "&" で結合した文字列を出力する
      2. "&"が存際しない場合、 T が出力済みクエリ U に含まれる場合は空文字を、含まれない場合は T を出力する
  2. 重複を除いたクエリ文字列をオブジェクトに変換する
    1. 与えられたクエリ文字列をオブジェクトに変換する
      1. クエリ文字列からキーのユニオン型を抽出する
        1. クエリ文字列をクエリ単位に分割したユニオン型に変換する
        2. クエリごとにキーを抽出する
      2. キーごとにクエリ文字列から値の型を生成する
        1. キーごとにクエリ文字列から値のタプル型を生成する
          1. クエリ文字列の先頭から順にクエリを取得する
          2. 取得したクエリから値をタプル型として取得する
          3. 取得したタプル型と残りのクエリ文字列に対して 2.1.2.1. を再帰実行したものをマージしたタプル型を出力する
        2. タプル型の要素が1つだけの場合は要素の型のみを取り出す
// 1.1.1.2.1.
type ConnectQueries<T extends string, U extends string> = U extends ''
  ? T
  : `${T}&${U}`

// 1.
type FilterUniqueQuery<
  T extends string,
  U extends string = ''
> =
  // 1.1.
  T extends `${infer Q}&${infer T1}`
  // 1.1.1.
  ? Q extends U
    // 1.1.1.1.
    ? FilterUniqueQuery<T1, U>
    // 1.1.1.2.
    : ConnectQueries<Q, FilterUniqueQuery<T1, U | Q>>
  // 1.1.2.
  : T extends U ? '' : T

// 2.1.1.
type SplitQueryString<T extends string> =
  // 2.1.1.1.
  T extends `${infer Q}&${infer T1}`
  ? Q | SplitQueryString<T1>
  : T

// 2.1.1.2.
type KeyOfQuery<T extends string> = T extends `${infer K}=${string}`
  ? K
  : T extends ''
  ? never
  : T

// 2.1.1.2.
type KeyOfQueryString<T extends string> = KeyOfQuery<SplitQueryString<T>>

// 2.1.2.1.2.
type ValueOfQueryKey<
  T extends string,
  K extends string
> = T extends `${K}=${infer V}` ? [V] : T extends K ? [true] : []

// 2.1.2.1.
type TupleValueOfQueryString<
  T extends string,
  K extends string
> =
  // 2.1.2.1.1.
  T extends `${infer U}&${infer T1}`
  // 2.1.2.1.3.
  ? [...ValueOfQueryKey<U, K>, ...TupleValueOfQueryString<T1, K>]
  : [...ValueOfQueryKey<T, K>]

// 2.1.2.2.
type UntupleSingle<T extends ReadonlyArray<string | boolean>> = T extends [
  infer U
]
  ? U
  : T

// 2.1.
type ParseFilteredQueryString<T extends string> = {
  [K in KeyOfQueryString<T>]: UntupleSingle<TupleValueOfQueryString<T, K>>
}

// 2.
type ParseQueryString<T extends string> = ParseFilteredQueryString<
  FilterUniqueQuery<T>
>

回答

type ConnectQueries<T extends string, U extends string> = U extends ''
  ? T
  : `${T}&${U}`

type FilterUniqueQuery<
  T extends string,
  U extends string = ''
> = T extends `${infer Q}&${infer T1}`
  ? Q extends U
    ? FilterUniqueQuery<T1, U>
    : ConnectQueries<Q, FilterUniqueQuery<T1, U | Q>>
  : T extends U ? '' : T

type SplitQueryString<T extends string> = T extends `${infer Q}&${infer T1}`
  ? Q | SplitQueryString<T1>
  : T

type KeyOfQuery<T extends string> = T extends `${infer K}=${string}`
  ? K : T extends '' ? never
  : T

type ValueOfQueryKey<
  T extends string,
  K extends string
> = T extends `${K}=${infer V}` ? [V] : T extends K ? [true] : []

type TupleValueOfQueryString<
  T extends string,
  K extends string
> = T extends `${infer U}&${infer T1}`
  ? [...ValueOfQueryKey<U, K>, ...TupleValueOfQueryString<T1, K>]
  : [...ValueOfQueryKey<T, K>]

type UntupleSingle<T extends ReadonlyArray<string | boolean>> = T extends [
  infer U
]
  ? U
  : T

type ParseFilteredQueryString<T extends string> = {
  [K in KeyOfQuery<SplitQueryString<T>>]: UntupleSingle<
    TupleValueOfQueryString<T, K>
  >
}

type ParseQueryString<T extends string> = ParseFilteredQueryString<
  FilterUniqueQuery<T>
>

216 - Slice

設問

Array.slice の型を表現する、という問題です。
これは前に作った TupleOf と LessEqual あたりの考え方が活かせそう。

解法

四則演算は使用できないので配列の length を再帰的に判定して結果を得ます。

  1. 開始位置 Start が設定されているかを判定
    1. Start が設定されている場合、Start が負の値（-から始まる値）かを判定
      1. 負の値の場合、結果の配列 SlicedArr の長さが Start の絶対値に一致するまで元の配列の要素を左から再帰的に別の配列 LeftSliced へ移動
      2. 負の値でない場合、元の配列の要素を左から別の配列 LeftSliced へ移動し、 LeftSliced の長さが Start に一致するまで再帰的に繰り返し、残った配列を SlicedArr とする
    2. Start が設定されていない場合、元の配列を返却
  2. 終了位置 End が設定されているかを判定
    1. End が設定されている場合、End が負の値（-から始まる値）かを判定
      1. 負の値の場合、1.1. で得た SlicedArr の要素を右から順に RightSliced へ移動し、RightSliced の長さが End の絶対値に一致したときの残りの配列を返却
      2. 負の値でない場合、1.1. で得た SlicedArr の要素を左から順に LeftSliced と結果用の配列へ移動し、 LeftSliced の長さが End に一致したときの結果用の配列を返却
    2. End が設定されていない場合、1.1. で得た SlicedArr を返却
// 1.1., 2.1.
type GetAbsoluteValueOfNegative<T extends number> =
  `${T}` extends `-${infer V extends number}` ? V : null

// 1.1.1.
type SplitByStartNegative<
  Arr extends any[],
  StartAbs extends number,
  LeftSliced extends any[] = []
> = Arr['length'] extends StartAbs
  ? [LeftSliced, Arr]
  : Arr extends [infer E, ...infer Arr1]
  ? SplitByStartNegative<Arr1, StartAbs, [...LeftSliced, E]>
  : [LeftSliced, []]

// 1.1.2.
type SplitByStartPositive<
  Arr extends any[],
  Start extends number,
  LeftSliced extends any[] = []
> = LeftSliced['length'] extends Start
  ? [LeftSliced, Arr]
  : Arr extends [infer E, ...infer Arr1]
  ? SplitByStartPositive<Arr1, Start, [...LeftSliced, E]>
  : [LeftSliced, []]

// 1.1.
type SliceFromStart<
  Arr extends any[],
  Start extends number
> = GetAbsoluteValueOfNegative<Start> extends infer StartAbs extends number
  ? SplitByStartNegative<Arr, StartAbs>
  : SplitByStartPositive<Arr, Start>

// 2.1.1.
type SliceToEndNegative<
  Arr extends any[],
  EndAbs extends number,
  RightSliced extends any[] = []
> = RightSliced['length'] extends EndAbs
  ? Arr
  : Arr extends [...infer Arr1, infer E]
  ? SliceToEndNegative<Arr1, EndAbs, [E, ...RightSliced]>
  : []

// 2.1.2.
type SliceToEndPositive<
  Arr extends any[],
  End extends number,
  LeftSliced extends any[],
  SlicedArr extends any[] = []
> = LeftSliced['length'] extends End
  ? SlicedArr
  : Arr extends [infer E, ...infer Arr1]
  ? SliceToEndPositive<Arr1, End, [...LeftSliced, E], [...SlicedArr, E]>
  : []

// 2.1.
type SliceToEnd<
  Arr extends any[],
  End extends number,
  LeftSliced extends any[]
> = GetAbsoluteValueOfNegative<End> extends infer EndAbs extends number
  ? SliceToEndNegative<Arr, EndAbs>
  : SliceToEndPositive<Arr, End, LeftSliced>

// 1., 2.
type Slice<
  Arr extends any[],
  Start extends number | undefined = undefined,
  End extends number | undefined = undefined
> =
  // 1.
  Start extends number
  // 1.1.
  ? SliceFromStart<Arr, Start> extends [
      infer LeftSliced extends any[],
      infer SlicedArr extends any[]
    ]
    // 2.
    ? End extends number
      // 2.1.
      ? SliceToEnd<SlicedArr, End, LeftSliced>
      // 2.2.
      : SlicedArr
    : never
  // 1.2.
  : Arr

回答

type GetAbsoluteValueOfNegative<T extends number> =
  `${T}` extends `-${infer V extends number}` ? V : null

type SplitByStartPositive<
  Arr extends any[],
  Start extends number,
  LeftSliced extends any[] = []
> = LeftSliced['length'] extends Start
  ? [LeftSliced, Arr]
  : Arr extends [infer E, ...infer Arr1]
  ? SplitByStartPositive<Arr1, Start, [...LeftSliced, E]>
  : [LeftSliced, []]

type SplitByStartNegative<
  Arr extends any[],
  StartAbs extends number,
  LeftSliced extends any[] = []
> = Arr['length'] extends StartAbs
  ? [LeftSliced, Arr]
  : Arr extends [infer E, ...infer Arr1]
  ? SplitByStartNegative<Arr1, StartAbs, [...LeftSliced, E]>
  : [LeftSliced, []]

type SliceToEndPositive<
  Arr extends any[],
  End extends number,
  LeftSliced extends any[],
  SlicedArr extends any[] = []
> = LeftSliced['length'] extends End
  ? SlicedArr
  : Arr extends [infer E, ...infer Arr1]
  ? SliceToEndPositive<Arr1, End, [...LeftSliced, E], [...SlicedArr, E]>
  : []

type SliceToEndNegative<
  Arr extends any[],
  EndAbs extends number,
  RightSliced extends any[] = []
> = RightSliced['length'] extends EndAbs
  ? Arr
  : Arr extends [...infer Arr1, infer E]
  ? SliceToEndNegative<Arr1, EndAbs, [E, ...RightSliced]>
  : []

type Slice<
  Arr extends any[],
  Start extends number | undefined = undefined,
  End extends number | undefined = undefined
> = Start extends number
  ? (
      GetAbsoluteValueOfNegative<Start> extends infer StartAbs extends number
        ? SplitByStartNegative<Arr, StartAbs>
        : SplitByStartPositive<Arr, Start>
    ) extends [infer LeftSliced extends any[], infer SlicedArr extends any[]]
    ? End extends number
      ? GetAbsoluteValueOfNegative<End> extends infer EndAbs extends number
        ? SliceToEndNegative<Arr, EndAbs>
        : SliceToEndPositive<Arr, End, LeftSliced>
      : SlicedArr
    : never
  : Arr

274 - Integers Comparator

設問

2つの数値 a と b を比較して、 a > b なら Comarison.Greater、a = b なら Comparison.Equal、a < b なら Comarison.Lower を返却する、という問題です。
こちらも前の設問と同じような数値の比較を行うことで解けそうです。

解法

失敗版

まずは前問と同様に何も考えず再帰的に判定する方法で書いてみましたが、こちらでは数値がある程度大きいと階層が深くなりすぎてエラーになりました。

enum Comparison {
  Greater,
  Equal,
  Lower
}

type IsEqual<A extends number, B extends number> = A extends B ? true : false

type GetAbsoluteOfNegative<T extends number> =
  `${T}` extends `-${infer Abs extends number}` ? Abs : null

type ComparePositiveValues<
  A extends number,
  B extends number,
  PileArr extends true[] = []
> = A extends PileArr['length']
  ? Comparison.Lower
  : B extends PileArr['length']
  ? Comparison.Greater
  : ComparePositiveValues<A, B, [true, ...PileArr]>

type Comparator<A extends number, B extends number> = IsEqual<A, B> extends true
  ? Comparison.Equal
  : [GetAbsoluteOfNegative<A>, GetAbsoluteOfNegative<B>] extends [
      infer An extends number | null,
      infer Bn extends number | null
    ]
  ? An extends number
    ? Bn extends number
      ? ComparePositiveValues<Bn, An>
      : Comparison.Lower
    : Bn extends null
    ? ComparePositiveValues<A, B>
    : Comparison.Greater
  : never

修正版

以上の失敗を踏まえて、数値の値をそのまま比較するのではなく、桁数の比較と桁ごとの比較に分割することで処理を軽量化しました。

  1. 2つの値 A と B が同値ならば Comparison.Equal を返却
  2. A と B が異なる場合
    1. A が負の値（ - から始まる数値）の場合
      1. B が負の値の場合
        1. A と B の絶対値を比較する
          1. Aの桁数 > Bの桁数の場合、 A < B < 0 なので Comparison.Lower を返却
          2. Aの桁数 < Bの桁数の場合、 0 > A > B なので Comparison.Greater を返却
          3. Aの桁数 = Bの桁数の場合
      2. B が負の値でない場合、 A < 0 ≦ B なので Comparison.Lower を返却
    2. A が負の値でない場合
      1. B が負の値でない場合
        1. A と B の値を比較する
      2. B が負の値の場合、 A ≧ 0 > B なので Comparison.Greater を返却
enum Comparison {
  Greater,
  Equal,
  Lower
}

type NumStringToDigits<
  T extends string,
  Arr extends number[] = []
> = T extends `${infer D extends number}${infer U extends string}`
  ? NumStringToDigits<U, [...Arr, D]>
  : Arr

type NumberToDigits<T extends number> = NumStringToDigits<`${T}`>

type IsNegative<T extends number> = `${T}` extends `-${number}` ? true : false

type Absolute<T extends number> = `${T}` extends `-${infer Abs extends number}`
  ? Abs
  : T

type CompareSmallAbs<
  A extends number,
  B extends number,
  Count extends 1[] = []
> = A extends B
  ? Comparison.Equal
  : A extends Count['length']
  ? Comparison.Lower
  : B extends Count['length']
  ? Comparison.Greater
  : CompareSmallAbs<A, B, [1, ...Count]>

type ShiftAndGetRest<T extends number[]> = T extends [
  number,
  ...infer T1 extends number[]
]
  ? T1
  : never

type CompareDigitsIfEqual<
  C extends Comparison,
  A extends number[],
  B extends number[]
> = C extends Comparison.Equal
  ? CompareDigitsIfEqual<
      CompareSmallAbs<A[0], B[0]>,
      ShiftAndGetRest<A>,
      ShiftAndGetRest<B>
    >
  : C

type CompareDigits<
  A extends number[],
  B extends number[]
> = CompareDigitsIfEqual<CompareSmallAbs<A['length'], B['length']>, A, B>

type CompareAbs<A extends number, B extends number> = CompareDigits<
  NumberToDigits<A>,
  NumberToDigits<B>
>

type CompareDifferentNumbers<
  A extends number,
  B extends number
> = IsNegative<A> extends true
  ? IsNegative<B> extends true
    ? CompareAbs<Absolute<B>, Absolute<A>>
    : Comparison.Lower
  : IsNegative<B> extends false
  ? CompareAbs<A, B>
  : Comparison.Greater

type Comparator<A extends number, B extends number> = A extends B
  ? Comparison.Equal
  : CompareDifferentNumbers<A, B>

462 - Currying 2

設問

与えられた関数についてカリー化できるようにする、という問題です。
具体的には関数が N 個の引数を持っているとして、まず N1 個の引数を与えるとまだ与えられていない (N - N1) 個の引数を求める関数が出力され、次に N2 個の引数を与えるとさらに残りの (N - N1 - N2) 個の引数を求める関数が出力されて・・・、というように N1 + N2 + ... が N に合致するまで多重のカリー化ができるような型を定義します。

解法

引数の配列を指定された範囲で区切って新しい配列を作る、という考え方は前の問題が応用できそうです。

回答

type LessEqualArrLength<
  Arr extends any[],
  Counter extends number[] = []
> = Counter['length'] extends Arr['length']
  ? [...Counter, Counter['length']][number]
  : LessEqualArrLength<Arr, [...Counter, Counter['length']]>

type LeftSubArray<
  Arr extends any[],
  Length extends number,
  Result extends any[] = []
> = Result['length'] extends Length
  ? Result
  : Arr extends [infer E, ...infer Arr1]
  ? LeftSubArray<Arr1, Length, [...Result, E]>
  : never

type LeftSubArrayUnion<Args extends any[], Length extends number> = {
  [L in Length]: LeftSubArray<Args, L>
}[Length]

type ShiftArray<Arr extends any[]> = Arr extends [any, ...infer Arr1]
  ? Arr1
  : never

type RightSubArray<
  Arr extends any[],
  Counter extends any[]
> = Counter['length'] extends 0
  ? Arr
  : RightSubArray<ShiftArray<Arr>, ShiftArray<Counter>>

type CurriedFn<Args extends any[], R> = Exclude<
  LessEqualArrLength<Args>,
  0
> extends infer Length extends number
  ? <Args1 extends LeftSubArrayUnion<Args, Length>>(
      ...args: Args1
    ) => Args1['length'] extends Args['length']
      ? R
      : CurriedFn<RightSubArray<Args, Args1>, R>
  : never

declare function DynamicParamsCurrying<Args extends any[], R>(
  fn: (...args: Args) => R
): CurriedFn<Args, R>

あとがき

全体的にいかに再帰処理を組み立てるかが重要となる印象でした。
基本的にはTypeScriptの公式ハンドブックに載っている内容を網羅できていれば解けるけど、配列の長さが数値リテラルとして取れることとかは実践してみないとわからないですね。

いい頭の体操になって楽しかった。

Discussion