こんにちは。これはでぶアドベントカレンダー2023(https://adventar.org/calendars/8539 )の記事です。
今年はお絵描きでぶをやってみようと思います。 AHCのビジュアライザで(に?)shojinさんを書いて動かしてみました。
ビジュアライザを改造して遊ぶ方法の記事を最近書きました。マスターズ選手権に向けてビジュアライザ筋トレをしよう! yunix-kyopro.hatenablog.com
AtCoderなどの競技プログラミングのコンテストに参加しているyunixです。 来年に開催されるマスターズ選手権、楽しみですね。マスターズ選手権は28歳以上の2~3人の団体戦で、時間が6時間のヒューリスティックコンテストになるそうです。
このコンテストの大きな特徴の一つはビジュアライザが提供されないことが明言されていることです。 ヒューリスティックコンテストではビジュアライザを使用して考察することがとても大事なステップになります。 従って、参加者自身でビジュアライザを開発することになると思うのですが、ビジュアライザの開発の準備をしていなければ
などの点で辛い戦いになってしまいそうです。
そこで、
ようにするために、ReactとRustを使ってビジュアライザ開発用のテンプレートを作りました(Reactに書き換えてはいるもののほぼ公式のビジュアライザを移植しただけなので大したことはやっていないのですが...)。 基本的にReactの部分は触らずに、Rustで問題ごとのビジュアライザや入力作成機能を作ればいつもの感じでビジュアライザが使えるようになっています。
この記事では作成したテンプレートの解説をしようと思います。(使用方法はリポジトリのreadmeを参照して下さい)
最近のAHC(AHC030など)では乱数生成などのクレートのバージョンが新しくなっていて、上記のリポジトリのCargo.tomlの内容では提供されたツールをコピペしても文法エラーになる可能性があります。 最近のAHCの配布ツールに合わせてクレートのバージョンを変更して使ってください。
AHC030では以下のもので配布されたツールをコンパイルすることができました。getrandom = { version = "0.2", features = ["js"] }の箇所が多分重要で、wasmにするのに新たにこの依存関係が必要です。
[package]
name = "rust"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[lib]
crate-type = ["cdylib"]
[dependencies]
wasm-bindgen = "0.2.89"
getrandom = { version = "0.2", features = ["js"] }
rand = { version = "=0.8.0", features = ["small_rng"] }
rand_chacha = "=0.3.1"
rand_distr = "=0.4.3"
itertools = "=0.11.0"
proconio = { version = "=0.3.6", features = ["derive"] }
clap = { version = "4.0.22", features = ["derive"] }
svg = "0.9.0"
delaunator = "1.0.1"
web-sys = {"version" = "0.3.44", features=['console']}
いつものビジュアライザの機能をほぼそのままReactに持ってきたような感じです(そのまますぎて怒られないかな...?)。 特に画像や動画の保存機能などについては処理をかなり参考にしました。
前述のような機能を実現しようと思ったときに、何が特定のコンテストに固有の処理で、何がコンテストによらずに共通で使えるかということを考えることは重要です。 コンテスト中にビジュアライザを作成しなければいけないため、極力使いまわせるところは使い回して、コンテストごとに固有の事情に集中できるようにしたいためです。 例えば、スライダーを動かしたり、フォルダのアップロード機能、入力のダウンロード機能などは使いまわせそうです。 一方で、入力を作成する機能や、出力に応じてスコアをつけたり画像を出力する機能はコンテストごとに作らなければいけません。
このように考えると、以下の3つの機能をコンテストごとに実装すれば良さそうだという結論に至りました(AHCで提供されているビジュアライザは大体そうなっているので踏襲しただけとも言えるのですが...):
これら3つの機能をRustの関数として記述して、WebAssemblyでJavaScriptから呼び出せるようにするだけで、大体いつものビジュアライザと同じような使用感で使えるようになります。 React側のフロントエンドについては、何か編集したい事情(ほかの画像を生やしたい、入力を増やしたいなど)がない場合には特に触る必要はありません。
フロントエンドをReact、コンテストごとに固有の部分をRustで作成してWebAssemblyでJavaScriptから使用できるようにしています。
このようになっている理由はいくつかあり、
従って、コンテストごとに固有の処理の部分を必ずしもRustで書く必要はなく、何で書いても大丈夫ではあります。 特に、インタラクティブな操作がビジュアライザに必要な場合にはReactで処理を書いた方が良い可能性もあります。必要に応じて書き換えましょう。
RustのWebAssemblyを扱うために、wasm-bindgenというモジュールを使っています。
Rust側で
#[wasm_bindgen] pub fn gen(seed: i32) -> String { // 処理 "結果".to_string() }
このように"#[wasm_bindgen]"をつけて関数などを記述し(構造体とかでも良い)、wasm-packを使用してRustをwasm化
wasm-pack build --target web
すると、JavaScriptの方でこのように呼び出すことができる関数が生成されます。
const inputText = gen(seed);
基本的には、 https://github.com/yunix-kyopro/visualizer-template-public/blob/main/wasm/src/lib.rs ここの3つの関数(gen, vis, get_max_turn)を編集して、JavaScriptから呼び出すことができるようにします。
前述したように、lib.rsの
をRustで実装すればいいです。 ここではyukicoder score contest 2を題材にしてこれらの関数を実装しました。
実装はこちらのブランチにあります: GitHub - yunix-kyopro/visualizer-template-public at yukicoder-score-contest-002
mainブランチから変更されたファイルは以下の2つです:
util.rsに問題の固有の処理(入力生成や画像生成など)を書き、lib.rsからそれを呼び出す形式で実装をしています。
util.rsの処理は、普段配布されているローカルテスタ(のlib.rs)の処理の内容をかなり踏襲していて、
などは記述方法をかなりそのまま持ってきています。svgの記述方法などは特に参考になり、作りたいビジュアライザに近い回のローカルテスタのvis関数の内容を参考にすると良いと思います。
これらだけを編集して、wasmをビルドすると、yukicoder score contest 2の内容のビジュアライザを使用できます。 こちらにseed=0のサンプル出力を用意したので、動かしてみましょう。
場合によっては一部の処理を実装することをサボっても良いかもしれません。 例えばサンプルケースがファイルとして配布されるようなときには、gen関数の実装はサボることも十分に考えられます。 また、スコア計算も実装がめんどくさくなりがちなので、サボってビジュアライズ部分だけを作るなどのこともあり得ると思います。
ビジュアライザを短期間のコンテストで開発するとなると、相応に準備と練習をしておいた方が良いです。 ここではこのツールを使う練習の方法について記述したいと思います。 動かすために必要な環境などはリポジトリのreadme.mdを参照してください。
yukicoder score contest 2の他にも、chokudai contest 005の実装を用意しました。 これらのブランチをチェックアウトして、
cd wasm && wasm-pack build --target web --out-dir ../public/wasm && cd ..
を実行してwasmをビルドし、
yarn dev
でビジュアライザを動かしてみましょう。
動いたらutil.rsのvis関数の内容を変えて、表示される内容を変えてみると良いかもしれません(その際にはwasmのビルドを忘れないようにしてください)。
次に、mainブランチのテンプレートから開発を始めて、既存のAHCのビジュアライザを再現してみましょう。 既存のAHCのビジュアライザを再現することで、どこで何を書けばいいのかを把握しましょう。
触るべき場所はlib.rsとそこから呼び出すモジュール(util.rsなど)です。 AHCのローカルテスタのlib.rsの中身を再利用するととても簡単にできます(引数などを調整しないといけないことはありますが、基本コピペをして、lib.rsから呼び出せばよい)。
コンテストで使用することを想定して、１からビジュアライザを作ってみましょう。 １からとは言っても処理を踏襲できるところは多いはずです。 これを素早くできるようになれば実践でも実用的になるはずです。
作ったビジュアライザはwebを経由してチームメンバーと共有できると楽です(ローカルにcloneしてきて動かすでも悪くはないと思うのですが...)。 この際に気をつけないといけないことは、
こう考えた時に良さそうなデプロイ先としてVercelがありました。 vercel.com
Vercelは
などの点でマスターズ選手権向けにはとても良さそうでした。 以下ではこの記事のテンプレートをvercelにデプロイして、BASIC認証をつけるために必要なことを書こうと思います。
とはいえ、vercelはすごく簡単で、Githubと連携してアカウントを作り、指示に沿って作業をするとフロントエンドのページをデプロイできてしまいます。 vercel自体の使い方についてはtutorial等を参考にしてください。
設定はこのようにするとうまくいくと思います:
Viteを選択して、ビルドはtsc & vite buildで実行してください。
以下ではテンプレートに対する変更に限って記述をしようと思います。 やるべきことは3つあり、
テンプレートではwasmのビルド結果はgitignoreでリポジトリから除外されているので、あらかじめビルドしてリポジトリの中に入れておく必要があります。 (やろうと思えばvercelでwasmのビルドができる気がするのですが、ローカルでやってしまうのが簡単だと思います)
yarn add @vercel/edge
コマンドを実行して、@vercel/edgeを追加しましょう。 これはBASIC認証をつけるために必要で、以下の記事を参考にしました。 zenn.dev
リポジトリのルートにmiddleware.jsを追加します(これも上記の記事を参考にしました)。 userとpasswordは適切に変更してください。
import { next } from '@vercel/edge'; export const config = { matcher: '/', }; export default function middleware(req) { const authorizationHeader = req.headers.get('authorization'); if (authorizationHeader) { const basicAuth = authorizationHeader.split(' ')[1]; const [user, password] = atob(basicAuth).toString().split(':'); if (user === 'ここを変更する!!!!' && password === 'ここを変更する!!!!') { return next(); } } return new Response('Basic Auth required', { status: 401, headers: { 'WWW-Authenticate': 'Basic realm="Secure Area"', }, }); }
これはEdge Middlewareという技術を使っているそうです。
Edge Middleware is code that executes before a request is processed on a site
こう書いてあるので、ページの前にIDとパスワードを要求しているような処理を実行していることになります。
以上の3つの事項を実装すると、BASIC認証がついたページをデプロイすることができました。(この範囲だと無料プランでできるはず...)
マスターズ選手権が楽しみすぎてもう準備を始めてしまいました。 この記事はビジュアライザをどう書けばいいか悩んでいる方へのヒントになればいいかなと思います。
個人的にもRustとWebAssemblyを触る良い機会になったと思います。3月までにRustをたくさん練習しておきます。 (チームメンバーも探さなきゃ... 声をかけていただけると嬉しいです)
質問などがありましたらコメント欄やtwitterにご連絡いただければと思います。
こんにちは。競技プログラミングのコンテストに参加しているyunixです。
マラソン系のコンテストに参加していると実装が複雑になりがちで、ソースコードが数千行くらいになることもあります。 一方でAtCoderをはじめとしたコンテストでは提出を一つのソースコードにしなければいけません。
いきおい一つのファイルにたくさんのクラスや関数を定義することになるのですが、
などの点で認知負荷が高くなっている気がしてストレスを感じていました*1。 マラソンでは気力が切れたら負けなので、コーディングの際のストレスは極力減らしたいです。
そこで最近は
g++ main.C -I . などとしてビルドできるというやり方を採用することにしました。 いまいちこのテーマで記事を見かけなかったので、やり方に関するメモを残そうと思います。 個人的には満足しているのですが、ベストな方法だとは思っていません。他の記事や良いやり方がありましたらコメントに書いていただければ嬉しいです。
*1:個人差はあると思います。chokudaiさんはこの前のあーだこーだーで適切にクラス分け等がされていれば一つのファイルでもそんなに苦じゃないと言っていました。
こんにちは。競技プログラミングのコンテストに参加しているyunixです。 HACK TO THE FUTURE 2023本戦(https://atcoder.jp/contests/future-contest-2023-final)に参加して3位でした！ 競プロを始めてから2年半、初めてのオンサイトのコンテストでとても楽しかったです。運営・参加された方々ありがとうございました。
コンテスト中にやっていたことを、提出履歴を見て思い出しながら書いていこうと思います。
焼きなましをするときにはこんな感じにクラスを作ると個人的にいい感じでした:
このようなクラス設計をすることで以下のようなメリットがあったと思っています:
関心ごとの分離
近傍操作をする際に状態管理の実装の詳細を隠蔽できる(これも関心ごとの分離の一種かも)
近傍操作の選択やrollbackの記述をシンプルにできる
場合によってはState部分には単体テストを入れてもいいかも
批判・自分はこうやっているなどのコメントをお待ちしてます^^
続きを読む