脳log[2011-09-25～]

最終更新: 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);
}

最終更新: 2011-09-17T05:22+0900

♪ [javascript] trailing commas ,

いくつかの点(文字列の行継続とか)で実装の追認をしてる 5th ed.ならいざしらず 3rd ed.では配列の末尾のカンマは無視できないだろう(IE8が正しい?)と思って昨日日記に書いたのだけど、よくよく読むとやっぱり IEが間違ってるっぽかったので消したのだった。

11.1.4 Array Initialiser

Syntax
 ArrayLiteral:
  [ Elision_opt ]
  [ ElementList ]
  [ ElementList , Elision_opt ]
 ElementList:
  Elision_opt AssignmentExpression
  ElementList , Elision_opt AssignmentExpression
 Elision:
  ,
  Elision ,

The production ArrayLiteral : [ ElementList , Elision_opt ] is evaluated as follows:
1. Evaluate ElementList.
2. Evaluate Elision; if not present, use the numeric value zero.
3. Call the [[Get]] method of Result(1) with argument "length".
4. Call the [[Put]] method of Result(1) with arguments "length" and (Result(2)+Result(3)).
5. Return Result(1).

The production Elision : , is evaluated as follows:
1. Return the numeric value 1.

The production Elision : Elision , is evaluated as follows:
1. Evaluate Elision.
2. Return (Result(1)+1).

1. Elision_opt(=カンマの 0以上の並び)は、カンマひとつにつき配列の長さをひとつ伸ばす。

2. ElementList: Elision_opt AssignmentExpressionや、ElementList: ElementList , Elision_opt AssignmentExpressionのように、Elision_optの右に AssignmentExpressionが隣接してるときはその数え方で自然。

3. ArrayLiteral: [ Elision_opt ] や、ArrayLiteral: [ ElementList , Elision_opt ] の場合は、Elision_optのカンマはその個数プラス1の要素を作り出すように見えるので、末尾のカンマがひとつ無視されたように感じる。

こんな結果になるなんて、余計なお世話もいいところだと思うんだけどな……

>>> [1,2,3,,,].length
5
>>> [1,2,3,,].length
4
>>> [1,2,3,].length
3
>>> [1,2,3].length
3

サイズ1の undefined配列を作れたりはするけど……(べつに嬉しくない)

>>> [].length
0
>>> [,].length
1

ちなみに JSONでは、思想から予想される通りに、末尾の余分なカンマは不許可。要素の省略(undefinedになる)もできない。ちなみに配列と違ってオブジェクトの初期化では、末尾の余分なカンマは不許可(3rd ed.しか確かめてないが)。

Syntax
 ObjectLiteral :
  { }
  { PropertyNameAndValueList }
 PropertyNameAndValueList :
  PropertyName : AssignmentExpression
  PropertyNameAndValueList , PropertyName : AssignmentExpression

例えばこれが JavaScriptのオブジェクト {prop:value,...}や Rubyの連想配列 {key=>value,...}や Cの enum {LABEL=1,...}の話であれば、末尾のカンマをあえて無視するのもいいだろう。要素の追加や並べ替えに便利なんだから。でも、JavaScriptの配列はダメだ。そこでは初期化の際に要素の省略ができる。空白に意味があるのだ。カンマの前後の空白の要素に関して、末尾だけ特別扱い(してるように見える)なんてのは不細工きわまりない。

最終更新: 2011-08-31T22:36+0900

♪ 日本人とルール。

なんか日本人って違うぞ？という疑問に答える本(著者はホンダの人)と大好きなコピペ。ただ、裏をかいたつもりでも法律の恣意的な運用で逮捕されたりはするのかな？ひろゆきとかホリエモンはどれでしょう。

ずるい!? なぜ欧米人は平気でルールを変えるのか (ディスカヴァー携書)
青木 高夫
ディスカヴァー・トゥエンティワン
￥ 1,050

世の中には５種類の人間が居る。

ルールを知らない奴。
ルールを守る奴。
ルールを破る奴。
ルールの裏をかく奴。
ルールを作る奴。

書いた順番に弱い。