1
0

More than 1 year has passed since last update.

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

Posted at

はじめに

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

TryRuby playground 実行例

最後「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
: (以下略)

TryRuby playground 実行例

問題例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行)

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

TryRuby playground 実行例 (3行)

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

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

先に進むには

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

TryRuby playground 実行例 (14行)

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

行数制限のヒント

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

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

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

最後に

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

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

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

  1. ステージ 2 の追加ルールを使うと解けます

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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0