A=B で楽しく学ぶ難解プログラミング言語

# はじめに

[A=B](https://store.steampowered.com/app/1720850/AB/?l=japanese) という、難解プログラミング言語 (Esolang) をテーマにしたパズルゲームがあります。使える道具は文字列置換だけ。楽しくて、全チャレンジ達成するくらい進めました。

そこで「楽しく学ぶ難解プログラミング言語」として紹介してみようと思います。ネタバレは控えめにするつもりですが、自力で方針を見つける方がより楽しいですので、ここまでで興味の出てきた方はポチっとどうぞ。580 円です。体験版でも途中まで遊べます。

## 難解プログラミング言語 (Esolang) とは

複数のプログラミング言語を触ろうとしたことがある方は、[Brainfuck \- Wikipedia](https://ja.wikipedia.org/wiki/Brainfuck) などの難解プログラミング言語 (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
```

[TryRuby playground 実行例](https://try.ruby-lang.org/playground/#code=txt+%3D+'ab'%0Arules+%3D+%3C%3CEOS%0Aa%3DA%0Ab%3DB%0AEOS%0A%0Aputs+txt%0A256.times+do+%7Ci%7C%0A++changed+%3D+false%0A++rules.each_line+do+%7Crule%7C%0A++++next+unless+rule+%3D~+%2F(.*)%3D(.*)%2F%0A++++next+unless+txt.include%3F(%241)%0A%0A++++txt%5B%241%5D+%3D+%242%0A++++puts+%22++++%23%7Brule%7D%22%0A++++puts+txt%0A++++changed+%3D+true%0A++++break%0A++end%0A%0A++break+unless+changed%0A++break+if+txt.length+%3E+255%0Aend&engine=cruby-3.2.0dev)

最後「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」が一時的に作られたとしても、続けて置換しようとしてしまいます。停止条件が必要です。

[^1]: ステージ 2 の追加ルールを使うと解けます

```
解答:
aa=bb
ab=ba
ba=ab
bb=aa

実行例:
ab
    ab=ba
ba
    ba=ab
ab
    ab=ba
: (以下略)
```

[TryRuby playground 実行例](https://try.ruby-lang.org/playground/#code=txt+%3D+'ab'%0Arules+%3D+%3C%3CEOS%0Aaa%3Dbb%0Aab%3Dba%0Aba%3Dab%0Abb%3Daa%0AEOS%0A%0Aputs+txt%0A256.times+do+%7Ci%7C%0A++changed+%3D+false%0A++rules.each_line+do+%7Crule%7C%0A++++next+unless+rule+%3D~+%2F(.*)%3D(.*)%2F%0A++++next+unless+txt.include%3F(%241)%0A%0A++++txt%5B%241%5D+%3D+%242%0A++++puts+%22++++%23%7Brule%7D%22%0A++++puts+txt%0A++++changed+%3D+true%0A++++break%0A++end%0A%0A++break+unless+changed%0A++break+if+txt.length+%3E+255%0Aend&engine=cruby-3.2.0dev)

## 問題例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
```

[TryRuby playground 実行例 (4行)](https://try.ruby-lang.org/playground/#code=txt+%3D+'_ab'%0Arules+%3D+%3C%3CEOS%0A_aa%3Dbb%0A_ab%3Dba%0A_ba%3Dab%0A_bb%3Daa%0AEOS%0A%0Aputs+txt%0A256.times+do+%7Ci%7C%0A++changed+%3D+false%0A++rules.each_line+do+%7Crule%7C%0A++++next+unless+rule+%3D~+%2F(.*)%3D(.*)%2F%0A++++next+unless+txt.include%3F(%241)%0A%0A++++txt%5B%241%5D+%3D+%242%0A++++puts+%22++++%23%7Brule%7D%22%0A++++puts+txt%0A++++changed+%3D+true%0A++++break%0A++end%0A%0A++break+unless+changed%0A++break+if+txt.length+%3E+255%0Aend&engine=cruby-3.2.0dev)

クリアまでなら、ここまででお疲れさまでした。さらに「追加の目的」を満たして行数制限実績を取ろうとすると、ここからどうやって数行削るのだろう…… と何度も悩まされるゲームとなります。

[TryRuby playground 実行例 (3行)](https://try.ruby-lang.org/playground/#code=txt+%3D+'_ab'%0Arules+%3D+%3C%3CEOS%0A_a%3Db_%0A_b%3Da_%0A_%3D%0AEOS%0A%0Aputs+txt%0A256.times+do+%7Ci%7C%0A++changed+%3D+false%0A++rules.each_line+do+%7Crule%7C%0A++++next+unless+rule+%3D~+%2F(.*)%3D(.*)%2F%0A++++next+unless+txt.include%3F(%241)%0A%0A++++txt%5B%241%5D+%3D+%242%0A++++puts+%22++++%23%7Brule%7D%22%0A++++puts+txt%0A++++changed+%3D+true%0A++++break%0A++end%0A%0A++break+unless+changed%0A++break+if+txt.length+%3E+255%0Aend&engine=cruby-3.2.0dev)

このようにすると、チューリングマシンのヘッド移動のように「なんでも書けそう」感があります。

# 解き方について (少しネタバレ)

## 先に進むには

前の方で解いた方法を、道具として後の方で組み合わせて使います。たとえば「ソート」は 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]。

[^2]: 2-6 は問題文を1時間以上読んでも意味が分からず、Steam 掲示板のお世話になりました……。

最初の問題を全列挙するならこのように。

```
入力: 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
```

[TryRuby playground 実行例 (14行)](https://try.ruby-lang.org/playground/#code=txt+%3D+'ab'%0Arules+%3D+%3C%3CEOS%0Aaaa%3DAAA%0Aaab%3DAAB%0Aaba%3DABA%0Aabb%3DABB%0Abaa%3DBAA%0Abab%3DBAB%0Abba%3DBBA%0Abbb%3DBBB%0Aaa%3DAA%0Aab%3DAB%0Aba%3DBA%0Abb%3DBB%0Aa%3DA%0Ab%3DB%0AEOS%0A%0Aputs+txt%0A256.times+do+%7Ci%7C%0A++changed+%3D+false%0A++rules.each_line+do+%7Crule%7C%0A++++next+unless+rule+%3D~+%2F(.*)%3D(.*)%2F%0A++++next+unless+txt.include%3F(%241)%0A%0A++++txt%5B%241%5D+%3D+%242%0A++++puts+%22++++%23%7Brule%7D%22%0A++++puts+txt%0A++++changed+%3D+true%0A++++break%0A++end%0A%0A++break+unless+changed%0A++break+if+txt.length+%3E+255%0Aend&engine=cruby-3.2.0dev)

まあ解答のネタバレを踏むよりは、これでも自力で無理やり解くことになるからまだ良いかも、という程度です。

## 行数制限のヒント

行数制限が加わると、全列挙という抜け道は塞がれます。考えてパズルを解きます。

軽いヒントを折り畳みの中に書いておきます。パズルのヒントはパズルの面白さを削いでしまいますから、見ないことをお勧めです。

<details>
<summary>行数制限のヒント</summary>

* 操作の順番を入れ替えると、終了条件を短く書けることがあります。
* 文字の種類ごとに置換ルールが必要です。文字の種類を減らせると、この行数も削減できます。
* ふつうのプログラミング言語の for 文のように、同じ操作を繰り返したいです。
* A=B に慣れてくると、操作途中の文字列が元の文字列より長くなることが良くあります。
</details>

# 最後に

このゲームを通じて、正規表現の `.` がどれだけありがたいものかがよく分かりました。

難解プログラミング言語を「書いたことはないけれど頑張ればなんでも書けるっぽい」から、「実際書いたことがあり、確かに頑張ればなんでも書けた」になると、同じ言葉でも重みが変わってくるのではと思います。

A=B はゲームという形で楽しく難解プログラミング言語を学べます。お勧めです。