ICFP 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


眠い

Comments

No comments yet

Add Comments

このアイテムは閲覧専用です。コメントの投稿、投票はできません。