日々の流転

λ. Google Code Jam 2012: Qualification Round

いつものように id: sakai で参加中。 今回は他に色々やりたいことがあったので、やる気あまりなかったけど、とりあえず Rank: 2771 Score: 60 でパス。

Problem A. Speaking in Tongues

問題毎に対応関係が違って頻度分析をして解くものだと思って解いてみたら、どうもサンプルと一致しない。 それで、対応関係は一つに固定されていてサンプルだけからそれが一意に決まることに気づく。

• A.hs

Problem B. Dancing With the Googlers

最低点と最高点の差が高々2なので、各人の総得点を3で割った余りから、サプライズがなかった場合のその人の得点内訳と、サプライズがあった場合のその人の得点内訳とがわかる(ここで、人の総得点が0だったときに、最初 -1,0,1 という実際にはありえない得点内訳を誤って考慮してしまって、その誤りに気づくのに時間をくってしまった)。あとは、「サプライズなしで基準を超えている人数 + min(サプライズ数, サプライズがあった場合に基準を超える人数)」を計算するだけ。

• B.hs

Problem C. Recycled Numbers

Smallは全列挙で。 Largeはまじめに解く必要があるかと思ったけど、全範囲について列挙したテーブル化して各caseで使いまわすようにしたら、最大のデータを作って実験しても大丈夫だったのでそれで。

• C.hs
• C2.hs

Problem D. Hall of Mirrors

面倒くさそうだったのでパス。

λ. Pseudo-Boolean Competition 2012 に参加

Pseudo-Boolean Competition 2012 (PB12) に簡単な自作ソルバを投稿してみた。

2011年振り返りのところで書いたように、昨年はいろんな決定手続きのアルゴリズムを書いたりして遊んでいて、どうせならコンペに出してみるかと、昨年秋に予定されていた Pseudo-Boolean Competition 2011 (PB11) の Second round を目指していた。 ただ、Second round は結局キャンセルになりその代わりに今回のPB12が開催されることになったので、今回のPB12に投稿することにしたのだった。 V. Manquinho and O. Roussel がオーガナイザとして開催するのは今回が最後の予定で、かつ Second round の予定の時点ではほとんど何も準備できていなかったので、延期でそれなりに準備できて参加できたのはラッキーだったかもしれない。

とは言っても、結局そんなに大したものはできず、基本的なSATソルバ + カウンターベースの素朴なPB制約の実装くらいしかできていない。 なので、全然 competitive なものにはできなかったんだけど、せっかくなので一応投稿はしておいた。 本当はLP緩和やMIS緩和による下界値計算、cutting plane proof system による conflict analysis 等をはじめ、やりたいことは色々あったんだけど、時間切れ。 やり残したことは悔しいけど勉強にはなったし、 ICFPC や Google Code Jam みたいなコンテストとはまた違って面白かった。 もし来年があるなら、来年までには色々何とかして、また参加したいね。

• PB12投稿版
  • PB12に投稿したバイナリ(x86_64 linux 用)
  • PB12投稿版のソース＠github
  • Win32版のバイナリ
• 2012-05-18 差し替え版: toysat-PB12-20120518-linux-x86_64.zip
• 2012-06-02 差し替え版: toysat-PB12-20120602-linux-x86_64.zip
• 最新版のソース＠github

λ. Linux版のGHCでスタティックリンク

Pseudo-Boolean Competition 2012 投稿用にスタティックリンクした Linux 向けバイナリを生成する必要があった。 それで試してみたら、GHC は -static がデフォルトだと聞いていたにも関わらず、ビルドしたら色々動的にリンクされてしまっていた。

% ldd toysat
linux-vdso.so.1 => (0x00007fffed5ff000)
libgmp.so.10 => /usr/lib/libgmp.so.10 (0x00007f84eb415000)
libffi.so.6 => /usr/lib/x86_64-linux-gnu/libffi.so.6 (0x00007f84eb20d000)
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f84eaf88000)
librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007f84ead80000)
libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f84eab7c000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f84ea7dc000)
libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f84ea5bf000)
/lib64/ld-linux-x86-64.so.2 (0x00007f84eb69c000)

どうしたら良いか困ったが、結局 linux - Haskell program built on Ubuntu 11.10 doesn't run on Ubuntu 10.04 - Stack Overflow に従って、「cabal configure --ghc-options="-static -optl-static -optl-pthread"」とすることでスタティックリンクしたバイナリを生成できた。

λ. Google Code Jam 2012 : Round 1A

A-Largeの予想外の不正解で Rank: 1274 Score: 43 となってしまいパスできず。(id: sakai で参加中)

• Participant Details: sakai ― Code Jam 2012 Statistic

Problem A. Password Problem

即座にenterを押して全文字入力し直すのと、バックスペースを何回か押して残りを入力するのと、全部期待値を計算して、その最小を取れば良い。 Smallは超素朴に計算(A.hs)。 Largeは適当に実験すると非常に時間がかかったので、全部の確率の積を毎回計算しないようにした(A2.hs)。 ただ、全部の積を計算してから要らないやつで割るという方法を取ってしまっていて、そのせいで計算誤差が蓄積してしまったようで不正解を食らってしまっていた。 逆に順番に掛けていくようにしたら、正しく計算できるようになったようだ(A3.hs)。 浮動小数点数の誤差でハマったのは生まれて初めてかもしれない。 あるいはいっそ有理数で計算していればよかったかも。

Problem B. Kingdom Rush

2-star rating でまだクリアしていなくて今クリアできるレベル(1-star rating でクリア済みのものを含む)がある場合には、それを選んでいけば良い。 問題は 2-star rating でクリアできるレベルが存在しない時に、どのレベルを 1-star rating でクリアするか。 Smallはまずは全通り試して最短手数のものを選択する方法で解いた(B2.hs)。 Largeはそれだと解けないので、レベル選択をちゃんと考える必要がある。 直観的には、(今 1-star rating でクリアできる未クリアのレベルのうち) 2-star rating に必要なスター数が大きいものは、その後スターが増えても一気に 2-star rating でクリアできる見込みは小さい。そこで、2-star rating に必要なスター数が最大のものを(諦めて) 1-star rating でクリアするようにしたら、Smallのデータセットの範囲では結果が一致したので、それで(B3.hs)。

Problem C. Cruise Control

任意の二つの車について初期位置と速度から隣り合ってもしくは重なってしまう時間を計算し、これを各車ごとに車線変更不可能な時間として保持。 その上で、初期時刻および何れかの車が車線変更不可能な時間に入るタイミングを順番に見ていき、そのタイミングであり得る車の車線の配置の全可能性を考える。 全可能性を考えるには、前のタイミングで在り得た配置をもとに、そのタイミングで車線変更可能な車を任意に車線変更したものを考えれば良いはず。 そうやって初期時刻から順に見ていき、可能な全ての配置で衝突状態になっている最初の時刻が答え。 車線変更不可能なタイミングに入るタイミングを全部見終わってそういう時刻がないなら、Possible が答え。

……と思ったんだけど、実装は間に合わず。

λ. MPSファイルのフォーマットは酷すぎる

線形計画(LP)や混合整数計画(MIP)の問題の記述に標準的に使われているMPSというファイル形式があるのだけど、そのフォーマットが酷すぎて呆れた話。

経緯

MIPLIB2010の簡単な問題ということで、enlight13 を色々なソルバに食わせて遊んでいたら、GurobiとSCIPは解を見つけるのに、自作ソルバは解がないと言ってきて、どんなバグを埋め込んでしまったかとかなり焦った。 焦ってしばらくバグ探しをした後に、ふとGLPKでも解いてみると、GLPKも解がないと言ってくる。それで、自作ソルバに食わせるためにGLPKでファイルをMPSファイルからLPファイルに変換していたのを思い出し、GLPKのMPSファイルの解釈がGurobiやSCIPと違うのではないかと疑った。 GLPKで変換したファイルをGurobiやSCIPに解かせて解がないという結果になるのを確認。さらに色々見ていると、GLPKのログメッセージでは変数は全部binaryなことになっているけれど、Gurobiの出力した解をみてみると2とかになっているのがある。これだ！

分かったこと

それで、「GLPK MPS bug」で検索してみると、 Re: [Bug-glpk] GLPK 4.46 fails to find solution with enlight13.mps というメールを発見し、原因箇所が判明。件のファイルのBOUNDSの指定に問題があるらしい。

ただ、それだけだと、GurobiやSCIPと解釈が違う理由は分からなかったので、MPSファイルについてさらに調べてみる。 すると、CPLEX では Special Records in MPS Files: ILOG CPLEX Extensions によれば、「MARKERで整数変数を指定する場合、その変数の範囲指定がBOUNDSセクションに存在しない場合には、範囲は[0,1]になる」ということらしいが、その辺りが解釈が違っているのが分かった。

問題のMPSファイルではBOUNDSセクションで変数の下限のみしか指定していなかった。GLPKの実装は、範囲をまず[0,1]で初期化した上で、BOUNDSセクションに記述された上下限でそれらを上書きするという実装になっていたため、上限は1のままになってしまっていた。 それに対して、GurobiやSCIPはどうも下限だけとはいえ範囲が指定されているので[0,1]というデフォルトはそもそも用いないようだ。 ついでに、lp_solve の MPS file format によると、lp_solveはBOUNDSセクションで下限だけでも指定されていればデフォルトは用いないようだが、ただしデフォルトは[0,1]ではなく[0,∞)だとか……

感想

歴史的経緯はあるのだろうけど、元のフォーマットをアドホックに拡張し続けて結果、歪な仕様になった上に、各ツールの解釈が全く違うというひどい状態。こんな腐ったフォーマットが現役で使われているとは酷すぎる……

参考

• MPS (format) - Wikipedia, the free encyclopedia
• Special Records in MPS Files: ILOG CPLEX Extensions
• MPS file format (lp_solve)