A=Bというゲームを1次不定方程式でゴリ押す

A=B

まず、『 A=B 』とは何かについて話す。これはSteamでプレイできる難解プログラミング言語をテーマとしたパズル的ゲームである。Artless Gamesが開発しており、他に『Understand』『Minesweeper Variants』などが有名である。
「プログラミングをゲーム感覚で学べる」といった趣旨のものは、近年たくさん出ているが、『A=B』はおそらくその類ではない。むしろナンプレやマインスイーパなどのパズルゲームに近く、楽しく頭を使える。
特性上、無限に遊び続けられるといっても過言ではないのだが、なんとたったの580円で購入できる。この記事を読んでいただけるような方が好むこと間違いなしのゲーム性である。

忠告

以降ネタバレを含むため、一度プレイしてから読んでいただくことを推奨する。

ゲームの趣旨

忠告を無視してスクロールしてしまった人のために、チュートリアル部分を拝借して、簡単にこのゲームの趣旨を説明する。（ただし、これは私の解釈であり、公式がこのようにプレイすることを推奨しているわけではない。）

1-1 AをBに

タイトルになっている「A=B」は、このゲームの説明としてもっとも端的に書かれたものである。数学における「=」は、左にあるものと右にあるものが等しいという意味だが、プログラミングに少しでも触れたことがある人はわかるように、ここにおいては左のものを右のものに置き変えるという意味である。
このゲームの最初のステージを見よう。まず課題が以下である。

入力：a,b,cからなる文字列
出力：すべてのaをbに置き換える。
制約：1 <= 入力文字列の長さ <= 7

そしてプレイヤーのすることはコーディングである。この場合はコードエディタに「a=b」と書き、実行ボタンを押す。すると課題にある「入力：～」の～を満たす文字列に対して、コードが実行されていく。

例えば$\mathrm{abca}$といった文字列は、左から順に文字をみて$\mathrm{a}$が見つかったので$\mathrm{bbca}$になる。コードは一度読んで終わりではなく、「=」の左にある文字列が部分文字列としてある限りは、「実行して初めから」を繰り返す。つまり次に$\mathrm{bbcb}$となり、もう$\mathrm{a}$は見つからないので出力は$\mathrm{bbcb}$となる。

当然1つや2つではなくたくさんのTest Caseが実行され、すべてが指定された出力になるようにコーディングできれば、クリアである。今回の場合は解答として「a=b」が必要十分である。

ここで読者にもう一題。

入力：a,b,cからなる文字列
出力：入力をアルファベット順に並べ替える。
制約：1<= 入力文字列の長さ <= 7

これはステージ「1-5 ソート」の課題である。解答が気になる方はご自身で購入して解いていただきたい。

ゴリ押し

このゲームの趣旨は前述の通り、あらゆる入力文字列に対しても指定された出力を返すようなコーディングをするということである。

しかし、勘のいい方は課題の文章に一つ違和感を抱くところがあるだろう。「制約：1<= 入力文字列の長さ <= 7」の部分である。これはあらゆる入力文字列は1文字以上7文字以下であるという制約を課すという意味なのだが、ということは入力文字列は高々有限パターンしかないのだ。つまり、ある程度のゴリ押しが効くということである。（最悪の場合はすべてのパターンを書けば解くことはできるだろう。）

数学の証明で言うところの「エレガント」な解答を考えるのが本来は良いのだろうが、ここでは「エレファント」な解答を与えてみよう。

ここから先はもっとネタバレをすることに加え、ある程度ゲームを進めていないとわからないような箇所が多いため、ゲームをプレイしてステージ「4-13」まで進めることを強く推奨する。

4-13 中央

さて、本題に入る。以下の課題をゴリ押す。

入力：a,b,cからなる文字列
出力：中央の文字を出力する。
制約：1 <= 入力文字列の長さ <= 7
入力文字列の長さ。

私は制約に目をつけた！
今回は1、3、5、7文字の文字列しか入力にない！

そして中央の文字が何かを教えろと言っている。要するに3文字だったら2文字目、5文字だったら3文字目、7文字だったら4文字目を出力すれば良いようだ。

例えば入力が3文字のものしかなければ
(once) = (start)|
|a = (end)a
|b = (end)b
|c = (end)c
(start)a = (return)a
(start)b = (return)b
(start)c = (return)c
で可能だろう。ここで最初に先頭に置く$|$の数を変えれば5文字や7文字のみのときでも対応できることがわかるだろう。

しかし、問題はそれらを一度に対応する統一のコードでなければならないことである。少し考えると、先ほどのコードの$|$の数が1個であることは対して重要ではないことに気付く。重要なのは「3で割って1余る」数であることだ。これは5文字や7文字でも同じで、「5で割って2余る」「7で割って3余る」数ならなんでも良いのだ。

そう、なんでも良いのだ！！！

では、「3で割って1余る」かつ「5で割って2余る」かつ「7で割って3余る」数は無いだろうか？
ずばりこの問いは1次不定方程式で解くことができる。
以下の式を満たす整数$k,x,y,z$を求める。
$$ k = 3x+1 = 5y+2 = 7z+3 $$
これを解くと、$n$を整数として
$$ k = 105n+52,\enspace x = 35n+17,\enspace y = 21n+10,\enspace z = 15n+7 $$
と求まる。これより例えば$k=52$は「3で割って1余る」かつ「5で割って2余る」かつ「7で割って3余る」数である。
つまり、$|$の数を52個にした
(once) = (start)||||||||||||||||||||||||||||||||||||||||||||||||||||
|a = (end)a
|b = (end)b
|c = (end)c
(start)a = (return)a
(start)b = (return)b
(start)c = (return)c
を実行すれば、すべて上手くいく。（1文字の場合は自明。）

これを応用すれば、文字列の長さに最大値さえあれば同様にして解けるし、次のステージの「4-14 中央2」も少し工夫することで解くことができる。

おわりに

「今回記事にした内容、共通テストの整数で出題されそうだな」と思ったが、すでに整数は共通テスト範囲外となったのだった。情報でプログラミングをやるようになった今だからこそ、本当に出題されてもおかしくはなかったのではないだろうか。

もし万が一、ここまでゲームをプレイすることなく読んでしまったという方が居るならば今すぐにSteamを開いてプレイしてみてほしい。まだこのゲームの3％も見せていないし、紹介した問題以外にも面白く悩まされる問題はたくさんある。

そして、すでにプレイしたことがある方にはわかってもらえると思うが、一度ステージをクリアすると追加の目的が現れる。これはコーディングの行数を最大何行で抑えるという目的である。
先ほどゴリ押した4-13は、追加の目的として10行までに抑えるように言われる。（とっくに達成している。）これはおそらくエレガントに解くことを想定して公式の用意した解答が10行で実現しているということだろうと推察する。
しかし、制約がない場合でも通用する8行のコードが知られている。 Steamコミュニティガイドには 最短解法ガイド があり、ここでは制約がある場合とない場合（unbounded）のそれぞれの最短（とされる）解法が載っている。ここにその8行の掲載がある。残念ながら先ほどの7行のエレファント解法も制約ありの最短解法として掲載されている。最短なのは嬉しいが、どこか悔しい。
（もちろんここにはすべての解法が載っている。リンクを踏まれる方は十分にネタバレに注意して閲覧してほしい。）

このゲームはパズル的に楽しめるが、単なるパズルではない。そこには歴としたプログラミング言語があり、理論計算機科学に深いつながりがある。計算機科学に興味がある私としては、このゲームをとことん遊びつくすつもりである。