ICFP 2010

June 22, 2010
与えられた問題を72時間かけてプログラミングで解く ICFP contest が今年も開催されました。今年は日本時間6月18日金曜21時から月曜21時までで、去年と同じく月曜日には有給を取りました。1人チーム (チーム名 riesz) で挑戦です。

スタート時間ちょうどに帰宅して問題を読みはじめ。あたえられたものは以下の3つ。

ルール http://icfpcontest.org/2010/
問題 http://icfpcontest.org/2010/task/
解答送信サーバ http://icfpcontest.org/icfp10/

問題文はところどころあやふやだったり、はっきり書いていなかったりして謎解きが必要になっています。

o 車の設計と燃料の設計が課題
o 車は upper と lower の2つの燃焼室をもっている
o 各燃焼室の途中で燃料と空気を混ぜ、空気の成分を変化させていく
o 燃焼室の廃棄がある条件を満たすと車は動く
o 参加者が提出するのは新しい車の設計図とその燃料、または他の参加者が提出した車に適した燃料
o 参加者は提出した燃料にあわせて報酬を貰える。燃料の供給者が少ないほど高い報酬

だいたいこんな感じです。個人的には 2007 年の Endo さんと同じぐらい面白かったです。みなさんも是非トライしてみてください!

ここまでかいて面倒になったので、以下、参加者にしかわからない適当な tweet 集をもって write up とさせていただきます。



ソース http://gulfweed.starlancer.org/gem/icfp2010/



問題読み終わったものの、なんだかわからない。とっつきやすそうな回路図の解読を試みる。

上が in で下が out かな。なんで ',' だけじゃなくて ':' が delimiter になっているんだろう。あぁ、最初と最後という以上の意味はないか。外部ゲートかな。

# の前の数字は何?あー、ゲートの種類か何かかな。3日目にゲートの種類が増えたりするのかな。

とりあえずサンプルや自分で作った最小限の回路を提出サーバに食わせてみよう

真理値表なんとかわからないかな・・・どうも、分析に使えるのは backward wire (要はラッチ入り wire) のみ。ラッチの初期出力が 0 と仮定して

外部入力 -> 0のL
0 ->外部出力 0のR

てな回路の出力を使えば分かりそう。

真理値表できたー

さすがに手で生の circuit descriptor 書いてるとつらいな。graphviz 的なフォーマットが使えるようにツールを作ろう。C++ でコーディング開始。

https://twitter.com/riesz/status/16492370314
全部0, 全部1, 全部2 の回路をゲットした
4:20 AM Jun 19th

使えそうな回路ができてくる。でも、こういうパーツができたところで、external input は分岐できないから、そう簡単には組み合わせられない。1つの回路にした時点で external input ではない何かを入力する必要が出てくる。

あー、入力ストリームもわからんし、どうしたらいいんだ

モンテカルロ、モンテカルロ、・・・無駄に時間 (現実も CPU 時間も) が過ぎてゆく

3 ゲートで identity できるじゃん。これに食わせれば入力ストリームが・・・

https://twitter.com/riesz/status/16517120895
やっと input がわかった #icfpc
12:02 PM Jun 19th

求めた入力ストリームのことはすっかり忘れて、一方

外部入力 -> nのL
0 -> 外部出力 nのR
1 -> 0のL 0のR
2 -> 1のL 1のR
...
n -> n-1のL n-1のR

みたいな回路 (通称 数珠) を使えば入力に関係なくきまったストリームが作れることに気づく。

and its input [0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1] これは結局何?・・・あぁ、これをサンプル回路に食わせると prefix が出てくるのか。なるほど、prefix はこれね。

でも出てくるストリームを調整する方法がわからない。どうにかして permutation 回路が作れないかと頑張るが無理。

数珠をたくさん作ってツリーにすればいいのかな・・・いや、わけがわからない

ねじればいいのかな。あれ、最後の方 0 と 1 しかでなくなった。だめじゃん

あー、もうわからん。とりあえず forward wire でノードを追加して permutation を試みてみよう・・・お、うまくいった!

https://twitter.com/riesz/status/16532449649
key できたあああああああああああああああああ #icfpc #icfp
5:32 PM Jun 19th

prefix のみの circuit は 35 nodes

% ./circuit_console.exe [~]
target> 11021210112101221
Circuit: 34L:3L3R0#1L1R,0L0R0#X34R,4L4R0#3L3R,2L2R0#0L0R,7L7R0#2L2R,
8L8R0#6L6R,5L5R0#7L7R,6L6R0#4L4R,12L12R0#5L5R,13L13R0#10L10R,
9L9R0#11L11R,10L10R0#12L12R,11L11R0#8L8R,14L14R0#9L9R,16L16R0#13L13R,
18L18R0#16L16R,15L15R0#14L14R,22L22R0#18L18R,17L17R0#15L15R,23L23R0#20L20R,
19L19R0#21L21R,20L20R0#22L22R,21L21R0#17L17R,24L24R0#19L19R,26L26R0#23L23R,
27L27R0#26L26R,25L25R0#24L24R,32L32R0#25L25R,33L33R0#29L29R,28L28R0#30L30R,
29L29R0#31L31R,30L30R0#32L32R,31L31R0#27L27R,34L34R0#28L28R,X1R0#33L33R:1L


さて、ここから先の input はどうなっているんだろう。周期12っぽいな。まぁ、このbackward wire 数珠使ってる分には関係ないんだけど

そもそも fuel の仕様はどうなっているんだろう・・・ためしにいろいろ作って submit してみよう。

有用なエラーメッセージがぽんぽん出てくるな。

なんか知らないけど2台目が通る。prefix + 1111111111... ってならべただけなのに

car submission では fuel submission みたいに複雑な回路 (少なくとも prefix が正しくないと有用なエラーが見られない) を造らなくても、適当に3進数をいれるだけでいろいろなエラーや対応する10進数値が帰ってくることがわかる。自然数エンコードの解析が楽になった

https://twitter.com/riesz/status/16540590740
Lightning division is over. 23rd place. No car submission. #icfpc #icfp
9:00 PM Jun 19th

でたらめな入力に対して 10那由他ぐらいの tank 番号が出てくる。表現力あるな・・・

会話しながらどんどん数値表現表とエンコード仕様を分析していく。

fuel フォーマットは大体理解。Car フォーマットもおおよそ理解。間に挟まっているのは main chamber フラグか。num_chamber や num_sections と fuel_id ではエンコードが違うんだな。罠

あきらかにとけていない問題に OK がかえってくる。あぁ、overflow か。多倍長整数にしなきゃだめだな。めんどくさい・・・

2次元行列の探索も冪零が必要な場面でうまいこと活躍してるみたいだ。

Chamber 0 : fuel0 > fuel1 の 665乗, Chamber 1 : fuel1 の 666乗 >= fuel0 みたいな条件の車に出くわす。2の666乗はさすがにでかすぎるだろう。いや、でも10那由他出たし・・・

線形な増加にしようと上三角行列なんかを駆使しようと試みるも、0行0列の要素はどうあがいても増えない。

いろんな人に追い抜かれて40位ぐらいになる。更新が止まっていたっぽいので、結構前からおちていたのかもしれない。

だらだらと 1chamber main upper = (0 0 0 0 0 0 0 0 ... 0) lower = (1) 系の単純な車に手作業で燃料を入れ続ける。虚しい

666乗問題が解けなくてくやしいので、簡単な convert ツールだけでも Java で作ることに。

いろいろ分析して自然数 parser & formatter の if switch をまとめていくと綺麗な形に。一般化成功。あぁ、これ 2^666 ぐらい軽く入るじゃん!

https://twitter.com/riesz/status/16651760840
そしてにっくき 9748 を倒した #icfpc #icfp

多倍長さえ対応すれば解けそうな問題にしょっちゅう出くわすため、結局、もっとも無難な Java の BigInteger を使うべく、C++ からコードの大半を Java へ port。

https://twitter.com/riesz/status/16671437788
C++ -> Java porting おわったぁ。最低限必要な部分だけだけど。 #icfpc #icfp

fuel descriptor がわかっても回路生成器が遅くてどうにもならないケースがあるな・・・

回路生成器に小手先の最適化をいくらか施した。あんまりかわらない

https://twitter.com/riesz/status/16680948704
そろそろ自動化するか・・・570台も手で submit したわけか #icfpc #icfp

提出は LWP あたりで。Car descriptor を Java の solver に渡して結果を・・・えー、Perl の open + パイプって読み書きはできないの!IPC::Open2 を使えって?CPAN めんどい。一方ロシアは引数を使った

ログイン処理とか面倒そうだな。Chrome でログインしてから JSESSIONID を確認して、ハードコードしちゃおう。

あぁ、なんかどんどん submit できてるけど点数増えないな。あぁ、終わる・・・

結果

score: 356.684
others' cars solved: 801
cars submitted: 3
46th place / 872 participants


眠い

Google CodeJam 2006

October 30, 2006
無事に終了したようです。日本からも1名(nyaさん)が参加されました。結局TopCoderでもレーティング1位のPetr氏が優勝した模様です。

GCJではTopCoderの講評みたいに統計が出ないようなのでメモっておきます。

優勝
Petr (Petr Mitrichev)
言語 C#
得点 927.02 (0.0 + 417.26 + 509.76)

問題概説
250点問題
与えられた複数の点に対する近似直線を求める問題
最速 pashka 7.34分
正答者 69

500点問題
ハッシュから元の文字列を求める問題
最速 tomek 9.06分
正答者 38

1000点問題
パラメータ表示された曲線上の格子点を零点にもつ多項式を求める問題
最速 andrewzta 33.64分
正答者 5

関連サイト
This year's CodeJam
Google Announces Winner of Global Code Jam 2006

私は決勝の様子をのんびり観戦していたのですが、対戦終盤にサーバからの情報が遅延しだしてついには切断。つなぎ直したときにはコンテストの情報が一切見られなくなっているという始末でした。悲しい。現在は得点やコードの閲覧が出来るようになっています。

TopCoderでCodeProcessor+TZTester+FileEdit

October 07, 2006
上位陣が結構使ってるプラグイン構成

FileEditは外部ファイルをソースとして自動で読み込むようにするもの。
Meadowなりなんなり好きなエディタが使えます。コピペの必要がありません。

TZTesterはテストコード自動生成プラグインで、
ローカルコンパイル&実行すると提示されているサンプルパターンを
全部一気にチェックしてくれます。

手順

Plugin紹介ページからTZTester.jar, FileEdit.jar, CodeProcessor.jarをダウンロード

Competition Arenaの「Options → Editor」で「Editor Preferences」を開く

Common ClassPathにBrowseボタンでTZTester.jar, FileEdit.jarを追加

Addボタンを押して以下のように入力してOKを押す
Name: CodeProcessor
EntryPoint: codeprocessor.EntryPoint
ClassPath: CodeProcessor.jarのパス

CodeProcessorを選択し、Configureを押して「CodeProcessor Configuration」を開く

「Editor EntryPoint」にfileedit.EntryPointと入力してConfigureを押す

「General」タブで「Enter directory to read/write problems to」にソースを置きたいディレクトリを記入

「Code Template」タブでTZTester用にTemplateを編集する。例えばC++ならば

class $CLASSNAME$ {
public:
$RC$ $METHODNAME$($METHODPARMS$) {

}
$TESTCODE$
};

// BEGIN CUT HERE
int main() {
$CLASSNAME$ ___test;
___test.run_test(-1);
}
// END CUT HERE


とする。「// {BEGIN|END} CUT HERE」で囲まれる部分は
CodeProcessor FileEditがSubmit時に削除してくれる。

Saveボタンを押したら今度は「Processor Class」に「tangentz.TZTester」と
記入して「Verify」を押す。3つのメソッドについて「found」と出たらOK。
だめだったらCompetition Arenaを再起動してからチェック。

使い方

新しい問題を開くとDefault Languageに基づいてスケルトンが出来上がる。
外部ファイルを編集・保存してからCompetition Arenaのほうで
Compileを押すと自動的にソースが読み込まれてコンパイルされる。
※ 問題を開いてから言語を変えた場合、前に選択していた言語のままのソースが
外部ファイルにエクスポートされてしまう模様なので注意。

外部ファイルをローカルコンパイルして実行するとTZTesterが生成したテストコードが
実行されて結果が出る。

かなり楽ちんになるでしょう。
ここまでやったらあとはコーディングの実力を・・・

Read more

前5件

次5件