ICFP Programming Contest 2013 優勝!


WINNER: UNAGI--THE SYNTHESIS
 
Java, C#, PHP, Ruby and Haskell
are programming tools of choice for discriminating hackers
 
Takuya Akiba, Yoichi Iwata,
Kentaro Imajo, Toshiki Kataoka,
Naohiro Takahashi, Hiroaki Iwami
 
University of Tokyo, Google, Keio University and AtCoder
Japan

8 月に開催された ICFP Programming Contest 2013 の結果が ICFP 2013 で本日発表され,我々は念願の優勝をついに果たしました.これは嬉しい!(事前に知っていましたが,例によって発表まで秘密にするように言われていました.)

写真は現地の imos のツイートより拝借.

ICFP Programming Contest について

ICFP Programming Contest は「なんでもあり」が特徴の,他とは一線を画す特徴的なプログラミングコンテストです.ACM関数型プログラミング言語の学会 ICFP (International Conference on Functional Programming) に伴って毎年開催されていまして (1) プログラミング言語自由 (2) 計算資源自由 (2) チーム人数制限なし (3) 72 時間勝負 (4) 問題の形式も毎年大きく変化,等の特徴があります.優勝者は「その年のプログラミング言語」を決めることとなっており「その年はその言語の文句は言えない」とか.

チームについて

今年は,以下のメンバーで出場しました.(アルファベット順)

  • chokudai
  • imos
  • iwiwi
  • sulume
  • tos
  • wata

チーム名は "Unagi: The Synthesis" です(何故か運営にいつも ":" を "--" に置換される).一応僕はリーダー的な立場でした(=呼びかけをしたのと雑用を多くしただけ).

このチームは,2 年前に準優勝したチーム "Unagi: The Gathering" をベースとしています.その際,優勝者は 301 点だったのに対し準優勝の我々は 300 点でした.準優勝はとても嬉しくはありましたが,一方で 1 点差にとても悔しい思いをしました.

去年は色々あって(主に僕の都合が悪く)一旦チームが崩壊していましたが,そこから,今年出られるメンバーで再集結&新たなメンバーを勧誘して結成したのが今年のチーム "Unagi: The Synthesis" です.今年も(今年は今まで以上に)勝ちに行くことを強く意識して結成しました.全員が他のプログラミングコンテスト (ICPC, TopCoder 等) のバックグラウンドを色濃く持つ一方で,能力のバランス(アイディア力,アルゴリズム実装力,システム実装力,関数型言語等)を考えながら構成しました.

問題と結果について

今年の問題は,Program Synthesis という研究トピックを題材にした,割と真面目な問題でした.一言で言うと,「向こうが秘密のプログラムを持っていて,入力を渡すと出力を返してくれるので,秘密のプログラムを当てる.どれだけ多くの問題を当てられるか」という問題です.詳細はこちら

我々のソルバーは,特に特別な道具 (SAT/SMT ソルバー等) には頼らず,基本的に枝刈り探索+ヒューリスティクスをひたすらチューニングしてきました.色々なバリエーションを作り,それを Amazon EC2 をふんだんに使って分散実行しました.

普段,ICFP Programming Contest はリバースエンジニアリングやショートコーディング等を伴うもっと奇抜な問題が多いのに対し,かなり純粋な問題だったところも,優勝につながった要因だと思います.また,(2 年前からひきずっている)チームの最大の欠点である,メンバーが使える・使いたいプログラミング言語がバラバラというのが余り問題にならなかったのも助かりました.

皆思い思いのプログラミング言語を使ったので,「今年のプログラミング言語」は「Java, C#, PHP, Ruby and Haskell」ということになりました.(多くてちょっとダサいですが,毎年大抵どの言語を指定するかは使った言語にかかわらず指定できるのに対し,今年はアンケートに書いたプログラミング言語がそのまま使われてしまいました.)今年のプログラミング言語たちをよろしくお願いします.

感想など

ICFP Programming Contest に 2 年前から本気で参加するようになったのは,3 年前に尊敬する先輩たちのチーム Pure Pure Code++ が優勝し,とてつもなくかっこ良く感じたというのがあります.この際の先輩方のチームも,ICPCTopCoder 等で名高い方々で構成されたチームで,そういう方々がそういうコンテストだけでなく色々な要素での総合力勝負でも圧倒したところに憧れ,自分もそうなってみたいと思い真面目に参加するようになりました.憧れの優勝についに手が届き,とても嬉しいです.

もちろん,次の目標は連覇です.今回は比較的問われる能力が純粋だった(総合力勝負性が少し低かった)という点もあり,「また勝つ」ということへのモチベーションは失われていないと思います.簡単なことではないと思いますが,どちらにせよ(順位に関わらず)とても楽しいイベントでもありますので,来年も参加したいと思います.

参加中の風景など


期間中は集まってやってました.


序盤(もちろん全完してない)から「全完した」などと意味不明な情報戦を仕掛ける wata.


ボーナス問題が出現すると共に「再集結」したなどとさらなる大嘘を書く wata.



最後は時間が足りなくなってきたので 4 問同時に見守る.


ちなみに,最終的な得点は 1696 点でした.2 位に 100 点程度差をつけての優勝ということです.


全完とはこういうことだったらしいです.