🔢

ネストされた配列の特定の要素を弄るジェネリクス型（TypeScriptの型レベルプログラミングでマインスイーパー: 中編）

2025/05/30に公開

TypeScript

記事投稿コンテスト「TypeScriptでやってみた挑戦・学び・工夫」

tech

はじめに

こんにちは。yossuli です。
本日（日付がすでに回ってしまいましたが...）#tskaigi_after_talk_afk に参加してきました。

なんと！個人的タイムリーな型レベルの世界の LT が！！！
型レベル純粋関数の世界が広がっていったら楽しそうですね()

さて、この記事は前回に引き続き、TypeScript の型レベルプログラミングを使ってマインスイーパーを作る方法を考えていきます。
今回の記事だけ読んでも学びがあるように作成しましたが、お時間がある方は前回の記事も読んでいただけるとうれしいです！

また、近日中に続編を公開する予定ですので、そちらもぜひご覧ください。

本題

まずは本記事のみご覧になっていただいた方のために、今回作成した型の要点だけ説明します。

type RandomsBitsPair<
  Seed extends Bit[],
  n extends number,
  size extends number,
  acc extends number[][] = []
> = acc["length"] extends n
  ? acc
  : Random<Seed> extends infer RandomSeed extends Bit[]
  ? Random<RandomSeed> extends infer RRandomSeed extends Bit[]
    ? [
        genIndex<RRandomSeed, size>,
        genIndex<RandomSeed, size>
      ] extends infer randomPair extends [number, number]
      ? randomPair extends acc[number]
        ? Random<RRandomSeed> extends infer RRR extends Bit[]
          ? RandomsBitsPair<RRR, n, size, acc>
          : never
        : RandomsBitsPair<RRandomSeed, n, size, [randomPair, ...acc]>
      : never
    : never
  : never;

この型は、n 個のランダムなペアを生成するためのものです。
G<A> extends infer B のように infer で全てを抽出することで型を再利用できるようにしています
- そして、Random<Seed> のように再帰的に Seed を更新していきます。
また、acc[number] ですでに生成したペアを展開して、現在追加しようとしている座標があてはまるかをチェックすることで、重複を避けています。
- ここまで複雑でも値の情報を number や string 等に抽象化せずに計算してくれる TypeScript の型システムはすごいですね...

type ____SetBomb<
  Field extends string[],
  Bombs extends number[][],
  K extends number,
  acc extends string[] = []
> = Field extends [infer _, ...infer Rest extends string[]]
  ? [acc["length"], K] extends Bombs[number]
    ? ____SetBomb<Rest, Bombs, K, [...acc, "B"]>
    : ____SetBomb<Rest, Bombs, K, [...acc, "_"]>
  : acc;

この型は、フィールドに爆弾をセットするためのものです。
Bombs は爆弾の位置を表す 2 次元配列で、K は現在の行番号を展開前の型から受け取ります。
再帰しながらタプル同士で比較して、その座標に爆弾をセットすべきかを分岐しています。
- RandomsBitsPair 同様に [number] を用いて展開しています。
なぜか配列をマップしているはずなのにオブジェクトとして扱われてしまって困ったので再帰にしています。
- 再帰だと確実にタプルの構造を維持されるのがうれしみポイントです。(処理が重いですが...)

以下はマインスイーパーに特化した説明になりますので、マインスイーパーに興味がない方はここまでで大丈夫です。

手順

ランダムな bits の配列をボムの数*2(次元)の長さで生成
1. ランダムにするために生成された bits を Seed として再帰的に使用
2. 重複があるといけないので、重複チェックをする
3. 配列の生成ついでに [number, number] にしておく
  - 重複のチェックも行いやすい
生成された [number, number][] をもとに、フィールドに爆弾をセット

2**n

type Pow2<Bits extends string[]> = Bits extends [
  infer _,
  ...infer Rest extends string[]
]
  ? [...Pow2<Rest>, ...Pow2<Rest>]
  : [""];

長さと要素をとって配列を生成

type ArrayFrom<T, N extends number, R extends T[] = []> = R["length"] extends N
  ? R
  : ArrayFrom<T, N, [...R, T]>;

Bit[] -> number

type __Bit2Dec<Bits extends string[]> = Bits extends [
  infer F,
  ...infer Rest extends string[]
]
  ? F extends "1"
    ? [...Pow2<Rest>, ...__Bit2Dec<Rest>]
    : F extends string
    ? __Bit2Dec<Rest>
    : [""]
  : [];

ランダムな座標の配列

type genIndex<SEED extends Bit[], Size extends number> = Bit2Dec<
  Mod2n<Random<SEED>, ArrayFrom<"1", Size>>
>;
type RandomsBitsPair<
  Seed extends Bit[],
  n extends number,
  size extends number,
  acc extends number[][] = []
> = acc["length"] extends n
  ? acc
  : Random<Seed> extends infer RandomSeed extends Bit[]
  ? Random<RandomSeed> extends infer RRandomSeed extends Bit[]
    ? [
        genIndex<RRandomSeed, size>,
        genIndex<RandomSeed, size>
      ] extends infer randomPair extends [number, number]
      ? randomPair extends acc[number]
        ? Random<RRandomSeed> extends infer RRR extends Bit[]
          ? RandomsBitsPair<RRR, n, size, acc>
          : never
        : RandomsBitsPair<RRandomSeed, n, size, [randomPair, ...acc]>
      : never
    : never
  : never;

フィールドに爆弾をセット

type ____SetBomb<
  Field extends string[],
  Bombs extends number[][],
  K extends number,
  acc extends string[] = []
> = Field extends [infer _, ...infer Rest extends string[]]
  ? [acc["length"], K] extends Bombs[number]
    ? ____SetBomb<Rest, Bombs, K, [...acc, "B"]>
    : ____SetBomb<Rest, Bombs, K, [...acc, "_"]>
  : acc;

type __SetBomb<
  Field extends string[][],
  Bombs extends number[][],
  acc extends string[][] = []
> = Field extends [infer F extends string[], ...infer Rest extends string[][]]
  ? __SetBomb<Rest, Bombs, [...acc, ____SetBomb<F, Bombs, acc["length"]>]>
  : acc;

type SetBomb<Field extends string[][], Bombs extends number[][]> = __SetBomb<
  Field,
  Bombs
>;

最終系

type GameSetting<
  lv extends number,
  bombNum extends number,
  Seed extends Bit[],
  FirstClick extends [number, number]
  // @ts-expect-error: そうそう再帰上限には引っかからないはず...
> = Pow2<ArrayFrom<"", lv>>["length"] extends infer Size extends number
  ? RandomsBitsPair<Seed, bombNum, lv, [FirstClick]> extends [
      ...infer Bombs extends number[][],
      infer _
    ]
    ? SetBomb<ArrayFrom<ArrayFrom<"0", Size>, Size>, Bombs>
    : never
  : never;

type bombMap = GameSetting<2, 16, SEED, [0, 0]>;
// クリックした場所以外のすべてが爆弾になっているか検証
// 仕様上16-1このボムが生成される
// あふれると再帰できなくなりエラーになるので、anyになっていないなら正しい

type bombMap2 = GameSetting<2, 6, SEED, [0, 0]>;
// Seedを変化させると配置が変わります
type SEED = ["1", "1", "1", "0", "1", "0", "0", "0", "1"];

こちらからお試しいただけます。

より簡潔にかけるよ～という方はぜひぜひコメントください！

おわりに

記事にするためにきれいに直していたらエラーになりまくって本当に苦しかったです...
特にマッチさせる際にはコンパイラは黙って never にしてくるのでどの分岐で never になっているのかを探すために [never] にするなどしていました...
いいデバッグ方法をお持ちの、型レベルの住人の型がいらっしゃいましたら初心者型レベラーに教えていただけると幸いです。

宣伝

また僕はここのところ連日 Zenn に記事を投稿しているので、よろしければ他の記事も読んでいただけると嬉しいです。

前回の記事も、繰り返しになりますがよろしくお願いします。

こちらの 2 記事でも型パズルについて扱っていますので、興味のある方はぜひご覧ください。