はじめに
A=B という、難解プログラミング言語 (Esolang) をテーマにしたパズルゲームがあります。使える道具は文字列置換だけ。楽しくて、全チャレンジ達成するくらい進めました。
そこで「楽しく学ぶ難解プログラミング言語」として紹介してみようと思います。ネタバレは控えめにするつもりですが、自力で方針を見つける方がより楽しいですので、ここまでで興味の出てきた方はポチっとどうぞ。580 円です。体験版でも途中まで遊べます。
難解プログラミング言語 (Esolang) とは
複数のプログラミング言語を触ろうとしたことがある方は、Brainfuck - Wikipedia などの難解プログラミング言語 (Esolang) についても聞いたことがあるかもしれません。
- 実用的ではないプログラミング言語
- 他のプログラミング言語で可能なことなら、頑張ればなんでも書ける (チューリング完全)
A=B もその難解プログラミング言語の一つです。難解ですけれど Brainfuck などに比べればまだ読める言語です。
ゲームの中で使える部品が少しずつ増えていきます。最後までやり切れば「頑張ればなんでも書ける」ところを感じられると思います。
A=B の基本ルールと問題例
基本ルール
「A=B: A を B に置き換える」が基本ルールです。
- 文字列を上から順に検索し、見つかれば置換して、最初に戻ります
- 検索でどれにも当てはまらなくなったところで、終了します
ステージが進むとルールが少し増えます。本記事ではこの基本ルールだけ使います。
このルールを適用して、入力に対して適切な出力が得られるかを、自動テストします。すべて通過すればクリアです。
問題例1: a を A に、b を B に置き換える
序盤の難易度です。このような問題がゲーム内に多くあります。
入力: a,b からなる文字列
出力: すべての a を A に、b を B に置き換える
制約: 1 ≦ 入力文字列の長さ ≦ 3
追加の目的: 最大 2 行
入出力例:
Input: ab
Output: AB
Input: aaa
Output: AAA
これを解くには、「a=A: a を A に置き換える」と「b=B: b を B に置き換える」の 2 つのルールを設定すれば良いです。
解答:
a=A
b=B
実行例:
ab
a=A
Ab
b=B
AB
最後「AB」になると、「a=A」「b=B」どちらの置換も行われなくなり、プログラムが停止します。これで「Input: ab」に対して「Output: AB」が無事得られました。
問題例2: a を b に、b を a に置き換える
上の問題だと楽しさが伝わらないので、文字列の入れ替えにしてみます。
入力: a,b からなる文字列
出力: すべての a を b に、b を a に置き換える
制約: 入力文字列の長さ = 2
追加の目的: 最大 3 行
入出力例:
Input: ab
Output: ba
Input: ba
Output: ab
これ、本記事のルールでは解けません 1。「Input: ab」に対して「Output: ba」が一時的に作られたとしても、続けて置換しようとしてしまいます。停止条件が必要です。
解答:
aa=bb
ab=ba
ba=ab
bb=aa
実行例:
ab
ab=ba
ba
ba=ab
ab
ab=ba
: (以下略)
問題例2': a を b に、b を a に置き換える + 先頭 1 文字
入力: 先頭は _、2 文字目からは a,b からなる文字列
出力: すべての a を b に、b を a に置き換える
制約: 入力文字列の長さ = 3
追加の目的: 最大 3 行
入出力例:
Input: _ab
Output: ba
Input: _ba
Output: ab
問題の先頭に _ 1 文字を追加しました。こうすると入力と出力を区別できます。お疲れさまでした。
解答:
_aa=bb
_ab=ba
_ba=ab
_bb=aa
実行例:
_ab
_ab=ba
ba
クリアまでなら、ここまででお疲れさまでした。さらに「追加の目的」を満たして行数制限実績を取ろうとすると、ここからどうやって数行削るのだろう…… と何度も悩まされるゲームとなります。
このようにすると、チューリングマシンのヘッド移動のように「なんでも書けそう」感があります。
解き方について (少しネタバレ)
先に進むには
前の方で解いた方法を、道具として後の方で組み合わせて使います。たとえば「ソート」は A=B 紹介ページにもある序盤で現れます。最初から最後までお世話になります。
全問解かなくても先のステージに進むことができますが、道具を揃えるという意味では、可能なかぎり解いておくのをお勧めします。
無理やり先に進むには
A=B で扱う想定入力ケースは全列挙できるくらいの数です。一番パターンが多い問題でもこれくらいです。
入力: a,b,c からなる文字列
制約: 1 ≦ 入力文字列の長さ ≦ 7
この入力パターンは全列挙して $3^1+3^2+3^3+3^4+3^5+3^6+3^7=3279$ 。ほかのプログラミング言語で全パターンの入出力を作成すれば終了です。終盤の問題でも解けてしまいます。問題文の意味さえ分かれば 2。
最初の問題を全列挙するならこのように。
入力: a,b からなる文字列
出力: すべての a を A に、b を B に置き換える
制約: 1 ≦ 入力文字列の長さ ≦ 3
追加の目的: 最大 2 行
入出力例:
Input: ab
Output: AB
Input: aaa
Output: AAA
解答:
aaa=AAA
aab=AAB
aba=ABA
abb=ABB
baa=BAA
bab=BAB
bba=BBA
bbb=BBB
aa=AA
ab=AB
ba=BA
bb=BB
a=A
b=B
実行例:
ab
ab=AB
AB
まあ解答のネタバレを踏むよりは、これでも自力で無理やり解くことになるからまだ良いかも、という程度です。
行数制限のヒント
行数制限が加わると、全列挙という抜け道は塞がれます。考えてパズルを解きます。
軽いヒントを折り畳みの中に書いておきます。パズルのヒントはパズルの面白さを削いでしまいますから、見ないことをお勧めです。
行数制限のヒント
- 操作の順番を入れ替えると、終了条件を短く書けることがあります。
- 文字の種類ごとに置換ルールが必要です。文字の種類を減らせると、この行数も削減できます。
- ふつうのプログラミング言語の for 文のように、同じ操作を繰り返したいです。
- A=B に慣れてくると、操作途中の文字列が元の文字列より長くなることが良くあります。
最後に
このゲームを通じて、正規表現の . がどれだけありがたいものかがよく分かりました。
難解プログラミング言語を「書いたことはないけれど頑張ればなんでも書けるっぽい」から、「実際書いたことがあり、確かに頑張ればなんでも書けた」になると、同じ言葉でも重みが変わってくるのではと思います。
A=B はゲームという形で楽しく難解プログラミング言語を学べます。お勧めです。