脳log[2011-10-10～]

最終更新: 2011-10-09T21:43+0900

♪ [COSMOS] PS/2ポート(マウスとキーボード)が入れ替わってるの図。(M/Bは MSI 790FX-GD70)

緑のケーブルが紫のポートに、紫のケーブルが緑のポートに繋がってる。紫のケーブルは延長ケーブルで、キーボード(Majestouch)が繋がってる。緑の変換アダプタに繋がってる USBケーブルはトラックボール(TrackMan Marble)のもの。最初からではなく、2009年に USBキーボードの Excellioをダメ元で、ちょうど画像のトラックボールと同じ場所に同じように繋いでみてから、紫のポートがマウス用のポートになってしまった。入れ替わりで緑のポートはキーボード用に。こんなことってあるんだろうか。

偽画像をでっちあげるためにわざわざケーブルをつなぎ替えたりはしてないよ。PS/2だからホットプラグ対応でないし、キーボードが誤って抜けたときは再起動するまで使えへんし。面倒くさい。

アシュラ男爵みたいな両用ポートが一個だけついてるマザーボードがあるらしいから BIOSの制御次第であり得るのか。BIOSアップデートしても CMOSクリアしても入れ替わったまんまではあるけど。CMOSクリアするタイミングでつなぎ替えたら元に戻るかな。

PS/2仕様<面白い。全然わからんけど。BIOSは何を手がかりにマウスとキーボードを見分けられるのかなぁ、と。

最終更新: 2011-10-28T14:10+0900

♪ [tDiary] リファラ置換リスト(対google)晒し。

^http://www\.google\.(?:[^/]+)/url\?.*?[&;]cd=(1\d)\b.*?[&;]url=[^&;]*?(\d{6}[\dpct]*).*?[&;]q=([^&;]+).*$ google検索 \1th of「\3」→ \2
^http://www\.google\.(?:[^/]+)/url\?.*?[&;]cd=(\d*1)\b.*?[&;]url=[^&;]*?(\d{6}[\dpct]*).*?[&;]q=([^&;]+).*$ google検索 \1st of「\3」→ \2
^http://www\.google\.(?:[^/]+)/url\?.*?[&;]cd=(\d*2)\b.*?[&;]url=[^&;]*?(\d{6}[\dpct]*).*?[&;]q=([^&;]+).*$ google検索 \1nd of「\3」→ \2
^http://www\.google\.(?:[^/]+)/url\?.*?[&;]cd=(\d*3)\b.*?[&;]url=[^&;]*?(\d{6}[\dpct]*).*?[&;]q=([^&;]+).*$ google検索 \1rd of「\3」→ \2
^http://www\.google\.(?:[^/]+)/url\?.*?[&;]cd=(\d+).*?[&;]url=[^&;]*?(\d{6}[\dpct]*).*?[&;]q=([^&;]+).*$ google検索 \1th of「\3」→ \2

• 適用する順番が大事。
• 「Google、検索リファラを変更、検索ランキングデータが取得可能に::SEM R」
• 高機能なリファラプラグインであれば対応してるのかも。(使ってないので知らない)
• (愚痴) リファラをクリックして自分のサイトが出ても嬉しくないんだよね。検索画面が出れば高確率で自分が関心を持つであろう他のサイトを見つけられるし、自分のサイトが何番なのか画面外なのかもどうせわかるのに。
• 気付かないふりをしたかったけど、cd, url, qパラメータがこの順番で出現しないと置換に失敗する。数は少ないものの失敗するリファラがこの日記にも届いてる。Ruby 1.8では名前付きキャプチャ、使えないのかなー。
• これらの正規表現って URLを相手にしてるもんだとばっかり思ってたけど、tdiary.rbの disp_refererメソッドを見るに、%HHをデコードしたあとのどうしようもない文字列が相手のような……。(理解が正しければ)

パラメータの順番を仮定しないために、結局こうなった。名前付きキャプチャは関係なくて、繰り返し付きキャプチャに最終的に入るものを把握することが大事。

^http://www\.google\.(?:[^/]+)/url(?:[?&;](?:url=[^&;]*?(\d{6}[\dpct]*)[^&;]*|q=([^&;]+)|cd=(1\d)|(?!cd=)[^&;]*))*$ google検索 \3th of「\2」→ \1
^http://www\.google\.(?:[^/]+)/url(?:[?&;](?:url=[^&;]*?(\d{6}[\dpct]*)[^&;]*|q=([^&;]+)|cd=(\d*1)|(?!cd=)[^&;]*))*$ google検索 \3st of「\2」→ \1
^http://www\.google\.(?:[^/]+)/url(?:[?&;](?:url=[^&;]*?(\d{6}[\dpct]*)[^&;]*|q=([^&;]+)|cd=(\d*2)|(?!cd=)[^&;]*))*$ google検索 \3nd of「\2」→ \1
^http://www\.google\.(?:[^/]+)/url(?:[?&;](?:url=[^&;]*?(\d{6}[\dpct]*)[^&;]*|q=([^&;]+)|cd=(\d*3)|(?!cd=)[^&;]*))*$ google検索 \3rd of「\2」→ \1
^http://www\.google\.(?:[^/]+)/url(?:[?&;](?:url=[^&;]*?(\d{6}[\dpct]*)[^&;]*|q=([^&;]+)|cd=(\d+)|(?!cd=)[^&;]*))*$ google検索 \3th of「\2」→ \1

 自己言及

リファラ周りを覗いたついでに、セルフリンクの記録を解禁した。my-sequel.rbプラグインの機能を代替できるかな、と。

tdiary.confのベースとした tdiary.conf.sampleに最初からセルフリンクよけがあるのでこれを削除。dayモードからのリンクでないものを除外するように(=dayモードからのリンクだけを記録するように)ブラウザで設定した。(index.rbの有無とか日付を ?date=形式で渡してるかどうかとかサイトに合わせた調整が必要)

リンク元記録除外リスト
^http://vvvvvv\.sakura\.ne\.jp(?!/ds14050/diary/\d{8})

最新の日記にだけ表示される「以前の日記へのリンク元」からのリンクは自己言及とは言えずノイズでしかないので 05referer.rbの referer_save_currentに次のコードを挿入した。

# reject self-reference from (maybe) volatile list
return if referer.start_with?(@conf.base_url) and (date = referer.scan(/\b(\d{4})(\d\d)(\d\d)\b/).last) and latest_day?(Struct.new(:date).new(Time.local(*date)))

期待通り動いてるか動いてないかはまだ観察できてない。

「以前の日記へのリンク元」へセルフリンクを記録しない方法をとらなかったのは、そこで過去の日記の動きを観察したかったから。でもリストに記録された日からどこへ移動したかはわからないね。リファラを集約するときに「どこへ(のリンクか)」という情報を蔑ろにしたせいだ。余計なお世話だと思ってた googleの新しい形式(といっても2009年)のリファラがその情報を与えてくれてたりする。

 除外リスト

tdiary.conf.beginnerには FeedReaderからのリンクを記録しない設定が予め用意されている。俺も除外したいと思った。でも tdiary.conf.sampleには用意されていない。beginnerの定義、.beginnerと .sampleを分ける法が知りたい。

 2011-10-28

どうやら volatile referer listからのリンクの除外に失敗してる。原理的にリファラを表示したときとリンクを踏んだときの間に日記の投稿があった場合には除外できないんだけど、それにしては数が多い。volatile referer listは特別に内部リンクを表示しないことにする。

plugin/05referer.rb: referer_of_today_long

@referer_volatile.each_referer( limit ) do |count,ref|
	next if ref.start_with?(@conf.base_url) # この一行。
	result << %Q[<li>#{count} <a rel="nofollow" href="#{h ref}">#{h disp_referer( @referer_table, ref )}</a></li>\n]
end

最終更新: 2011-10-02T17:49+0900

♪ ジュンク堂ネット書店その2。(→その1)。

注文手続き中にこの本は以前購入したと教えてくれるけど、その本は在庫なしでキャンセルになったもので、持ってないんだ。知ってるでしょ。

漏れてた本を追加注文したかったが注文の変更はできない。さっき注文した本(10冊くらい)を一冊ずつ取り消す必要がある。その際も、まとめて取り消すことも連続して取り消すこともできずに冗長な操作を要求される。

キャンセルしてすぐ再注文するのがわかってるから、取り消しを行ったのと同じ注文履歴画面からそれぞれの本のページを前もって開いておいた。が、いざその時になって気付いたのだが「カートに入れる」ボタンがない！一度注文した本はもう買えないのかと思って(※ありえないとは思ったがこの程度の不合理はガラパゴスではあるかもしれないとも思った)、ログオフしてリロード(Ctrl+F5)してみたが変わらない。途方に暮れつつふと URLをみると*本を表す IDパラメータのほかに &Mode=show なんてくっついてる。これが「カートに入れる」ボタンを隠すコマンドだった。

アマゾンは購入したことを教えてくれはするけどカートに入れることを制限したりはしないよね？注文履歴から本を注文する人なんていないと思った？そこ(目的)は譲っても、あなた同じ本を二冊買おうとする客を体を張って止めたり(手段)しますか？ Webで数量の違いは見えにくいし、同じ本を誤って何度も買うのは本読み共通の悩みだから知らせてくれるのはいいが、その後どうするかは自由だ。選択肢を奪うな。

その1では商品ページにこっそりコンテクストを埋め込み、今度は商品ページの URLにコンテクスト情報を付加して、結果的にユーザーを欺いてる。前回も今回もまったくわけがわからないよ。

こんな 3、4回使っただけの人間の行動をカバーすること(※規制することじゃないよ)もできてないんじゃ、自分たちで使ってみることもしてないんじゃない？ハイレベルすぎて俺にこのサイトは満足に使えない。

最終更新: 2011-10-01T04:28+0900

♪ [Ruby] Google Code Jam Japan 練習問題

練習問題。それも Aだけ。Bは撃墜されました。

# small用
def last_output(n, k)
	snappers = [false] * n
	k.times{
		# 電流をたどってひっくり返す。
		0.upto(n-1){|i|
			snappers[i] = ! snappers[i]
			break if snappers[i] # previously OFF (=next snapper's IN was OFF)
		}
	}
	return snappers.all?
end

# large用
def last_output(n, k)
	# k1 = 2**n-1 # k1:最初に n個の snapperがすべて ONになる操作回数.
	# k = p*k1+(p-1) を満たす自然数pが存在するなら電球は ON.
	return (k+1)%(1<<n) == 0
end

caseno = 0
$stdin.readline; # drop # of cases.
$stdin.each_line{|ln|
	n,k = *ln.scan(/\d+/).map(&:to_i)
	break unless k
	caseno += 1
	puts "Case ##{caseno}: #{last_output(n,k)?'ON':'OFF'}"
}

最終更新: 2013-05-18T14:03+0900

♪ [ProjectEuler] Problem 205, Problem 300

 Problem 205

行き詰まっている。新しくなった Progress画面でテキトーに問題をクリックしたら勝率の高い(正答者数の多い)問題だったでござる。

# さいころふりふり
total4 = [0,1,1,1,1] + [0]*32 # サイコロを 1回振って出目(o)の合計が i(=1,2,3,4,...,36)である場合の数を total4[i]。0番目は単なるプレースホルダ。
8.times{ # 2-9回目
	(total4.size-1).downto(1){|i|
		total4[i] = (1..([4,i].min)).inject(0){|sum,o| sum + total4[i-o] }
	}
}
total6 = [0,1,1,1,1,1,1] + [0]*30
5.times{
	(total6.size-1).downto(1){|i|
		total6[i] = (1..([6,i].min)).inject(0){|sum,o| sum + total6[i-o] }
	}
}
# 集計
win4 = 0
sum4, sum6 = 0, 0
1.upto(36){|total|
	win4 += total4[total] * sum6
	sum4, sum6 = sum4 + total4[total], sum6 + total6[total]
}
p 1.0*win4/sum6/sum4

 Problem 300

5時間以上かかった……(実行に)。

Process.times: #<struct Struct::Tms utime=20471.855, stime=8.268, cutime=0.0, cstime=0.0>

どうすれば……。

1. すべての折りたたみパターンを列挙。(点対称は除いたつもり。鏡像はそのまま。593611通り)
2. パターンをコンタクトポイント(インデックスのペア)列に変換|sort|uniq。(12495通り)
3. すべてのタンパク(2^{15}通り)をさっき求めたコンタクトポイントの列(12495通り)に当てはめて(約408701758通り)、最良の H-Hコンタクトポイント数の合計を得る。

何の工夫もないナイーブなやり方だから手を付ける余地はあり余ってるんだろうけど、どういうやり方をしたらいいのか途方に暮れる。

スレッドを見たら先頭から 3つ 4つ立て続けに「brute force」の文字。それでも 20秒やら 3分で終わるらしい。バブルソートと同じくバカの代名詞(※ごく少数を対象にするなら妥当な選択肢)みたいに思ってるけど、その中でもさらに利口なのとバカなのとがあるのね。最低限のたしなみとして作業領域の大量コピーはしてないんだけど。

最初は 6時間かかったけど 12分に縮まったという人もいた。そういうことならもう少し手を入れてみよう。

 @2011-09-27

 1.折りたたみパターンの列挙

• 団子(直線や突起を含む)か、1つ以上の連結したドーナツ状になるしかない。
• 団子がコンタクトポイント数を稼ぐのに一番有利。

というあたりでひとつ(どうにかならないか？)。

おっと、ドーナツになるとコンタクトポイントにボーナス(+1)が付くのだった。

 2. 12495通りのコンタクトポイント列

• 頭としっぽの区別をなくしたら、半分とはいかないまでも減る。不可
• 他ののサブセットになってるのがあったら除外できる。12495→3409通り

 3. すべてのタンパク(2^{15}通り)をコンタクトポイントの列(12495通り)に当てはめる。(408701758通り)

手立てなし。

ステップ2でサブセットを除去したら 2分。ただし C++で。

最適化オプションを目に付いただけくっつけただけで 15秒になるんだもんな。>PE300.cpp C++で 3秒だという人がいるけど、これ以上の悪足掻きをするかは微妙。

しかしまあ、投稿されたコードを眺めると、アホな人間は自分から問題を難しくしてそれに四苦八苦してるような印象を受ける。自虐してるの？ 要するに、上にアップロードしたコードはもっとシンプルに書けるはずだ、と。HとPの長さ15の配列としてのタンパクを 0から 2^{15}未満の整数のビットパターンで表したり……。手立てなしとしたステップ3こそが実行時間の大半を占めてるので高速化のメインステージなのだ。再帰してる場合でも vectorをループで回してる場合でもないのだ。こういう筋トレっぽいトレーニングをしてくれる問題は貴重。これまで考えたことがないから。

 2011-10-17

優れた人々は無意識にやっているので、あまりこういうことは教えてもらえない(というか当然やっていますよねJK、などと思われていたりする)ので本書のように、あらためて書いてくれている本は大変貴重だと思った次第。すごい人達が「ナイーブな手法でいいんじゃね」という時は「本書で書いてあるようなことを当然踏まえた上で適切にナイーブな手法を組み合わせて使っている」という意味だったりするので十分注意したい。

ナイーブという単語に反応した。上の方で「何の工夫もないナイーブなやり方だから手を付ける余地はあり余ってるんだろうけど」と書いたときのナイーブはもちろん……。練習問題、やります。

 @2012-03-03

C++で３秒だという人のコードを読んでいた。自分でコードできるほど十分には理解してないけど見つけたアイディアだけ書いてみる。

for (auto a = s.begin(); a != s.end(); ++a) {
    bitset<64> _t = t & *a;
    m = max(m, (int)_t.count());
}

タンパク質(t)とコンタクトポイント列(a)が long long intで、sはコンタクトポイント列の集合。コンタクトポイント列とタンパク質の照合が bitwise andで済んでしまっている。

俺が vector<pair<char,char> >としたコンタクトポイント列がどのように long long intにパッキングされているのか。

 ペアの大小。

pair<char,char>は、タンパク質の先頭からのインデックス(0..14)を使って、(4,9)も (9,4)も表現できるが両者は同じなので (9,4)だけ表せればいい。インデックス iの(i+1番目の)アミノ酸とペアになりうるインデックスは全部で i種類。これなら必要ビット数は \sum_{i=0}^{14}i = 105。

 ペアの偶奇。

チェス盤の黒白を考えるとわかりやすいけど、黒いマスの隣には白いマスしかない。インデックスが奇数のアミノ酸(H,P)の隣にはインデックスが偶数のアミノ酸しかこない。これで情報を失わずに表現形を半分に減らせる。\sum_{i=0}^{14}\lceil\frac{i}{2}\rceil = \sum_{i=0}^{14}\lfloor\frac{i+1}{2}\rfloor = 56ビット(→床関数)。long long intに収まるサイズになった。

と、ここまで読んだ*んだけど、15ビット以上の整数型で表されるタンパク質を照合用の56ビット表現に変換するところの解読がまだ。プログラム全体としては無駄がなくて、そういう意味ではわかりやすいんだけど。(L=15; int hを long long int tに変換)

long long int t = 0;
for (int i = 0; i < L; ++i) {
    t <<= ((i + 1) / 2);
    if (h & (1 << i))
        for (int j = (i + 1) % 2; j < i; j += 2)
            if (h & (1 << j))
                t |= 1 << (j / 2);
}