ICFP
今年は点が取れず…むむむ…くやしいなぁ
結局回路シミュレーターっぽいのを作ったところで、回路の自動生成方法が思いつかなくて終了。来年はもっとがんばりたいところ。やっぱなんか修行がいるなぁ。
以下適当に流れとか
金曜日
23 時ぐらいに開始。しばらくは問題読み。とりあえず回路を最初に作らねばならないらしいので、回路の構文を把握すべく適当にいろいろ入れてみる。
構文自体はサーバのエラーメッセージで大体つかめてきたので、以下の簡単な回路を作って出力を確認。
┌──┐ ┌──┐ ┌─┐┌─┐ │ │ │ │ ││ ││ ││ │ ││ ││ │ ┌┴┴┐││┌┴┴┐ │┌┴┴┐┌┴┴┐│ │ ││││ │ ││ ││ ││ └┬┬┘││└┬┬┘ │└┬┬┘└┬┬┘│ ││ ││ ││ │ ││ ││ │ └─┘└─┘ └─┘ └─┘
これ入力なんだろうなぁと思いつつ Angle Beats 見て寝た(ぉ
土曜日
10時ぐらいから再開。とりあえず入力と出力から傾向をつかもうと思って悩む。簡単な回路の出力を入力にすればいいことに気付いて実施。
途中で心が折れかけたが、いくつかの入出力について 1step ずつ追いかけることで以下の9パターンっぽいと判断。
# 入力:出力 {[0,0]:[0,2], [0,1]:[2,2], [0,2]:[1,2], [1,0]:[1,2], [1,1]:[0,0], [1,2]:[2,1], [2,0]:[2,2], [2,1]:[1,1], [2,2]:[0,0]}
とりあえずこのパターンで回路シミュレータを作ってみる。出来たらいくつか簡単な回路の出力をサーバと比較して答えがあってることを確認。
手元に出力と回路があるので入力を逆算。そして公式の回路と入力を使って key prefix ゲット!というところで区切りがよさそうなので寝る。
日曜日
昼ぐらいから再開。公式の回路を入れた場合、サーバでの結果とシミュレータの結果が違っていることに気付く。
回路の評価順番をいろいろいじってみたが不明。(この地点では幅優先探索を使っていた)
よくよく考えてみると今の探索順だと根本的におかしいことが判明。これは回路の並べ方かなと当たりをつけて試してみると見事一致。
これでほんとの key prefix ゲットだぜということで。この key prefix を得るための回路を考え始めるが、思い浮かばず…
特にいいアイディアも思いつかなかったのでランダムサーチするプログラムを作ってまわしつつ、入出力の間をとって、それを入出力にさらに回路をくっつけ…という感じで以下のように回路をつなげていった。
が、4段目ぐらいで先頭の計算が間違っていることに気付いて終了。時間も結構遅かったので寝る。
┌──┐ ││ │ ┌┴┴┐ │ │ │ │ └┬┬┘ │ ││ │ │┌─┼─┐ ││ │ │ ┌┴┴┐│ │ │ ││ │ └┬┬┘│ │ └┼─┘ │ │ │ ││ │ ┌┴┴┐ │ │ │ │ └┬┬┘ │ └┼──┘
月曜日
仕事で何も出来ず…
おわり
というところで時間切れ。最初の回路作成ぐらいは何とかしたかったなぁ。