アルゴリズム概要 

inputs[:512] <- [規定入力, 乱数*300]
outputs[] <- eval inputs
探索範囲[:1000くらい] <- `親ソルバー < サイズとoperator`

loop:
  if children.size < CPUの2倍:
    child <- `子ソルバー -t 探索範囲.pop < (inputs, outputs)`
    children.push(child)

  child.onFinish:
    if 出力なし:
      goto loop
    else:
      program <- 出力
      探索範囲.push(all 探索中)
      killall children
      status, 反例 <- guess program
      if status == 'win':
        print program
        探索終了
      if status == 'mismatch':
        inputs.append(反例), outputs.append(反例)
      goto loop

という風にやってました。自然言語より似非コードの方が伝わるんで書きなおしてみた。

この辺の作業は時系列順に言うと

  1. @tzik さんが細かい単位で書いていた。
  2. 手作業が面倒だったので全体を繋げた。
  3. @tzik さんが並列化。

という感じに進んでて、よく見ると Python 知識が必要なところは @tzik さんがガシガシ書いてくれました。

ざっとやってた流れ

1日目

  • 開始時間。問題を読む読む。tfold よくわからない…。@tzik さんが問題文の概訳を書いてくれてた。
  • @nodchip さんがソルバーを書き出す。まずは fold 無視。
  • wget を直接叩いたりしながらサーバとのやりとりを確認。/eval しちゃダメ。
  • ソルバーv0.1 完成。完成後に入力フォーマットを言われ、テストデータ作成プログラムを書く。
  • この辺で wget wrapper が作られている。auth token がハードコードされてるから便利。
  • 問題状況を確認するために spreadsheet 作成。
  • /train で作った小さなケースで確認。計算時間的には 10 くらいが限界じゃないかなーくらい。
  • tfold の意味がようやく分かる。
  • 結局 lightning では size 3,4,5 だけ /guess して 120 点。

2 日目

  • 昨日 /eval → ソルバー(シングル版) → /guess のやりとりが面倒だったので python で wrap する。
  • fold や tfold の対応が実装される。
  • ついでに mismatch だった場合に反例を付け加えてソルバー再起動する形を作る。夕方。
  • eval に渡す値を 256 個から 512 個へ倍増。1 問あたり /eval /eval /guess の 3 request 以上になる。
  • @nodchip さんが高速化を頑張ってるので、そこにつけ込んで得点を取るタンポポワークを淡々とこなす。5 req/20 sec 対策のため手動でやっている。

3 日目

  • @nodchip さんは並列化のために親子プロセスを分け、@tzik さんは wrapper を並列化させる。
  • その間私は single 版で淡々と得点を取るタンポポワーク。そろそろ全問題チャレンジできるか不安になり始める。
  • 並列化システムでデバグがしにくくなる。I/O の全ログを取るシステムをようやく作る。
  • CPU がネックになる問題を解いてる隙を突いて自動化システムを作成する。
  • 19:00 @nodchip さん帰宅。
  • 20:00 @tzik さん、解を見つけられなかったログからフィードバック部分にバグを発見＆修正。
  • 23:00 @tzik さん、ソルバー周りでバグ発見＆修正。この時点になってようやくソルバーのコードを真っ当に見始めている。
  • 24:00 半自動化システムに残り問題の情報を与えて帰宅。

4 日目

  • 8:00 に起きて進み具合を確認。ついでに家マシンでちょっとチャレンジさせて 2 点増やすなど。
  • 9:30 何か form に色々入力する。ここでようやく auth token がどこから取得できるか知る。

技術的に感心した事

この辺はまた使えるなー、他のチームとは違うかもなーというポイントを幾つか。大体 @tzik さんの作品。

  • ソルバーの詳細は @nodchip さんの blog 参照
  • HTTP Request は全部 wget 経由。標準入力を POST して返ってきた Body を標準出力に出す bash を作成。
    • path と同じ名前のシンボリックリンクを作って path の違いを吸収させる。
    • 変な status code だったら body を標準エラーに吐いた上で retry する…という形で 5 req / 20 sec をクリア。
  • 半自動化 script (bash) は 62h 経った頃に作成。timeout コマンドを利用して 5 min の時間制限も確認。
  • 終盤変な挙動が見られたが、入出力セットなどから @tzik さんが解析し、ソルバーと全体を回す python の両方にバグが有るのを発見、デバグ。その頃、ソルバーを実質一人で作ってた @nodchip さんは所用のため帰っていたのでした。

反省点

  • 異なるプログラムを連結させる場合は全入出力をファイル化して、問題ごとに纏めておくべきだった。このシステムができたのは 60h くらい経った頃。遅すぎる。
  • 1 問の中は並列化するけど、問題ごとに見れば 1 問 1 問順に解いていく形だったので、CPU がネックになっている問題を解いている最中はネットワークが空いていた。他の非力マシンを使ってでも解いていくべきだったかもしれない。
  • どうせ 5 分ギリギリ (4'30" とか) に解けることなんてそうそう無いんだから 1 問あたりの制限時間は 2-3 min にしておくべきだったと思う。
  • 自分たちのチームだけでも状況を常に把握できるスクリプトというかそんなの欲しい。大きなモニタに映せるとモチベーションアップできる。
  • 少しでも test 書けるようにはしたほうが良かった気がする。問題解くルーチンは C++ で書くのがチーム内で確定しつつあるっぽいから class だけ作るといいかも。ファイルを分けるのが難しいかもしれない。