2010年06月26日

All your fuel are belong to us - ICFP-PC'10 participation report

(Note: this entry contains spoilers for ICFP Programing Contest 2010)

Our team strategy

On 18-22 June I participated in ICFP Programming Contest 2010 in a team "Pure Pure Code ++" with 6 members. Thanks so much for contest organizers! We enjoyed this year's contest very much. Fortunately enough, we could cling to the place within 5th position at the end of the contest. I decided to write up this entry so that participated teams can find each other - this year, Googling other teams is difficult because of masked top five team names. I hope that PigeonRank marks this entry well with white traces and other teams can find us. I would rather like the latter without the former.

We used C++, Haskell, and Python as main languages; "pure for purely functional, pure for purely imperative, ++ to increment and concat two languages" is the origin of our team name, that I invented right now. Not any connection to Japanese Anime, probably, maybe, possibly. Perhaps. We used Linux, MacOS and Windows (cygwin) as platforms; thus, basically, our team-play was a full of mess.

Our basic strategy was very simple: try to solve any fuels encounted. This requires a strong solver for cars; for that purpose @tanakh wrote up a nice, simple, simulated annealing solver. The solver was written around the end of the first day, and it turned our game into a lottery - srand() determines your shares. After several improvements the solver "burns" most of cars and cdrs within 30 secs each. For specially designed problems which is difficult to solve by burner, we wrote several half-automated solvers. Some cars are mathematically strong and we failed to breach them - we even tried ECM. If you can not understand what I mean, I promise that it's worth finding. Hint 1: ECM is not Electronic CounterMeasures. Hint 2: check for cars with many tank 2 and 3 (0-origin) intakes.

Solving process is mostly automated. @nya3jp wrote a neat submit helpers / web interfaces; he uploaded a screenshot of the web interface which can be seen on the near-bottom of his blog. We spend last 12 hours continuously reloading the "unsolved problems" page; if we find a series of unsolved problems, write a special solver up, and return to reloading the web interface page. Not a few times we found the cars burnt while writing solvers.

At the middle of the 2nd day, we are very confident with our solvers; thus, to ship our own cars, we just crash-tested them with several variants of annealing solvers. We first generate a fuel, then form random products of fuel matrices. Pairs are picked up so that they form inequalities.

Unfortunately we could not assign enough resources (and finding fine ideas) to shorten circuits. We made constants by combining several circuits, and inserted latches between them. Our circuits are not very efficient in general (more than 4 gates / trits).

Finally here with a list of teammate's wrapups (all written in Japanese):

and @nya3jp uploaded a mini-presentation on his blog.

What I did

Here is a list of my great contributions. Look upon my works, ye Mighty, and despair!

  • Prepared a server which froze and never come back
  • Constantly stirring other members like the pointy-haired manager
  • Gathered geeky quotes from team members
  • Injected uncountable number of bugs into SA solvers

I thank again for contest organizers. Playing ICFP-PC is fun.

posted by chun at 20:35| Comment(0) | 日記
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: