A=B

ちょうど最近Texがチューリング完全だという話が流れてきたところだが、このA=Bもチューリング完全な、特殊なプログラミング言語をベースにしたパズルだ。

出される問題としてはこうだ。ある文字列が与えられるので、条件に応じた文字列を、プログラムを利用して出力する。例えば、与えられた文字列を逆順にした文字列を出力する(abcが与えられたらcbaと出力)、与えられた文字列からaを除いた文字列を出力(bacbならbcb)、足し算の式が与えられるので、その結果を出力するなんてものもある。

その問題に対して、プログラムで出来ることは、基本的には、与えられた文字列(またはプログラムで改変された文字列)から指定した文字列を探して最初に見つかったものを削除し、代わりの文字列を挿入する、ということだけだ。挿入する位置は最初は削除した場所だけ(普通はこの作業を「置換」と呼ぶ)だが、途中から文字列の最初または最後に入れたり出来るようになる。また、検索についても文頭や文末を条件に加えられるようになる。

この検索と置換という命令を何行か書く。そうすると最初の行にある検索から開始して、もし見つかれば置換を行い、また最初の行にある検索を開始する。見つからなければ次の行の検索を行い、見つかれば置換して最初の行に戻り、見つからなければ次の行の検索…というようにプログラムが動いていく。そして最後の行の検索でも見つからなければ、現在の改変された文字列を出力する、というように動く。ただし、途中からreturnと言う特別な命令が増え、この命令は検索で見つかったら指定した文字列を返す、という特別な動きをする(主にTrue/Falseを返すために使用する)。また、1度置換を行ったら、その後はこの行の検索を行わない、という命令を入れることも出来るようになる。

文章にするとややこしい感じがするけれど、1行ごとに何が行われているかを見れば、理解するのは難しくないと思う。色々あって混乱するという人は、安心してほしい。このゲームは最初のルール、つまり文字列の置換を行うだけで解くことができる、らしい。そして気付くはずだ。色々出来るって便利なんだと。ちなみに私は置換だけで全部解くなんてことは出来ませんでした。ちなみに「プログラム」なので再利用ができないといけない。つまり、違う文字列に対しても同じ検索と置換を行って、欲しい結果が出力されないといけない(abcもababも、同じプログラムでcbaだったりbabaだったりにしないといけないわけだ)。

そんな感じのプログラミングパズルなわけだが、まあ難しいのなんの。特にややこしくさせているのが、「置換を行ったら最初の行に戻る」というルールだと思う。順繰りに作業を行おうとしても、最初に戻って締まって、最初の方にある検索に引っ掛かってしまって意図しない置換が行われる、ということが良くあった。「ここで部分ループが使えれば…」と思うことも本当に良くあった。正直に言うと、最後の方は解答を見てしまった。そして見たけどよく分からなかったのだ。トークンの使い方が…謎…。

このゲームで特に重要なのが、プログラムを記述するエディタだろうが、コピー・ペーストが行える・実行速度を変化させられる、一時停止と1行ごと進めて処理の行われ方を確認するステップ実行が行えると、基本的に必要にな理想な機能は一通り揃っている。エディタのページも1問につき3ページあるので、部分的な処理を別のページに書いて、その部分だけ挙動を確かめて元のページに貼り付ける、みたいなことも出来る。各問解いた後もプログラムがセーブされているので、前やった問題からコピペして使い回す、みたいなことも出来る。個人的には、文字列が出力されるまで高速化する、みたいな機能があると助かることもあったかなとは思う。

ちなみにパズルだけではなく、学生と教授のメールのやりとりという形で簡単なストーリーも語られている。このパズルは学生が自作したプログラム言語で、その成果をもって単位をもらおうと教授に詰め寄る、というような内容が楽しめる。実はこのゲームのルールも、そんなストーリーに合わせてかPDFで参照出来るようになっている。読みながらパズルを解くことで、「頼むから小手先でなんとかしようとしないで一般的な言語のコンパイラを作ってくれ…！」と思うこと請け合いだ。

プログラマーも非プログラマーも同じスタートを切れそうなくらい特殊な言語で、ぜひ頭を悩ませてほしい。