6月 2019
日 月 火 水 木 金 土
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 ICFPC 2019 に出た.
参加するチームの人数に制限はないので基本的に多ければ多いほどよい. 次のように分担する. 毎年やって自然にこうなった.
コンテストが始まるとまず皆で問題を読み始める. 文章は英語なので、共同で和訳した. 今年は hackmd に書いていった
詳細はかなり細かいのでざっくり述べると,
二次元のマス目の空間が与えられる. マス目のうちのいくつかは空白でいくつかは壁で埋まっている. 自分が初め一体、空白のどこかにいて、縦横に移動することができる. 移動をすると自分の体があったマスは色塗られるので、できるだけ少ない移動量（時間）で全てのマス目を塗りたい. どんな移動を行えばよいだろうか？ という最適化問題.
ただし、自分の体はちょうどテトリスの T 字の形をしている. できることは移動以外に回転がある. また空間にはいくつかアイテムが落ちてあり、拾って使うことでさらに、体を伸ばしたりすることが出来るので上手く使うことが求められる.
また画期的なアイテムとして（これは予想できたが）、クローン C がある. これは名前の通り、自分の分身を作ることが出来るアイテムである. ただし C は X というマスの上でしか使用できない.
クローンたちは並列に同時に行動をするので、単純に、2体に分身するだけでも全体の行動量は 1/2 になることが期待でき、かなり強いアイテムであることが分かる. しかも、クローンたちは同じマスで重なっても良いし、また（去年みたいに）最後に一つに戻らないと行けないみたいなことも無いので、本当にただ分身してそれぞれは互いのことを考えずに好き勝手に移動すれば良いので、かなり使いやすい.
本当はシンプルなAIくらい作るつもりだったのだが、気がついたらエディタ（というよりペイントツール？）を作っていた. これは要するに手で解くためのツールだ. 1000 手で解けるくらいの問題なら 10 分程度で解ける.
初めは 1 手ずつ入力してたが、もちろんすぐに無理になる. ライブラリ担当の udon さんが filling shortest path (マスを一つ指定したらそれを塗るための最小のコマンド列を幅優先探索する; 結局それにはワーカーの場所と向きが状態になって、場所は高々 \(200 \times 200\) くらいで向きは 4 通りなので、実は簡単に探索できる) を実装してくれたので、これをエディタに組み込んだ. ところで私以外は皆 C++ で書いていたのを私は Rust に翻訳してエディタに取り込むということをしていた.
描画ライブラリには ncurses を使った. そしてこれにはマウスクリックを検知する機構も入っている!! 点を移動して移動、また矩形選択（対角の二点を指定する）でその中全ての塗りつぶしが出来る.
これは要はサブ問題に対するAIである. 完全に手で解くよりは性能は悪いが、それなりに使える. チームの他メンバーの成績と対決しながらやってたが、手で解いた結果は全てソルバに勝っていた. もちろん、致命的なネックは一問ずつを10分程度掛けないといけない点なのだが.
クローンは後半の大きな問題にしか無かったので、エディタの守備範囲外だと思っていたのだが、購入の概念が導入され、アイテムを拾わなくてもゲーム内のお金を払えば初めから所有することが出来る. というわけでエディタにもクローンを実装する必要がでた. 問題は、クローンたちはもちろん同時に動くのだが、それをエディタでどうやって操作するかということだった. 初めはターン制を導入したが、すぐにやってられないと分かったので、時間の同期を取らずに、それぞれが勝手に移動することにした.
フォーカスがあたっているのが赤色. タブキーで他のワーカーにフォーカスを切り替えて操作が出来るようになる.
何が理由というわけでもないけど、この土日の間に口の中に口内炎が同時に二箇所に出来た.