最底辺ICFPC参加者のメモ

初日

21時に問題がオープンになって、訳し始める。訳してる時はまぁこれから72時間頑張ろうみたいな感じだったけれども、翻訳してる時が、一番楽しい時間だった。

取りあえず翻訳し終わって、どうしようみたいな感じに。取りあえず回路読めないと話がはじまらないっぽい事だけは分かったので、うんうん唸っていたけど寝るまで結局分からなかった。

初日は、key circuitを見て勝手に色々ルールを作ったりしていた気がする。寝るまでに、Xと0Rと0Lを適当に組み合わせて作ってみたヤツを投げると何か返って来たので、これが実はサーバが投げて来ているヤツそのものなんじゃないかなぁという感じだった。

1日目

起きてすぐにコマンドラインからsubmitするヤツをにはさんがmechanizeを使って作っていたので、一方net/httpsを使って直に叩くヤツを書く。こういう時に使えるのは、FirefoxのアドオンのLiveHeaderさんで、でも別に何も難しく無くてすぐに書けた。

回路の読み方が分からなくて大変焦っていたので、

0L:
X0L0#0RX:
0R

みたいなXと0だけ使う回路を全部作って片っ端からsubmitするヤツを作った。すると

X:
0L0R0#0L0R:
X
出力が01202101210201202
X:
0R0L0#0R0L:
X
出力が01202101210201202

含めて6つぐらい出て来てこれが恐らくexternal gateとgate 0を使って作れる回路の全てに成っているはずで、この二つはexternal gateで閉じているもののはずで、間違いなくサーバの渡している入力がコレだというのは分かった。

しかしどうやっても6つの回路をこのsyntaxから作れる方法が分からなくて詰む。

行の順番を入れ替えるとエラーが出たり出なかったりするし、parseの仕方が、前から順番に見てるだけなのか一回全部みて不整合起こしている所を出しているだけなのか、他にも些細なケースまで無駄に調べまくっていた気がする。

ここでにはさんが休憩というなの小睡眠に入ってしまったので、マナカさんと相談しながらやっていると、line by lineで読めば分かるんじゃないかということを閃いて、この時点で凡そ24時間。余りにも遅過ぎる・・・。アホか！

その後は、ゲートのセマンティクスを色々考えて寝る。

2日目

gateを0しか使わないベース回路(これが今回のうちのチームの活動拠点！！)4つを色々繋いでみたりする事をやっていた。

あとは、簡単そうに見えてどうも挙動が意味の分からん回路を色々作っていて、何故かにはさんが"X::X"で見付けられるという事を発見した。

この時ぼくに無駄な閃きが走ってしまって。それは

スクリーンショット（2010-06-22 0.17.07）

この「ゲート上部でループしていて、下部を通って行くゲート」を只管繫げて行くと、次のようにすると完全に入力に対する生成ルールが分かる、というものでした。

そのルールは、「ゲートの中には状態が存在していて、ゲートは実はステートマシンになっている」というもので意味は無いから詳しく書きたくはないのですが

初期状態をaとして

(X,Y) → (X',Y')というのを、状態がXの時に入力Yが来ると、次の状態がX'になり、出力がY'となる　と表す

(a,0)→(a,2) (a,1)→(c,2) (a,2)→(b,2)
(b,0)→(b,2) (b,1)→(a,0) (b,2)→(c,1)
(c,0)→(c,2) (c,1)→(b,1) (c,2)→(a,0)

これと同様に、下部でループしていて、上部を通って行くゲートも実は生成出来てしまって、ここでゲートを0しか使わずに只管それと同じ物を追加していくものは実は同様にステートマシンで解釈出来るのではないかというのを考えて強引に全通り調べてみたら、見事に4つともステートマシンが作れてしまった。

「これで勝つる！！」(全然違います

ここで他にもツールを量産しまくった気が。

ステートマシンでは、どうにも解釈出来ないような回路が幾つも手元にも在ったけれども、これはデフォルトの出力とか、他の隠しパラメータとか、backwardの考え方でどうにかなるんや！！という強引な考え方で翌日に進む。

3日

なんとbackwardでもステートマシンを変更しなくても動くようにする方法を発見してしまう。でも、ココまで来てもまだ解釈出来ない回路があるが完全に無視。

もう時間がなかったので、ここでサーバの入力から、key-circuitに渡すべき出力を、手元でステートマシンとして解析済みだと思い込んでいた8つの繋ぎ方を10段試すと上手くいったので、それを繫げると何とかlegalなprefixが得られるという感じで、この時既に残り3時間少し。

あとは車を適当に何とかするべきだよなーという感じで色々やっていたけれども、サーバが余りにも遅過ぎたのでgdgdになって終わってしまった。

まとめ

「ありのまま今起こったことを話すぜ。終了後にtwitterを見ていたら、同じコンテストで別のゲームをしていた事が分かった。」