naoya_t@hatenablog

いわゆるチラシノウラであります

ICFPC2013参戦メモ

Programming Contest Gauche

ぼっち参戦しました。
ICFP Programming Contest 2013
今年のホストはMicrosoft Researchさん。

チーム名「Я⦿Ж⦿R」でエントリしています。ケロン軍です。

総括


問題自体は楽しめる要素が多かったと思うのだけれど

  • MSなんとか
  • leaderboardの不在
  • （英文読解力の欠如なのだろうけれど）主催者の意図を掴みきれずにサーバ仕様をあちこち読み違えていて問題を難しくしていた

という３つの（主に心理的な）障壁を乗り越えるところまで行けませんでした。

（72時間のうち、合計参戦時間より合計睡眠時間の方がはるかに長かったです・・・）

kinabaさん他みなさんによるtogetterまとめ：ICFPC 2013 おつかれさまでしたー

開催まで

  • 大会要項ページ。どうでもよさそうな事ばかりテキストでぶわーっと書いてあって頭に入ってこなくてさげぽよ
  • EasyChairめどい。個人情報沢山取られる
  • 他のエントリしてるチームの情報がない
  • コンテストどこでやるのか当日のその時間まで分からない
  • こういう（情報取るだけ取って）フィードバック薄い系すきじゃない

初日

http://icfpc2013.cloudapp.net/

  • とりあえず\BV言語のインタプリタ、というか\BVのプログラムをschemeのラムダ式に翻訳する物を書いてみた
  • サーバと通信してみた
  • とりあえず3〜4ノードのやつを解くのを書いていくつか/guess
    • 最初はソルバーと通信器の連携をしていなくて手動で送った
    • 時々同じ問題出てない？
  • /myproblems は問題数上限に達するまで何度でもリクエストできて、5分で賞味期限が切れて、リクエストの度に違う問題が出てくるのだと思っていた
    • 5分経ったらまた /myproblems 呼ばなくちゃ（※誤解）
    • /myproblems リクエストに含まれる、その場で解いていない（5ノード以上の）やつの個数が問題数上限を削っていく（※誤解。/evalしてなければ大丈夫）
    • いや、"If you are unable to solve a problem in your myproblems set, your potential maximum score will be reduced. "（太字はnaoya_t）とあるから、スコア上限が減らされるのはその回の myproblems の問題が*1問も*解けなかった場合だけだ（※誤解）
    • 1問でも解けてればいいのか、と思って無駄に/evalで開いてしまって数十ポイントをロストしている件


  • とりあえず、いつ突然問題数上限に達してしまうかわからないので /myproblems 自重（※誤解に基づく判断）
    • ちゃんと解けるソルバー書いてからじゃないと駄目だな（※誤解に基づくものの、これは正しい判断）
  • /trainで練習問題と回答を取得して少し眺めてみる

2日目

  • lightning division終了。この時点で1日目に投げた分の20ポイントだけ。
  • 24時間経過時にみんなの様子がどうなのか全く分からないという事態
  • leaderboardないし。出す気ないみたいだし。げんなり。


  • 全探索のしかたをミーティングが始まる前にカフェで考えていたけれど飽きてきた
  • Operators関数とtfoldの意味は分かった

3日目

  • leaderboard無しだとモチベーションが72時間維持できない症候群
  • bonus問題とか出てた(42)。とりあえず(lambda (x) (if0 (and e0 1) e1 e2)) 構造は把握した
  • 最後の夜、ちょっと続きやろうかなと思ってMBAを開く。（残り12時間切ってる）
  • カフェで考えてた探索を実装するか
  • これDBに突っ込んで検索すべきだよなー
  • あれれー？おかしいぞー
    • /myproblemsって何回叩いても同じ問題リストが出るの？
    • 問題って/evalで開くまでtimeLeft減らないの？
  • （パターン列挙に時間とメモリを食うので）1、2分で出る範囲（トップのlambdaも入れて8ノードまで）でパターン列挙。tfoldありfoldなし。
    • 最初は、op1,op2,[01x] の箇所に1,2,0を入れて (1 (2 0 (1 0))) みたいな方式
    • 後で関数名を順列組み合わせするのがめんどくさくなったので関数名を入れて、あとその関数に入力（サイズ256のベクトル）を渡した時の結果も保持
    • より小さいノード数のプログラムをcartesian-productで合成していく感じ
  • とりあえず8ノード以内のfoldなしの分でtimeLeftがあるやつを全部解いた。
  • bonus問題もう1つ出てた(137)。こっちはでかすぎてあれ
  • bonus-42のなんちゃってソルバを書いた。

    • eval結果の半分以上が一致するパターンe1を探す（これはthenないしelse節に入る）
    • e1がeval結果と一致しない時には下1ビットが1にならないようなパターンe0を探す（これはcondition節に入る）。逆に0にならないパターンもe1をelse節に入れることで使えるので探す。
    • 少なくともe1の下1ビットが0なときにはeval結果と一致するようなパターンe2を探す
    • (lambda (x) (if0 (and e0 1) e1 e2)) に組み上げて提出
  • 実戦投入したらmismatch連発してさげぽよ…e0,e1,e2の探索範囲が狭すぎるようだ（4〜7ノードで、op2のオペランドの少なくとも片方がatomなやつしか見てなかった）
  • そんなこんなで123点取って気が済んだので、6時間ほど残して寝た。

終了後

  • 起きたら終わってた（けれどleaderboardなくてさげぽよ）
  • 201〜224位のどこか
  • 100位ぐらい入りたいなーと思ってたけど心折れまくってて無理だった。無茶だった。無駄だった。
  • みんなのスコアは3桁後半〜4桁っぽいね
  • survey送った

  • もしかして、同じ挙動さえするなら言われたsizeやoperatorsと違うプログラムを返してもよかった？