esolangを書く
この記事はTSG Advent Calendar 2016 - AdventarとIS17er Advent Calendar 2016 - Adventarの1日目の記事として書かれました。
どちらもまだわりとすっかすかですが完走できるんでしょうか....
先日のTSGのハッカソンでesolang大会が突発的に発生したので、それによって生えたコードを紹介していきます。
esolangとは
1つ忘れてました！ 教室の壁には先日のesolang陣取り大会で部員が作成したesolangのソースコードを展示しています。Brainf**kやRailは力作です！ぜひご覧ください。 pic.twitter.com/WLiAKp1zib
— TSG@駒場祭516 (@tsg_ut) November 27, 2016
これです。
Esolang, the esoteric programming languages wiki
Wikiがあるので、そこのHello World一覧(Hello world program in esoteric languages - Esolang)を眺めるとよいでしょう。
いろいろな見た目のものがありますが、どれも共通しているのは、非実用的な目的で設計されている言語だということです。
問題
esolang陣取り大会のルールは簡単、「100桁の2進数を10進数に変換するプログラム」を指定された言語で書くと陣地をゲットできます。現在6つの言語がTSG部員の手に落ちました。 pic.twitter.com/voEVTBlq5U
— TSG@駒場祭516 (@tsg_ut) November 20, 2016
solang陣取り大会の続報です。現在TSG部員の無駄な努力によって、100言語中48言語が制覇されました。だいぶ賑やかになってきましたね。あと52言語！ pic.twitter.com/34eIcZfNBJ
— TSG@駒場祭516 (@tsg_ut) November 28, 2016
これです。現在100言語中だいたい半分が制覇されています。
言語についての説明はいろいろと良い資料が落ちているのでそれをぐぐってください。
解法
たとえば、pythonとかの多倍長整数をサポートしていてつよい言語は、
print int(raw_input(),2)
とでも書けば解けてしまいます。
esolangの中でも、極端に短く書けることを目標に設計された言語などは、多倍長や基数変換機能があったりするので、さっと解けます。
で、多倍長整数のないCなどは、たとえば以下のようにして変換することになります。
int a[100]; for(int i=0; i<35; i++){ a[i]=0; } for(int k=0;k<100;k++){ for(int i=34; i>=0; i--){ a[i] *= 2; if(a[i]>=10){ a[i+1]++; a[i] -= 10; } } if(getchar()%2)a[0]+=1; } for(int i=35; i>=0; i--){ putchar('0'+a[i]); }
このアルゴリズムはわりと汎用性が高いので、これをもとにして解いていくことにします。
Brainf*ck
みんな大好きBFです。命令が8個だけと少ないわりに書きやすいのが魅力的ですね。
コード
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ [< < <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]> >,------------------------------------------------[<+>-] >-] <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< ++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>
生成したpythonコードのほうが読みやすいのでそれを載せます。
#coding: utf-8 t = 100 d = 35 mod = 10 print '>' * d * 3 print '+' * t #初期化 print '[<' print '<' print '<' * 2 * d s = '>>[<++>-]<' s += '[->+<' * (mod-1) #内側に入るならば10より多い。そうでないなら引く。 s += '[-<+> >[-]<[->+<]]' s += ']' * (mod-1) s += '''> ''' print s * d print '>,' + '-' * ord('0') + '[<+>-]' print ''' >-] ''' #以降出力 print '<' * d * 2 print d * ('+' * ord('0') + '.' + '>>')
解説
BFは実装によって、メモリの上限値がなかったり256だったりします。多倍長だと2倍していくだけでうまくいってよいのですが、今回は256が上限だったので、Cと同様の方法をとることにします。
今回、メモリの配置のイメージとしては、
| ... | a[35] | 0 | a[34] | 0 | ...... | a[1] | 0 | a[0] | 0 | k(カウンタ) | ... |
|---|
みたいな感じにしました。以降、色のついたマスが現在のポインタの位置と思ってください。
まず、for文
for(int k=0;k<100;k++){ ほげふが }
は、
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ [< ほげふが >-]
によって実現できます。
で、まず
for(int i=34; i>=0; i--){ a[i] *= 2; if(a[i]>=10){ a[i+1]++; a[i] -= 10; } }
ですが、今回は面倒だったので、似たような文を34回繰り返すことにしました。
各ループ内の
a[i] *= 2; if(a[i]>=10){ a[i+1]++; a[i] -= 10; }
に対応するのは、
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
です。まず、この部分の実行直前には、
| ...... | a[i+1] | 0 | a[i] | 0 | ...... |
|---|
となっています。で、
>>[<++>-]<
によって、
| ...... | a[i+1] | a[i]*2 | 0 | 0 | ...... |
|---|
となります。
さて、if(a[i]>=10)の部分ですが、僕は愚直に
[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
とすることにしました。
まず、a[i]*2が10以下、たとえば4の場合は、
[->+<[->+<[->+<[->+<[
この時点で、メモリは
| ...... | a[i+1] | 0 | 4 | 0 | ...... |
|---|
となっているので、その後の[より内側は飛ばされ、結局 > のみが実行されて
| ...... | a[i+1] | 0 | 4 | 0 | ...... |
|---|
となり、うまいこと次のiに移っていきます。
また、a[i]*2が10以上のときは、
[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
まで、一度もメモリが0にならずに実行されます。このとき、メモリは
| ...... | a[i+1] | a[i]*2 - 9 | 9 | 0 | ...... |
|---|
となっています。で、その後、
-<+> >[-]
で
| ...... | a[i+1]+1 | a[i]*2-10 | 0 | 0 | ...... |
|---|
となり、
<[->+<]
で
| ...... | a[i+1]+1 | 0 | a[i]*2-10 | 0 | ...... |
|---|
となります。この時点で、指しているところは必ず0なので、あとはがりがり脱出していき、最終的に
]]]]]]]]]]>
で
| ...... | a[i+1]+1 | 0 | a[i]*2-10 | 0 | ...... |
|---|
となり、うまいことうまいこと次のiに移っていきます。
あとやるべきことは入出力くらいで、
>,------------------------------------------------[<+>-]
によって
a[0]+=getchar()-'0';
を、
++++++++++++++++++++++++++++++++++++++++++++++++.>>
を35回繰り返すことによって
putchar('0'+a[i]);
をやっています。
Befunge
2次元プログラミング言語の中でも有名なやつです。プログラムサイズが80*25に制限されているのでうまいことそこに収める必要があります。
これも整数の実装が多倍長でなかったので、Cと同様にやっていきます。
コード
v
v >:\0\0pv >:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv
>75*>:| >75*>:| >:66*\-0g"0"+,v
>25*:* >:| >~"0"-75*0g+75*0pv >75*>:|
^ - 1< > ^ > @
^ - 1 <
^ -1 $ < ^ -1 < こんな感じです。お絵かきですね。
何も知らなくても、最初は左上隅に実行ポインタがあって、^v<>で実行の向きが変わる、ということを知っていればなんとなくどう実行されるか推測がつくのではないでしょうか。
解説
見たまんまです...といってもあれなので説明します。
Befungeはのメモリはスタックのみであり、スタックに対するランダムアクセス命令もないので、一見Cのように書くことができないかと思いますが、実はBefungeは自分のソースコードを読み込んだり書き換えたりすることができるので、(pで書き込み、gで読み込み)これを用いてソースコードの0行目を配列がわりに用いています。また(1,1)の座標のものをカウンタiとして用いています。
v
v >:\0\0pv
>75*>:|
>25*:* >
^ - 1< まず、この部分で、0行目の35(7*5)か所分を0で初期化しています。
条件分岐は | で行うことができ、非0なら上、0なら下に実行の向きが変わるので、35個分初期化したら100((2*5)^2)をスタックに積んで次の部分へ行きます。
>:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv
>75*>:| >:66*\-0g"0"+,v
>:| >~"0"-75*0g+75*0pv >75*>:|
> ^ > @
^ - 1 <
^ -1 $ < ^ -1 < 本体はここです。
for(int k=0;k<100;k++){ for(int i=34; i>=0; i--){ a[i] *= 2; if(a[i]>=10){ a[i+1]++; a[i] -= 10; } } if(getchar()%2)a[0]+=1; }
は、
>:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv
>75*>:|
>:| >~"0"-75*0g+75*0pv
>
^ - 1 <
^ -1 $ < でやっていきます。
for(int i=34; i>=0; i--){ a[i] *= 2; if(a[i]>=10){ a[i+1]++; a[i] -= 10; } }
は
>:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv
75*>:|
>
^ - 1 < ですね。今回はBFに比べてわりと直観的に書けます(メモリからの読み出しと書き込みが面倒ですが)
で、外の部分
for(int k=0;k<100;k++){ if(getchar()%2)a[0]+=1; }
は、
>75*>:|
>:| >~"0"-75*0g+75*0pv
>
^ -1 $ < ですね。
で、後は35個分の値を、
>:66*\-0g"0"+,v
>75*>:|
^ > @
^ -1 < で出力していきます。
