Programming Archive

Google Code Jamというのに参加してみた。

ぎりぎりに参加するかという気になったせいもあって、時間がいきなり7時間になってた。おまけに夜中。申し込んでやらないのもしゃくなので、んだかんだで朝になった。くそー。

問題はというと、3題あって、小さい入力と、大きい入力が用意されてて、求められる出力を提出する。少なくとも、小さい入力と大きい入力をひとつづつクリアできれば、参加資格が得られるとかそんな感じ。出題はもちろん英語。おまけにはじめてなので、システムもよくわからなくて困った。でも、問題自体はひねりもない解ける問題（英語なのでそっちのほうがorz）

なんか、わざわざJavaで書くような問題じゃないよなー、とおもって久々にPerlで書いたらリファレンスの文法とか変数宣言とか復習しながら書くはめになってむしろ大変だった。2、3回か間違えたけど、大問を2つ答えておいた。

結果とかどうやってでるんかな？謎。

MacでもMacportsでGLPKを入れてコンパイルしてみたけどダメ。とりあえず、-lglpkオプションは通りません。ソースからコンパイルして、.oを指定すればコンパイルできましたが。このへんの振る舞いは、Macportsかaptかの違いくらいでDebianの振る舞いと同じ。

楽することはいったんあきらめてソースからコンパイルして、サンプルコードをsrc/*.oでコンパイルすればできた。そこで教えてもらったarを使って、

ar cru src/libglpk.a src/*.o

とすると、.oを.aにすることができて、libglpk.aを使ってコンパイルできた。

あとで気がついたことやけど、ソースからコンパイルするとsrc/.libs/っていうディレクトリがあって、その中には.oと、libglpk.aもあった。どうゆう構成になってんやろ？

ちなみに、Macportsでいれた、GLPKは、

ar x libglpk.a

で、.oに展開して試してみたけどコンパイルできんかった。Macportsはコンパイルしながらインストールしてたっぽいのにな。

あとDebianではsudoできんかった。なぜか今日はMacからのscpもパスワード入力ではじかれた。またなんとかなろう。久々に直接Linux使ったけどフォントの汚さが。。。

まだまだプロトタイプの段階ですが、将来的にプログにテキストで投稿すれば自動で図を描いてくれると便利だなぁと思って作ってみました。最近、グラフ描画のデモをごそごそやっていたのもそのためです。

Continue reading

Eadesの力学モデルをベースとしたグラフ描画をFlexで実装しています。辺交差がなくなるまで、周期的に大きな力を加えて局所解から脱するにしています。表示範囲を指定した場合に高速な収束が期待できます。

辺交差している辺と隣接している頂点にのみ大きな力を加えるようにすれば、もっと高速化できるかもしれないとは思っています。

Continue reading

Eadesの力学モデルのグラフ描画のFlexによる実装です。周期的に局所解から脱するような大きな力を加える工夫をして、局所解に陥らないようになりました。制約時間内の最もよい描画を記憶しておくとよさそうです。

収束させるためには、やっぱり辺交差数を求める必要がありそうですね。

Continue reading