ズンドコキヨシ with Brainf**k

#はじめに
みんな大好き[ズンドコキヨシ](https://twitter.com/kumiromilk/status/707437861881180160)~~猫まっしぐら!~~ …[Perlで書いた](http://ideone.com/ChbhUV)んですが、BFでもまあ書いてみようかと。

#注意点
ただし、BFにはそもそも乱数を扱う仕組みがありません。いえ、乱数生成アルゴリズムを自分で書くことはできますが、seedを受け取る ( 時刻情報等、seedに使える情報をOSから貰う ) 手段がありません。

ということで、ここはひとつ割り切って、seed はstdinからの入力文字列でこさえることにします。他の言語での実装との大きな違いですね。

まあ要するに、PRNGの実装を試してみるというのが大きな目的、ということでひとつ。

#M系列
M系列というのは…。適当にググってください。bit-xorによる線型漸化式を適切に選べば、とっても長い周期のbit乱数が得られるPRNGです。

~~正直、線形合同法よりもBFでは実装が楽なので~~線形合同法は[アルゴリズム集](https://esolangs.org/wiki/Brainfuck_algorithms#x_.3D_pseudo-random_number)に載っているので、今回はM系列を実装することにしました。え? MT? はっはっはご冗談を。

M系列に使える漸化式は色々ありますが、最長周期$2^{28}-1$の隣接29項間漸化式、$r_n =r_{n-3}+r_{n-28}$を採用しました。( この足し算は$GF(2)$でのものであり、実装上はbit-xorです )
#実装
ということで、以下がコードです。http://ideone.com/41y2ar にあるものと同じです。実行環境である ideone の bff に合わせて書いています。

~~詳しく説明するのは面倒くさい~~コメントに概要を載せているので、それで何とか ( 英語は即興なので多分デタラメです )。特徴としては、次の通りです。

* 出力文字列はutf-8のコード ( 1文字につき3byte ) を直に作っています。ただし、正の値で作るより、負の値の方が早いのでそうしています。( 例えば 0xe3 だったら -29 とか。~~od -td1でコードしらべたら負の値だったので面倒くさくてそのまま採用した、なんてことはありません~~ )
* seedについては、入力文字列を7bitのbit-stringに変換して、それをつなげて使います。28bitだけ使うので、最後の4文字分が有効です。
* 乱数は、常に最新の28項を保持し、iteration毎に一番古い値を消して、新しい値を継ぎ足していくようにしています。
* 最初の方の乱数はseedの特徴が直に出やすいので、ループを空回りさせて捨てるようにしています。
* 単純に「最後の5個の乱数の値」で終了判定すると、まだ「ズンズンズンズンドコ」と出力し終わっていないにも関わらず、誤判定をおこしかねないので、ループカウンタの値で挙動を切り替えています。
    * ループカウンタが5以上の場合は、単に乱数を更新するだけ
    * ループカウンタが1～4の場合は、ズン/ドコも出力するが、終了判定は行わない
    * ループカウンタが0になった後は、「終了条件を満たさなければカウンタエクステンド」~~今風に言えば、「マリア、コンティニューだ」「サンキュ～マ・リ・ア!!」的な~~

```zundoko.bf
* make seed from stdin *
,+[-
 * make 7bit bitstring
 [[->[-->+>>>+<<]>>[-<<]<<+<]+>>]
 <<[-<<]
>>>>>>>>>>>>>>>>,+]
* current memory state: (s_)*s_s_s*
* create a counter ( some initial random numbers should be discarded )
>++++++++++[->++++++++++<]
* M sequence generation loop
*  r(n)=r(n minus 3)xor r(n minus 28)
* memory layout:
*  (r_)*r_r_r__C
>[
 * slide and decrement the counter
 -[->>+<<]
 * move to the oldest random number ( 28 terms before )
 * ( making 2 markers to return )
 -<<<<<<++++[-<<++++++>>]-<<[-[-<<+>>]<<]
 * slide that to the next cell
 <[->+<]
 * move r(n minus 28) towards the top
 >>>+[-<<[->>+<<]>>>>+]
 * add r(n minus 3)
 <[-<+>>+<]>[-<+>]
 * move again
 +[-<<[->>+<<]>>>>+]
 * fix the bit ( change 2 to 0 )
 <<[-[->-<]>+<]
 * watch the counter
 *  if over 4: do nothing
 *  if 1 thru 4: only print "zun" or "doko"
 *  if 0: print "zun" or "doko" and judge wheter to extend the counter
 >>+>+>>+<
 * memory layout:
 *  (r_)*r_rpjCt
 *   p: print flag
 *   j: judge flag ( extension of the counter )
 *   t: temporary
 [-[-[-[-[++++<<->->>-
 ]>[-<    ++++<   ->>>]<
 ]>[-<    +++ <   ->>>]<
 ]>[-<    ++  <   ->>>]<
 ]>[-<    +   <   ->>>]<
 ]>[-                >]
 * print "zun" ( if the last random number is 0 ) or "doko" ( else )
 <<<<[
  ++++++[->>>>+++++>--------->-------->->--[---------<]<<<]+
  <[>->>> ->-.>+.>.<<.>-.>>>.+[,+<+]  ]
  >[->>>-> -.>.>>.<<<.>+.>>>.+[,+<+]> ]
 <<<<]
 * judge wheter to extend the counter
 *  calculate the sum of r(n minus 4) thru r(n minus 1) and ( 1 minus r(n) )
 *  extend the counter except the sum is 0 
 >[-
  >-<<<<<<<<+[-<<<[-<+>>+<]<[->+<]>>[->>+<<]>>>>+]<
  <+<[-<+>>-<]<[->+<]>>[[-]>>+<<]>
 ]
>]
* print "kiyoshi!"
+++++++[->>+++++++>------->->+>+++++<[-----------<]<]
>>-.>.>+.<<.>+.>>+.<<<.>.>-----.<<.>.>>.<<<.>-.>>----.>--.
```
#終わりに
ついカッとなってやった。BFが組めればなんでも良かった。特に反省はしていない。