ICFP2010まとめ

Program ICFP

ICFP終わったー。.naka2kaiは0点でした。
0点とはいえ、ここ最近稀に見る濃密な3日間でした。楽しかった。
以下、残念すぎるメモ。
とりあえず始まった時点から問題を読み間違えていた件。CircuitとGateと言う言葉が出てきたんだから、これは2入力2出力の論理ゲートだと見ればいいものを、何故か真理値表の通じない順序回路の可能性を捨てずに考慮して時間ロスした。
で、入出力に関しても勘違い。入出力は1入力1出力のゲートがあるというのを読み取って、問題文中のFactoryのX18L0#X7L:の部分を見て、Xは入出力を表す接頭辞だと思いこんでしまった。要するに最後から2番目の行はExternalゲートの記述で、接頭辞付きで書かなきゃいけないんだな、と解釈。
ちなみに正解は、XはExternalゲートのポートにつなぐ、の意味。確かに上記の解釈だといろいろと冗長だし、最初と最後の行をいじるとinconsistent connectionって言われるのも割と初期に気づいてたので、もっと早く気づいても良かった。これに関しては、20日の17時頃に@tanitaninがSkypeで教えてくれたのでかなり進展したけど、逆に言えばそれまで完全に停滞してた。ひどい。
そして、とりあえず

0L: X0R0#X0R: 0L

とかで確実に変わらない入力を得て、こいつのL側出力を

0L: X0R0#1L0R, 0L1R0#X1R: 1L

こんな感じで他のゲートに流し込んで出力を見ることで真理値表を全探索。@mitsu_kohの回路生成プログラムを使いつつ、テストケースの組み立てに手こずったり、プログラムがバグったりして、結局真理値表が得られたのは1時くらい。それから問題文の回路をシミュレーションして、key prefixを得る。ここで1時45分。
それから色々と考えて、とりあえず定数を吐く関数とecho関数を作り、サーバーの入力を得る。

0R:
2LX0#1R1L,
0R0L0#2L2R,
1L1R0#0L3R,
5L2R0#4R4L,
3R3L0#5L5R,
4L4R0#3LX:
5R

zero関数。これを使うとoneとtwoとechoができる。
この辺で4時。任意の出力を得るためにどうすればいいかを考えるけど、思いつかないのでとりあえず就寝。


そして大学でまた会議。@tanitaninがdup関数を思いつく。でもその時同時に全探索説が有力になっていたので、とりあえずゲートを直列につなぐパターンを大量に生成して、key prefixになるものが来ないかを見る作戦に。
しかし、15個くらい直列にしてもそういうパターンは見つからず、20時。とりあえず#219くらいは取りたいなーと思いつつ、頭で考える方針に転換。
で、しばらく考えてるうちに、dupをたくさん繋いで17個に分枝させた後、葉ノードに定数関数をくっつけてその間をdelay関数で繋げば出来るんじゃないかという結論に達する。しかし、時既に遅し。
そんな感じ。ちなみに最後のやつのゲート数を概算してみると460個前後で、一覧表見るとだいたいその辺に塊が見えるので、同じ事考えた人はやっぱいるんだなー、と思った。


とりあえず、色々とひどい。なんというか知識と英語力が足りていない・・・。