星空を描く ~esolang(難解プログラミング言語) writeup ~

esolang

　３月末に、TSGというサークルでesolang( esoteric language ;難解プログラミング言語の略)陣取り大会というゲームが開催されました。この記事はそのwriteupです。割とポエムです。

TL;DR

　 esolangショートコーディングは、僕がポエムを書いてしまうくらいには熱い

この記事に書かれているのはこれだけです。

目次

ルール

esolang陣取り大会のルールは、

  • 赤と青の二つのチームに分かれたチーム戦
  • 「百桁の数列をソートして出力せよ」という問題を解く （例えば４桁の例として、4321 -> 1234）
  • 各チームは獲得済みの陣地の四方の言語に挑戦可能で、各マスの言語でお題にかなうコードを書くと、陣地として獲得可能
  • 相手の陣地も、より短いコードを出せば、取り返せる

(相手の解答は終了までは見れない)

というものです。要するに『より短いコードで、ソートをせよ！』というある種のコードゴルフ的な要素を秘めています。

　大会の様子については、TSGの公式Twitterをご覧ください。

　結果は、赤チームが27-20で勝ちました（僕は赤チームでした）。

f:id:moratorium08:20170405194150p:plain

競技の推移

こんな感じで陣地が変わっていきました

youtu.be

解法の概観

　各言語のwriteupを書く前に、「百桁の数列をソートして出力」という問題に対するいくつかのアプローチを紹介します。

　ソートと聞けば、クイックソートやヒープソートなどを思い浮かべがちですが、今回は計算量よりもコードが短いことが正義です。そういった実装は、大きくなりがちなので、今回は一度も直接的に（ライブラリとしてソートがある場合は別として）、それらを実装することはありませんでした。

　今回僕が用いた方針は大きくわけて３つです。

  • バケツソート
  • 0〜9についてそれぞれ文字列をなめて、一致したら出力（以下、総なめ方針と呼ぶ）
  • 言語やそのライブラリにソート実装がある（Golf言語や実用言語）

バケツソートは、Wikipediaにもありますが、数列を順に見ていき、0~9のそれぞれの数を順に数え、その後その回数分その文字列を出力する、という方針です。これは簡単なループで書くことができ、今回の問題に関しては非常に強力でした。

以下、僕が解いた言語について（最終的に最短解ではなかったものも含めて）、書いていこうと思います。

Starry

　僕はこの言語が結構好きで、タイトルや年賀状にしてしまいました。

　スタックベースの言語で、内部実装はRubyです。言語仕様はesolang wikiを参照してください。

方針1. バケツソート

　Rubyは多倍長整数をサポートしているので、100桁の数値も、int型として保持可能です。この性質を利用して、0~9の「バケツ」を100進数の数の各桁として保持するという方針でまず解きました。

     +               + +  *     +* `  + ,            + +  *      + * *      +  +      +'   `  +         + +  *         +*  *  +      + *` +   '    +*  +      + * + '    +     +  `  + +         + +  *         +*    *      +     '    `   +   + +.   +      + *     ` +    '    +         + +  *         +*   *  +      +* +               + *  '

(339bytes)

綺麗な星空です。星空は観賞用で、実装自体はPythonを使って書いたので、内容はstarry/solve1.pyを見てください。

方針2. 総なめ方針

　最初339bytesの星空が描けて満足していたんですが、この後kurgm氏が260bytesの回答を提出し、抜かされます。そこで、方針を切り替えて、上で挙げた三つの方針のうちの二番目、『総なめ方針』に切り替えました。

　実は、このesolang問題サーバーは、テストが甘く、毎回乱数でテストケースを生成しますが、ケースが一つだけなので、コーナーケースがあったとしても常識的な範囲で通れば通せてしまうという話があります。今回短くするにあたって、実はこの方針は先頭の文字が0だとその0が失われてしまうというコーナーケースが存在します。

　しかしそれを回避するコードを描くと少し長くなってしまうので、今回は多少のコーナーケースには目をつぶりました。

, +     +  `  +` +               +    *   +   + +   + * ' +. `  +               +   * +'*      +*  + +   +   + +               + *  '

(133bytes)

　実装方針は、starry/solve2.pyです。

　一応この後青チームに奪われなかったので今回はこのコードが最終解になりました。

Emoji

　この言語は、Unicodeにある絵文字を使ってプログラミングをする言語です。スタックベースの言語ですが、変数が定義可能で、変数名でのデータ参照が可能です。内部実装はPythonです。詳しい仕様に関してはEsolang Wikiを見てください。

方針

　この言語は最初kurgm氏が248bytesの解法で解いている状態から始まりました。これ自体が既に十分短く、簡単なバケツソートでは太刀打ちができませんでした。そこで、上で示した2番目の方針である総なめ方針を使いました。

　この言語は、配列や文字列のn番目の値にアクセスをすることが可能で、ただし、outputは必ず改行が入ってしまうという問題がありました。

　したがって、基本方針としては、0~9について順に、100桁の数を一つずつ見ていき、一致すればresult用文字列の後ろにつけ、最後にその文字列を出力するという方針をとりました。

　しかし、実はこれも愚直に２回のループを使って実装すると248bytesを抜けませんでした。そこでさらに発想を加えて、１回のループでこれを実現することを考えました。

　具体的には「インデックスとして保持する変数を100進数として見た時、1桁目を文字列のインデックスに、2桁目を今どの文字を参照しているか？にあてる」という方針を使いました。

　例えば、4805という数字は、48（「0」のascii文字コード）を2桁目が差していて、1桁目が5を差しています。すなわち、このループでは、 「6442285896459673378121435372838284681661827573016871763560392310008272763218711572923569634914483640」 というような数列に対して、(0indexで)五番目の2が、0か？を判定する処理を書けば良いです。

　このようにすると、競技中に229bytesまで縮めることができました。

💬💬📲💬💬💬0💬🔢⛽💬1💬🔢👫👥💬5800💬🔢🐣🚘 ⛽👥👥💬100💬🔢🍴🔍👥💬c💬📲🔀💬100💬🔢💸💬💬📱🔀🔑👬🔚🔀💬c💬📱👫🔀🐧🚘 🔃🔀➡

(229bytes)

競技中はこれが最短解となりました。実装用に競技中に使用したPythonスクリプトemoji/solve.pyです。

競技後

　競技後、敵チームだったkurgm氏と解答について話し合っていると、実は、emojiの仕様や内部実装であるPythonの仕様、さらにはUnicodeの仕様を理解していると、さらに短くすることが可能であることが判明しました。Slackで挙げられていたものを勝手に羅列させてもらえば、

  • Pythonにおいて「False + 1 = 1」となるので、0初期化はFalseを使うべき
  • 📤の１文字でインクリメントが可能
  • PythonのDictはKeyとしてFalseやTrueが使えるのでそちらを使うべき
  • 文字列生成は、emojiには二つパターンがあるのですが、そのうち、⛽🚘の方が💬💬より1byte短い（！）

などです。これを適用するとkurgm氏が一気に183bytesまで短くするなど、していたので、なかなかに奥が深い言語だったなぁという感じです。

Element

　非常に人間の温かみを感じる言語。今回書いたesolangの中では最も書きやすい言語でした。実際競技中に解く際も、Pythonなどでコード生成するのではなく直接Elementを書いたので、そういう意味でも良い言語でした（後に出てくる２次元系言語は仕方なしに直接書きましたが）。

　仕様は、Esolang Wikiに詳しいですが、簡単に解説すれば、制御用のスタックとデータ保持用のスタックがあり、変数を作ることもできます。大きな特徴は変数参照「~」にあります。これは「a~」と書くと、aという名前の変数に代入されている値を取り出すという意味になり、さらに「a~~」のようにすると、aという変数に代入されている値の名前の変数を参照する、、、というように、組み合わせることで、一つの変数から色々な場所へ飛ぶことができます。これを今回はフル活用しました。

　方針は典型的なバケツソートで、変数名0~9をバケツとして扱い、それをそのあとに取り出すという方針です。

0 0;
0 1;
0 2;
0 3;
0 4;
0 5;
0 6;
0 7;
0 8;
0 9;
_ q;
100'[
q~ ( x; q;
1 x~~ + x~;
]
10'{
"k;
10 k~ -+ i;
i~~'[
i~`
}
k~ 1 -+ '
}

(element/code) さらに、不要な改行やスペースを取り除き、短くすると88bytesになりました。

00;01;02;03;04;05;06;07;08;09;_q;100'[q~(x;q;1 x~~+x~;]10'{"k;10 k~-+i;i~~'[i~`}k~1 -+'}

(88bytes, element/code.min)

Minus

　驚くべきことに、この言語には命令「-=」しか備わっていません。つまり、基本的に演算が引き算しかありません。しかし、この言語はチューリング完全です（brainfuckがシミュレート可能）。言語仕様に関しては、公式サイトに書いてありますが、見辛い（背景の灰色が主にその要因）ので、今回使った話を少しまとめます。

　-=しか使えない、と書きましたが、特定のレジスタを書き換えることや、レジスタの値を参照することで、inputやoutput、さらにはループを実現します。

レジスタ

　基本的に小文字のアルファベットはレジスタです。特に、c, i, o, pは重要な意味を持つレジスタで、さらにj, q, rも意味のあるレジスタです（今回は使いませんでした）。それ以外は汎用レジスタとして使えます（のはず）。

　まず、inputに関連するレジスタは、iです。例えば、

a-=i

とすると、inputから１文字を読み込んでその値をレジスタaから引き算します。

　outputに関連するレジスタはo, j, qがありますが、今回はoのみ考えます（詳しい話は公式を見てください）。oから値を引くと、その値が出力されます。ここで注意すべきなのは、oに何か値があるというわけではないので、例えばA-=48;o-=A;o-=Aというコードは２回0が表示される。あくまでも引かれた数が出力されます。

　さらに、cというレジスタがx86でいうところのeipというやつ、すなわち、インストラクションポインタです。基本的に命令はファイルの上から下へ進み、それに伴いcの値は加算されていきます。しかしここで、c-=1などとかくと、無限ループさせることができます。これを駆使してループを実現することができます。

　そして最後にpレジスタです。MinusにはBrainfuckのように無限長のメモリがあります。これがMinusのメモリ機構になるのですが、このメモリを参照する際のベースポインタを表しているのがpレジスタです。そして、pレジスタからの特定のオフセットの値を読み書きするために使えるのが大文字のアルファベット群です。これはAがp+0、Bがp+1、…というように特定のオフセットへのメモリアクセスを可能にしています。

　メモリに関して具体例を示します。例えば、次のように、Aに値(48は0のasciiコード)を入れたあとにpを1引くと、その前に入れた値はBへ移ります。

コード

A-=48
p-=1
o-=B

実行結果

% minus code
0%

方針

　Minusは、esolang大会で最初に解いたesolangで、このころはまだ愚直にバケツソートばかり書いていました（そして最後まで奪われなかった）。なので、この解答はあまり短く無いかもしれません。

　内容は、疑似コードとして

for i in range(100):
  mem[p-getc()]++
for i in range(48, 58):
  for j in range(mem[p-i]):
    write(i)

のようなコードをMinusで再現しました。

p-=p
k-=k
l-=l
k-=100
l-=k
p-=90
A-=A
k-=k
k-=l
A-=9
p-=k
c-=A
p-=p
A-=i
p-=A
K-=1
A-=K
p-=p
A-=A
l-=1
c-=16
p-=p
p-=p
k-=k
l-=l
k-=10
l-=k
p-=60
A-=A
k-=k
k-=l
A-=31
p-=k
c-=A
p-=p
A-=A
A-=58
m-=m
n-=n
m-=10
n-=m
n-=l
A-=n
p-=A
u-=u
u-=A
A-=A
p-=p
p-=30
A-=A
v-=v
v-=u
A-=7
p-=v
c-=A
p-=p
A-=A
A-=48
A-=n
o-=A
u-=1
c-=15
p-=p
l-=1
c-=38

(337bytes)

まぁこれを見てわかる人は少ないと思うので、このコードを生成したスクリプトminus/solve.pyです。

Emmental

　僕が言語仕様を捉えきれずに解いてしまった言語です。おそらくもっとずっと短くなるはずのコードについて説明します。

　まず、Emmentalに関してはkimiyukiさんのブログに詳しいので割愛します。良い言語らしいのですが、数字を変数として扱うと突然どっかへ飛んで行ってしまったり、そもそもデバッグがしづらい、僕の技量が足りない、等の理由であんまり短くすることを諦めました。

　そもそもこの言語、文字列は#[Ascii code]という形でスタックにpushするのですが、関数定義はコードとして評価可能な文字列を変数に代入することで行います。すると、手でコードを生成しようとすると#.. #..を無限に打つハメになりさすがにダメです。これに関しては、kimiyukiさんのブログでも指摘されている通り、大体表現を用いて後からcodeをトランスパイル的なことをすれば良いというになります。 　 　そのためのコードが、emmental/transolator.pyです。これを用いると、「; 'v'^'$ 'z!」（rotate関数）のように書いたコードを、トランスパイルすると'[文字]の部分が、#[ascii code]化されて「;#118#94#36#77!」となります。さらに、追加機能で「;'(ABC)!」とすると（これ再帰表現には対応していないですが）、「;'A'B'C!」と展開されるような機能もついています。これで少しコードが書きやすくなります。

方針 バケツソート

　 　この言語でもバケツソートを用いました（この言語は比較処理が強くないので適切なはず）。しかし書いた解法どちらにもコーナーケースが存在しました。特に二つ目に関しては5回に1回くらいしか通らないゴミです。そして、一つ目と本質部分は変わらないので、一つ目だけ少し書きます。

　この言語、メモリがrotate可能です（queue型）。すると、読み込み部分は楽にかけます。

// push functions
;'(v#1+^$rrrrrrrrr)#65!
;'(rv#1+^$rrrrrrrr)#66!
;'(rrv#1+^$rrrrrrr)#67!
;'(rrrv#1+^$rrrrrr)#68!
;'(rrrrv#1+^$rrrrr)#69!
;'(rrrrrv#1+^$rrrr)#70!
;'(rrrrrrv#1+^$rrr)#71!
;'(rrrrrrrv#1+^$rr)#72!
;'(rrrrrrrrv#1+^$r)#73!
;'(rrrrrrrrrv#1+^$)#74!

// read 100 times
;','#'1'7'+'?'t!
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt
tttttttttt

(rはrotate)

お察しの通り、読み込んだ文字に17を足して（これを数字のままマッピングするとバグる）、大文字のアルファベットにマップし、queueをうまいこと回転させてバケツに入れます。

　問題はこの後で、この言語、条件分岐はなく、関数名のマッピングで、飛ぶ先をうまく操作する必要があります（だから条件分岐がないわけではないが）。

　この言語ではこれを達成するため（？）に、logxという関数があります。この使い方に関してはkimiyukiさんのブログに少し書いてあります。これはPythonで言うところの、floor(log(x,2))とほぼ同じのはずです。ただし、log(0)は8になったりなど、ちょっと急いでいる（相手チームも取れるマスだった）ときに理解がうまく走らなかったので、仕方なく愚直解を書きました。

; '#'4'8'.'p!
;'p'#'1'-':'#'6'5'+'?'l!

; '*'A!
; 'l'B!
; 'l'C!
; 'l'D!
; 'l'E!
; 'l'F!
; 'l'G!
; 'l'H!
; 'l'I!
; 'l'J!
; 'l'K!
; 'l'L!
; 'l'M!
; 'l'N!
; 'l'O!
; 'l'P!
v:#65+?

具体的にはこうです（これは0の場合）。バケツが1以上の時は、lに行き、0の時にnopをするようなsled的なものを作り、対処しました。まぁ動きます（自明なコーナーケースがありますがそんなには落ちません）。

　残る問題として、これを0~9全部について書かなければいけないということです。予定では、このl-sledとも呼ぶべきA~Pの関数群は、定義されたタイミングでのlに飛ぶようになっているようで、次に新しく1のためのlを定義すると、また新しくこのsledを作る必要があります（今気づいたんですが、文字を表すシンボルを外部においておいて、それを参照するようにすれば、lを再定義する必要がなくなる気がしますが、当時はそういう発想はありませんでした）。

　結果、コードが、2844bytesになります。一応完成コードemmental/code1, とトランスパイル前emmental/solve1です。

　さすがに短くできるだろうと、この後ループ等に挑戦するもうまくいかず結果として生成されたコーナーケースだらけコードが、emmental/solve2です。一応1838bytesになりますが、こんなものは参考記録です。

Beam

　世の中には、Befungeなどに代表されるtwo dimensional languagesというものが存在します。普通の言語は、通常、一行一行が上から下へ、そして、各行は左から右へ実行されるのが常識だと思います。しかし、この手の「二次元プログラミング言語」（どう訳されるのか知りませんが）は、プログラムが２次元の格子状にマッピングされ、プログラムのされかたによって、インストラクションポインタが縦横無尽に格子上を駆け巡ります。

　では、このBeamという言語の仕様について簡単に説明します。詳しい仕様は、Esolang Wikiに書いてあります。

　この言語の特徴は、beamとstoreと呼ばれる二つのレジスタです。プログラムの進行の制御はこの二つのレジスタを介して達成されます。

　基本骨格としては、>^<vを使ってプログラムの進行をぐるぐると回してループをさせつつ、条件分岐をする、ということになります。 　 　しかし、ここで一つ問題があって、よくあるBrainfuckなどの無限長メモリがある言語では多くの場合、初期値として無限長のメモリに0が代入されている、という仕様になっているはずです。しかし、Beamでは初期にはメモリは長さ0の配列という形になっていて、ここで値を参照するとUndefinedになります（予定では0）。Beamの仕様を詳しく読んでいないので、実はBeamの実装が正しくないという可能性（しばしばesolangの実装は仕様と異なる時がある）があるのですが、このために、最初に使う範囲のメモリを0でfillするという作業を加えました。 　その部分が

 P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'v
vP'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'<
>`````````````````````````````v
v`````````````````````````````<

ここです。そして、100回入力を読み込みます。これはEOFまで読み込むはずです。

>>    rg'sSv
 ^         )
v         L<

あとは、0~9についてはループを書いても良さそうだったんですが、相手陣地から遠いということもあって、愚直に全部とりあえず書きました（そして奪い返されなかったのでこのままになった）。

v s<
g
(@`^
+

これが表示部分（のひとつ）です。最終的なコードはbeam/codeです(418bytes)。かなり書きやすい言語だったという印象です。

Minimal-2D

　 　これも「二次元プログラミング言語」の一つです。しかもこの言語、コマンドが非常に少ないのが特徴で、11個しかありません。Esolang Wikiに詳しい言語仕様が書いてありますが、簡単に各命令について書きます。

記号 内容
> メモリベースポインタを一つ右にずらす
< メモリベースポインタを一つ左にずらす
U プログラムの進行を上向きへ
D プログラムの進行を下向きへ｜
L プログラムの進行を左向きへ｜
R プログラムの進行を右向きへ｜
/ ベースポインタが指すメモリの値が0ならば次の命令を無視する
+ 現在のベースポインタが指すメモリの値を1増やす
- 現在のベースポインタが指すメモリの値を1減らす
. ベースポインタが指す値を出力
, 入力をベースポインタが指すメモリに書き込む

これだけです。インストラクションポインタをぐるぐると回してループをしつつ、条件分岐を/で行うのが骨格となります。また、メモリがスタックではなくポインタで参照なので、この点にも留意が必要です。

方針

　 　これもバケツソートです。こういうスタック型でない言語はバケツソートが書きやすいので、多分適しています（書きやすいから、適するは真か？）。

　実はこの言語は、相手陣地から遠く離れたところにあって、競争を免れていたので、あまり短くする努力をしませんでした。なので、コード自体は非常に見やすいものとなっていますが、良いコードかは保証しません。

<++++++++++++++++++++++++D
D>+++++++++++++++++++++++L
R++++++++++++++++++++++++++++++++++++++++++++++++++ D
 D++++++++++++++++++++++++++++++++++++++++++++++++++L
 R>,------------------------D
   D------------------------L
   R/D >+<                                            D
     R-/D  >> + <<                                    D
        R-/D >>> + <<<                                D
           R-/D  >>>> + <<<<                          D
              R-/D >>>>> + <<<<<                      D
                 R-/D >>>>>> + <<<<<<                 D
                    R-/D >>>>>>> + <<<<<<<            D
                       R-/D >>>>>>>> + <<<<<<<<       D
                          R-/D >>>>>>>>> + <<<<<<<<<  D
                             R-/D>>>>>>>>>>+<<<<<<<<<<D
DU/ -<                                                L
R<<+>>>R<<<.>>>-/D<<<+>>>>R<<<<.>>>>-/D<<<<+>>>>>R<<<<<.>>>>>-/D<<<<<+>>>>>>R<<<<<<.>>>>>>-/D<<<<<<+>>>>>>>R<<<<<<<.>>>>>>>-/D<<<<<<<+>>>>>>>>R<<<<<<<<.>>>>>>>>-/D<<<<<<<<+>>>>>>>>>R<<<<<<<<<.>>>>>>>>>-/D<<<<<<<<<+>>>>>>>>>>R<<<<<<<<<<.>>>>>>>>>>-/D<<<<<<<<<<+>>>>>>>>>>>R<<<<<<<<<<<.>>>>>>>>>>>-/D<<<<<<<<<<<+>>>>>>>>>>>>R<<<<<<<<<<<<.>>>>>>>>>>>>-/D
       U         L        U           L          U             L            U               L              U                 L                U                   L                  U                     L                    U                       L                      U                         L                        U                           L

(1542 bytes, )

brainfuck同様、大きな数（100とか）の初期化はループを用いて短くできるなどのテクはこの言語でも有効ですが、短くする必要がなさそうだったのでしていません。

　やっていることは100文字読み込んで、メモリに配置したバケツに入れ、その後一番下の長い長い（ここもちゃんとループを書けば短くなるはず）部分で、それぞれの文字を吐き出しています。力技です。

(Brainfuck)

　最初に800bytes超えのコードを出して喜んでたらその夜くらいに、daiさんが36bytesとかいう意味不明すぎる解答を提出して、驚きを通り越して笑ってしまいました。おわり。

Golf言語たち

　Golf言語たちは、ググってドキュメントをあたれば大体わかります。そして入力を受け取ってソートをするというような処理は、非常に短い文字数で達成できます。大体sortのSに近いワードが割り当てられてるのでエスパーでも当てられるきもします。

MATL

jS

CJam

q$

05ab1e

I{

2sable

I{

（実は2sableと05ab1eは両方、{でいけるんですねこれが（何故競技中お互い気づかなかったのか））

Jelly

ɠṢ

Stuck

s$

実用言語たち

　みんな大好きPython、Octave、C（これはsatosさんに抜かれた）、C#（これはliesegangさんに抜かれた）、D（これはkurgmさんに抜かれた）。

　Anarchy Golfのネタバレにもなりますし（Anarchy Golfより短いものができているのならまだしも）、コードを出すまでもないので（まあPythonとか大したコードでもないので）、スルーします。

　C言語に関しては、多分環境がAnarchy Golfと違うので結構長いコードになってしまっているのですが、これもまた面白かったです。C言語の最初のCorrect Answerが112bytesでここから、多分５〜７個くらいの発想の追加で、57bytesになりました。C言語は本当に奥が深いです。

Cubix(解けなかったけど紹介)

　これ終了２時間前くらいに解こうと決意して、結局解き終わらず、今も解けていないんですが、非常に興味深い言語です。言語仕様は、Befunge, Labyrinthや今回解いたMinimal 2D, Beamのような2次元に書くプログラミング言語の一種なのですが、なんと意味不明なことに、それを立方体の表面に貼り付けるというのです。

　これでショートコーディングをするということは、論理的な力だけでなく、立体把握能力さえも問われるという、非常に脳みそ破壊的言語なわけです。もはやこれだけで大会を開けるのではないか、というレベルです。 　

終わりに

　ここまで読んでくれた方はいないでしょうが、esolangは非常に楽しいので、つい時間を溶かしてしまってさらにはポエムまで書いてしまう怖さがあるなぁ、ということがわかります。

　特に、esolangでショートコーディングするにあたって「言語仕様を理解し、それに合った実装を行う」というステップはパズルのようでかなりはまります。是非今後もやっていきたいという感じです。