特殊な2倍関数

いきなりですが次のコードを見てみましょう：

a(X):XXXXrXXXXa(sX)
a(r)
16byteで2重の正方形を回りながら描きますね．

これを2倍関数により解消しても，実は短縮にはなりません．

w(X):XX
a(X):w(w(XX)r)la(sX)
a(r)
これだと17byteでかえってbyte数が増えてしまっています．
もう少し工夫した2倍関数の利用により，同byte数の16byteで動きを再現することは可能です．
w(X):XrX
a(X):w(w(w(X))r)a(sX)
a()

再帰の一部ではなく，次のような状況ならどうするでしょうか？

ssssrssss
これならわざわざ2倍関数を定義する人は少ないと思います．
このときは，2回出てくる「ssss」または4回出てくる「ss」を文字で置いて
p:ss
pprpp
のようにすれば短縮になりますね．実は同じようなことを再帰の一部でも使うことができます．

具体的には次のようなコードで1byteの短縮に成功しています．
（実は最初のコードと少し向きが違うものを描くのですが…見逃してください．）

a(X,Y):YrYa(sX,XXXX)
a(r,)
まさに，「Y=XXXX」として，XXXXを他の文字で置いているのが分かりますよね．

他にもXYXやXllXなどを他の文字で置くことにより短縮につながることがあります．
もちろんn倍関数などを使うのが有利な場合もあるので，
（いつも書いているけど）色んな方法を念頭に置くようにしてください．

この方法にはいくつか注意点があります．これはこの方法を使うときの
リスクであるとともに，裏を返せば「この方法だからこそ書けるコード」に繋がる可能性もあります．

まずは，「何段階目か」がずれるということです．
先ほどのコードでは，再帰の「YrY」の部分はとして実行されるものは次のようになります：

1段階目：r
2段階目：[rrrr]r[rrrr]
3段階目：[srsrsrsr]r[srsrsrsr]
4段階目：[ssrssrssrssr]r[ssrssrssrssr]
2段階目のYに1段階目のXが代入されるため，1段階目の実行では1段階目のXは反映されていないのです．
これが先ほど言った「実は最初のコードと少し向きが違うものを描く」ことの理由ですね．

つまり1段階目のYは，ある意味で使われていないのです．実は
ここを有効利用することもできます（特別な初項の講でも説明する予定です）．例えば

a(X,Y):YrYa(sX,XXXX)
a(r,sss)
などと実行してみてください．"sssrsss"が実行
1段階目：[sss]r[sss]
2段階目：[rrrr]r[rrrr]
3段階目：[srsrsrsr]r[srsrsrsr]
4段階目：[ssrssrssrssr]r[ssrssrssrssr]
と実行されていくのが分かると思います．初期位置を調整しながら
再帰を実行し始めるような場合に，「YrY」という関数に
好きなものを代入する形で使うことができます．過去にも少ないですが
ここを利用した短縮がありました．

次の注意点を述べましょう．例えば

a(X):XXrXXrXXrXa(sX)
a()
というコードを見てみましょう．「XXr」が多量に含まれるためにそこを文字で置いて
a(X,Y):YYYXa(sX,XXr)
a(,)
としたくなる場面ですね．実はこれではズレてしまいます．
n段階目の「Y」は，n-1段階目のXを用いた「XXr」であるためです．

このように中途半端に他変数Yに預けると，XそのものとYで成長速度に差が出るのです．
「わざと差をつける」ことで巧妙な短縮が出来る場面もあるのでテクニックとして
覚えておくとよいですが，慣れないうちは間違えやすいので気をつけてください．
なおこのことを（3倍関数などを使わず）解消するには，Xも成長速度を遅らせる方法があります．

a(X,Y,Z):YYYZa(sX,XXr,X)
a(,,)
（なお，実は上のコードはa(X,Y):YYYXa(sX,XrX), a(,)を実行したものと同じになります．
この理由も考えてみると面白いかもしれません．）

戻る inserted by FC2 system