読者です 読者をやめる 読者になる 読者になる

esolangを書く

この記事はTSG Advent Calendar 2016 - AdventarIS17er Advent Calendar 2016 - Adventarの1日目の記事として書かれました。
どちらもまだわりとすっかすかですが完走できるんでしょうか....

先日のTSGのハッカソンでesolang大会が突発的に発生したので、それによって生えたコードを紹介していきます。

esolangとは


これです。
Esolang, the esoteric programming languages wiki
Wikiがあるので、そこのHello World一覧(Hello world program in esoteric languages - Esolang)を眺めるとよいでしょう。
いろいろな見た目のものがありますが、どれも共通しているのは、非実用的な目的で設計されている言語だということです。


問題

これです。現在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  <     

で出力していきます。

感想

Esolangの中でも有名な言語たちなので、サンプルコードやインタプリタが大量にあってよいです。良いインタプリタを使うとデバッグがはかどるので良いインタプリタを探して使っていきましょう。

Esolangを書こうとしてみると、いつも使っている言語がいかに書きやすく設計されているかありがたみが分かってよいので一度書いてみましょう。