/ 最近 .rdf 追記 設定 本棚

脳log[2011-09-25~]



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++で3秒だという人のコードを読んでいた。自分でコードできるほど十分には理解してないけど見つけたアイディアだけ書いてみる。

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);
}

* というか大部分の時間を「a <<= ((d + 1) / 2);」を眺めることに費やしてた。「なぜ d(+1) bitしか必要ないのか?」「あちこちに現れる割る2とは何なのか?」


2011年09月20日 (火) Firefox6と Thunderbird6の stop the worldがひどい。おれは 8GBでも 4GBの時でもメモリには困ってなかった。今は頻繁な 5秒を超える停止時間にいらだってる。


2011年09月17日 (土) Songbirdのダメだな、と思うところ。リストの再生が終わる。リピート設定にはしてない。そういうときに再生しろ、とか次の曲を再生しろ、とかいうユーザーの操作(※グローバルホットキーだったりする)を受ける。でも何もしない。Songbirdは複数のリストを選択できるので若干複雑なのだけど、同じリストを再生するとか次のリストを再生するとかしたらいい。お前は何だ?■■■それと不具合ぽいの。1.アルバムの再生が終わる。2.違うアルバムをダブルクリックして再生しようとする。3.その違うアルバムの最後の曲が再生されて一曲だけで停止する。二つのアルバムの曲数が同じ時に起こるような気がする。そうでないときは期待通り一曲目から再生が始まる。


2011年09月16日 (金) 電影少女を読んだ。D・N・A2との共通点は多いが「神尾まい」は比べる対象がない。あの前髪とまゆ毛とその隔たりはまったくすばらしい。中身が(外面からの)期待を裏切らない悪魔だというのと、結局はやられ役の残念なキャラだというのもポイント高し。

最終更新: 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年09月15日 (木) タイムリーにも、思い出した頃にネルリの人に動きが>「ネルリ」石川博品の新作、「平家さんって幽霊じゃね?」前編公開 - Togetter


2011年09月14日 (水) 液晶テスト「この画像の中の数字全部読めない人の液晶はクズ(らしい)... on Twitpic」バックライト 0%でも 100%でもコントラスト 0%でも 100%でも、15 12 9 6まで読める。その右は枠の存在すらわからない。MDT243WG. モードによる違いが顕著。普段使いの sRGBは 6が本当にかろうじて見えるレベルだが IVテキストだと 6まで余裕。逆に TVやシネマはすべて真っ黒。一番右の 3はどうやっても存在を疑うレベル(枠も見えない)。■■■ 3が見えないのは Firefoxだから。Safariや Operaや IrfanViewなら見えた。


2011年09月13日 (火) じんあい。ちり・ほこり。じんかい。ちりあくた。塵埃が読めるのが我ながら不思議だったが、挨拶から推測したらしい。共通のパーツが使われていることすら認識してなかったが。


2011年09月12日 (月) Valkyrie Profile2. モンスターの部位を破壊して得たアイテムをもとに装備やスキルを得る。ネトゲやモンハンはやらないがこういう要素は好き。だがしかし、供給源たるモンスターが強さごとにきっちりダンジョンに配置され、ダンジョンはストーリー進行にあわせて開放されるというのが残念すぎる。入手できるアイテムやスキルがストーリー進行に沿ってコントロールされているのがありありとわかるのが興ざめ。DQ1(1986年発売)にも劣る。tri-Aceはバトルシステムがすべて(※)でストーリーなんて飾りなんだから、あとは探索する楽しみのあるバトルフィールドを用意してほしい。※SO2のちまちましたアイテム群や VP1の重層的な書き割りも好きだった。声も欠かせない。


2011年09月11日 (日) Throwing garbage on the sidewalk: The sad history of the rundll32 program - The Old New Thing - Site Home - MSDN Blogsrundll32.dllでてきとうな DLL(powrprof.dll)のてきとうな関数(SetSuspendState)を呼び出しても、何となくうまくいったりいかなかったりする理由。「push a hundred bytes of garbage onto the stack」タダではなかったのね。■■■Rubyがインストールされてるならこうする>20091121p01。Windows標準ツールでやりたいものだが。PowerShellは実行するまでが面倒くさい。JScript.NETもコンパイルが必要でもはや"Script"ではない。JScriptから利用する DynaCallとかあったなあ……。■■■「DynaCall で構造体を扱うという半ば反則的で一般のプログラマの怪訝そうな表情が浮かぼうが構わず楽しもうというサイト(デッドリンク)」ъ( ゜ー^) WSH補完クンのページとか Iriaとか Mysterious Syndromeを思い出す……。


2011年09月09日 (金) Firefox6. ver.4のときに書いた「ちまちまちまちまタブの横幅を変更されるとマウスで連続して閉じるのが大変」というのがいつのまにか改善してた。マウスがタブの上にある間は幅が変わらなくなってる。全く期待してなかっただけに嬉しい。


2011年09月06日 (火) Mobile Edy. 支払いの手続きが変わった。メールから一度 EZWebに接続して Edyアプリを起動するように手間が増えた。その間接ページは「ご購入者メールアドレス」の確認を行ってるように見えるが、それを確認して何が防げるだろう。アマゾンで Mobile Edyでの支払いを選ぶとケータイメールアドレスの入力(※1)を求められる。そこで入力したメールアドレスに(※2)メールが届き、そこからメールアドレス確認ページに飛んでるのだ。※2の部分の嘘(転送)はバレても※1の部分の嘘はわからんよ。■■■というのはあまり気にしてなくて、EZWeb接続に伴うパケット代と、「Edyアプリを起動する」という文字のように見えるが文字ではないリンクが、EZWebブラウザで画像を表示しない設定にしているとクリックできないことが気に入らない。その設定にするときに「ダウンロードやページの表示ができなくなる場合があります」と表示されるから、ま、なにかどうでもいいけど必要なことをしてるのかもしらん。その必要性がこちらの利益に繋がるのかは大いに疑わしいが。たぶんこれまでも着うたのダウンロードなんかができなかったんだろう。気付かなかったけど。>MySync専用USBケーブル■■■ auの Wi-Fi WINという機能。auが有料で提供してくれるものが何か、俺にはよくわからない。Wi-Fiに対応する携帯端末もインターネットに接続した無線LANも自前なのだ。EZWebサイトに接続できること?(追記:答えを見つけた>「なぜ自宅のWi-Fi環境を利用するのに、Wi-Fi WINでは別途、月額利用料が必要となるの?」)。それが不要なら月額525円を節約できて(、それでもインターネットに接続はできて)然るべきだがどうなってるだろう。「本サービスはベストエフォート型サービスです。」って、それを言うのは ISPであって auではない。厚顔無恥とはこのこと。■■■ことあるごとに書いておこう。俺は auが心底嫌いだ。だからといって、docomoが割高な料金に見合った堅実で誠実な商売をしてるかというとそうでもない(一部で auの悪いところの後追いをしてる)のだから乗り換えられない。足元見られてるよな。*SIGH*


2011年08月31日 (水) /.Jのリニューアル。こいつが憎い。「a:focus { outline: 0 none; }」これでフォーカスリングが消える。1pxの破線では不十分だからと userContent.cssで指定していたアウトラインもキャンセルされる。もちろん !importantを付けてキャンセルされないようにするんだけど、クソだ。どうせならマウスポインタも隠したらどうだ。チューチュー走り回られてさぞかし邪魔だろう。■■■Fx6と IE9と Safari5ではアウトラインだけでなくフォーカスリングまで消えた。Opera11.50はアウトライン(あるいは太いフォーカスリング)を表示しつづけた。自分の頭でユーザーのことを考えてるのは Operaだけなんじゃないか。


2011年08月30日 (火)

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

日本人とルール。

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

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

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

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

書いた順番に弱い。