PythonワンライナーでBrainf*ckインタプリタ(第零部)
9月11日の日記の中に書いていた内容を切り出して一つのエントリーにしました。以下。
OSASKの川合さんの「BIOSを圧縮してしまってOSASKを入れる」という話を聞いていて全く無関係にワンライナーをさらに圧縮してしまえばさらに短くなると思いついてしまいました。 復元コードが簡単で短くないといけないので長くて頻出する部分文字列を使われていない文字に変換するのが一番ですね。
>>> eval("".join({"^":"lambda ","$":"10"}.get(c,c) for c in"(^x:x+$)($)"))
20
解凍用のプログラムが58文字なのでlambdaが10個あればお得になりますね。 (中略) で、Pythonワンライナーを圧縮するストーリーの続き。解凍用のロジックを導入済みであれば、 長さN出現回数Mの文字列を使われていない1文字に変換することで、 解凍ロジックの長さは 7 + N 文字増え、コードの長さは (N - 1) * M 文字減るので、全体で MN - M - N - 7 文字の削減になります。ささださんの提案された自動ワンライナー化をした場合の嫌なところはよく似たコードだらけになって非効率なところなのですけど、圧縮することを前提にすればそれはそれで悪くないのかも知れませんね。人力で
x.__setitem__("foo", 1) or
x.__setitem__("bar", 2) or
x.__setitem__("baz", 3)
# 77文字
を
[x.__setitem__(k,v)for (k,v)in[("foo",1),("bar",2),("baz",3)]]and 0
# 67文字
にするよりも
@foo", 1) or @bar", 2) or @baz", 3) # 35文字 ただし22文字解凍部分で増える
にする方が、同じ「同じ物をまとめる」でもPythonの文法に縛られない分大胆に同じ物をまとめられるので小さくなりそうです。
で、この圧縮解凍を試すためにはターゲットとなるワンライナーが必要なので作りかけた物が以下。まだワンライナーになりきっていないBrainf*ckインタプリタ。一応TAKESAKO @ Yet another Cybozu Labs: Brainf*ckで100までの素数を列挙してみるテストのコードが走ることは確認済みです。 pointerなどの値をglobalsに入れれば参照部分はmem["pointer"]じゃなくてpointerだけになるのだけどそこを手で修正して圧縮するのと機械的に文字列だけ見て圧縮するのとどちらがいいのやら。
# BF Interpreter
import sys
from itertools import count, ifilter
jumpGen = lambda k: lambda :(mem.get(mem["pointer"], 0) == 0) ^ (k == -1) and (mem.__setitem__("t", mem["caret"] + k) or mem.__setitem__("depth", 1) or ifilter(bool, (mem.__setitem__("depth", mem["depth"] + {"]": -1, "[": 1}.get(code[mem["t"]], 0) * k) or mem["depth"] == 0 or mem.__setitem__("t", mem["t"] + k) for x in count())).next() and mem.__setitem__("caret", mem["t"] + 1) or 1) or mem.__setitem__("caret", mem["caret"] + 1)
globals().__setitem__("mem", {"pointer": 0, "caret": 0})
mem.update(
{
">": lambda :
mem.__setitem__("caret", mem["caret"] + 1) or
mem.__setitem__("pointer", mem["pointer"] + 1),
"<": lambda :
mem.__setitem__("caret", mem["caret"] + 1) or
mem.__setitem__("pointer", mem["pointer"] - 1),
"+": lambda :
mem.__setitem__(mem["pointer"], (mem.get(mem["pointer"], 0) + 1) % 256) or
mem.__setitem__("caret", mem["caret"] + 1),
"-": lambda :
mem.__setitem__(mem["pointer"], (mem.get(mem["pointer"], 0) + 255) % 256) or
mem.__setitem__("caret", mem["caret"] + 1),
".": lambda :
sys.stdout.write(chr(mem.get(mem["pointer"], 0))) or
mem.__setitem__("caret", mem["caret"] + 1),
",": lambda :
mem.__setitem__(mem["pointer"], ord(raw_input(">")[0]) % 256) or
mem.__setitem__("caret", mem["caret"] + 1),
"[": jumpGen(1),
"]": jumpGen(-1),
}
)
code = file("primes.txt").read() # sys.argv[1]
while mem["caret"] < len(code):
mem[code[mem["caret"]]]()
今までならこの後jumpGenを2回呼び出すために何らかの辞書に入れてからそれを参照するコードが必要になるのですが、文字列的な圧縮が行われることを前提にすると、この長ったらしい関数定義をそのままコピペで2回使った方が短くなる可能性が高いです。
ただ今の解凍コードでは解凍は一段階だから関数定義自体は圧縮できなくてちょっともったいないかもしれないですね。
最初のコードでは、文字の順に置換をしていったのだけど、そうではなくルール順に置換をするようにすれば、先に置換されるべき物を先に置くだけでよくなりますね。
>>> reduce(lambda x,y:x.replace(*y.split()), "@ ^+^|^ a".split("|"), "@*@")
'a+a*a+a'
