Future Tech Blog
フューチャー技術ブログ
Programmingカテゴリ

HACK TO THE FUTURE 2022本選のビジュアライザ作成しました

テクノロジーイノベーショングループ コアテクノロジーユニットの山田です。
HACK TO THE FUTURE 2022本選のビジュアライザ開発担当したのでその体験記を残しておきます。

HACK TO THE FUTUREとは

HACK TO THE FUTUREはフューチャーグループが2018年からAtCoderで開催しているオンライン競技プログラミングコンテストで、全国から高度なプログラミングスキルを持つユース世代を発掘し、交流を図り切磋琢磨し合う場を提供することを目的として開催しています1。

【本選概要】
開催日時：2021年12月18日(土) 10:00〜20:30
プログラム：プログラミングコンテスト(10:30~18:30)、表彰式・懇親会(任意)
実施形式：オンライン (開会式・表彰式、懇親会はバーチャル空間oViceを利用)
コンテストサイト：AtCoder「HACK TO THE FUTURE 2022本選」
＜本選出場者＞https://atcoder.jp/contests/future-contest-2022-final
＜オープン参加＞https://atcoder.jp/contests/future-contest-2022-final-open

HACK TO THE FUTUREは予選と本選に分かれていて2、今回のコンテストでは予選は744人、本選は（本選と同時刻に行われる本選オープンと合算で）186人の方が有効回答を提出しています。HACK TO THE FUTUREは厳密解を求めるのが難しい問題が出題されるヒューリスティックコンテストで、競技者はより良い解を求めることが要求されます。ヒューリスティックコンテストでは、競技者はアルゴリズム改善のヒントを得るために解を可視化するビジュアライザを使用することがあります。ビジュアライザは必ずしも公式で提供されるわけではありませんが、HACK TO THE FUTUREでは必ず提供しています。

問題

今回の問題は、与えられたプログラムの通りに部屋を掃除するお掃除ロボットがあり、入力で与えられた部屋を掃除するプログラムを計算するという問題でした。掃除できた範囲が広いほど高いスコアを得ることができ、部屋全体を掃除できた場合は更にプログラムの短さに応じたボーナススコアが入ります。

プログラムはLRlrF()0123456789の文字で構成された文字列で、L,R,l,r の命令により向きを変え、F命令で前進します。また、括弧で命令列をグループ化し、数値で命令列の繰り返し回数を指定できます。詳しくは問題文をご参照ください。

ビジュアライザを開き、input欄に「rFL3F」を1文字ずつ順番に追加入力してsimulateボタン押下してみてください。

output欄に1文字ずつ「r」と入力→simulateボタン押下→「r」のあとに「F」→simulateボタン押下→…と進めていくとロボットの動きが動いていくのが確認できます。

  1. r：壁を向いているので右を向く
  2. F：前に壁がないため1マス進む
  3. L：90度左を向く
  4. 3F：前に壁がないため3マス進む
    ※実際には作成したプログラムで出力した文字を貼り付けるとsimulateボタンを押下せず一気にロボット動かせます。

入力前のビジュアライザの状態
2022-01-20_11h20_48.png

入力後のビジュアライザの状態
2022-01-20_11h15_49.png

アニメーション
Animation.gif

ビジュアライザ開発業務の流れ

応募

全社メールにビジュアライザ作成メンバー募集のメールが送られており、今年はコンテストに参加する予定もなくビジュアライザ作成業務に興味があったこともあり応募しました。

複数人応募があったようですが、運良く私が選ばれました。

事前準備

問題が完成する前段階で事前準備を行いました。

まずは、コンテスト開催を主導している塚本さんから過去のビジュアライザ開発の流れや注意点などを教えていただき、それから過去問のビジュアライザの実装を見てビジュアライザの実装について理解を深めつつ開発環境の構築を行っていました。

ビジュアライザは個人開発のため、これまではソース管理などは行っていなかったということだったのですが、塚本さんと共有するためのプラットフォームとしての意味も含めgitlabで管理することにしました。その後linterやformatterの導入を進めましたが、元々linterやformatterを使わずに開発されたプロダクトに後から導入するのには壁があり、結局eslintでJavaScriptのlintのみ行うようにしました3。

cypressも導入できるとpush時にリグレッションテストを行ったりビジュアライザの動きをmp4で動画化して成果物として保存したりできるのかなと思っていたのですが、そこまで手が回らなかったのが残念でした。

ビジュアライザ開発

問題完成し、こちらで問題内容が確認できるようになってから開発を開始しました。部屋の情報とプログラムから掃除の過程をシミュレーションする処理はAtCoder社側で作成したwasmによって提供されており、可視化部分の開発に注力することができました。

ビジュアライザの開発では、まず入出力のバリデーションの処理を書き4、それから可視化に必要な素材集めを行いました。今回は壁のあるグリッドを掃除ロボットが掃除するという設定だったので、壁を表現できるタイル、汚れの表現、掃除ロボットの素材を探しました。

素材についてはぴぽや倉庫さんからお借りしました。ぴぽや倉庫さんの無料素材は素材データの転売のみ厳格に禁止で改変等については自由という非常に利用しやすいライセンスとなっているため、過去コンテストでも使用しています。ありがとうございます。

今回使用したいただいた元素材は以下の通りです。

ホコリに使った素材

部屋の埃を表現に使用しました。埃っぽさを増すために明度をあげて使用しました。

タイル

壁付きの部屋を表現するのに使用した素材です。後述の素材のフローリング部分と合成して洋風の部屋にしています。

床

部屋の床をフローリングにするため、右下の部屋の床部分を切り出して前述の素材と合成しました。

お掃除ロボット

お掃除ロボットです。目の部分を書き換えて使用しています。

コンテスト中

コンテスト中の質問5対応等については全て塚本さんが担当していたため、コンテスト中はTwitterで反応を見ていました。ビジュアライザ関連のトラブルが発生しないか不安でしたが、コンテスト中は不具合なく動いていたようでほっとしました。

懇親会

表彰式参加したかったのですが、共有機能にバグが見つかったため表彰式中は共有機能のバグ修正に追われていました6。表彰式終了の少し前に対応が終わり、なんとか懇親会には参加できました。
懇親会ではロボット（の名前が「お掃除高橋くん」なのに）かわいいという感想をいただいたりして、とても嬉しく思いました。（ロボットの名前が「お掃除高橋くん」というのは、そこで言われるまで気づいていなかったため驚きましたが）

共有機能のバグについて

命令列の最後が)で終わる場合、末尾の括弧がURLとして判定されず不正な命令列となってしまう不具合が発生しました。今後同じ轍を踏まないように GitHub - twitter/twitter-text を見て軽く調査しました。（内容に誤りがありましたらご指摘いただけると幸いです）

tweet内のURLの解析の正規表現は下図のように、validUrlQueryChars と validUrlQueryEndingChars が分かれているため、クエリ文字列として使用可能だが終端には置けない文字が存在します。

正規表現

クエリ文字列として使用可能な文字集合

正規表現

クエリ文字列の終端として使用可能な文字集合

正規表現

今回問題となった)はクエリ文字列として使用可能だが、終端として使用可能な文字ではないためこのような現象が起きてしまったようです。今後共有機能を使う際には#などの文字を番兵として配置しておくのが無難でしょう。

感想

ビジュアライザ開発が間に合わなかったら多方面に迷惑をかけてしまうのでとても緊張感がありましたが、無事開発できて安心しました。開発は普段の業務と大きく違う内容なので、新鮮味があり楽しく開発ができました。Twitterの方でもビジュアライズに言及いただき大変励みになりました。

今後ヒューリスティックコンテストがこれまで以上に盛り上がり、各社独自のビジュアライザ自作する流れができたら面白いなと思います。

反省点としては下記の3点です。

  1. メッセージやUIの修正を最後に回してしまったが、これらの修正は先に行い、後はアニメーションや機能追加の方のクオリティを向上させるだけという状態を作るべきでした。
  2. 共有機能でバグらせてしまい、競技者の皆様やAtCoder社の方にご迷惑をおかけしてしまった。
  3. 競技者にとってあると嬉しい機能を提案したかったが、いい案が浮かばず提案できなかった。

詳しい日程は未定ですが、今年も開催予定なので参加お待ちしています！

  1. 1.オンライン競技プログラミングコンテスト「HACK TO THE FUTURE 2022 for Youth」本選 12月18日開催 ↩
  2. 2.本選オープンも同時刻に行われ、そちらは誰でも参加することができます ↩
  3. 3.弊社には社内にeslint-plugin-vueのメインコミッターの方もおり、linterなどの設定は社内のドキュメント通りに設定すれば済んでいたためこのあたりの作業をしたことがなかったのですが、やってみると細かいところで躓いたりして、きちんとした環境が用意されていることのありがたみを感じました。 ↩
  4. 4.いつもは、素材集め→アニメーション無しマスの描画→入出力のvalidation→wasmを用いたスコアや盤面の表示→アニメーション作成という順番で行っているそうです ↩
  5. 5.競プロの世界ではclarと呼ばれることが多い ↩
  6. 6.結局AtCoder社の方がよりよい方法で対応してくださったため、私の対応は使われることはありませんでしたが。 ↩