naoya_t@hatenablog

いわゆるチラシノウラであります

ショートコーディング「世界を革命する力を」

golf あとで書く neta

ふとしたツイートからコードゴルフ大会が勃発

続きを読む

MacBook Airの電源アダプタが断線すると読書が捗る

Mac

でMacが使えなかったので、週末は「きつねさんでもわかるLLVM」とか「Real World OCaml」とか読んでました。

きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~
きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~
posted with amazlet at 13.07.01
柏木 餅子 風薬
インプレスジャパン
売り上げランキング: 1,220
Amazon.co.jpで詳細を見る

Real World OCaml
Real World OCaml
posted with amazlet at 13.07.01
Jason Hickey Anil Madhavapeddy Yaron Minsky
Oreilly & Associates Inc
売り上げランキング: 31,941
Amazon.co.jpで詳細を見る

Real World OCamlはβ版（HTML、無料）のやつですけど。


電源アダプタは互換品をポチりました。

【1年保証】APPLE 45W MagSafe 互換電源アダプタMac Book純正品質保証付（Ｌ字コネクタ）
【1年保証】APPLE 45W MagSafe 互換電源アダプタMac Book純正品質保証付（Ｌ字コネクタ）
posted with amazlet at 13.07.01
Remarks Japan
売り上げランキング: 529
Amazon.co.jpで詳細を見る

graph-tool（のMacへのインストールに挫折してvagrantと戯れるの巻）

Python グラフ理論 Mac

Pythonでグラフの最小カットを計算しようと思ったのだけれど、Wikipediaから拝借してきた最大フローを求めるFord-Fulkersonコードを元に書いたものでイマイチ速度が出なかった*1ので、速いと噂の
graph-tool
を試してみることにした。

brewで入れるとか、easy_installで入れるとか色々試したけれど自分のMac環境では依存関係のあちこち（Boost, CGAL, cairo, ...）で軒並み引っかかってビルドに失敗する。

Ubuntuだとapt-getで一発で入ったのに。

時間も気力も溶けて行くので、諦めてローカルにUbuntuのvirtualboxを立てて使うことにした。vagrant便利だし。
http://qiita.com/awakia/items/895b3d61311b19737237 あたりを見て

boxの選択は Ubuntu Quantal 64 (12.10) Vanilla (※389MB) にしてみる。

$ vagrant box add quantal64-vanilla https://dl.dropboxusercontent.com/u/165709740/boxes/quantal64-vanilla.box

$ vagrant init quantal64-vanilla

$ vagrant up

これで

$ vagrant ssh

ローカルのvirtualboxに入れる。

Pythonは2.7.3, 3.2.3が入っていた。

本家ダウンロードページにある指示どおりに /etc/apt/sources.list を編集し、apt-get update した後

vagrant@quantal64-vanilla:~$ sudo apt-get install python-graph-tool

など実行。graph-tool がさくっと入った。

Mac側のホームディレクトリでvagrantを立てたので、virtualbox側の /vagrant/ 以下にホームの内容が見える。個人的に使うにはとても便利。

Mac側でスクリプトを編集して

$ vim foo.py

中身はこんな感じ。ここの最初のプログラムから。

from graph_tool.all import *

g = Graph()

v1 = g.add_vertex()
v2 = g.add_vertex()

e = g.add_edge(v1, v2)

graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18,
           output_size=(200, 200), output="two-nodes.pdf")

print(v1.out_degree())

これをvirtualbox側で実行

vagrant@quantal64-vanilla:~$ python graph.py
** (graph.py:25309): WARNING **: Could not open X display

うーむ。
Xが開けないのはMac側に繋いでやればいいはずなので*2Mac側で

$ vim ~/.vagrant.d/boxes/quantal64-vanilla/virtualbox/Vagrantfile 
Vagrant::Config.run do |config|
  # This Vagrantfile is auto-generated by `vagrant package` to contain
  # the MAC address of the box. Custom configuration should be placed in
  # the actual `Vagrantfile` in this box.
  config.vm.base_mac = ...

  config.ssh.forward_x11 = true  ## ←この1行を追加
end

...

これでvagrantを立ち上げなおしたら行けるんじゃね

vagrant@quantal64-vanilla:~$ exit
logout
Connection to 127.0.0.1 closed.
$ vagrant halt
$ vagrant up
$ vagrant ssh
...
Last login: Wed Jun 26 07:11:08 2013 from 10.0.2.2
vagrant@quantal64-vanilla:~$ python graph.py
1

今度はうまく行った。
Mac側で

$ open two-nodes.pdf

すると
f:id:n4_t:20130626161813p:plain
ちゃんと出来てた。

*1:see gist https://gist.github.com/naoyat/5866296

*2:本当はXを開かずにどうにかできるオプションがあるのではないかと期待

PRML §8.3.3 例：画像のノイズ除去

PRML あとで書く Python グラフ理論

【次回復々習レーン（2013/7/21開催予定）の発表資料準備】

反復条件付きモード（ICM）での画像復元

  • 左上から順番に走査しながら、反転するとエネルギーを減らせるピクセルを反転
  • 走査前後のエネルギー差分がεを下回ったら（あるいは10回やったら）終了

MacBook Air (1.8 GHz Intel Core i7) でノイズ除去にかかった時間:

noise iter sec
5% 5 0.850
10% 6 1.037
15% 6 1.029
20% 8 1.374
25% 10 1.705
30% 8 1.373

320x180の画像をPythonで1秒前後で処理できています。
25%で走査数が多いのは気にしない（ノイズ生成パターンをいくつも作ったら吸収されると思う）

続きを読む

Pythonの辞書内包表記 (2.7〜)

Python

3.1で入ったのは聞いてたけれど、今使ってる2.7でも使えるの知らなかった＞＜

  • 集合のリテラル文法 ({1,2,3} は mutable set になります)
  • 辞書と集合の内包表記 ({i: i*2 for i in range(3)}).

see: http://docs.python.jp/2/whatsnew/2.7.html

コードテンプレート加筆 + TZTesterの文言変更

TopCoder

assert() を使おう

SRMがドジっ子アピールの場となっている現状を打破すべく

#define NDEBUG
$BEGINCUTS
#undef NDEBUG
$ENDCUTS
#include <cassert>

を追加。
全体だとこんな感じ→ https://gist.github.com/naoyat/5821991

これでローカルテストの時だけassert()が使える。こんな感じ。

typedef long long ll;

...

bool f(ll x) {
  ...
}

ll lo = 1LL, hi = LONG_LONG_MAX;
int z = 0;
while (true) {
  // lo:x hi:o
  assert(lo < hi);
  assert(0 <= lo);
  assert(!f(lo));
  assert(f(hi));
  if (lo+1 == hi) {
    return hi;
  }
  ll mi = (lo + hi)/2;
  if (f(mi)) hi = mi;
  else        lo = mi;
  assert(mi >= 0);
}

TZTester文言変更：Expected/Received を Expected/Your answer に変えてみる

SRM583 Div2 Easy "SwappingDigits" より。わざと間違えてます。

Test Case #0...PASSED (0.024 msec)
Test Case #1...PASSED (0.009 msec)
Test Case #2...PASSED (0.006 msec)
Test Case #3...FAILED (0.004 msec)
	   Expected: "10234"
	Your answer: "01234"
Test Case #4...FAILED (0.006 msec)
	   Expected: "13218910471211292496"
	Your answer: "03218919471211292416"
Test Case #5...FAILED (0.006 msec)
	   Expected: "10720376171328422763213753122612211005355347513"
	Your answer: "01720376171328422763213753122612211005355347513"

これでテスト失敗時の視認率が上がるかも。
https://github.com/naoyat/TZTester
↑他にも魔改造が施されているので、ご利用は計画的に＆自己責任で！

SRM撃墜大好きっ子に贈る：二分探索問題の撃墜 〜慎重に撃墜ケースを検討すべき一例〜

TopCoder

SRM582 Easy(250) "SpaceWarDiv1"

問題意訳

魔法少女（複数）と敵（複数）がいる。
魔法少女は自分と同等以下の敵を倒せるが、1人倒すたびにソウルジェムが濁っていく。
敵は全て倒したいが、ソウルジェムの濁りが特定の少女に集中し魔女化してしまうのを避けるため、戦闘回数を分散したい。
最大限にうまくやったとき、ソウルジェムの濁りはどこまで抑えられるか。

※雰囲気はそんな感じだけど正確なところは原文でちゃんと読んでください。writerは準急さん(semiexp)です。

続きを読む