ICFP-PC 2021 参加記

2021年 7/9(金) ~ 7/12(月) に開催された ICFP-PC 2021 にチーム chirijako で参加しました
コンテストサイト
https://icfpcontest2021.github.io/index.html
リポジトリ (諸々認証情報は無効化済み)
https://gitlab.com/icfp-pc2021_e-seikatsu/icfp-pc2021

ちょこちょこメンバーが変わりつつ、このチームで参加するのは今年で五年目ぐらい
(去年は諸事情により自分は参加しなかった)
今年は Rust で参加しました
例年 C++、Python で参加してましたが、今年は何故かメンバー全員 Rust 使えるようになっており凄い

結果

6/160 位でした
いつもは 30 位くらいなのでかなり健闘できた (嬉しい)

チームでやったこと

焼きなましソルバ

  • Rust でチームメイトが実装
  • クソつよ EC2 インスタンス (c5.24xlarge) 借りて並列でソルバーを回した結果、ほとんどの問題をいい感じに解いた

Web ダッシュボード

  • TypeScript + React でチームメイトが実装
  • これまで出した解の一覧が問題ごとにランキング形式で見れる

  • 簡易的な操作機構がついており、後述するビジュアライザが出来るまでは、コレで手動で解いていた

ビジュアライザ

  • Rust で自分が実装
  • ソルバーで解けない問題はコレを使って手動で解いた
  • 詳細は後述

自分がやったこと

例年ソルバー係をやっていましたが、今年は途中で無力を感じてビジュアライザ係になりました

チームメンバーの意見を参考にしつつ色々追加していった結果、↑の通りかなり多機能になった
「実装」 -> 「メンバーからのフィードバック」 -> 「実装」 のサイクルができていて、開発楽し〜〜となっていた

ビジュアライザについて振り返ってみて感じたことなど

ソルバーとの結合は重要

  • ソルバーの挙動確認やデバッグの効率が上がる
  • ビジュアライザとソルバーを結合することで、手動解も作りやすくなる
  • できれば実装を始める前にソルバー係とインタフェースの打ち合わせをしたほうが良い

手動で解くのが有効かどうかで実装方針が変わる

手動で解くのが有効化どうかは、以下の点が重要

  • ソルバーの実装が難しい
  • 盤面が人間の脳に理解しやすい
    • 二次元の問題
    • 操作順がスコアリングに影響しない問題
      • 順番を気にするのは人間には難しい
  • 手動で解いてくれそうなメンバーが居る
    • 手動で解く人が居ない場合、手動で解くことは有効でない
    • 多ければ多いほど手動で解くことは有効

手動が有効でないならソルバーの挙動確認がビジュアライザの主目的になるので、実装方針に影響する
一部の問題のみ↑が当てはまるのはありがちなストーリーなので、問題の把握は大事

web で実装するか、ネイティブで実装するか

結構悩みどころで、比較してみると

  • ネイティブアプリ
    • 環境依存の挙動が比較的出やすい
    • ソルバーをビジュアライザと結合しやすい
      • 言語が同じなら結合コストがかなり小さくなる
    • 入出力はコマンドライン上の指定が可能で楽
    • 自由に言語選択できる
    • 言語に対する習熟度によっては実行までのコストが大きい
      • バイナリを配布できるなら大丈夫
  • Web アプリ
    • 環境依存の挙動が少ない
    • ソルバーとの結合が難しい
      • ウェブアセンブリ使えばまあ出来る?
      • 少なくともネイティブアプリよりはコストがかかるはず
    • 入出力ファイルのインターフェースが (普通に実装すると) 扱いづらい
    • (基本的には) 言語を typescript に強制される
    • どこかにホスティングすれば実行までのコストは無

上記踏まえて、ソルバーとの結合が結構重要なので、ソルバー係と言語を合わせてネイティブアプリが良さそうかもと思った
ウェブアセンブリに習熟すれば話が変わるのかも

来年に向けてやっとくこと

ソルバー周り

  • いい感じのソルバーを実装できなかったのは反省
  • 焼きなましを AHC の過去問とかで素振りする

ビジュアライザ周り

  • 三次元の何かのビジュアライザを実装してみる
  • 今回の実装から二次元ビジュアライザのテンプレを作る
  • ウェブアセンブリの素振り

幾何

  • 自前実装が結構しんどいのでいい感じの幾何ライブラリを探す