ToDo:
http://shinh.skr.jp/m/?date=20120728#p02
の続き。
今日日本時間朝11時から2時間ほど、Rubyスピードゴルフ勝負をしようということになりました。普通に2週間問題として出題しますが、参加する人は自主的に (2hrs) という suffix を名前の後ろにつけて参加する感じで。その後は suffix を勝手にはずして縮めていけば良いです。 Ruby 以外も大歓迎ですが、競争する相手がいるかは残念ながら謎です。とりあえず3人は参加者が確保できてます。
ゴルフとか久しぶりっていう人僕もそうなのでぜひ。
問題はたぶん perlgolf にもあったマインスイーパ。サイズは違うけど。でもはじまるまで考えないでください。
(08:40)
Seed というのが優勝した。この人は GSL 的には今年入ってから Code A/S の下の方に一瞬あらわれては死んでる感じだったのが、なんか突然優勝した。まぁ正直相手の運も良かったんだと思う。
この人は半年だか1年くらい前の GSTL でかなり衝撃的な感じの4人抜きだか5人抜きだかをやったので、はやく Code S 来ないかなぁと思ってたけど、すごく時間がかかってしまった。俺はアイツだいぶ前から知ってるぜ…みたいなことを言いたいわけだけど、しかし SC2 とか今でも見てる人の半分くらいは優勝する前から知ってる気がするし、そして韓国的にはこの人 SC1 の時からやってたらしいし…
決勝も P やってる身としては面白かった。 PvP は他の race の人からするとつまらんらしく、相手側の MC の方が人気あることもあるのか、結構イマイチだったーと言ってる人多かったけど…
思うに PvP だけ "greedy" の定義が違うんだと思う。 tech を進めのが他のマッチアップにおける expo くらいで、 fast expo とかは double expo くらいの感覚な気がする。昔は 4gw 以外の戦略は全て tech が進めるという意味で greedy で、本当に 4gw しか無いのはつまらなかったと思う。でも今はラッシュ多いとはいえ、色んな種類の rush が増えて、少し tech が進めつつやる rush が多いので、 allin 要素が少し少ない…と思う。
最近の新しい人だと Symbol ってのが良いようだ。なんかまぁ普通に強いし、いろいろスタンダードに正しい感じのことしてる気がする。 muta より infestor 多用ってのも今風なんだと思う。
でもそんなのより Freaky というのが良い。 infestor が好きでしょうがないらしくて、何に対しても mass infestor で対抗する。当然弱いので Code A/S には来ない…でも GSTL では NSHoSeo の選手層の薄さのおかげか、結構出てるぽい。
あとはこの MKP の CC first vs 6pool に感心しましたね…
http://www.gomtv.net/2012gsls3/vod/67627
(11:03)
についてなんか書こうかと思いつつ、特に何も書くことがないっていうか、どう書くとまともな説明になるのかよくわからない。「libc は strip されてるからバックトレースにシンボルが出ないんじゃ」みたいな頭痛が痛くなる発言をちょくちょく聞く気がするんだけど、何をどう説明すりゃそのへん系統だてた説明になるのかよくわかってない。
まー素直に最近僕が学んだことみたいなのをだらだら書いてくと良いのかもしれないんだけど、今ひとつ基本が浸透してないジャンルなので、それはそれでこう全く関係ない反応とかあるとしんどかったりも。
(13:18)
LLVM に投げてた趣味パッチが submit されたぽい。
http://llvm.org/viewvc/llvm-project/?view=rev&revision=160899
こっち見るとわかるのはこれのせいで ICFPC に 15 分ほど出遅れたということですね…
http://llvm.org/bugs/show_bug.cgi?id=13351
内容はしょうもなくて、 GCC だと入ってるけど LLVM は入れない dwarf の情報をひとつ入れただけ。 binutils がそれ使って読まなくていいとこの読み飛ばしをやってるんで、できたバイナリを addr2line するのが10倍くらいはやくなったりする。
テスト結果変わるから修正したりテスト増やしたりしてて気付いたんだけど、 lit とかいうテストツール使ってるんだなと。ぱっと見 dejagnu みたいなもんなんだけど、こういうテストツールみたいなのはプロジェクトごとに再生産した方がいいのかもね…とか。
(12:43)
leonid 先生と会う機会があったので4時間とか喋ってた。印象はなんかこの人なんでもよく覚えてるな…っていう。色々興味深い話を聞いた。覚えてるので面白かったのは、
http://golf.shinh.org/p.rb?Verhoeff+Algorithm
の問題。これ python が異様に短いんだけど、これにはタネがあるっていう話。これ出題した SeeNoEvil さんは短いコードを submit してあったんだけど、他の誰もタネに気付かないからヒント、ってことで SeeEvilRedBalloon って名前で投稿したと、で red balloon は base128 のデコーダ書けって話で、こっちの問題のテストケースを base128 で溶かすと python コードが出てくるからそれを exec するだけ…て話らしい。おもろい。
で、なんか coding session みたいなのすると楽しいんじゃないかってことだったので、いいねってことで、今度の月曜のたぶん19時くらいに問題投稿して1,2時間程度の勝負をしようみたいな話になった。日本時間だと火曜11時? 参加しにくそうですが暇な人は競ってくれればな…と思います。
あと言ってたのは、ペアプロでやるとかも面白そうだね、とか。チーム戦とか楽しそうではある…
(14:13)
4人席で2人で昼飯喰ってて、外人が寄ってきて、なんか聞く。文脈的に、「この椅子持っていっていい? 」か「この椅子誰か使ってるわけじゃないよね?」とかそんな質問である。実際僕の漠然としたリスニング能力も特にこの仮説を否定しない。
でこのへんで僕は投機的に yes と言ってしまう。質問がどっちだとしても、日本語だと、「うん」が正しい答えだから。で、言ってしまってから、ああ否定質問に、日本語で言う「うん」と言うには No という必要がある、っていう超基本的なことが頭によぎって、しまった No と言いなおさなきゃ、でもそれ以前にそもそも大本の質問は後者なんだっけ…とか、そのあたりでこう脳は全力で考えてるもののなにか言わなけりゃ、ということでタイムアウトした時の処理が走ることになる。タイムアウトの処理は比較的単純で、前回発話した単語からハッシュをひいて、その後にマルコフ連鎖的な意味で一番頻度が高い単語が出てくる。 "Yes" と既に言ってしまってるから、そのあとの単語は人工無能的には当然 please である。
この yes please というのは論外だってのは最初からわかってるし、そもそも sure とか go ahead とか言っときゃ無難だったのはすぐわかるんだけど、しかしこう既に愚かな発言をした後であって、はてどうしたもんかと思ってる間に相手は椅子を持ち去ってくれて、特に問題は起きない。いやあ相手が適当にこっちの意図を組んでくれる人で良かったなーと思うんだけど、 google ではたらいてる人とかはこういう意図を組んでくれる確率が非常に高くて、まあなんだかんだで頭いい人達だってことなのかなぁとかよく思う。あんまそれに頼って意思疎通するのよくないよね…
(15:19)
あと、なんかこう、 I always uses とかよく言ってしまう、って話をした。 uses は当然 use が正解。こういうミスをする理由もまたマルコフ連鎖で、僕の中では I or you なら動詞は use で、「それ以外」なら uses 、ってのが結びつけられてる。この時なんでまちがうかっていうと、 always がはさまってて、それは「それ以外」だから uses だろう、みたいな、ここまではほとんど考えてないレベルでの脳の反応だと思う。
でまあ、これはべつにひとつ前の話と違って、まぁぶっちゃけ間違っても問題なく通じるから、単純にほっとくと良い。言いなおしたりするとかえって混乱を招くから、言いなおすべきじゃない。そのへんはわかってるんだけど、しかし頭の中では「あー今 s/uses/use/ だなー」とか考えちゃう。それはまぁ日本語とかだとそんな問題なくて、多少ヘンな喋りかたしてしまって(こいうのは敬語がからむと結構あるころで、敬語で言うべき動詞を丁寧語で言っちゃった時とかに一瞬考えると思う)もまぁそこまで会話の流れに影響を及ぼさないんだけど、英語でこの手のミスをすると、「あーしくった!」「今のusesはuseと言うべきだった」「あーalwaysがはさまったせいだな!」とか、そいう思考が脳をかけめぐってしまう。でも、英語喋ってる時とかは少ない脳のCPUリソースが全部英会話に行ってるわけで、かつ全ての思考を英語に使わないとキツいわけで、比較的重要でないs/uses/use/問題とかにCPU時間を使ってる場合ではない。でもなんかあれこれ考えてしまって…みたいな感じで、よく詰む。
(15:33)
アンタのコードは大きいマップで大丈夫なの? と聞かれた。いい質問だなぁと思ったので、 tanakh さんとこのチームのリポジトリにランダム生成されたマップがあったなーと思い出したので、適当にやってみた。
https://github.com/tanakh/ICFP2012
結果としては、 128 と 256 くらいはまー一応 positive なスコア返す結果を出してるみたいだ。 1024 は10秒くらいで切り上げるとなんか 1byte とかの結果出してて、つまりとなりの lambda 取っただけ、って感じですかね…もうちょい待つとまぁそれなりに長い答えが出たり出なかったり。まぁでも正直動いてることに感心、ってだけの話ですね…
一応画面の更新は Growth のタイミング以外では全体をなめないようにしてあるんで、 befunge とはいえ、まぁまぁな速度で動いてるはずなんで、まーそんなもんかなー的な感じ…
(15:43)
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
via http://research.swtch.com/qsort
「quicksort の最悪計算量は O(n^2) ですよ、でも pivot のとりかたとかでだいたい大丈夫にすることはできますよ」、ってのはよく言われる話だけど、実際 quicksort が n^2 になるようなデータを作る方法を考えてみた、っていう話。
作りかたがちょっと面白くて、 qsort を実際に呼んで、 callback で呼ばれる比較関数で小さい数字から少しずつデータを確定させていく、みたいな。
このコード、 mac とか linux で実行してみると n^2 にならない。 russ cox によると glibc の qsort は実際は merge sort らしいからそういうもんらしい。 mac もそういう感じなのかな。 N が小さい時はわりと n^2 ぽい挙動してるけど…
ぱっとコード見た感じ、 2*(log(N)-1) 回越えて再帰する時は heapsort する、みたいなコードに見えるかな。まーなんとなくわからんでもないし、あとまぁそれならそういう挙動するかな的な。
自分で適当に qsort 書いてみて antiqsort に渡してみたら、モロに O(n^2) になった。おもしろい。 qsort は C だとっていうか余計なメモリ使わない実装は結構むずかしいと思ってて、昔書いた時はすっと書けなかった気がするけど、今回はそんなに苦労しなかった。全然テストしてないからあってるかは知らんけど。
void myqsort(void* base, size_t nel, size_t width,
int (*compar)(const void*, const void*)) {
char* pivot = (char*)base;
char* b = pivot + width;
char* e = (char*)base + nel * width;
char* buf = (char*)malloc(width);
size_t lc = 0;
while (b < e) {
int r = compar(pivot, b);
if (r >= 0) {
b += width;
lc++;
} else {
e -= width;
memcpy(buf, b, width);
memcpy(b, e, width);
memcpy(e, buf, width);
}
}
if (lc) {
memcpy(buf, b - width, width);
memcpy(b - width, pivot, width);
memcpy(pivot, buf, width);
myqsort(pivot, lc, width, compar);
}
free(buf);
if (nel - 1 - lc)
myqsort(b, nel - 1 - lc, width, compar);
}
(16:59)
こういうマップを妄想してた。
###L### # \\\ # # # # # # # #* # # * * # # * # # # # # #* # # # # # # *# # * * # # * # # # # R # #######
僕の AI に解かせてみたところ、なるほどこのロボット頭で岩止めれるのか…と気付いた。
(01:56)
2時に寝て8時に起きてしんどすぎると二度寝して、11時くらいと12時くらいと1時くらいと2時くらいでそれを繰り返して、明日からアメリカだから休もう…とメール書いた。で、また3時くらいでそれをやって、その時飯を喰って、あと2回そういう繰り返しをして今に至るがまだ体だるい…
とりあえずそろそろ準備しないとな…
(19:41)
http://herpolhode.com/rob/utah2000.pdf
読んだ。まーそうなんだろなっていう。よくわかってないけど CS とか半分くらいはそろそろ大学でやることじゃないんじゃないかな…てのは割とずっと思ってることだけど。
計算量とか数学系は続けりゃいいと思うし、科学技術計算のための大型計算機とかもやりゃいいと思う。ただシステムプログラミングとかは、もう企業にやらせりゃいいんじゃないかな…ていう感はある。12年前の rob pike の苦言を見て、そんな感じなんだろうなあと今思うてことは、たぶんあんま良くなってないんだろうな…
(21:43)
kinaba さんの動画ぼんやり見ててソルバというかシミュレータのバグに気付いた。
トランポリンの入口入った時に同じ出口に向かうやつ全部消えるってやつ、消さなくても次入ったら消える感じでいいかなーと思ってたけど、上に乗ってた石は動きだすべきなんだね…くそう完全に正しいの作れたかなーと思ってたのにがっかりだ。
これくらいはまぁ大変だけど実装できた気がするな。つっても1時間くらいはかかるだろうから、きわどいところだなー。
C++ より次元が多くてすばらしく見える Befunge 欠点は変更がしづらいことで、基本一度書いたコードの位置を移動させようとすると、多大な苦労を強いられることになる。特にメモリレイアウトとか変えようとすると死ぬので、最初にだいたいこういう感じで書こう…と決めた通りになるべく進めたい。
読みにくいのも問題といえば問題で、あーあそこバグってるなーと思っても、実際バグってるコードを探すのが結構大変。たった100行程度のコードなのに! 普通はそういうのをふせぐためにコメントを書いたりすると良いわけだけど、コメントがこれまた書きづらい。というのは、コメントに副作用があるのが問題で、ここは絶対に実行されてない、と確信を持つのに時間がかかるし、将来的にここを通したくなることは無い、って言える場所が少ない。例えば、
> このへんからメインループがはじまる
>
| ゴール判定のためにラムダの残り数を数えるコードがこのへんにある
goal->@
^ 1ターンが終わると端を通って戻る
みたいなコードがあって、上の例だと親切のつもりで書いた goal ってコメントが、 g は Befunge では実行できる命令なので、特にエラーも出ず、スタックの長さが突然変わることになる。この例みたいな重要なコードパスならまーすぐ気付くだろうけど、あんまり通らないとことか、あるいは今トランポリンを集中工事してるんだ、って時に洪水のとこがバグったりすると、すごい遅れて気付くことになる。というわけで今集中してるとこ以外はいじらないのが得策で、コメントもほとんど書けない感じだった。一応、未実装のとこは付近に空間ができがちなんで、 @ で潰して近くに文字列置いたりはしてたけど。
うーむ残念だ。他にもバグあったりするかなぁ…
(00:43)
README が文章も typo も無茶苦茶ですがな。英語がうんぬん以前に論理的につながって無い系。
こう疲れてるんで、 README は後から提出できる感じにしてほしいよね…
(01:21)
3日間聞いてたのは、ウテナ→ミク→ぷよm@s という感じだった。基本的になんかやかましいのが鳴ってると集中できるんだけど、ウテナとかミクずっとはさすがにうざい。ていうかミクはわりとすぐにつらくなってやめた。
ぷよm@s は色んな音が流れつつ、たまにやかましいのが流れるのが僕的には作業向けなんだけど、丈が短いからすぐループしはじめる。別な part に移動したらいいんだけど、今回は細心の注意が必要すぎる作業をしてたので、結果としてなんかずっと同じ曲聞いてた気がする…
それで思い出したんだけど、 part27 のあずささんの連鎖がいつ見てもすごいと思い出した。コレの11手目。
http://ips.karou.jp/simu/pv.html?_0uk8iiSkCukaiucgkwkIcgcKMKW-S1
via http://unknown72.seesaa.net/article/235037702.html
フツーに考えるとこういう12手発火5連になる気がする。作中で指摘されてたのは4+5の4ダブで、初代だとそっちの方がいいんだろうけど。
http://ips.karou.jp/simu/pe.html?_0uk8iiSkCukaiucgkwkIcIcaMKW-S1
(01:50)
| 前 | 2025年 7月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
_ mtve [:)]