型パズルを好きになるために、競プロを型システムだけで解いてみることにした

TypeScript の型システムに興味を持ち、「type-challenges」で学ぼうとしましたが、思ったよりも難しく、すぐに挫折してしまいました。しかし、私は競技プログラミングが好きで、アルゴリズムを解くのは得意です。そこで「型パズルを競プロのように解けば楽しく学べるのでは？」と考え、TypeScript の型システムだけを使って競プロの問題を解いてみることにしました。

TypeScript の型システムはチューリング完全であり、本質的にはプログラミングが可能です。型の推論や再帰型を駆使することで、典型的な競技プログラミングの問題を解くことに挑戦しました。本セッションでは、その試行錯誤の過程を共有しながら、型レベルプログラミングの面白さと難しさをお伝えします。型パズルを学ぶのが難しいと感じている方に向けて、新しいアプローチを提案できればと思います。

Transcript

1. 型パズルを好きになるために、 競プロを型システムだけで解いてみることにした いまいまい 1
2. 自己紹介 いまいまい (今井俊希) 株式会社ゆめみ 24卒 フロントエンドエンジニア 2
3. みんなは TS の型パズル好き？ 3
4. みんなは TS の型パズル好き？ 私は好きじゃなかった（過去形） infer ? extends ? satisfies ? 記号より意味が受け取りづらい単語がたくさん出てくる それが数珠繋ぎにつながってるので、難読英文読解みたいになる 4
5. type-challenges いっぱい型の問題がある いろんな人の回答を見れる 型に慣れられる よ〜し勉強するぞ〜 5
6. easy の時点でムズない？ 例）Awaited Await 型を自作する Promise の中の型を取ってくればいい type ExampleType = Promise<string>; type Result = MyAwaited<ExampleType>; // string // テストケース type X = Promise<string>; // ←わかる type Y = Promise<{ field: number }>; // ←わかる type Z = Promise<Promise<string | number>>; // ←わかる type Z1 = Promise<Promise<Promise<string | boolean>>>; // ←なるほど type T = { then: (onfulfilled: (arg: number) => any) => any }; // ←なんやこいつ 6
7. TSの型システム自体がチューリング完全らしい あるとき、一個の issue を見つける 7
8. 型システムだけでプログラミングできるやん せや、競プロやったろ 8
9. 気づく そもそも、型は文字列に出力できない const inputs = // 入力を受け取る type Result = Solve<typeof inputs> console.log(Result) // ←これできない ので、一旦ゴールを決定 const inputs = "固定の値"; type Result = Solve<typeof rawInput>; // この型の推論が答えと一致してればヨシ 9
10. 問題を解いてみよう 問題（概要） 「A 時 B 分」が締切で「C 時 D 分」に提出しました 間に合っているなら"Yes"、間に合わないなら"No"を出力 文字列 "A B C D"が与えられる // 普通に解いてみる const [A, B, C, D]: number[] = input.trim().split(" ").map(Number); if (A > C || (A == C && B > D)) return console.log("Yes"); console.log("No"); 10
11. 解く 1 type Split< S extends string, Acc extends string[] = [] > = S extends `${infer H} ${infer R}` ? Split<R, [...Acc, H]> : [...Acc, S]; 文字列を空白で区切って配列にする型 infer H で先頭の単語を取得 infer R で残りの文字列を取得 再帰的に処理して単語の配列を作る 11
12. 解く 2 type ToNumber<S extends string> = S extends `${infer N extends number}` ? N : never; 文字列を数値に変換する型 テンプレートリテラル型の特性を利用 infer N extends number で文字列が数値に変換可能か検証 変換可能なら数値型 N を返す 12
13. 解く 3 type LessThan< A extends number, B extends number, Arr extends unknown[] = [] > = Arr["length"] extends A ? Arr["length"] extends B ? false : true : Arr["length"] extends B ? false : LessThan<A, B, [unknown, ...Arr]>; Arr の長さを 1 ずつ増やしながら再帰 Arr["length"] extends A で A に到達したか判定 Arr["length"] extends B で B に到達したか判定 A に先に到達 → A < B → true を返す B に先に到達 → A > B → false を返す 13
14. 解く 4 type Earlier< A extends number, B extends number, C extends number, D extends number > = LessThan<C, A> extends true // 提出時の「時」が小さい ? true : A extends C // 同じ「時」なら「分」を比較 ? LessThan<D, B> extends true ? true : false : false; 時間の前後関係を判定するロジック 14
15. 解く 5 type Solve<S extends string> = Split<S> extends [ infer SA extends string, infer SB extends string, infer SC extends string, infer SD extends string ] ? Earlier<ToNumber<SA>, ToNumber<SB>, ToNumber<SC>, ToNumber<SD>> extends true ? "Yes" : "No" : never; 入力文字列から結果を判定する型 15
16. 解いた結果 // 締切: 22時40分 // 提出: 22時30分 const rawInput = "22 40 22 30"; type Result = Solve<typeof rawInput>; // "Yes" やったぜ 16
17. 学び ・Array["length"]で数字を表すあたりで黒魔術を感じた ・infer と extends を使った再帰的な型には慣れた（でかい） 17
18. 話せなかったこと ・AtCoder で提出して AC を取るまで ・DFS とかのアルゴリズムの時点で再帰の場合 18
19. ありがとうございました 型で苦しむなんでなんぼあってもいいですからね 19