Zenn
Closed18

type-challenges【extreme】

TypeScript
かしかし

GetReadonlyKeys

問題

Distributive conditional type を使って、 T のすべてのキーに対してそれぞれ操作を行う。
キーを Pick したものとそれに Readonly を付与したものが一致するならば、もともと readonly だったと言えるので、そのようなキーを集める。

type GetReadonlyKeys<T, K extends string | number | symbol = keyof T> =
  K extends keyof T
  ? Equal<Pick<T, K>, Readonly<Pick<T, K>>> extends true
    ? K
    : never
  : never;
かしかし

Query String Parser

問題

まず文字列を '&' で分割する。

type Split<T extends string, K extends string, Acc extends string[] = []> =
  T extends `${infer F}${K}${infer S}`
  ? Split<S, K, [...Acc, F]>
  : T extends ''
  ? Acc
  : [...Acc, T];

type x = Split<'k1=v1&k2=v2', '&'>;
// type x = ["k1=v1", "k2=v2"]

''k1=v1&k1=v1'' というテストケースがあるが、重複したクエリは無視する。
なので次のような Uniq を実装する。
先頭の要素を優先するために後ろから見ていき、その要素よりも前に等しい要素が存在するならば破棄する。

type Find<T extends any[], U> =
  T extends [infer Head, ...infer Tail]
  ? Equal<U, Head> extends true
    ? true
    : Find<Tail, U>
  : false;

type Uniq<T extends any[], Acc extends any[] = []> =
  T extends [...infer Init, infer Last]
  ? Find<Init, Last> extends true
    ? Uniq<Init>
    : Uniq<Init, [Last, ...Acc]>
  : Acc;

type x1 = Split<'k1=v1&k1=v1', '&'>;
// type x1 = ["k1=v1", "k1=v1"]
type x2 = Uniq<Split<'k1=v1&k1=v1', '&'>>;
// type x2 = ["k1=v1"]

KeyValue でクエリの文字列をキーと値に分割する。
'=' を含む場合は前半をキー、後半を値とする。
'=' を含まない場合は、文字列そのものをキーとして値は true とする。

クエリを先頭から見ていき、オブジェクトを構成する。
キーが共通なクエリの値はタプルで持つ。

type KeyValue<Q extends string> =
  Q extends `${infer K}=${infer V}`
  ? [K, V]
  : [Q, true];

type Merge<T extends Record<string, any[]>, Q extends string> =
  KeyValue<Q> extends [infer Key, infer Value]
  ? {
      [K in keyof T | (Key & string)]: 
        K extends Key
        ? K extends keyof T
          ? [...T[K], Value]
          : [Value]
        : K extends keyof T
          ? T[K]
          : never
    }
  : never;

type ComposeObject<Q extends string[], Acc extends Record<string, any[]> = {}> =
  Q extends [infer Head, ...infer Tail]
  ? Tail extends string[]
    ? ComposeObject<Tail, Merge<Acc, Head & string>>
    : never
  : Acc;

type x = ComposeObject<Uniq<Split<'k1=v1&k2=v2&k1=v2&k1=v3', '&'>>>;
type x = { k1: ["v1", "v2", "v3"]; k2: ["v2"]; }

要素数 1 のタプルは要素を取り出して完成

type UnwrapUnneccesaryTuple<O> = { [Key in keyof O]: O[Key] extends [infer X] ? X : O[Key] };

type ParseQueryString<T extends string> = UnwrapUnneccesaryTuple<ComposeObject<Uniq<Split<T, '&'>>>>;
かしかし

Slice

問題

ToIndexTuple で Start、End は扱いやすいように tuple に変換する。
また、負の数も与えられる。
長さ L の tuple Arrに対して Start や End が負の数 N のとき、 L + N = L - abs(N) で置き換える。

type NumberOfTuple<N extends string, Acc extends any[] = []> =
  `${Acc["length"]}` extends N
  ? Acc
  : NumberOfTuple<N, [...Acc, any]>;

type Minus<A extends any[], B extends any[]> =
  [A, B] extends [[infer _, ...infer ANext], [infer _, ...infer BNext]]
  ? Minus<ANext, BNext>
  : A;

type ToIndexTuple<N extends number, L extends number> =
  `${N}` extends `-${infer AbsN}`
  ? Minus<NumberOfTuple<`${L}`>, NumberOfTuple<AbsN>>
  : NumberOfTuple<`${N}`>;

Arr、 Start、 End をともに先頭から見ていく。
Start の長さが 0 でないとき、それぞれの先頭の要素を1つ破棄する。
Start の長さが 0 のとき、End の長さが 0 出なければ Arr の先頭の要素を Acc に追加する。
Arr か End の長さが 0 になったときに操作を終了する。

type SliceSub<Arr extends any[], Start extends any[], End extends any[], Acc extends any[] = []> =
  [Arr, End] extends [[infer Arr1, ...infer ArrNext], [infer _, ...infer EndNext]]
  ? Start extends [infer _, ...infer StartNext]
    ? SliceSub<ArrNext, StartNext, EndNext, Acc>
    : SliceSub<ArrNext, [], EndNext, [...Acc, Arr1]>
  : Acc;

type Slice<Arr extends any[], Start extends number = 0, End extends number = Arr["length"], L extends number = Arr["length"]> =
  SliceSub<Arr, ToIndexTuple<Start, L>, ToIndexTuple<End, L>>;
かしかし

Integers Comparator

問題

数字を符号と0以上の自然数の組に分割する。(0 の符号は常に + とする)
Template literal type で数字の文字列を生成し、その先頭に '-' が含まれるか否かで符号を判定する。
0 以上の自然数は tuple で表現する。

enum Sign {
  Pos,
  Neg
};

type NumberOfTuple<N extends string, Acc extends any[] = []> =
  `${Acc["length"]}` extends N
  ? Acc
  : NumberOfTuple<N, [...Acc, any]>;

type SignNum<N extends number> =
  `${N}` extends `-${infer AbsN}`
  ? [Sign.Neg, NumberOfTuple<AbsN>]
  : [Sign.Pos, NumberOfTuple<`${N}`>];

自然数同士の比較を行う。
tuple の長さを比較すればいいので、ともに1つずつ要素数を減らしていけば判定できる。

type Comp<Na, Nb> =
  Na extends [infer _, ...infer NaNext]
  ? Nb extends [infer _, ...infer NbNext]
    ? Comp<NaNext, NbNext>
    : Comparison.Greater
  : Nb extends []
  ? Comparison.Equal
  : Comparison.Lower;

符号を含めて数字の比較ができるようにする。
符号がともに '+' のときと '-' のときで Comp の引数の順番が逆になっている。
（A、B がともに負の数のとき、2数の大小関係とそれぞれの絶対値の大小関係が逆転するから）

type Comparator<A extends number, B extends number> =
  SignNum<A> extends [infer Sa, infer Na]
  ? SignNum<B> extends [infer Sb, infer Nb]
    ? [Sa, Sb] extends [Sign.Pos, Sign.Pos]
      ? Comp<Na, Nb>
      : [Sa, Sb] extends [Sign.Neg, Sign.Neg]
      ? Comp<Nb, Na>
      : [Sa, Sb] extends [Sign.Pos, Sign.Neg]
      ? Comparison.Greater
      : [Sa, Sb] extends [Sign.Neg, Sign.Pos]
      ? Comparison.Lower
      : never
    : never
  : never;
かしかし

Currying 2

問題

DynamicParamsCurrying の型 DynamicParamsCurryingType は引数として与えられた関数の引数と戻り値の型（Fargs と R）によって決まる。
DynamicParamsCurryingType は関数の型で、型 Args のいくつかの引数をとる。

type DynamicParamsCurryingType<Fargs extends any, R> = <Args extends any[]>(...args: Args) => any;

declare function DynamicParamsCurrying<Fargs extends any[], R>(fn: (...args: Fargs) => R): DynamicParamsCurryingType<Fargs, R>;

Fargs と Args を先頭から順に比較していく。
それぞれの先頭の要素（HeadF と HeadA）を比較する。
HeadA が HeadF の subtype になってなければならない。
subtype になっているときは Fargs と Args の先頭の要素を除いた引数同士で再帰的に計算する。
subtype にそうなってない場合は never とする。

この操作を Args の長さが0になるまで繰り返す。
Fargs と Args の長さが一致しているとき、 関数の戻り値の型 R になる。
そうでない場合、Fargs の残りを引数、戻り値を R とする関数として DynamicParamsCurryingType を返す。

また、 Args のほうが Fargs よりも長いときは引数の渡しすぎなので never とする。

type EvalCurry<Fargs extends any[], Args extends any[], R> =
  Fargs extends [infer HeadF, ...infer TailF]
  ? Args extends [infer HeadA, ...infer TailA]
    ? HeadA extends HeadF
      ? EvalCurry<TailF, TailA, R>
      : true
    : DynamicParamsCurryingType<Fargs, R>
  : Args extends []
  ? R
  : never;

type DynamicParamsCurryingType<Fargs extends any[], R> = <Args extends any[]>
  (...args: Args) => EvalCurry<Fargs, Args, R>;
かしかし

Sum

問題

一桁の自然数を表現する、1桁の文字列と文字列を tuple に変換する型を用意する。

type DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type Digit = {
  '0' : [],
  '1' : [any],
  '2' : [any, any],
  '3' : [any, any, any],
  '4' : [any, any, any, any],
  '5' : [any, any, any, any, any],
  '6' : [any, any, any, any, any, any],
  '7' : [any, any, any, any, any, any, any],
  '8' : [any, any, any, any, any, any, any, any],
  '9' : [any, any, any, any, any, any, any, any, any],
};

筆算の足し算のやり方で、一の位から順番に計算する。
2つの1桁の自然数と直前の桁で繰り上がりが存在するかの判定から、その桁の答えと次の桁への繰り上がりがあるかの判定を返す AddDigit を実装する。
A+B が2桁になっている場合は、繰り上がりがあり、かつその桁の答えが A+B の一の位になる。

type AddDigit<A extends any[], B extends any[], Carry extends boolean> =
  `${[...A, ...B, ...(Carry extends true ? [any] : [])]["length"] & number}` extends infer Sum
  ? Sum extends DigitString
    ? [Digit[Sum], false]
    : Sum extends `${infer C}${infer N}`
    ? [Digit[N & DigitString], C extends '1' ? true : false]
    : never
  : never;

type a = AddDigit<[any, any, any], [any, any, any, any], false> // 3 + 4
// type a = [[any, any, any, any, any, any, any], false] // 答えが 7 で繰り上がりなし
type b = AddDigit<[any, any, any, any, any, any, any], [any, any, any, any, any], true> // 7 + 5 + 1
// type b = [[any, any, any], true] // 答えが 3 で繰り上がりあり

数字の文字列から一の位の数だけ分離する GetOnePlace を実装する。
一桁の数字を表す literal の union type の DigitString を用意する。
与えられた文字の最後の一文字を DigitString でマッチングさせて、最後の一文字を除く Init を推論する。
最後の文字 One は N と Init を使って推論できる。
便宜上、文字列が空文字列ならば One は '0'、 Init は空文字列とする。

type GetOnePlace<N extends string | number | bigint> =
  `${N}` extends `${infer Init}${DigitString}`
  ? `${N}` extends `${Init}${infer One}`
    ? [One, Init]
    : never
  : ['0', ''];

これらを組み合わせて Sum を実装する。
A と B から GetOnePlace で一の位の数を取ってきて、 AddDigit でその桁の答えと繰り上がりを求める。
求めたその桁の答えは Acc の先頭に追加し、再帰的に計算を続ける。
A と B がともに空文字列になっていて、かつ繰り上がりが無くなったときに計算を終了する。

type Sum<A extends string | number | bigint, B extends string | number | bigint, Carry extends boolean = false, Acc extends string = ''> =
  [A, B, Carry] extends ['', '', false]
  ? Acc
  : GetOnePlace<A> extends [infer OneA, infer NextA]
  ? GetOnePlace<B> extends [infer OneB, infer NextB]
    ? AddDigit<Digit[OneA & DigitString], Digit[OneB & DigitString], Carry> extends [infer S, infer NextCarry]
      ? Sum<NextA & string, NextB & string, NextCarry & boolean, `${(S & any[])["length"]}${Acc}`>
      : never
    : never
  : never;
実装全体
type DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type Digit = {
  '0' : [],
  '1' : [any],
  '2' : [any, any],
  '3' : [any, any, any],
  '4' : [any, any, any, any],
  '5' : [any, any, any, any, any],
  '6' : [any, any, any, any, any, any],
  '7' : [any, any, any, any, any, any, any],
  '8' : [any, any, any, any, any, any, any, any],
  '9' : [any, any, any, any, any, any, any, any, any],
};

type GetOnePlace<N extends string | number | bigint> =
  `${N}` extends `${infer Init}${DigitString}`
  ? `${N}` extends `${Init}${infer One}`
    ? [One, Init]
    : never
  : ['0', ''];

type AddDigit<A extends any[], B extends any[], Carry extends boolean> =
  `${[...A, ...B, ...(Carry extends true ? [any] : [])]["length"] & number}` extends infer Sum
  ? Sum extends DigitString
    ? [Digit[Sum], false]
    : Sum extends `${infer C}${infer N}`
    ? [Digit[N & DigitString], C extends '1' ? true : false]
    : never
  : never;

type Sum<A extends string | number | bigint, B extends string | number | bigint, Carry extends boolean = false, Acc extends string = ''> =
  [A, B, Carry] extends ['', '', false]
  ? Acc
  : GetOnePlace<A> extends [infer OneA, infer NextA]
  ? GetOnePlace<B> extends [infer OneB, infer NextB]
    ? AddDigit<Digit[OneA & DigitString], Digit[OneB & DigitString], Carry> extends [infer S, infer NextCarry]
      ? Sum<NextA & string, NextB & string, NextCarry & boolean, `${(S & any[])["length"]}${Acc}`>
      : never
    : never
  : never;
かしかし

AddDigit が正しいことは、足し算の筆算で繰り上がりが2以上にならないことを示せばよい。
一の位は繰り上がりがないので、2つの一桁の自然数の和の最大値は18となり、繰り上がりの数は最大で1。
下の桁の繰り上がりが0か1ならば、繰り上がりと2つの一桁の自然数の和の最大値が19となり、繰り上がりは2以上にならない。
以上のことから、数学的帰納法で示せる。

かしかし

Multiply

問題

Sum と同様に筆算と同じような方式で実装したい。
掛け算の筆算では、繰り上がりが 0か1 だけでなく 0から9になる（厳密には 0から8 までだが、簡単のために厳密にしない）

Sum の AddDigit に相当するような、一桁の自然数の積を計算する MultDigit を実装する。
AddDigit と異なり、繰り上がりとして一桁の自然数が使えるようにする必要がある。
積は B の数だけ A を足し合わせて求める。 AddDigit と同様に、その桁の答えと繰り上がりの数を求める。

type MultDigit<A extends any[], B extends any[], Carry extends any[], Acc extends any[] = Carry> =
  B extends [infer _, ...infer NextB]
  ? MultDigit<A, NextB, Carry, [...Acc, ...A]>
  : `${Acc["length"]}` extends infer Prod
  ? Prod extends DigitString
    ? [Prod, []]
    : Prod extends `${infer C}${infer N}`
    ? [N, Digit[C & DigitString]]
    : never
  : never;

type a = MultDigit<[any, any, any], [any, any], []>; // 3 * 2
// type a = ["6", []] // 答えが6で繰り上がりは0
type b = MultDigit<[any, any, any, any, any, any], [any, any, any, any, any, any, any], [any, any, any]>; // 6 * 7 + 3
// type b = ["5", [any, any, any, any]] // 答えが5で繰り上がりが4

一旦、B が一桁の自然数であるという制約をつけて積を求められるようにする。
A の一の位と B の積と下の桁からの繰り上がりから、その桁の答え P と次の桁への繰り上がり NextCarry を求める。
Sum と同じように、A が空文字列になるか繰り上がりが無くなるまで再帰的に計算する。

type MultiplySub<A extends string, B extends DigitString, Carry extends any[] = [], Acc extends string = ''> =
  [A, Carry] extends ['', []]
  ? Acc
  : GetOnePlace<A> extends [infer OneA, infer NextA]
    ? MultDigit<Digit[OneA & DigitString], Digit[B], Carry> extends [infer P, infer NextCarry]
      ? NextCarry extends any[]
        ? MultiplySub<NextA & string, B, NextCarry, `${P & string}${Acc}`>
        : never
      : never
    : never;

type a = MultiplySub<'12345', '4'>;
// type a = "49380"

B が2桁以上でも計算できるようにする。
B の最上位桁から MultiplySub を計算し、計算結果を Acc の10倍に加算していく。
文字列で表現された数字の10倍は、単に末尾に '0' を追加して表現できる。
加算のために、前問の Sum をそのまま使っている。

計算の都合で先頭に不要な0が付く場合があるので、それを取り除いたら完成。

type RemoveUseless0<N extends string> =
  N extends `0${infer M}`
  ? RemoveUseless0<M>
  : N extends ''
  ? '0'
  : N;

type Multiply<A extends string | number | bigint, B extends string | number | bigint, Acc extends string = ''> =
  `${B}` extends `${infer HeadB}${infer TailB}`
  ? Multiply<A, TailB, Sum<`${Acc}0`, MultiplySub<`${A}`, HeadB & DigitString>>>
  : RemoveUseless0<Acc>;
実装全体
type DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type Digit = {
  '0' : [],
  '1' : [any],
  '2' : [any, any],
  '3' : [any, any, any],
  '4' : [any, any, any, any],
  '5' : [any, any, any, any, any],
  '6' : [any, any, any, any, any, any],
  '7' : [any, any, any, any, any, any, any],
  '8' : [any, any, any, any, any, any, any, any],
  '9' : [any, any, any, any, any, any, any, any, any],
};

type GetOnePlace<N extends string | number | bigint> =
  `${N}` extends `${infer Init}${DigitString}`
  ? `${N}` extends `${Init}${infer One}`
    ? [One, Init]
    : never
  : ['0', ''];

type RemoveUseless0<N extends string> =
  N extends `0${infer M}`
  ? RemoveUseless0<M>
  : N extends ''
  ? '0'
  : N;

type AddDigit<A extends any[], B extends any[], Carry extends boolean> =
  `${[...A, ...B, ...(Carry extends true ? [any] : [])]["length"] & number}` extends infer Sum
  ? Sum extends DigitString
    ? [Digit[Sum], false]
    : Sum extends `${infer C}${infer N}`
    ? [Digit[N & DigitString], C extends '1' ? true : false]
    : never
  : never;

type Sum<A extends string | number | bigint, B extends string | number | bigint, Carry extends boolean = false, Acc extends string = ''> =
  [A, B, Carry] extends ['', '', false]
  ? Acc
  : GetOnePlace<A> extends [infer OneA, infer NextA]
  ? GetOnePlace<B> extends [infer OneB, infer NextB]
    ? AddDigit<Digit[OneA & DigitString], Digit[OneB & DigitString], Carry> extends [infer S, infer NextCarry]
      ? Sum<NextA & string, NextB & string, NextCarry & boolean, `${(S & any[])["length"]}${Acc}`>
      : never
    : never
  : never;

type MultDigit<A extends any[], B extends any[], Carry extends any[], Acc extends any[] = Carry> =
  B extends [infer _, ...infer NextB]
  ? MultDigit<A, NextB, Carry, [...Acc, ...A]>
  : `${Acc["length"]}` extends infer Prod
  ? Prod extends DigitString
    ? [Prod, []]
    : Prod extends `${infer C}${infer N}`
    ? [N, Digit[C & DigitString]]
    : never
  : never;

type MultiplySub<A extends string, B extends DigitString, Carry extends any[] = [], Acc extends string = ''> =
  [A, Carry] extends ['', []]
  ? Acc
  : GetOnePlace<A> extends [infer OneA, infer NextA]
    ? MultDigit<Digit[OneA & DigitString], Digit[B], Carry> extends [infer P, infer NextCarry]
      ? NextCarry extends any[]
        ? MultiplySub<NextA & string, B, NextCarry, `${P & string}${Acc}`>
        : never
      : never
    : never;

type Multiply<A extends string | number | bigint, B extends string | number | bigint, Acc extends string = ''> =
  `${B}` extends `${infer HeadB}${infer TailB}`
  ? Multiply<A, TailB, Sum<`${Acc}0`, MultiplySub<`${A}`, HeadB & DigitString>>>
  : RemoveUseless0<Acc>;
かしかし

Subtract

問題

順番が前後するが、ついでなのでやる。
最後のテストケースがエラーになってるのは、再帰の上限に引っかかってるからだと思う。
これは再帰でやることを想定しているっぽいが、この解法は MinusOne の中で一般化した Minus を使えばできる。

https://zenn.dev/link/comments/5a2b831826da34

ここでは、もう少し大きい数字の計算までできるようにした Subtract を実装する。
ただし、テストケースの expected を文字列にする必要がある。

基本的には Sum と同じ方法でよさそう。
違いは繰り上がりではなく繰り下がりになる点。
繰り下がりが必要な場合は、上の桁から 10 を借りてきて計算を続ける（再帰呼び出しをしているところでは、9 (=10-1) を渡している）。

type SubtractDigit<A extends any[], B extends any[], Borrow extends boolean, ResultBorrow extends boolean = false> =
  Borrow extends true
  ? SubtractDigit<A, [...B, any], false>
  : B extends [infer _, ...infer NextB]
    ? A extends [infer _, ...infer NextA]
      ? SubtractDigit<NextA, NextB, false, ResultBorrow>
      : ResultBorrow extends true
      ? never // 繰り下がりは2回発生しない
      : SubtractDigit<Digit['9'], NextB, false, true>
    : [A, ResultBorrow]

type a = SubtractDigit<[any, any, any], [any], false> // 3 - 1
// type a = [[any, any], false] // 答えは2で繰り下がりなし
type b = SubtractDigit<[any, any, any], [any, any, any, any, any, any], true> // 3 - (6 + 1)
// type b = [[any, any, any, any, any, any, any], true] // 答えは7で繰り下がりあり

あとは Sum と同様に一の位から順番に SubtractDigit を適用していく。
引かれる数も引く数も 0 なのに最後に繰り下がりが残っている場合は、引く数のほうが大きいということなので never にする。
最後に不要な0も削除する。

type Subtract<M extends string | number | bigint, S extends string | number | bigint, Borrow extends boolean = false, Acc extends string = ''> =
  [M, S] extends ['', '']
  ? Borrow extends true
    ? never
    : RemoveUseless0<Acc>
  : GetOnePlace<M> extends [infer OneM, infer NextM]
  ? GetOnePlace<S> extends [infer OneS, infer NextS]
    ? SubtractDigit<Digit[OneM & DigitString], Digit[OneS & DigitString], Borrow> extends [infer Diff, infer NextBorrow]
      ? Subtract<NextM & string, NextS & string, NextBorrow & boolean, `${(Diff & any[])["length"]}${Acc}`>
      : never
    : never
  : never;
実装全体
type DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type Digit = {
  '0' : [],
  '1' : [any],
  '2' : [any, any],
  '3' : [any, any, any],
  '4' : [any, any, any, any],
  '5' : [any, any, any, any, any],
  '6' : [any, any, any, any, any, any],
  '7' : [any, any, any, any, any, any, any],
  '8' : [any, any, any, any, any, any, any, any],
  '9' : [any, any, any, any, any, any, any, any, any],
};

type RemoveUseless0<N extends string> =
  N extends `0${infer M}`
  ? RemoveUseless0<M>
  : N extends ''
  ? '0'
  : N;

type GetOnePlace<N extends string | number | bigint> =
  `${N}` extends `${infer Init}${DigitString}`
  ? `${N}` extends `${Init}${infer One}`
    ? [One, Init]
    : never
  : ['0', ''];

type SubtractDigit<A extends any[], B extends any[], Borrow extends boolean, ResultBorrow extends boolean = false> =
  Borrow extends true
  ? SubtractDigit<A, [...B, any], false>
  : B extends [infer _, ...infer NextB]
    ? A extends [infer _, ...infer NextA]
      ? SubtractDigit<NextA, NextB, false, ResultBorrow>
      : ResultBorrow extends true
      ? never
      : SubtractDigit<Digit['9'], NextB, false, true>
    : [A, ResultBorrow];

type Subtract<M extends string | number | bigint, S extends string | number | bigint, Borrow extends boolean = false, Acc extends string = ''> =
  [M, S] extends ['', '']
  ? Borrow extends true
    ? never
    : RemoveUseless0<Acc>
  : GetOnePlace<M> extends [infer OneM, infer NextM]
  ? GetOnePlace<S> extends [infer OneS, infer NextS]
    ? SubtractDigit<Digit[OneM & DigitString], Digit[OneS & DigitString], Borrow> extends [infer Diff, infer NextBorrow]
      ? Subtract<NextM & string, NextS & string, NextBorrow & boolean, `${(Diff & any[])["length"]}${Acc}`>
      : never
    : never
  : never;
かしかし

Divider（オリジナル）

ついでに割り算を実装する。

先頭から一桁ずつ計算していくと、答えが 0~9 になる割り算の繰り返しで解くことができる。（証明は割り算の筆算を思うと自明っぽい）。
答えが必ず一桁になるような割り算を解くDividerSub は Subtract を使って、割られる数 A から割る数 B を引けるだけ引く。
引いた回数が商、引けなくなる直前の A の値があまりになる。

type DividerSub<A extends string, B extends string, Cand extends DigitString = '0', Count extends any[] = [any]> =
  Subtract<A, B> extends infer NextA
  ? [NextA] extends [never]
    ? [Cand, A]
    : DividerSub<NextA & string, B, `${Count["length"]}` & DigitString, [...Count, any]> 
  : never;

Divider は「前回までのあまり Reminder を10倍した数に割られる数 A の先頭を足したもの、を B で割る」という操作を DividerSub を使って繰り返す。

type Divider<A extends string | number | bigint, B extends string | number | bigint, Quotient extends string = '', Reminder extends string = ''> =
  `${A}` extends `${infer HeadA}${infer TailA}`
  ? DividerSub<`${Reminder}${HeadA}`, `${B}`> extends [infer DigitQuotient, infer NextReminder]
    ? Divider<TailA, B, `${Quotient}${DigitQuotient & string}`, NextReminder & string>
    : never
  : { quotient: RemoveUseless0<Quotient>, reminder: Reminder};
実装全体
type DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

type Digit = {
  '0' : [],
  '1' : [any],
  '2' : [any, any],
  '3' : [any, any, any],
  '4' : [any, any, any, any],
  '5' : [any, any, any, any, any],
  '6' : [any, any, any, any, any, any],
  '7' : [any, any, any, any, any, any, any],
  '8' : [any, any, any, any, any, any, any, any],
  '9' : [any, any, any, any, any, any, any, any, any],
};

type RemoveUseless0<N extends string> =
  N extends `0${infer M}`
  ? RemoveUseless0<M>
  : N extends ''
  ? '0'
  : N;

type GetOnePlace<N extends string | number | bigint> =
  `${N}` extends `${infer Init}${DigitString}`
  ? `${N}` extends `${Init}${infer One}`
    ? [One, Init]
    : never
  : ['0', ''];

type SubtractDigit<A extends any[], B extends any[], Borrow extends boolean, ResultBorrow extends boolean = false> =
  Borrow extends true
  ? SubtractDigit<A, [...B, any], false>
  : B extends [infer _, ...infer NextB]
    ? A extends [infer _, ...infer NextA]
      ? SubtractDigit<NextA, NextB, false, ResultBorrow>
      : ResultBorrow extends true
      ? never
      : SubtractDigit<Digit['9'], NextB, false, true>
    : [A, ResultBorrow];

type Subtract<M extends string | number | bigint, S extends string | number | bigint, Borrow extends boolean = false, Acc extends string = ''> =
  [M, S] extends ['', '']
  ? Borrow extends true
    ? never
    : RemoveUseless0<Acc>
  : GetOnePlace<M> extends [infer OneM, infer NextM]
  ? GetOnePlace<S> extends [infer OneS, infer NextS]
    ? SubtractDigit<Digit[OneM & DigitString], Digit[OneS & DigitString], Borrow> extends [infer Diff, infer NextBorrow]
      ? Subtract<NextM & string, NextS & string, NextBorrow & boolean, `${(Diff & any[])["length"]}${Acc}`>
      : never
    : never
  : never;

type DividerSub<A extends string, B extends string, Cand extends DigitString = '0', Count extends any[] = [any]> =
  Subtract<A, B> extends infer NextA
  ? [NextA] extends [never]
    ? [Cand, A]
    : DividerSub<NextA & string, B, `${Count["length"]}` & DigitString, [...Count, any]> 
  : never;

type Divider<A extends string | number | bigint, B extends string | number | bigint, Quotient extends string = '', Reminder extends string = ''> =
  `${A}` extends `${infer HeadA}${infer TailA}`
  ? DividerSub<`${Reminder}${HeadA}`, `${B}`> extends [infer DigitQuotient, infer NextReminder]
    ? Divider<TailA, B, `${Quotient}${DigitQuotient & string}`, NextReminder & string>
    : never
  : { quotient: RemoveUseless0<Quotient>, reminder: Reminder};

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

type cases = [
  Expect<Equal<Divider<36, 6>, { quotient: '6', reminder: '0' }>>,
  Expect<Equal<Divider<47, 5>, { quotient: '9', reminder: '2' }>>,
  Expect<Equal<Divider<494, 14>, { quotient: '35', reminder: '4' }>>,
  Expect<Equal<Divider<20, 467>, { quotient: '0', reminder: '20' }>>,
  Expect<Equal<Divider<2862, 31>, { quotient: '92', reminder: '10' }>>,
  Expect<Equal<Divider<12345678, 4321>, { quotient: '2857', reminder: '581' }>>,
];
かしかし

Tag

問題

条件が多いので、上の条件から順番に満たすように型を定義していく。

代入

次のケースが解けるように実装する

https://github.com/type-challenges/type-challenges/blob/88812626578f86b7084bf623262ef32f0227238e/questions/00697-extreme-tag/test-cases.ts#L6-L59

付与された Tag をオプショナルなキーとして扱うことで、元の型が一致しているときに代入可能な型になる。
UnTag は、付与したキーを排除する型として定義する。
この定義で通るので一旦よしとする。（元の型のキーと一致する Tag を付与するとバグりそうだけど、いったんここでは目をつぶる）

type Tag<B, T extends string> = B & { [Key in T]?: unknown }
type UnTag<B> = { [Key in keyof B as Pick<B, Key> extends Required<Pick<B, Key>> ? Key : never ]: B[Key] }

型が null | undefined の場合

https://github.com/type-challenges/type-challenges/blob/88812626578f86b7084bf623262ef32f0227238e/questions/00697-extreme-tag/test-cases.ts#L71-L72

型が null や undefined の場合に、 Tag を付与せずにそのまま返すように指示されているので、そのように Tag と UnTag を修正する。

type Tag<B, T extends string> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : B & { [Key in T]?: unknown };

type UnTag<B> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : { [Key in keyof B as Pick<B, Key> extends Required<Pick<B, Key>> ? Key : never ]: B[Key] }

Tag を string のキーとして追加しない

https://github.com/type-challenges/type-challenges/blob/88812626578f86b7084bf623262ef32f0227238e/questions/00697-extreme-tag/test-cases.ts#L73

現状の実装で、 type k = keyof Tag<{ x: 0 }, 'foo'> & string は type k = 'x' | 'foo' となる。

Tag は、キーとして string 以外を取るようにしたい。
値を Tag を表すオブジェクトのキーとして unique symbol を使うことにする。

https://www.typescriptlang.org/docs/handbook/symbols.html#unique-symbol

併せて UnTag も修正する。

declare const Tagged: unique symbol;
type TaggedKey = typeof Tagged;

type Tag<B, T extends string> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : B & { [Key in TaggedKey]?: { T: unknown } };

type UnTag<B> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : { [Key in keyof B & string]: B[Key] };

Tag で埋め込んだ情報を GetTags で取り出せるようにする。

まず、 GetTags が与えられたタグをすべて取り出せるように、 Tag で適切に情報を埋め込めるようにする必要がある。
Tag が次のような型になってるとよさそうである。
{ 0: 0 } がないと代入がうまくいかない（プロパティがすべてオプショナルになるのが問題？よくわかってない）。
タグのタプルのキーになってる文字列は、代入可能にするために付与したタグによって一意に定まる必要がある。
ここでは、タグに '|' を含む文字列が登場しないことを前提に実装している。

GetTags は ['b'] や ['a', 'b'] の部分を抜き取るといい。

declare let x2: Tag<I, 'b'>
// x2: I & { [Tagged]?: { 0: 0 } & { 'b'?: ['b'] } }
declare let x3: Tag<Tag<I, 'a'>, 'b'>
// x3: I & { [Tagged]?: { 0: 0 } & { 'a|b'?: ['a', 'b'] } }

これを構成するために、 Tags と GetTags を実装する。

type TaggedDefault = { 0: 0 }; // 代入可能にするために必要

type GetNextTagsKey<B, NewTag extends string> =
  [B] extends [{ [Key in TaggedKey]?: TaggedDefault & infer T }] // B が never なケースに対応するため Tuple でラップしてる
  ? Equal<T, unknown> extends true
    ? NewTag
    : `${keyof T & string}|${NewTag}`
  : NewTag;

type GetTags<B, T = TaggedKey extends keyof B ? Exclude<B[TaggedKey], undefined> : {}> =
  true extends Equal<B, null> | Equal<B, undefined> | Equal<B, any> // B が null か undefined か any のとき
  ? []
  : Equal<keyof T & string, never> extends true
    ? []
    : T[keyof T & string] extends infer Tags
    ? Tags extends string[]
      ? Tags
      : never
    : [];

type Tag<B, T extends string, TagsOrNever extends string[] = GetTags<B>, NextTagsKey extends string = GetNextTagsKey<B, T>> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : Omit<B, TaggedKey>
    & {
        [Key in TaggedKey]?:
          TaggedDefault
          & {
              [Key in NextTagsKey]?: Equal<TagsOrNever, never> extends true ? [T] : [...TagsOrNever, T]
            }
      };

HasTag / HasTags / HasExactTags

タプルの要素が連続して含まれていることを検知する IsIncludedArray を使って HasTag と HasTags 次のように実装する。
IsIncludedArray は、InSquence を使って連続しているか否かを判定する。
HasExactTags は一致をみるだけ

type IsIncludedArray<As extends any[], Bs extends any[], InSquence extends boolean = false> =
  As extends [infer HeadA, ...infer TailA]
  ? Bs extends [infer HeadB, ...infer TailB]
    ? Equal<HeadA, HeadB> extends true
      ? IsIncludedArray<TailA, TailB, true>
      : InSquence extends true
      ? false
      : IsIncludedArray<As, TailB, false> // As と Bs の先頭要素が異なるなら、Bs から先頭を除いたものと As を比較する
    : false
  : true;

type HasTag<B, T extends string, BTags extends string[] = GetTags<B>> =
  IsIncludedArray<[T], BTags>;

type HasTags<B, Ts extends string[], BTags extends string[] = GetTags<B>> =
  IsIncludedArray<Ts, BTags>;

type HasExactTags<B, Ts extends string[], BTags extends string[] = GetTags<B>> = Equal<BTags, Ts>;
実装全体
type IsIncludedArray<As extends any[], Bs extends any[], InSquence extends boolean = false> =
  As extends [infer HeadA, ...infer TailA]
  ? Bs extends [infer HeadB, ...infer TailB]
    ? Equal<HeadA, HeadB> extends true
      ? IsIncludedArray<TailA, TailB, true>
      : InSquence extends true
      ? false
      : IsIncludedArray<As, TailB, false> // As と Bs の先頭要素が異なるなら、Bs から先頭を除いたものと As を比較する
    : false
  : true;

declare const Tagged: unique symbol;
type TaggedKey = typeof Tagged;
type TaggedDefault = { 0: 0 }; // 代入可能にするために必要

type GetNextTagsKey<B, NewTag extends string> =
  [B] extends [{ [Key in TaggedKey]?: TaggedDefault & infer T }] // B が never なケースに対応するため Tuple でラップしてる
  ? Equal<T, unknown> extends true
    ? NewTag
    : `${keyof T & string}|${NewTag}`
  : NewTag;

type GetTags<B, T = TaggedKey extends keyof B ? Exclude<B[TaggedKey], undefined> : {}> =
  true extends Equal<B, null> | Equal<B, undefined> | Equal<B, any> // B が null か undefined か any のとき
  ? []
  : Equal<keyof T & string, never> extends true
    ? []
    : T[keyof T & string] extends infer Tags
    ? Tags extends string[]
      ? Tags
      : never
    : [];

type Tag<B, T extends string, TagsOrNever extends string[] = GetTags<B>, NextTagsKey extends string = GetNextTagsKey<B, T>> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : Omit<B, TaggedKey>
    & {
        [Key in TaggedKey]?:
          TaggedDefault
          & {
              [Key in NextTagsKey]?: Equal<TagsOrNever, never> extends true ? [T] : [...TagsOrNever, T]
            }
      };

type UnTag<B> =
  Equal<B, null> extends true
  ? B
  : Equal<B, undefined> extends true
  ? B
  : { [Key in keyof B & string]: B[Key] };

type HasTag<B, T extends string, BTags extends string[] = GetTags<B>> =
  IsIncludedArray<[T], BTags>;

type HasTags<B, Ts extends string[], BTags extends string[] = GetTags<B>> =
  IsIncludedArray<Ts, BTags>;

type HasExactTags<B, Ts extends string[], BTags extends string[] = GetTags<B>> = Equal<BTags, Ts>;

参考

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

かしかし

Inclusive Range

問題

カウントアップする Count と、 Lower と Higher の間にいることを記憶している InRange を使って再帰的に処理する。
Count と Lower / Higher の関係や InRange の状態によって分岐させる。
開始と終了が一致しているときだけ特別な扱いが必要で、一番最初に処理しておく

type InclusiveRange<Lower extends number, Higher extends number, InRange extends boolean = false, Count extends any[] = [], Acc extends number[] = []> =
  Lower extends Higher
  ? [Lower]
  : Count["length"] extends Higher
  ? InRange extends true
    ? [...Acc, Higher]
    : []
  : InRange extends true
  ? InclusiveRange<Lower, Higher, InRange, [...Count, any], [...Acc, Count["length"]]>
  : Count["length"] extends Lower
  ? InclusiveRange<Lower, Higher, true, [...Count, any], [...Acc, Count["length"]]>
  : InclusiveRange<Lower, Higher, false, [...Count, any]>;
かしかし

Sort

問題

クイックソートの要領で解く。
先頭要素を Pivot とし、 Pivot を基準に残りの要素を2つのグループに分割する。
Desc のフラグに応じて Left と Right の順番を逆にすることで、ソート順を決められる。

type Sort<Xs extends number[], Desc extends boolean = false> =
  Xs extends [infer Pivot, ...infer Others]
  ? Others extends number[]
    ? Grouping<Pivot & number, Others> extends [infer Left, infer Right]
      ? Left extends number[]
        ? Right extends number[]
          ? Desc extends true
            ? [...Sort<Right, Desc>, Pivot, ...Sort<Left, Desc>]
            : [...Sort<Left, Desc>, Pivot, ...Sort<Right, Desc>]
          : never
        : never
      : never
    : never
  : [];

Grouping は Pivot と配列の要素を比較し、Pivot 以上とそれ以外で分類する。
自然数の大小を比較する Comp と併せて次のように実装したら完成。

type NumberOfTuple<N extends number, Acc extends any[] = []> =
  Acc["length"] extends N
  ? Acc
  : NumberOfTuple<N, [...Acc, any]>;

type Comp<A extends number, B extends number, Ta extends any[] = NumberOfTuple<A>, Tb extends any[] = NumberOfTuple<B>> =
  Ta extends [infer _, ...infer TailA]
  ? Tb extends [infer _, ...infer TailB]
    ? Comp<A, B, TailA, TailB>
    : -1
  : Tb extends []
    ? 0
    : 1;

type Grouping<Pivot extends number, Xs extends number[], Left extends number[] = [], Right extends number[] = []> =
  Xs extends [infer Head, ...infer Tail]
  ? Head extends number
    ? Tail extends number[]
      ? Comp<Pivot, Head> extends -1
        ? Grouping<Pivot, Tail, [...Left, Head], Right>
        : Grouping<Pivot, Tail, Left, [...Right, Head]>
      : never
    : never
  : [Left, Right];
かしかし

Assert Array Index

問題

for文のインデックスを型安全に指定するための型を作るという問題。
インデックスがその配列に対して有効であることの判定は key というユニークな文字列を使って行う。

Assertion typing を使って、 assertArrayIndex が呼ばれた後の型の制約をつける。

https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-7.html#assertion-functions

for文の中で Index<typeof matrix> 型の値 i を < で比較したり i+=1 のように数値の計算をしたりしているので、 Index<T> は number の subtyping になっている必要がありそう。
一旦こんな感じで assertArrayIndex の型に asserts をつけてみる。

function assertArrayIndex<Array extends readonly unknown[], Key extends string>(
  array: Array,
  key: Key
): asserts array is Array & { [I in 0 | 1 | 2]: Array[number] }  {}

type Index<Array> = 0 | 1 | 2;

出力を観察してみると、 次のことが分かった

  • assertArrayIndex の key が異なると Index<Array> の型が異なるので、 Array は key の情報を保持する
  • matrix[0] のような具体的な数字を使って値を取り出す場合は X | undefined の型になる

Assertion typing で array の型に Key の情報を埋め込むことができる。
GetIndex という Key の型によってインデックスとなる型を返す多相型を使って次のように実装することで、 ここまで解決することができた。
（配列の具体的なインデックスと衝突しないように、 GetIndex の型は負の数とした）

type GetIndex<T extends string> = T extends "columns" ? -1 : T extends "rows" ? -2 : never;

function assertArrayIndex<Array extends readonly unknown[], Key extends string>(
  array: Array,
  key: Key
): asserts array is Array & { key: Key } & { [I in GetIndex<Key>]: Array[number] }  {}

type Index<Array extends { key: string }> = GetIndex<Array["key"]>;

現状の GetKey は、取りうるすべてのキーに対して列挙できないので、何か実装方法を考える必要がある。
Key のアルファベットを 0/1 の符号に変換し、数字のリテラルの Union type を構成することで解決できそう。
StringBit で、文字列に対応した 0/1 で構成された文字列を得ることができる。
GetIndex は StringBit で変換した 0/1 の文字列を使って数字のリテラルの Union type を構成する。

type Nums = [
   -1,  -2,  -3,  -4,  -5,  -6,  -7,  -8,  -9, -10,
  -11, -12, -13, -14, -15, -16, -17, -18, -19, -20,
  -21, -22, -23, -24, -25, -26, -27, -28, -29, -30,
  -31, -32, -33, -34, -35, -36, -37, -38, -39, -40,
  -41, -42, -43, -44, -45, -46, -47, -48, -49, -50,
  -51, -52, -53, -54, -55, -56, -57, -58, -59, -60,
  -61, -62, -63, -64, -65, -66, -67, -68, -69, -70,
  -71, -72, -73, -74, -75, -76, -77, -78, -79, -80,
  -81, -82, -83, -84, -85, -86, -87, -88, -89, -90,
  -91, -92, -93, -94, -95, -96, -97, -98, -99, -100,
  -101, -102, -103, -104, -105, -106, -107, -108, -109,-110,
  -111, -112, -113, -114, -115, -116, -117, -118, -119, -120,
  -121, -122, -123, -124, -125, -126, -127, -128, -129, -130,
  -131, -132, -133, -134, -135, -136, -137, -138, -139, -140,
  -141, -142, -143, -144, -145, -146, -147, -148, -149, -150,
  -151, -152, -153, -154, -155, -156, -157, -158, -159, -160,
  -161, -162, -163, -164, -165, -166, -167, -168, -169, -170,
  -171, -172, -173, -174, -175, -176, -177, -178, -179, -180,
  -181, -182, -183, -184, -185, -186, -187, -188, -189, -190,
  -191, -192, -193, -194, -195, -196, -197, -198, -199, -200,
]

type AlphabetBit = {
  'a': '00001',
  'b': '00010',
  'c': '00011',
  'd': '00100',
  'e': '00101',
  'f': '00110',
  'g': '00111',
  'h': '01000',
  'i': '01001',
  'j': '01010',
  'k': '01011',
  'l': '01100',
  'm': '01101',
  'n': '01110',
  'o': '01111',
  'p': '10000',
  'q': '10001',
  'r': '10010',
  's': '10011',
  't': '10100',
  'u': '10101',
  'v': '10110',
  'w': '10111',
  'x': '11000',
  'y': '11001',
  'z': '11010',
}

type StringBit<T extends string, Acc extends string = ''> =
  T extends `${infer Head}${infer Tail}`
  ? StringBit<Tail, `${Acc}${AlphabetBit[keyof AlphabetBit & Head]}`>
  : Acc;

type GetIndex<Key extends string, KeyBit extends string = StringBit<Key>, Count extends any[] = [], Acc extends number = never> =
  Count["length"] extends Nums["length"]
  ? never
  : KeyBit extends `0${infer NextKeyBit}`
  ? GetIndex<Key, NextKeyBit, [...Count, any], Acc>
  : KeyBit extends `1${infer NextKeyBit}`
  ? GetIndex<Key, NextKeyBit, [...Count, any], Acc | Nums[Count["length"]]>
  : Acc;


type a = StringBit<'pikachu'>;
// type a = "10000010010101100001000110100010101"
type b = StringBit<'dedenne'>;
// type b = "00100001010010000101011100111000101"

この実装だと、 'a' が作る Union type が 'c' が作る Union type の subtyping になってしまう。
これは bit 演算において 1 | 3 = 3 になることに由来する。
https://github.com/type-challenges/type-challenges/blob/8316fc4441f568f694b179adfb934fc587a57f1b/questions/00925-extreme-assert-array-index/test-cases.ts#L70

_7 C_3 = 35 でアルファベットの文字数を超えるので、AlphabetBit を0を4文字と1を3文字の長さ7の 0/1 で構成される文字列で、かつ、ある文字列の1の登場するbitの集合がほかの文字列の1の登場するbitの集合の部分集合にならないような文字列を構成する。

type AlphabetBit = {
  'a': '1110000',
  'b': '1101000',
  'c': '1100100',
  'd': '1100010',
  'e': '1100001',
  'f': '1011000',
  'g': '1010100',
  'h': '1010010',
  'i': '1010001',
  'j': '1001100',
  'k': '1001010',
  'l': '1001001',
  'm': '1000110',
  'n': '1000101',
  'o': '1000011',
  'p': '0111000',
  'q': '0110100',
  'r': '0110010',
  's': '0110001',
  't': '0101100',
  'u': '0101010',
  'v': '0101001',
  'w': '0100110',
  'x': '0100101',
  'y': '0100011',
  'z': '0011100',
};

最後に、引数 array に tuple を渡すと型エラーになるようにする。
配列と tuple の型の違いには、 length プロパティが前者は number に、後者は具体的な数字のリテラル（1、2、とか）になることがある。

type IsTuple<T extends readonly any[]> = number extends T["length"] ? false : true;

function assertArrayIndex<Array extends readonly unknown[], Key extends string>(
  array: IsTuple<Array> extends true ? never : Array,
  key: Key
): asserts array is (IsTuple<Array> extends true ? never : Array) & { key: Key } & { [I in GetIndex<Key>]: Array[number] }  {}
実装全体

type IsTuple<T extends readonly any[]> = number extends T["length"] ? false : true;

type Nums = [
   -1,  -2,  -3,  -4,  -5,  -6,  -7,  -8,  -9, -10,
  -11, -12, -13, -14, -15, -16, -17, -18, -19, -20,
  -21, -22, -23, -24, -25, -26, -27, -28, -29, -30,
  -31, -32, -33, -34, -35, -36, -37, -38, -39, -40,
  -41, -42, -43, -44, -45, -46, -47, -48, -49, -50,
  -51, -52, -53, -54, -55, -56, -57, -58, -59, -60,
  -61, -62, -63, -64, -65, -66, -67, -68, -69, -70,
  -71, -72, -73, -74, -75, -76, -77, -78, -79, -80,
  -81, -82, -83, -84, -85, -86, -87, -88, -89, -90,
  -91, -92, -93, -94, -95, -96, -97, -98, -99, -100,
  -101, -102, -103, -104, -105, -106, -107, -108, -109,-110,
  -111, -112, -113, -114, -115, -116, -117, -118, -119, -120,
  -121, -122, -123, -124, -125, -126, -127, -128, -129, -130,
  -131, -132, -133, -134, -135, -136, -137, -138, -139, -140,
  -141, -142, -143, -144, -145, -146, -147, -148, -149, -150,
  -151, -152, -153, -154, -155, -156, -157, -158, -159, -160,
  -161, -162, -163, -164, -165, -166, -167, -168, -169, -170,
  -171, -172, -173, -174, -175, -176, -177, -178, -179, -180,
  -181, -182, -183, -184, -185, -186, -187, -188, -189, -190,
  -191, -192, -193, -194, -195, -196, -197, -198, -199, -200,
]

type AlphabetBit = {
  'a': '1110000',
  'b': '1101000',
  'c': '1100100',
  'd': '1100010',
  'e': '1100001',
  'f': '1011000',
  'g': '1010100',
  'h': '1010010',
  'i': '1010001',
  'j': '1001100',
  'k': '1001010',
  'l': '1001001',
  'm': '1000110',
  'n': '1000101',
  'o': '1000011',
  'p': '0111000',
  'q': '0110100',
  'r': '0110010',
  's': '0110001',
  't': '0101100',
  'u': '0101010',
  'v': '0101001',
  'w': '0100110',
  'x': '0100101',
  'y': '0100011',
  'z': '0011100',
};

type StringBit<T extends string, Acc extends string = ''> =
  T extends `${infer Head}${infer Tail}`
  ? StringBit<Tail, `${Acc}${AlphabetBit[keyof AlphabetBit & Head]}`>
  : Acc;

type GetIndex<Key extends string, KeyBit extends string = StringBit<Key>, Count extends any[] = [], Acc extends number = never> =
  Count["length"] extends Nums["length"]
  ? never
  : KeyBit extends `0${infer NextKeyBit}`
  ? GetIndex<Key, NextKeyBit, [...Count, any], Acc>
  : KeyBit extends `1${infer NextKeyBit}`
  ? GetIndex<Key, NextKeyBit, [...Count, any], Acc | Nums[Count["length"]]>
  : Acc;

function assertArrayIndex<Array extends readonly unknown[], Key extends string>(
  array: IsTuple<Array> extends true ? never : Array,
  key: Key
): asserts array is (IsTuple<Array> extends true ? never : Array) & { key: Key } & { [I in GetIndex<Key>]: Array[number] }  {}

type Index<Array extends { key: string }> = GetIndex<Array["key"]>;

参考

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

かしかし

JSON Parser

問題

Utility type がいくつか用意されているけど責務は明示されていないので、まず方針を立てる。

  • Tokenize... 文字列を Token の tuple に分割する
  • ParseResult ... Token の tuple を先頭から見ていき、型を生成する（生成に使わなかった余りの Token も返す）
  • ParseLiteral ... 与えらえた Token を過不足なくすべて使って型を生成する

Tokenize

まずは Token を定義する。かっことカンマ、コロンといくつかのリテラルを用意すると十分そう。Tokenize で処理をしやすいように、 Blank も用意しておく。
Tokenize では、まず Token に続く文字列 Rest を検出して、改めて Token の部分を推論することで簡潔に実装した。
テストコードには、改行やエスケープ文字を含むものもあるので、それらにも対応しておく。

type StringLiteral = `"${string}"`;
type PrimitiveLiteral = "true" | "false" | "null" | StringLiteral;
type Token = "{" | "}" | "[" | "]" | "," | ":" | PrimitiveLiteral;

type Blank = " " | "\n";

type Unescape<T extends string, Acc extends string = ""> =
  T extends `\n${infer _}`
  ? never  
  : T extends `\\r${infer R}`
  ? Unescape<R, `${Acc}\r`>
  : T extends `\\n${infer R}`
  ? Unescape<R, `${Acc}\n`>
  : T extends `\\b${infer R}`
  ? Unescape<R, `${Acc}\b`>
  : T extends `\\f${infer R}`
  ? Unescape<R, `${Acc}\f`>
  : T extends `${infer C}${infer R}`
  ? Unescape<R, `${Acc}${C}`>
  : Acc;

type Tokenize<T extends string, Acc extends Token[] = []> =
  T extends `${Blank}${infer Rest}`
  ? Tokenize<Rest, Acc>
  : T extends `${Token}${infer Rest}`
  ? T extends `${infer First}${Rest}`
    ? First extends `"${infer Y}"`
      ? Tokenize<Rest, [...Acc, `"${Unescape<Y>}"` & StringLiteral]>
      : Tokenize<Rest, [...Acc, First & Token]>
    : never
  : Acc;

ParseResult

ParseResult は ParseObjectRestul、ParseArrayResult、ParsePrimitiveLiteral で構成する。
ParsePrimitiveLiteral は単純な実装

type ParseStringLiteral<T extends StringLiteral> = T extends `"${infer X}"` ? X : never;

type ParsePrimitiveLiteral<T extends PrimitiveLiteral> =
  T extends StringLiteral
  ? ParseStringLiteral<T>
  : T extends "true"
  ? true
  : T extends "false"
  ? false
  : T extends "null"
  ? null
  : never;

type ParseResult<T extends Token[]> =
  T[0] extends "{"
  ? ParseObjectResult<T>
  : T[0] extends "["
  ? ParseArrayResult<T>
  : T extends [PrimitiveLiteral, ...infer Rest]
  ? [ParsePrimitiveLiteral<T[0]>, Rest]
  : never;

ParseArrayResult は、次のように実装した。
Expected で T の先頭の Token に制約をかけている。
先頭が "," / "]" でないときは何らかのオブジェクトを取得できるはずなので、 ParseResult を再帰的に呼び出している。

type ParseArrayResult<T extends Token[], Acc extends any[] = [], Expected extends Token = "["> =
  T extends [Expected, ...infer Rest]
  ? Rest extends Token[]
    ? Equal<Expected, "["> extends true // 先頭の "[" は特別に処理する
      ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{" | "]">
      : T[0] extends ","
      ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{">
      : T[0] extends "]"
      ? [Acc, Rest]
      : ParseResult<T> extends [infer Obj, infer Rest]
      ? Rest extends Token[]
        ? ParseArrayResult<Rest, [...Acc, Obj], "]" | ",">
        : never
      : never
    : never
  : never;

ParseObjectResult は次のように実装した。
ParseArrayResult との違いは、オブジェクトのキーに該当する StringLiteral を検知したときの処理を追加していること。あとは大体同じような実装。

type ParseObjectResult<T extends Token[], Acc extends object = {}, Key extends string | undefined = undefined, Expected extends Token = "{"> =
  Key extends string
  ? (
      ParseResult<T> extends [infer Obj, infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, SetProperty<Acc, Key, Obj>, undefined, "}" | ",">
        : never
      : never
  ) : (
    T[0] extends Expected
    ? T extends [StringLiteral, ":", ...infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, Acc, ParseStringLiteral<T[0]>, PrimitiveLiteral | "[" | "{">
        : never
      : T extends ["{" | ",", ...infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, Acc, undefined, StringLiteral | "}">
        : never
      : T extends ["}", ...infer Rest]
      ? Rest extends Token[]
        ? [Acc, Rest]
        : never
      : never
    : never
  );

ParseLiteral

ParseResult を呼び出し、あまりの Token がないことを確認する

type ParseLiteral<T extends Token[]> =
  ParseResult<T> extends [infer Obj, infer Rest]
  ? Rest extends []
    ? [Obj, Rest]
    : never
  : never;
実装全体
type Pure<T> = {
  [P in keyof T]: T[P] extends object ? Pure<T[P]> : T[P]
}

type SetProperty<T, K extends PropertyKey, V> = {
  [P in (keyof T) | K]: P extends K ? V : P extends keyof T ? T[P] : never
}

type StringLiteral = `"${string}"`;
type PrimitiveLiteral = "true" | "false" | "null" | StringLiteral;
type Token = "{" | "}" | "[" | "]" | "," | ":" | PrimitiveLiteral;

type Blank = " " | "\n";

type Unescape<T extends string, Acc extends string = ""> =
  T extends `\n${infer _}`
  ? never
  : T extends `\\r${infer R}`
  ? Unescape<R, `${Acc}\r`>
  : T extends `\\n${infer R}`
  ? Unescape<R, `${Acc}\n`>
  : T extends `\\b${infer R}`
  ? Unescape<R, `${Acc}\b`>
  : T extends `\\f${infer R}`
  ? Unescape<R, `${Acc}\f`>
  : T extends `${infer C}${infer R}`
  ? Unescape<R, `${Acc}${C}`>
  : Acc;

type Tokenize<T extends string, Acc extends Token[] = []> =
  T extends `${Blank}${infer Rest}`
  ? Tokenize<Rest, Acc>
  : T extends `${Token}${infer Rest}`
  ? T extends `${infer First}${Rest}`
    ? First extends `"${infer Y}"`
      ? Tokenize<Rest, [...Acc, `"${Unescape<Y>}"` & StringLiteral]>
      : Tokenize<Rest, [...Acc, First & Token]>
    : never
  : Acc;

type ParseStringLiteral<T extends StringLiteral> = T extends `"${infer X}"` ? X : never;

type ParsePrimitiveLiteral<T extends PrimitiveLiteral> =
  T extends StringLiteral
  ? ParseStringLiteral<T>
  : T extends "true"
  ? true
  : T extends "false"
  ? false
  : T extends "null"
  ? null
  : never;

type ParseObjectResult<T extends Token[], Acc extends object = {}, Key extends string | undefined = undefined, Expected extends Token = "{"> =
  Key extends string
  ? (
      ParseResult<T> extends [infer Obj, infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, SetProperty<Acc, Key, Obj>, undefined, "}" | ",">
        : never
      : never
  ) : (
    T[0] extends Expected
    ? T extends [StringLiteral, ":", ...infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, Acc, ParseStringLiteral<T[0]>, PrimitiveLiteral | "[" | "{">
        : never
      : T extends ["{" | ",", ...infer Rest]
      ? Rest extends Token[]
        ? ParseObjectResult<Rest, Acc, undefined, StringLiteral | "}">
        : never
      : T extends ["}", ...infer Rest]
      ? Rest extends Token[]
        ? [Acc, Rest]
        : never
      : never
    : never
  );

type ParseArrayResult<T extends Token[], Acc extends any[] = [], Expected extends Token = "["> =
  T extends [Expected, ...infer Rest]
  ? Rest extends Token[]
    ? Equal<Expected, "["> extends true
      ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{" | "]">
      : T[0] extends ","
      ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{">
      : T[0] extends "]"
      ? [Acc, Rest]
      : ParseResult<T> extends [infer Obj, infer Rest]
      ? Rest extends Token[]
        ? ParseArrayResult<Rest, [...Acc, Obj], "]" | ",">
        : never
      : never
    : never
  : never;

type ParseResult<T extends Token[]> =
  T[0] extends "{"
  ? ParseObjectResult<T>
  : T[0] extends "["
  ? ParseArrayResult<T>
  : T extends [PrimitiveLiteral, ...infer Rest]
  ? [ParsePrimitiveLiteral<T[0]>, Rest]
  : never;

type ParseLiteral<T extends Token[]> =
  ParseResult<T> extends [infer Obj, infer Rest]
  ? Rest extends []
    ? [Obj, Rest]
    : never
  : never;

type Parse<T extends string> = Pure<ParseLiteral<Tokenize<T>>[0]>;

参考

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

かしかし

他の人の回答を見て気づいたけど、 infer に続けて extends を書くと、型の推論まで一緒にできて楽に表記できるらしい
もっと早く気づきたかった。

https://devblogs.microsoft.com/typescript/announcing-typescript-4-7/#extends-constraints-on-infer-type-variables

ParseArrayResult や ParseObjectResult も短くかける

type ParseObjectResult<T extends Token[], Acc extends object = {}, Key extends string | undefined = undefined, Expected extends Token = "{"> =
  Key extends string
  ? (
      ParseResult<T> extends [infer Obj, infer Rest extends Token[]]
      ? ParseObjectResult<Rest, SetProperty<Acc, Key, Obj>, undefined, "}" | ",">
      : never
  ) : (
    T[0] extends Expected
    ? T extends [StringLiteral, ":", ...infer Rest extends Token[]]
      ? ParseObjectResult<Rest, Acc, ParseStringLiteral<T[0]>, PrimitiveLiteral | "[" | "{">
      : T extends ["{" | ",", ...infer Rest extends Token[]]
      ? ParseObjectResult<Rest, Acc, undefined, StringLiteral | "}">
      : T extends ["}", ...infer Rest extends Token[]]
      ? [Acc, Rest]
      : never
    : never
  );

type ParseArrayResult<T extends Token[], Acc extends any[] = [], Expected extends Token = "["> =
  T extends [Expected, ...infer Rest extends Token[]]
  ? Equal<Expected, "["> extends true
    ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{" | "]">
    : T[0] extends ","
    ? ParseArrayResult<Rest, Acc, PrimitiveLiteral | "[" | "{">
    : T[0] extends "]"
    ? [Acc, Rest]
    : ParseResult<T> extends [infer Obj, infer Next extends Token[]]
    ? ParseArrayResult<Next, [...Acc, Obj], "]" | ",">
    : never
  : never;
このスクラップは2022/11/03にクローズされました