難解プログラミング言語で AtCoder の問題を解いてみた
AtCoder Beginner Contest 178のA問題にて、次のような問題が出題されました。とてもシンプルな問題です。
入力が 0 なら 1 を、1 なら 0 を出力してください。
ところで、世の中には難解プログラミング言語 (esolang) と呼ばれるものがあります。多くのプログラミング言語が実用を目的として作られたのに対し、非常に読み解くのが困難な言語となっています。
どんな難解プログラミング言語でも、上で挙げたような問題なら解けるのではないかと思い、難解プログラミング言語について調べてみました。
Brainfuck
Brainfuck は難解プログラミング言語の中で最も有名な言語と言えるでしょう。何故か AtCoder は Brainfuck に対応しています。
AtCoder Beginner Contest 178 A - Not
,>++++++++[<------>-]>+<<[+++++[>++++++++<-]>.>-<<]>>[+++++[>++++++++<-]>+.<]
初めて見たときはなにが書いてあるかわからないと思います。
Brainfuck では十分に長い配列とポインタがあります。
Brainfuck には 8 種類の記号があり、それらを使って配列やポインタを操作します。これらの記号の解説は他の記事に譲って、上のコードの解説を行います。
まず 0 番地に入力を代入します。例えば入力が '0' のとき、ASCIIコードで '0' に対応する 48 が 0 番地に代入されます。
'0' は ASCII コードで 48 なので、48 を減算することで入力が '0' の場合 0 、'1' の場合 1 になります。48 回減算をしてもよいのですが、48=6×8 を用いてコードを短くしています。
2 番地に条件分岐のためのフラグ1を設置します。
入力が 1 だった場合、[+++++[>++++++++<-]>.>-<<] の部分が実行されます。 1 番地に '0' である 48=6×8 を作り、出力します。2 番地にあるフラグを 0 にしてループを抜けます。
入力が 0 だった場合、[+++++[>++++++++<-]>+.<] の部分が実行されます。 1 番地に '1' である 49=6×8+1 を作り、出力してループを抜けます。
せっかくなので他の問題も解いてみましょう。
AtCoder Beginner Contest 151 A - Next Alphabet
,+.
入力を 1 文字読み込み、インクリメントして出力します。とても Brainfuck で書きやすい問題でした。
AtCoder Beginner Contest 149 A - Strings
----------[++++++++++>,----------] --------------------------------[++++++++++++++++++++++++++++++++<--------------------------------] >[.>] <[<]<[<] >[.>]
- (1 行目) 改行が来るまで読み取ります。
- (2 行目) 空白の位置に移動します。
- (3 行目) 空白より右側の文字列を出力します。
- (4 行目) 左端に移動します。
- (5 行目) 残りの文字列を出力します。
感想
たった 8 種類の命令でこれだけ色々できるのは面白いですね。今回解いたのは文字列操作に関する簡単な問題だけですが、がんばればもっと複雑な問題も解けるようです。Brainfuck で解くのは苦行でしかなさそうですが…。
05AB1E
05AB1E はスタックをベースにした言語です。コードゴルフ用言語でもあります。AtCoder の問題を 05AB1E で解く試みには先駆者がいます。
AtCoder は 05AB1E には対応していません。なので Try It Online で動かしました (以下紹介する言語も同じです)。
AtCoder Beginner Contest 178 A - Not
≠
なんと 1 文字で書けました。流石ゴルフ用の言語ですね。一応解説すると、これは値が 1 と等しくないかを判定する命令です。
せっかくなので他の問題も解いてみましょう。
AtCoder Beginner Contest 140 A - Password
3m
3 と書くとスタックに 3 が追加されます。m はスタックから 2 つ取り出し、べき乗を計算する命令です。
AtCoder Beginner Contest 149 C - Next Prime
<ÅN
$X$ 以上の最小の素数を求めるという複雑そうな問題も、05AB1E ならたった 3 文字で書けてしまいます。ÅN という命令で、$X$ より大きい最小の素数を求めることができます。なので 1 を引いて ÅN を使えばよいです。
感想
Brainfuck とは違って命令が豊富にあるのが特徴です。コードゴルフも面白そうだなと思いました。
ferNANDo
ferNANDo は名前の通り NAND 演算をもつ言語です (むしろ他の演算がありません)。何故か ABC148 の解説に登場しています。
AtCoder Beginner Contest 178 A - Not
ko bo shi ga a ra wa re ta ta ta ta bo shi ga a ra wa re ta
ferNANDo では、変数の値は 0 または 1 のみです。1 行に 9 変数を書くと入力を表します。1 つ目の変数に入力が成功したかどうかが入り、2～9 番目に文字の ASCII コードの 2 進表記が入ります。
1 行に 3 変数 A B C を書くと、A に B NAND C を代入するという意味になります。
1 行に 8 変数を書くと、その値を ASCII コードとする文字を出力します。
入力で与えられる文字は 0 または 1 であり、これらは末尾の 1 ビットのみ異なっています。よって末尾 1 ビット (ta) を反転させればよいです。NOT x = x NAND x が成り立つことを用いています。
AtCoder Beginner Contest 151 A - Next Alphabet
r a7 a6 a5 a4 a3 a2 a1 a0 c0 c0 d0 a0 c0 e0 a0 d0 f0 c0 d0 b0 e0 f0 c1 d0 d0 d1 a1 c1 e1 a1 d1 f1 c1 d1 b1 e1 f1 c2 d1 d1 d2 a2 c2 e2 a2 d2 f2 c2 d2 b2 e2 f2 c3 d2 d2 d3 a3 c3 e3 a3 d3 f3 c3 d3 b3 e3 f3 c4 d3 d3 d4 a4 c4 e4 a4 d4 f4 c4 d4 b4 e4 f4 c5 d4 d4 a7 a6 a5 b4 b3 b2 b1 b0
半加算器を知っていますか？ボクは知っています。
ざっくり説明すると、1 ビット変数の A, B の和を S 、桁上がりを C とすると、S, C は A, B と NAND を組み合わせて求められます。これが半加算器です。今回行うのは入力に 1 を足すことなので
- a_0 に 1 を足し、和 b_0 と桁上がり c_1 を得る。
- a_1 に c_1 を足し、和 b_1 と桁上がり c_2 を得る。
- …
ということを行います。これは半加算器を用いるとできます。
AtCoder Beginner Contest 162 A - Lucky 7
r a7 a6 a5 a4 a3 a2 a1 a0 s0 a0 a1 x0 s0 s0 t0 x0 a2 v t0 t0 r b7 b6 b5 b4 b3 b2 b1 b0 s1 b0 b1 x1 s1 s1 t1 x1 b2 n1 v v v n1 t1 r c7 c6 c5 c4 c3 c2 c1 c0 s2 c0 c1 x2 s2 s2 t2 x2 c2 n2 v v v n2 t2 ~v v v 1 0 0 1 0 v 1 ~v ~v v loop a v loop b a v c a loop xor b c ~loop loop loop ~xor xor xor 0 1 1 loop ~v ~loop ~xor 1 loop ~xor ~xor loop
1 桁の整数 a7a6...a1a0 を受け取ったとき、それが 7 であるための必要十分条件は a0=1 AND a1=1 AND a2=1 です。 AND は NAND を用いて、a AND b = (a NAND b) NAND (a NAND b) と表せます。これで 3 つの数それぞれについて 7 であるかどうかを判定します。
3 つの中に少なくとも 1 つ 7 が含まれているかどうかは、OR を用いて判定できます。 OR は NAND を用いて、a OR b = (a NAND a) NAND (b NAND b) と表せます。 条件を満たす場合 v=1、満たさない場合 v=0 となります。
さて、v の値に応じて出力を変えたいのですが、ferNANDo には if 文がありません。困ってしまいました。 ここでまだ紹介していない ferNANDo の最後の機能、ループを使います。 ferNANDo でのループは次のように動作します。
- 1 行に 1 変数だけ書かれている場合、その値が 0 なら無視し、1 なら直前にその変数が登場する行まで戻る。
最初に loop が登場するとき、初期値は0なので素通りします。 v=0 のとき 1 文字、v=1 のとき 2 文字出力したいので、次のようにしたいです。
- v=0, loop=0 のとき、loop=0 とする
- v=1, loop=0 のとき、loop=1 とする
- v=1, loop=1 のとき、loop=0 とする
よって、loop = v XOR loop とします。 XOR は NAND を用いて、a XOR b = (a NAND (a NAND b)) NAND (b NAND (a NAND b)) と表せます。
あとはうまく出力を行えばよいです。
感想
めちゃくちゃ大変でしたが楽しかったです。半加算器の知識を用いたり、NAND 回路をフルに用いたりできて、ferNANDo の面白さに触れることができました。この言語でどこまでの問題が解けるのか気になります。
Taxi
Taxi は、名前の通りタクシーを運転するプログラミング言語です。よくわかりませんね。実際にプログラムを見てみましょう。
AtCoder Beginner Contest 178 A - Not
Go to Post Office: west 1st left, 1st right, 1st left. Pickup a passenger going to The Babelfishery. Go to The Babelfishery: south 1st left, 1st right. Pickup a passenger going to the Knots Landing. Go to the Knots Landing: north 6th right. Pickup a passenger going to The Babelfishery. Go to The Babelfishery: west 1st left. Pickup a passenger going to the Post Office. Go to the Post Office: north 1st left, 1st right. Go to the Taxi Garage: north 1st right, 1st left, 1st right.
タクシーに客 (変数) を乗せて、様々な施設に移動することで操作を行います。地図を見ながらタクシーを移動させることになります。地図はesolang wikiをご覧ください。
まずはじめにタクシーは Taxi Garage にあります。入力を受け取るために Post Office へ向かいます。ただ目的地を入力するだけではだめで、何番目の交差点を曲がるといった指示を与えなければいけません。
Post Office で乗客を乗せます。これは入力を受け取ることを表します。次に The Babelfishery に向かいます。ここで客を降ろすことで、入力を文字列から整数に変換します。
再び客を乗せ、Knots Landing へ向かいます。ここでは 0 でない値を 0 に、0 を 1 に変換します。再び The Babelfishery に向かい、整数を文字列に変換します。再び Post Office に向かい、現在の値を出力します。
最後に Taxi Garage に戻ります。戻らないと会社をクビにされてしまうので気を付けましょう。
おわりに
「はい」「やるだけ」と評されがちな A 問題も、難読言語ではかなり解きごたえがありました。パズルを解いているような面白さがありました。
AtCoder の問題は新しく言語を覚えたいときに最適という言葉を耳にしたことがありましたが、難読言語でもそれはいえそうです。言語によって全く解法が異なるのも面白かったです。
また新しく esolang を触ってみたらこの記事の第 2 弾ができるかもしれません。
