Xを1つ含む関数

経路が不規則になればなるほど, 2倍, 3倍関数などの利用場所は限られてきます.
関数は, Xをたくさん含むほど, (上手に使えたときの利は大きくなりえますが)適用できる箇所が少なくなりやすいです.

ここで紹介するのは, 1変数関数でしかもXを1つしか含まないものの利用法です.
このような関数は, a(X):[1]X[2]の形だけです.
Xをn個含む関数はn倍関数を修正したものと見ることができるので,
これはある意味1倍関数を修正したものですね.
そのような関数の有用性ははじめは見落としやすいですが, 意外と汎用性のある強力な手法になります.


いきなりですが, 次のコードを少ないbyte数に書き換えることを考えましょう:

【44byte】abcpqabcuvabcpqwvupqwabcupqvabcpqabcpqabcabc

abcとpqがたくさんいるのが分かりますね.

[abc][pq][abc]uv[abc][pq]wvu[pq]w[abc]u[pq]v[abc][pq][abc][pq][abc][abc]

実は上手な短縮をすると, このコードでClear出来る経路は, 24byteで書くことができます.
腕に自信がある人は, 読み進める前に自力で試してみると面白いかもしれません.


さて, 24byteになったでしょうか?まずは素直な考え方を紹介しましょう.
[abc]は3文字で8回, [pq]は2文字で6回現れる ので, これらは別の文字でおく方が短くなります:

x:abc
y:pq
xyxuvxywvuywxuyvxyxyxx【4+3+22=29byte】

だいぶ減りました. さらに[xy]が4回現れているので, これを再び 文字でおけば, この方法で28byteまで減らすことができます.

x:abc
y:pq
z:xy
zxuvzwvuywxuyvzzxx【4+3+3+18=28byte】

さて, 上のコードを見ても, これ以上減らせる箇所はなさそうです.
たくさん出てくるものはもうまとめきったし, n倍関数も役には立たなさそうです.


しかし, 実はもっと良い方法があります. x:abc, y:pqと定義した代わりに

f(X):abcXpq

という関数を定義しましょう. 関数定義に8byte使っていますが,
「abc****pq」がある度にf(****)にすることで4byteの得が出来ます.
[pq]が出てくるたびに直前の[abc]とペアにすることで次の手順でどんどんコードを短縮していくことができます.

【8+44byte】[abc][pq][abc]uv[abc][pq]wvu[pq]w[abc]u[pq]v[abc][pq][abc][pq][abc][abc]
【8+40byte】f()[abc]uv[abc][pq]wvu[pq]w[abc]u[pq]v[abc][pq][abc][pq][abc][abc]
【8+36byte】f()[abc]uvf()wvu[pq]w[abc]u[pq]v[abc][pq][abc][pq][abc][abc]
【8+32byte】f()f(uvf()wvu)w[abc]u[pq]v[abc][pq][abc][pq][abc][abc]
【8+28byte】f()f(uvf()wvu)wf(u)v[abc][pq][abc][pq][abc][abc]
【8+24byte】f()f(uvf()wvu)wf(u)vf()[abc][pq][abc][abc]
【8+20byte】f()f(uvf()wvu)wf(u)vf()f()[abc][abc]

一気にさきほどのコードのbyte数に追いつきました. さきほどの

x:abc
y:pq

という文字のおき方では, 1つをxにするたびに2byte, 1つをyにするたびに1byteの得でしたが,
今回の関数は, 1度使用できると4byteの得になっています.
文字で置きたいもの2つをまとめて1つの文字で置いたかのような効果になるためです.
また, 関数を定義する部分

f(X):abcXpq

x:abc
y:pq

よりも1byte余分なだけで済んでいます.


さて, 随分と縮めた

f(X):abcXpq
f()f(uvf()wvu)wf(u)vf()f()[abc][abc]【28byte】

というコードですが, さらに短縮が可能です.
素直な方法だと, 全体に3度(1つはf(X)の定義)現れる[abc]を文字で置いて2byte短縮可能です:

x:abc
f(X):xXpq
f()f(uvf()wvu)wf(u)vf()f()xx【26byte】

よりよい方法は, 「辿り終わった後に余分に実行しても構わない」ということに注目したものです.
(逆に言えば, 止まらないといけない部分では使えません).
つまり, 最後に[pq][pq]を足して考えてやればよいのです.
このことで, [abc]の部分を新たに文字で置かずとも1文字に変形できます.

f(X):abcXpq
f()f(uvf()wvu)wf(u)vf()f()[abc][abc][pq][pq]【28+4byte】
f(X):abcXpq
f()f(uvf()wvu)wf(u)vf()f()[abc]f()[pq]【28byte】
f(X):abcXpq
f()f(uvf()wvu)wf(u)vf()f()f(f())【24byte】

予告通り, 24byteに短縮することができました! 今回は「f(X):[abc]X[pq]」という関数による短縮を紹介しましたが, これで全ての[abc][pq]が処理できるのは,

先頭から順に数えて, どの段階でも[abc]が[pq]よりもたくさんある

という状況に限られます. [pq]の方が少したくさんある場合などは,
一部の[pq]についてはこの関数とは別の方法(新たに文字でおくなど)で対処する必要があります.


なお, この「文字列を関数に置き換えて短縮していく」という作業は結構大変です.
しかも途中で1箇所間違えてカッコが1つ足りなかったりしても, 後から見つけるのが困難な場合が多いです.
短縮を繰り返すほど「見ても仕組みがよく分からないコード」が出来あがっていきます.
たくさんこの短縮を利用する場合は, こまめに実行してエラーが起きないか,
動きは想定通りかなどの検算をやりながら作業を進めるのが良いと思います.


今回のコードでは, いかにもたくさん反復されるもの[abc][pq]がありました.
「そんな上手い状況はそうそう現れないだろう」と思うかもしれませんが, 意外と適用例は多いです.
2例ほど紹介して終わることにしましょう. ちなみにどちらも別に深い意味のある動きではないです.

もちろん他の手法がより有力な場合もありますので, 「いつでもこういう関数」というよりは
あくまで選択肢の1つと考えてもらえればよいでしょう.

右側に付け加える

最初のf(X):abcXpqの場合に, Clear後に実行されない[pq]を敢えて付け加えることで短縮につながる例を紹介しました.
一方, パーツを作る際など, 余分に実行されると困る場合には, 敢えて付け加える方法は使えません.

「Clear後に実行される部分に付け加える」以外にも, 「実行されない部分に捨てる」短縮はありえます.
それは, 繰り返しや再帰の右側に付け加える場合です.
実例を見てみましょう.

a:rsslsrslssrslsrssslsrslsla
a
only_one_X_1.png

繰り返しだとか0変数再帰だとか呼ばれる形の構文ですね.
rslXsという関数で圧縮ができそうです. 試しにやってみると,

x:rsl
a:xxsxssxsxxxsxsla
a
x:rsl
f(X):xXs
a:f(f()f())f()xxf()f()la
a

となっていきます. しかし, xとsの個数が合っておらず, xが余分にあるため,
結局rslを定義する必要がでてきてやや未練の残るコードです.
「あとsが2つ余分にあれば...」という状況ですね.

このs2つを, 普段まず使われない部分に付け加えてやることで短縮が可能になります.

x:rsl
a:xxsxssxsxxxsxslass
a

とした上で短縮を施し,

f(X):rslXs
a:f(f()f())f()f(f(f()f()la))
a

が最終形ですね. 再帰の場合も同様に, 右側に付け加えることによる短縮がありえます.
通常, 再帰の右側に何かを書くのは無駄でしかないので盲点になりやすい考え方ですね.


添付ファイル: fileonly_one_X_1.png 93件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-19 (土) 10:11:34 (2097d)