特殊な2倍関数

Herbertは,4つの移動方向を持つという意味で,4という数は少し特別です.
例えば特定の動作を4回繰り返し,さらにはそれをさらに向きをかえて4回繰り返すなどは
そこそこ頻繁に要求されるように思います.

4倍すべきものが何かの2倍だったりすることも多く,
4倍したいけど2倍関数を用意しておく方が賢い場面はしばしばあります.
実際,

f(X):XXXX
f(p)

f(X):XX
f(f(p))

では後者の方が少ないんですよね.4倍を3回やると4倍関数の方が良いので一概には何とも言えませんが,
小回りが利く2倍関数は重要です.


いきなりですが,田の字を描く次のコードを見てみましょう.

f(X):XX
f(f(f(f(sr))r))

4倍したものを,向きを変えてさらに4倍しています. この動きとほぼ同じ動きを,同byte数の別のコードでも書くことができます:

f(X):XrX
f(f(f(f(s))r))

動き終わった際の向きが違います("r"が足りない)が,同じ経路を辿ります.
2倍関数に方向転換を織り交ぜてあるため,関数の定義自体は1byte余分ですが,
実行ラインで1byteの得をしており,合計で同じbyte数のコードになっています.

なお,「2倍関数に方向転換を混ぜる」という発想でf(X):XXrなどの関数を
定義するという発想もありそうですが,この関数で同経路を辿るとより多くのbytes数を必要とします.
実はXXrやrXXなどの関数は,「4倍を作る」のには向いていません.
"r"の位置を少し変えただけで大きく性質が変わって不思議な感じがするかもしれませんね.
これについては変数変換の講でも触れようと考えています.

逆に言うと今回の2倍関数f(X):XrXは4倍操作との相性が良いです.
より一般的に,f(X):XpXの形の2倍関数は4倍操作との相性が良いです. 具体的には,f(f(X))と2回合成すると,

w(w(X))=XpXpXpX 

となって,"Xp"の4倍からpだけ足りないものが出てきます.
w(X):XrX,w(w(w(w(s))r))というコードで,田を描くことや元の向きと変わったことの理由が分かるのではないかと思います.
上の例では活用できていませんが, 通常の2倍関数と比べ, srslなどのパーツで1B節約できることも重要です.


この形のテクニックで筆者が最初に利用し始めたのが, XrXやXlXなどの, 2倍関数と方向転換の併用でしたが,
それ以上によく用いられるのが,

f(X):XssX

f(X):XsrslX

などの関数です. この場合,

f()

としてssやsrslのよく現れるパーツを作れることが強みで,

a:ss
f(X):XX
などとするのに比べて定義に必要なバイト数が少ないため, 

という場合に短縮につながる場合が多いです.
使いこなすのに少し練習が必要で, 同じ関数で実装しても1Bロスしてしまうような
事例が多いようなので, コンテスト問題などでしっかり練習してみましょう.


最後に, X[1]Xの形の関数が特に有効なのは

場合の話であることを強調しておきましょう.
単にssが多く出てきて, さらに2倍関数を使う, などの場合には, XXssやssXXなどの関数が
有効ということもありえます. XssX特有の旨みは, 4倍して初めて生じるものとも言えるかもしれません.
パーツと2倍関数を兼ねる関数では, X[1]Xの形が最重要であることは間違いないですが,
その他の関数の方が有利ということも多いので, 慎重に手法を判断しないといけませんね.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-11 (月) 23:25:48 (2132d)