Rust でなんか書く
せっかく Rust がちょっと書けるようになってきたので何か書こうと思い、テトリスの AI を作ってみることにしました。2週間くらいちまちまコード書いてシステムの土台だけ作りました。以下は動作確認のためにCUIで表示&手動操作してるもの。
ゲーム AI を作るにあたってどういうアルゴリズムにするかは大体決めているのであとは2週間くらいで第一弾みたいなものを作りたいところ。上手く動くかは分からないけども。
これを書くにあたって色々外部ライブラリ(具体的にはcurses、乱数、シリアライズ、時刻、argparse等)を利用していますが、cargo のおかげでこういうのが気楽に使えるのはありがたい。
Rust は配列とか Vec のインデックスアクセスに usize 以外実装する気がなさそうなのが個人的に意味不明なのですがそれ以外は結構使いやすくて良いと思います。
写像の組 f,g:Z→Z で f,g,(f+g) が3つとも全単射になるようなものはあるか?
タイトルまんまですが、ちょっとおもしろかったので。
本筋とは必ずしも関係ない考察
もし $f,g,(f+g)$ が全部 $\mathbb{Z} \rightarrow \mathbb{Z}$ の全単射だとすると、任意の全単射 $\pi$ について \[ \begin{align} \pi(x) &= (f+g)\circ(f+g)^{-1}\circ\pi(x) \\ &= f\circ(f+g)^{-1}\circ\pi(x) + g\circ(f+g)^{-1}\circ\pi(x) \\ &= F(x) + G(x) \end{align} \] となる。ここで $F := f\circ(f+g)^{-1}\circ\pi$、$G := g\circ(f+g)^{-1}\circ\pi$ とした。$F,G$ は全単射なので、任意の全単射は2つの全単射の和で書けることになる。
これより、例えば $(f+g)(x) = x$ となるようなものについてだけ考えれば良いことが分かる。
構成
実はタイトルの条件をみたすような $f,g$ は作ることが出来る。 便宜上、整数は $0<1<-1<2<-2<3<-3<...$ みたいな順序付けがされているものとする(0が最小)。 $f(x),g(x)$ の値が記されたテーブルを考える。最初、テーブルには何も書かれていない。このテーブルでは $f(x)+g(x)=x$ が全 $x\in\mathbb{Z}$ について成立ち、かつ $f(x)$ と $g(x)$ が全単射になっていなければならない。そうなるようにテーブルに値を埋めていくことを考える。(↓イメージ図)
| x | f(x) | g(x) |
|---|---|---|
| 0 | ? | ? |
| 1 | ? | ? |
| -1 | ? | ? |
| 2 | ? | ? |
| ... | ... | ... |
(↑これの ? のところを埋めたい)
以下のようにすればこのテーブルを条件を満たすように埋めつくせる。
- $y<y'$ で、$y'=f(x')$ となるような $x'$ は存在するが $y=f(x)$ となるような $y$ が存在しない時、十分大きい $x$ を取ってきて $f(x):=y, g(x):=x-y$ とできる。このような $(y,y')$ ペアが存在しなくなるまでこれを行う。
- $g$ についても同様のことを行う。
- $x<x'$ で、$f(x')$ の値は決まっているが $f(x)$ の値は決まっていないような時、十分大きい $y$ を取ってきて $f(x):=y,g(x):=x-y$ とできる。このような $(x, x')$ が存在しなくなるまでこれを行う。
- $g$ についても同様のことを行う。
- 1-4 を繰り返す。もし1-4を一通り行ってもテーブルに値を埋められなかった場合、ある $x$ が存在して、$f,g$ は $\{0,1,-1,...,x\}$ 上での全単射になっている。その場合は、順序上での $x$ の次の数を $x'$ として、$f(x')$ と $g(x')$ の値を適当に決めると良い。
手順 1,2 によって $f,g$ が全射であること、また手順 3,4 によって $\mathbb{Z}$ 上の全ての範囲で写像の値が定義され、かつ埋める方法によって $f,g$ は単射でかつ $(f+g)(x)=x$ が満たされることがわかります。
感想
どうせ存在しないんだろうなぁと思ってたら存在してびっくりした。
