Hatena::ブログ(Diary)

菊やんの雑記帳

2008-09-14 Quine.grassネタバレ

[][] さすがにもう縮まないのでネタバレ 22:23  さすがにもう縮まないのでネタバレ - 菊やんの雑記帳 を含むブックマーク

最終的に1525バイトになった。劇的に縮められる新機軸はもうなさそうなのでネタバレ

データは以下のようにひとつの関数エンコードする。すなわち「w → Ww」「W→WWw」「v→WWWw」になる。

  let.dat = abs o1 do
    let.o2 = o1(o1) # w
    let.o3 = o1(o2) # W
    let.o4 = o1(o3) # v
    let.o5 = o4(o4) # w
    let.o6 = o4(o5) # W
    let.o7 = o4(o6) # v
  end

スタックの少し前にある関数スタックのトップを適用すると、スタック位置の差によって「wWv」のいずれかが出力される。

よって、oN は次のように動作しないといけない。

o3(o3) -> (out w); o4   |    (out Ww);   o4
o2(o3) -> (out W); o4   |    (out WWw);  o4
o1(o3) -> (out v); o4   |    (out WWWw); o4

エンコード前のデータを出力するときは左の結果、エンコード後のデータなら右。

ふたつの動作はほとんど同じなので、各々トリプルを作ってdatをスキャンする関数に渡せばよい

ラムダ計算ではトリプルはこうやって作る。

  let.triplet = abs a, b, c, f do
    f(a, b, c)
  end
  let.tr1 = triplet(out_w, out_W, out_v)
  let.tr2 = triplet(out_Ww, out_WWw, out_WWWw)

  scan_dat(tr1)  # エンコード前のデータが出力される
  scan_dat(tr2)  # エンコード後のデータが出力される

あとはscan_datをどう作るかである。

oNはoMを受け取ったら、(M-N)%3を計算して、o(M+1)を返さないといけないので、

とりあえずは

  let.oN = abs my, tr, n, oM do
    ... 
    (exec_tr tr (m_n_mod3 (get_m oM) n)))
    ...
    (my my tr (succ (get_m oM)))
  end

こういう感じになると思う。

ここで、問題になるのは

o3 == (oN oN tr 3)
o2 == (oN oN tr 2)

という感じに、oNとoMの中身は同じ関数なので、oMからMをとってくる機能もこの関数の中にいれないといけないのである。

これが今回一番難しいところだ。

2008-09-13 結局、新しい方法を実装しちまった

[][] 新しい方法があまりに斬新なので 06:21  新しい方法があまりに斬新なので - 菊やんの雑記帳 を含むブックマーク

一晩で実装してしまった。

$ ruby grass.rb quine5.grass >quine5-out.grass
$ cmp quine5.grass quine5-out.grass 
$ ls -l quine5*
-rw-r--r-- 1 kik kik 2462 2008-09-13 06:19 quine5-out.grass
-rw-r--r-- 1 kik kik 2462 2008-09-13 06:19 quine5.grass
-rw-r--r-- 1 kik kik 2199 2008-09-13 06:19 quine5.rb

やべえ、最適化なんてまったくしてないのに、2462バイトしかねえぞ

以下、新しいエンコード方法

新しい方法では

wwWWWwwwv

エンコードすると

WwWwWwwWwwWwwWwWwWwWwww

になる。うはwこれ以上ww簡単にできねえwww

2008-09-12 Quine.grassの続きの続き

[][] wWvを生成するコードをもらってきた 02:42  wWvを生成するコードをもらってきた - 菊やんの雑記帳 を含むブックマーク

昨日の続き

wWvを生成するコードを短くして、細かい最適化をやったところ

$ time ruby grass.rb quine4.grass >quine4-out.grass

real    0m0.796s
user    0m0.704s
sys     0m0.040s
$ cmp quine4.grass quine4-out.grass 
$ ls -l quine4*
-rw-r--r-- 1 kik kik 8947 2008-09-13 02:34 quine4-out.grass
-rw-r--r-- 1 kik kik 8947 2008-09-13 02:34 quine4.grass
-rw-r--r-- 1 kik kik 1958 2008-09-13 02:34 quine4.rb

なんとか9kBを切った。そんなに遅くはないのだけれど、それでもゴルフ鯖はタイムアウトする。

今日はランレングス圧縮する予定だったけどやめた。

一文字を10文字程度でエンコードする方法を思いついたので、明日はそれを試すかも。

以下コード。こうやって見ると、なんかまだ無駄がいっぱいありそうだ。

wwWWwWWWwWWWWWWw
vwwWWwWWWw
vwWWWwwwwwWWWWwWWWwWWWWWwwwwWwwWWwWwwwwwwwwwwww
vWwwwWWwww
vwwWWWWWWWWww
vWwwwWWwwwWWWwwwwwwwwwww
vwwWwwwwwWwwwwwWwwwwwWwwwww
vwwWwwwwwWwwwwwwWwwwwwwwWwwwww
vwwWWWWWwWWWWWWwWWWWw
vwWWwwwwwwWWWwWwww
vwwWWWwWWWWWWWWwWWWWWwWWWWWWWwwwwwWwwwwwWWWWWWWWWWWWWWw
vwwWWWWWwwwwwwwwWWWWwWWWwWWWWWWWWwWWWWWWWwWWWWWWWWwwwwwwwwwwwwwWWWWwwWwwWwwwwwwwwww
vwwwwWWWwwwWWWWWwWwwwwWWWWw
vwwWWWwWwWwwww
vwWWwWwwwwwwwwwwWwwwwwwwwwwwwwwWWWwwwwwwwWwwwwwwwwwwwwwwwWWWWWWWWWWWWWWWWwWWWWWWwwwwwwwwwwwwwwWwwwwwwwwwwwwwwwww
vwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwwwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vwwwwWwwwwwWwww
vWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWw

そのあと、ちょっと減らして8790Bになった。

と思ったら、もっと短いエンコード方法あるじゃん。明日はそれを試す。

2008-09-11 Quine.grassの続き

[][] コードサイズをmainに比例するようにした 02:21  コードサイズをmainに比例するようにした - 菊やんの雑記帳 を含むブックマーク

昨日の続き。

昨日のはコードサイズがmainの自乗に比例していたので、1MBになった。

今回は定数倍ですむようにした。

定数倍にするには

let data p1 w W v =
  v(W(W(w(w(w(W(W(W(...(W(p1))...)))))))

let dat1 w W v =
  w (dat0 w W v)
in
let dat2 w W v =
  W (dat1 w W v)
in
let dat3 w W v =
  W (dat2 w W v)
in
let dat4 w W v =
  v (dat3 w W v)

のように、一文字あたり一関数エンコードするよりないと思うのだが、これではまめっちのと同じなので、

ちょっと工夫して

let dat1 w W v rec =
  rec dat0 w
in
let dat2 w W v rec =
  rec dat1 W
in
let dat3 w W v rec =
  rec dat2 W
in
let dat4 w W v rec =
  rec dat3 v

こうすると、一文字当たり約16文字でエンコードできるようになった。

この結果 30KB まで縮んだ。

「W」と「v」を生成するコードがいい加減なので、かなりバイト数を食ってる。

どっかにいい方法落ちてないかなと思って探してたら

http://d.hatena.ne.jp/youz/20080911/1221150265

こんなところにあった。

次はランレングス圧縮をやる

ku-ma-meku-ma-me 2008/09/12 02:39 16 文字エンコードきたああ

2008-09-10 quine.grass

[] Quine作った 01:03  Quine作った - 菊やんの雑記帳 を含むブックマーク

みんなQuine作ってるので、作ってみた。

$ time ruby grass.rb quine1.grass >quine1-out.grass 

real    1m16.528s
user    1m13.429s
sys     0m3.108s
$ cmp quine1.grass quine1-out.grass 
$ ls -l quine1*.grass
-rw-r--r-- 1 kik kik 1087824 2008-09-11 00:54 quine1-out.grass
-rw-r--r-- 1 kik kik 1087824 2008-09-11 00:45 quine1.grass

てきとーに作ったら1MBになった

dataとmain部分があって、dataにはmain部分がエンコードしておいてある

# data
let data p1 p2, p3 p4 = エンコードされたmain
in
# main
out(w)
out(w)
out(w)
out(w)
data(ラムダ内部を直接吐く引数) # data の定義を吐く
data(デコードして出力する引数) # data をデコードして吐く

問題はエンコードのしかたがいい加減なので、data は mainの自乗のサイズになることだ(ぉ。

その結果が1MB

ようするに

let data p1, w, W, v =
  v(W(W(w(w(w(W(W(W(...(W(p1))...)))))))

こうなってるから自乗になるわけだ。リニアにするのが難しいわけではまったくない。手抜き。まめっちのリニアに同じようなことをやってるのかな。