HACK TO THE FUTURE 2022 本選に参加しました。
問題はCode Golf for Robot Vacuums。独自言語でコードゴルフする問題でした。
Code of the Rings？知らない子ですね。
結果は提出54人中19位、オープンも合わせると提出186人中29位でした。
問題
単純なコマンドを組み合わせて全セルを巡回してね。
繰り返しとかも出来るよ。
考察
これは左手法*1が強そう。
あとはAHC005に似てるかな。半端に効率の良い場所を探すより、愚直に一番近い場所に行くのを繰り返した方が強い可能性がある。
直進、左手法、右手法、と組み合わせるだけで、最短距離の最適化だけならかなり出来そう。ただ、向きの概念があるので400セル*4方向で1600状態。辺は1600*1600、ゴールをセルだけに限定しても1600*400か。ワーシャルフロイドは間に合わないな。
ということは、複数命令の組み合わせの前計算は諦めて、単純な命令の組み合わせでやるしかないか。
実装
～1:30
壁が与えられるという入力形式に慣れておらず、受け取ってデータを構築するのに難儀。
固定コマンドで400(rF)とか試してた。これくらいだと狭い場所にはまってしまうことが多い。
ん－、まずは簡単なもので完成させないと辛そうだな。
～2:30
とりあえず、左手法でいずれ大幅にコマンドを削減できるとしても吸い残しは出るはず。
スコア計算的に全マス掃除できないと低得点なので、まずは貪欲に全マス掃除を目指してみる。TSPまでやらないなら、残りを吸うのも全部吸うのも実装的には同じだしね。
とりあえず雑に、方向は考慮せず距離だけでDFSしたコストで、歩くのも1マスずつ。
9.5M点。結構出る。
～5:00
繰り返しの表現だけど、命令をCompositeパターン風に構造で持つことにした。これをすると3(5(rF)5(lF))みたいな複雑な構造にも対応できるのが良いところ。*2それから、「突き当りまで移動」のような意味のある行動を理解させれば、「R3FR2FR6F」のような命令を「3(R9F)」のように出来る。*3逆に2RFRFRFをR3(RF)にするような、構造の途中でぶった切るのは苦手そう。そういうのに対応したいならランレングス圧縮も良さそうだけど、*4ライブラリとして持っていないのでぶっつけ本番は怖かった。
連続したLRFのそれぞれを繰り返すだけで10M点。
コスト計算は、Fを繰り返す際に「Fの度に必ず1回曲がる(Uターンは考えない。*5最初の1回は別途差分計算すればよい)」「長さが2桁になる通路はそんなに無い」の2点を前提とすると「L9F」のように3文字に置き換えられる。1マス進むなら「LF」のように2文字。*6なので、優先度付きキューを使ってコストが低い順にDP*7をすればほぼ最低コストとなるものを求められた。*8
これで11M点。
～6:10
左手法と右手法を実装。
400[L3rF]のようにした。7～8文字程度の命令なので、大体4マス掃除できるなら左手法を優先するようにした。特に外周を回るのが強くて、9文字で130～180マス程度一気に掃除できる。
18M点。
～6:40
スコアが伸びず迷走。
愚直に移動するより左手法の方が短ければ左手法にしてみたり、一度直進が終わったタイミングで再考させてみたり。
貪欲スコアを[掃除可能マス/移動コスト]にするのも試してみたけど、やっぱり劣化してしまう。やはりここはAHC005方式で良いらしい。
ん－、壁をTSPするのか？いや、実装無理だろ…。
得点は微増。
～7:40
左手法が終わった後(左手法で掃除できる最後の汚れを掃除した後)、次の動作に繋がらずに愚直に動いてしまうことが多い。
繰り返し回数は0～1コストで増やせるので、上手く動作同士が繋がるようにしたいんだけど…。
うーん、汚れに隣接するまで延長すれば良さそう？汚れが無い場合は相変わらず分からないので最後の汚れの位置で。
これで19M点。あとはパラメータガチャして終了。
終了時のseed0のビジュアライズはこんな感じでした。
他の人の解法を見て
左手法は[LrrF]で良いらしい。*9コマンドの長さは一緒だけど、一応命令展開後の実行回数にも制限があり、そちらが節約できる分優秀。
全体としては、200(2(LrrF)3(RllF))のように、左手法と右手法を適当な回数で交互にやるのがとても強かったらしい。交互にやるのを更に繰り返すのは、かなり適切な値を埋め込まないと動かない気がして諦めたんだけど、割と動くんですね…。
感想
まず左手法を知らないと爆死するのと、*10それを上手く連結するのも天才的ひらめきが必要そうなので、天才向けコンテスト感が強かったです。
スコアにはあまり響かない部分でしたが、方向や変則的コストを考慮した最短経路の計算はやりごたえがありました。
余談ですが、今年はオープンでない本選に出場できたので、グッズや懇親会用の夕飯などをいただきました。食べながら書いています。ありがとうございました！
