Zenn
✅

型でランダムを表現する（TypeScriptの型レベルプログラミングでマインスイーパー: 前編）

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

初めに

こんにちは。最近 TypeScript の型をこねるのにハマっている yossuli です。
記事投稿コンテスト、盛り上がっていますね！
特に先日 TSKaigi が開催されてからより一層盛り上がってる気がします。
僕も現地で参加して、今すごく TS のモチベが高いです。
このモチベをプロダクト開発に向けることができればいいのですが、あいにく僕は何かを作ることには関心がないのです...
今年就活性で何かしらアウトプットしないと面接で何もアピールできず困ってしまうので、せめて記事を書いてアピールしようという次第です。
#1 日 1Zenn と題して毎日記事を書いていて本日が 5 日目です。
よろしければ他の記事も読んでいただけると嬉しいです。

本題

さて、前置きが長くなりましたが、今回の本題です。
僕は技術サークルに属していて、現在新入生が初期の課題としてマインスイーパーを React でつくっています。
僕も n 回目のマインスイーパー作成を一緒に行いながら教えていくのもいいなぁと思ったのですが、コンテストで

https://zenn.dev/forcia_tech/articles/202505_hatano_bit_type_tictactoe

このような記事を見つけ、TypeScript の型レベルプログラミングでマインスイーパーを作るのも面白いなと思い、挑戦してみることにしました。

手順

  1. ランダムを作成する
  2. ランダムにボムを配置する
  3. ユーザーの入力を再帰的に処理して盤面の状態を型で表現する
  4. ゲームの状態(クリア、ゲームオーバー)等を型で表現する

このような手順で進めていきたいと思います。
本記事では、1. の「ランダムを作成する」を行っていきます。

型でランダムを表現する

アルゴリズムの検索

まず、ランダムを表現するためにどのような手段があるのか調べました。
一旦、JS の実装でどのようなアルゴリズムがあるのかなと調べると以下の記事を見つけました。

https://zenn.dev/ame_x/articles/b3ada5021ed174

let x = state.a;
x ^= x << 7;
x ^= x >>> 9;
state.a = x;
return x;

実装の検討

  • ビット演算の型の実装
    • シフト演算は何個シフトするかと結果の配列の長さを比較しながら再帰すればよさそう
    • XOR 演算は Mapped Types で実装できそう
  • 任意の範囲にする
    • 2**n なら単純なビットマスクでよさそう

https://camidion.wordpress.com/2012/11/10/speedy_modulo/

実装

ユーティリティ

type Bit = "1" | "0";

type Random<Seed extends Bit[]> = Xor<
  Fill<Seed, 16>,
  ShiftL<Seed, 7>
> extends infer T
  ? T extends string[]
    ? Xor<T, ShiftR<T, 9>>
    : never
  : never;

type Fill<Bits extends string[], n extends number> = Bits["length"] extends n
  ? Bits
  : Fill<["0", ...Bits], n>;

type SliceR<
  Bits extends any[],
  n extends number,
  acc extends any[] = []
> = Bits["length"] extends n
  ? Bits
  : Bits extends [infer First, ...infer Rest extends any[]]
  ? Rest["length"] extends 0
    ? [...acc, First]
    : SliceR<Rest, n, [...acc, First]>
  : never;

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

左シフト

type ShiftL<
  Bits extends string[],
  n extends number,
  acc extends string[] = []
> = Bits extends [infer First extends string, ...infer Rest extends string[]]
  ? acc["length"] extends n
    ? [...acc, First, ...Rest]
    : ShiftL<[...Rest, "0"], n, [...acc, First]>
  : never;

右シフト

type ShiftR<
  Bits extends string[],
  n extends number,
  acc extends string[] = []
> = Bits extends [...infer Rest extends string[], infer Last extends string]
  ? acc["length"] extends n
    ? [...Rest, Last]
    : ShiftR<["0", ...Rest], n, [Last, ...acc]>
  : never;

差異としては、左シフトは桁が大きくなることを許容するので n 回シフトした後にaccをそのまま残すのに対し、右シフトでは 0 の桁より右に動いた桁は切り捨てるのでaccを遺さない点がります。

XOR

type Xor<A extends string[], B extends string[]> = {
  // @ts-expect-error: 再帰にすればエラーにならないが...
  [K in keyof A]: A[K] extends B[K] ? "0" : "1";
};

再帰にすればエラーがなくより安全であるが、ここで再帰を深くしないために Mapped Types を使用しています。

ランダム

type Random<Seed extends Bit[]> = Xor<
  Fill<SliceR<Seed, 16>, 16>,
  SliceR<ShiftL<Seed, 7>, 16>
> extends infer T extends string[]
  ? Xor<T, ShiftR<T, 9>>
  : never;

なんとなくきりがいいので 16 ビットになるようにしています。
実際のところどの桁で区切るのがいいのかは検証していないです。
詳しい方がいらっしゃいましたらコメントください。

Mod

export type Mod2n<Bits extends string[], Row extends Bit[]> = Fill<
  Row,
  Bits["length"]
> extends infer RowF
  ? {
      [K in keyof Bits]: Bits[K] extends "1"
        ? // @ts-expect-error: 再帰にすればエラーにならないが...
          RowF[K] extends "1"
          ? "1"
          : "0"
        : "0";
    }
  : never;

同じく再帰にすればエラーがなくより安全であるが、再帰を深くしないために Mapped Types を使用しています。

任意の範囲(ここでは 2**n のみですが...)のランダムな値

type RandomInRange<Seed extends Bit[], n extends number> = Mod2n<
  Random<Seed>,
  ArrayFrom<"1", n>
>;

これで 0 ~ 3, 7, 15 などのランダムな値の Bit の配列を生成することができます。

おわりに

ここまでで、TypeScript の型レベルプログラミングを使用してランダムな値を生成する方法を実装しました。
掛け算などを実装すれば 2**n 以外の範囲のランダムな値も生成できるようになりますが、今回はここまでにしておきます。
興味のある方はちょうどコンテストの記事である以下の記事を確認するとよいのではないでしょうか？

https://zenn.dev/mitate_gengaku/articles/type-level-arithmetic-operations

宣伝

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

https://zenn.dev/yossuli/articles/eb3e471d954c15
https://zenn.dev/yossuli/articles/2cc7275de41c49

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

Discussion