■ [ICFPC] ICFP Programming Contest 2019 
https://icfpcontest2019.github.io/
https://github.com/tomerun/icfpc2019
一人で参加した。一人でフル参加したのは何気に初めて。
- 2009: 途中で萎えた（同時に開催されてたマラソンマッチに移行した）
- 2010: 休み取ってなくて2日しか参加できず
- 2011: 問題読んで本格的な関数型の知識を要求されてそうで怖じ気づいた（同時に開催されてたマラソンマッチに移行した）
- 2012-2018: チームで参加
1日目
会社で問題を読んで、帰宅して環境整備から取りかかった。
最低限の目標として、コンテストの順位は二の次で、快適に解答を実行できる環境を整備することに置いていたので、ライトニングは無視です。
AWS Batchで並列実行できるようにすることをもくろむ。そのためにDockerイメージを作る。
Crystalで書くつもりだったのでCrystal公式イメージをベースに作った。
実際の動作はソースコードに同梱したシェルスクリプトを実行して行わせるので、Dockerでやることはs3からソースコードとテストデータを落としてきて、ソースコードを解凍して中にあるスクリプトをたたくだけ。パラメタ的なのは環境変数で渡す。
なのでイメージに必要なのはawscli（とそのためのPython）くらい。
けど入れてみたらイメージサイズが700MBくらいになってECRへのアップロードがメッチャ時間掛かっていたので一旦停止して、Alpine Linuxのイメージから自分で作ることにした。
だがCrystalがすんなり動かず、依存パッケージを自分で色々入れないといけないらしい。
https://github.com/sam0x17/crystal-alpine/blob/master/Dockerfile
これを参考にしたけど、最新より一つ古いバージョンの0.28.0で試したものっぽいし、結局これらインストールしてたらイメージサイズも別に小さくなってないしで、結局最初の方針通りcrystal公式イメージから作った。だいぶ時間ロス…
あと結果を入れるためのRDSも立ち上げて、テーブル定義しておく。
ややこしいエンティティ間の関連があるわけじゃないし保守性の制約も緩いから、RDSじゃなくてDynamoDBのほうが適切そうな気もするけど、NoSQL本格的に使ったことないのでとりあえずRDBで。
2日目
イメージの準備ができたのでAWS Batchでジョブを定義していく。
初見では概念が色々ややこしいけど、クラスメソッドさんのブログを熟読してとりあえず動くレベルで設定をした。
昼過ぎぐらいにはジョブを投げて並列で実行されることを確認できた。初回はEC2インスタンス立ち上げからなのでジョブの実行が始まるまで数分かかることを知った。
入力パーサを書き始める。ソルバで使うことを考えて情報を色々リッチに持たせていたらだいぶ時間かかってしまった。
各テストケースを画像化しようかと思ったけど、Crystalに良い感じの画像ライブラリがなさそうだったのであきらめた。
このあたりで開始から24時間が経過して、仕様が出そろった。けど最後に出てきた追加仕様は弱小一人チームでは手が足りなすぎて無視するしかないやつで、はい…という気持ちになった。
ライトニングの順位表凍結が解除されたので、とりあえず順位表情報を10分おきに取得しておく。これはLambdaを使って定期実行した。コンテスト中には何も使わなかったけど、グラフ化でもしてみるつもり。
ひとまず正の得点を出すべく、単純に直近のまだ塗っていないところを塗りに行くグリーディーソルバを書いていく。
3日目
最初は単純なソルバからと思っていたのと相反して、Extension of the Manipulator使ったり、直近3歩だけは全探索して一番塗れるパターンを探したり、などいろいろやり始めてしまい、動かせるものになったのはこの日の21時くらいだった。
これで実行環境に投げて実行されている間に、DBからベストな結果を取ってきて提出用のzipにするスクリプトを書き、出てきた結果を提出してみた。
するとちゃんと点数が出て、しかも想像していたよりだいぶスコアが高く、一人で盛り上がった。
テンション上がってきて、Fast Wheels使うのとか、ブースターが近くにあったら優先的に取りに行くのとか、小さな非連結成分を塗り残していたら優先的に塗りに行くのとか、5時近くまで実装やってしまった。
Extension of the ManipulatorやFast Wheelsは取ったら即使うように決め打ち。
Manipulatorの追加位置は、本体から遠い箇所が選ばれやすいようなランダムで。
4日目
引き続きテンション上がっているので9時過ぎぐらいから活動開始。
ビジュアライザで見ると明らかに塗り残しがあるまま先に進んじゃっているのが見られるので、これをなんとかしたいと思う。
直近のまだ塗っていない所を探すときに、現在位置からの距離が直近な場所ではなく、ボットに「ベース位置」みたいなものを決めて、そこからの距離が近い場所を塗りに行くようにした。
あまりにも遠いところになってしまう場合は、現在位置をベース位置としておき直す。
本当はもっと大局的に、盤面をざっくりとグラフ構造としてみてTSPで経路最適化、とかをやりたかったが、シンプルに実装する道筋が見えず、アドホックな改善を積み重ねる形になってしまった（初日の環境整備に使った時間がなければ…）。
Fast Wheelを使ったときの探索がバグりまくって苦しかった。スピードアップしてると細い道から脱出できずに行動できないことがあるとか、最初想像できていなかった…。
自前チェッカのようなものは準備していないので、公式のビジュアライザでちまちま動かすのつらい。
残り5時間くらいで、まだDrill,Teleport,Cloneを使えていない状況で、それらを実装するか、ブースターは捨てて探索を賢くするのを頑張るか迫られた。
が、せっかくある仕様はできるだけ実装しておきたく、ブースターを実装するほうを選択した。
まずDrill。これは取ったらすぐ使うわけではなく、近い位置に塗り残しがなくて次にどこを塗るかBFSするタイミングで、Drillを使ったとした場合の探索も行い、時間が短くなるようなら使う、とした。
Drillを使うことにどれくらい効果があったかはよくわからないが、プラスの意味はあったと思う。
そしてClone。これはLambda Coinガン無視チームにとっては80ケースしか影響しないのであまり気は進まなかったが、やらないとその80ケースが壊滅的になるのは明らかなので、仕方なく実装した。
本当は分裂したBotたちを上手く協調させることをやらないといけないんだろうけど、各Bot独立にこれまでのアルゴリズムで動かしただけ。
それでも目に見えて結果は良くなったので、さすがにやって良かったという気になった。まあトップのスコアから見たら、ひどいゴミが多少マシなゴミになったくらいの変化ですが…。
Teleportは上手く使えそうに思えなく、時間もなかったので無視することになった。
終了1時間前に、最後の実行としてジョブを投げまくっていたら、インスタンスがkillされることがちょこちょこあってちょっと焦った。スポットインスタンスでやっていたので、リザーブドインスタンスの環境も急遽立ち上げ。
それでも一部ジョブの実行がなかなか始まらなくてやきもきさせられた。
これ、実行開始のレイテンシが気になるときは、Minimum vCPUを大きめの値にして常時インスタンス立ち上がっている状態にしておくものですね…（学び）。
手元で十分なバリデーションができてなくて、提出したらFailedになるのが怖いので、実行途中で何度か提出して様子を見る。無事最後まで全部validな解になっていて良かった。
感想
ちゃんと環境作れたのは大変良かった。手元でスクリプト一つ流したら勝手に実行して結果を保存してくれるのは最高だ。
これ、マラソンマッチとか他のコンテストでも役立ちそうなので使えるように整備しておこう。
今回は画面は何も作らなかったので、次回はダッシュボード画面を頑張りたい。まあ一人チームでは自己満足にしかならなそうだけど、楽しいのが重要。
ソルバーのほうは、仕様を実装するので精一杯という感じで、全く詰められた感じはしないなあ。
探索ロジックはだいぶアドホックになりすぎたきらいはあって、最初からもっと大局的に考えられれば良かったのかなあという感じ。未実装仕様が残っていることによる実装プレッシャーがあると、じっくり考えるの難しいが…。
クラウド費用は1800円くらい。ソルバ実行をガンガン動かしたのは最後だけだから、こんなもんか。
