近況
風邪ひきました。風邪をひくとしんどいので健康に生きようと思うんですが、健康だとだらだら生きたくなるので難しいです。
Elias delta to Fibonacciおわた
http://golf.shinh.org/reveal.rb?Elias+delta+to+Fibonacci/flagitious/1192543347
えらいことになってます。風邪引いててしんどいですが、まあ調べながらしんどくなるまで書きます。
とりあえず意味不明なマジックナンバーから調べましょう、ということで。
irb(main):059:0> 2564/4181.0 => 0.613250418560153
これは黄金比ですね。フィボナッチ数列の隣り合う二項の比は黄金比になることが知られています。
「9227465」は34項目のフィボナッチ数です。wikipedia参照。
で、いい感じに33とかいう文字列がありますね。まあよく分かりませんが適当にこんなのを実行すると。
irb(main):063:0> v=9227465 => 9227465 irb(main):064:0> 33.times{print "%8d"%[v=-~v*2584/4181]} 5702887 3524578 2178309 1346269 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1=> 33
フィボナッチ数列が逆順に出力されます!かっこえーですね。
さてマジックナンバーもわかったので、読める形に直したコードにコメントをつけてみましたが、どうみても読めません。本当にありがとうございました。
あとだるいのでテストしてません動かなかったらごめんなさいですが誰も多分困りません。
#!ruby -p while q = $_ =~ /1/ # q には文字列先頭から並んでいる 0 の個数が入ってます わかれ! # 物凄く適当に説明すると、デルタ符号は # [0が並んでる部分][1][始めの0が並んでる部分と同じ長さのコード(ガンマ符号で元の整数のビット数が入ってる)][元の整数のビット列から頭を取り除いたもの] # みたいな感じになってるので 0 の個数を知る必要があるわけですね q = eval('x = 0b1'+$'[/.{#{q}}/]) - 1 # 残ったコードから並んでいた0の個数だけ取り出す ガンマ符号の部分です # x は二進数リテラルをうまく使って元の整数のビット数が代入されます # q はそれより一つ少ない値です v = 9227465 # v は34項目のフィボナッチ数です $_ = $' # 処理した部分を捨てる q = eval('x = 0b1'+$'[/.{\#{q}}/]) - 1 # 上と同じコードですが、違うことをします # q は「元の整数のビット列の長さ数 - 1」でした # デルタ符号では元の整数のビット列が頭を取り除かれた状態で符号化されているので # q 文字分持ってくるとうまい事変換できるわけです わかれ! # ということでめでたく x に元の整数が代入されました # q には x - 1 がやはり代入されます # 既に二つ(頭に並んでいる0の個数、ガンマ符号で表されたビット列の長さ)の使い方をされている q ですが、後でまた別の使い方をします # キモいですね v = 9227465 # 同じ代入を二度しているため冗長に見えるかもしれませんが、 # 元のコードでは eval を使って「"ソースコード"*2」のような形にしているので問題ないです $_=$' # 処理した部分を捨てる # ここでしんどいので続きはWebで!とかでしめようと思いましたがまあ頑張ります 33.times{|n| x %= v # v は (34-n) 項目のフィボナッチ数です わかれ! # x はデルタ符号から変換された整数でした # 処理し終わった分だけ取り除く処理をしています w = v * 2584 / 4181 + 1 # w は (33-n) 項目のフィボナッチ数です o = [ x / w, (x < q ? o : 1)] # とてもキモい部分なので覚悟して読んでください 説明も適当です # まず x / w は (33-n) 番目のフィボナッチ数が使われていれば 1 そうでなければ 0 になります # 理由は自分で考えてください…分かりますよね! # (x < q ? o : 1) はキモい # q = x - 1 でした。よって x の値が x %= v で減ってない限りは偽になります # 偽になり続ける限り [ 0, 1 ] または [ 1, 1 ] が代入されます # 真になる一つ前のループで o は [ 1 , 1 ] になります # これは終端を表す "11" になってます わかれ! # x が x %= v で減っていた場合、x < q は真になります。 # 真だと x / w と o(自分自身)を要素に持つ配列が o に代入されます # すると o が[ 0, [ 1, [ 0, ..... [ 1 ,1 ]]]]] のような多重配列になります。 # わあ符号化できちゃった! v = w # 次のループのために一つ前のフィボナッチ数にしておきます } $><< o # o は符号化されたコードが多重ネストで入っている配列です # $><< や print で出力するとあら不思議。join されてちゃんと出力されます end # まだ終わってないよ # 最終的に処理が終わると01の部分が全て取り除かれて $_ = "\n" のような状態に # これを -p オプションで出力することで改行を出力します
風邪でだるいのにこんなことをしていては治るものも治りませんから、よい子は真似してはいけません。
えーと、先に fibonacci code の変換の仕方説明したほうがよかった気がしますがもうだるいので誰か偉い人やってください…
全体的に記述があほなので元気になったら書き直す。