AHC向けスクリプト整理

phspls

■これは何？

AHCの動作確認をローカル環境だけで完結させるタイプの人向けの記事です。
大量のテストを消化する際のスクリプトをいくつか書いています。
AHC031のデータを使いながら書いたので、インタラクティブについては必要に応じて書き換える必要があります。

■なぜ今？

  • PCを新調して一括でテストすることがある程度負荷にならなくなったため。
    VSCodeでコーディングしていますが、PC新調前は1000行くらいでカーソルの動きが重くなっていたので、とても裏でテストを走らせられる状況ではありませんでした。
    (VSCode周りのプラグインの影響が大きい気もしますが、カスタマイズしていないvimやhelixエディタでも1000行程度でカーソルの動きにラグが出ていました)

  • 一括テストの環境など、単純に整理するのを面倒がっていたため、長期コンテストでビジュアライザの確認だけで閉じていた状態になってました。入力に対する出力結果の傾向を見るのもそうですが、システムテストで想定していないWAとかREとか出るのは単純に嫌なので、対策はやっておきたいです。

■前提

Apple M2 pro Mac mini のバージョン13.5とそのDocker上のUbuntu 24.04の2つの環境で動作確認を行なっています。
前述の通り動作確認はAHC031のデータを使っています。
あとRustはインストール済でcargoコマンドは使用できる前提です。

作成したスクリプト類は$HOME/bin以下に置くことを前提としています。
なので下記のように.bashrc等で$HOME/binへのパスを通していることを前提としています。

#!/bin/bash

export PATH="$PATH:$HOME/bin"

大抵の場合AHCでは入力生成ファイルとビジュアライザが提供されています。
個人的にはビジュアライザはWeb版しか利用しないのですが、ローカル版はソースコードからsvgファイル生成部分を削除することで、正しいスコア計算をするプログラムになります。そちらを利用します。

$ # プログラムをダウンロード、展開したディレクトリに移動。サンプルはAHC031
$ # src/bin/vis.rs を変更して画像を出力しないようにしておく
$ cargo build --release --bin gen
$ cargo build --release --bin vis
$ # これらを実際に提出用ソースを書く作業ディレクトリにコピー
$ cp target/release/gen (作業ディレクトリの場所)
$ cp target/release/vis (作業ディレクトリの場所)

私はRustで競技プログラミングを行なっていて、作業ディレクトリが以下の状態からスクリプト作成していきます。

$ tree
.
├── Cargo.lock
├── Cargo.toml
├── rust-toolchain
├── gen # 提供される入力生成のソースコードから生成した実行ファイル
├── vis # 提供されるビジュアライザのソースコードをいじってスコア計算する実行ファイル
└── src
    └── main.rs # ソースコード

他、Rustで実行可能ファイルを作成している箇所について、クレートは2024/04/07時点のAtCoderのジャッジ環境と全く同じものを利用しているので、AtCoderのRust環境を構築してビルドしてください。Cargo.tomlにこちらの内容を記述する形になります。
下記のようにビルドしたファイルを$HOME/bin以下に置きます。

$ cargo build --release
$ cp target/release/main $HOME/bin/(適当なコマンド名)

■スクリプト類作成

●シード値の作成

早速ですがbashだと$RANDOMが最大32767だったり、$SRANDOMはzshで使えなかったりと面倒そうなので、Rustで書きます。これを書いている際の直近のコンテストAHC031では、seed値として符号なし64bit整数が利用されているので、その範囲で被らないように生成します。

use std::collections::HashSet;
use rand::Rng;
use itertools::Itertools;

fn main() {
    if std::env::args().len() != 2 {
        eprintln!("Usage: {} (生成したい乱数の数)", std::env::args().nth(0).unwrap());
        return;
    }
    let N = std::env::args().nth(1).unwrap();
    let N: usize = N.trim().parse().expect("引数は自然数で");
    let mut vals = HashSet::new();
    let mut rand = rand::thread_rng();
    while vals.len() < N {
        vals.insert(rand.gen_range(0..=u64::MAX));
    }
    println!("{}", vals.iter().map(|&v| v.to_string()).join("\n"));
}

最初のRust実装なので細かく書きますが、

$ cargo new script_test # script_testディレクトリができる
$ cd script_test
$ # 上のRustコードをsrc/main.rsにコピー
$ # Cargo.tomlを■前提に記載した通りに記入
$ cargo build --release
$ cp target/release/main $HOME/bin/create_seed
$ which create_seed # ここで$HOME/bin/create_seedが表示されるのを確認。
$ # 上記でcommand not foundならパスが通っていないので。前提部分の記載内容を確認した後、
$ # 問題なければsource ~/.bashrc等で設定を読み込み再度実行

とすることでcreate_seedコマンドが実行できるようになり、

$ create_seed 3000

を実行することで3000個の乱数を標準出力します。大抵の場合はseeds.txtに保存したいので

$ create_seed 3000 > seeds.txt

とすれば3000個の乱数がseeds.txtとして上書きまたは新規作成されます。
これで入力生成プログラムを実行すれば、inディレクトリが作成され、それ以下に3000の入力ファイルが生成されます。

$ ./gen seeds.txt
$ tree
.
├── Cargo.lock
├── Cargo.toml
├── gen
├── in
│   ├── 0000.txt
│   ├── ... # 多いので省略
│   └── 2999.txt
├── rust-toolchain
├── seeds.txt
├── src
│   └── main.rs
└── vis

●一括実行

一括実行では

  • 全力で素早く終わらせる。エディタが遅くなってもいい

  • エディタとか遅くならない程度のリソースを残しつつ素早く終わらせたい

  • 寝る前に実行し、起きる頃には完了している、PCのファンは静かな方がいい

の3つのモードを使い分けたいと思っています。
あと、

  • 管理が適当だと何の実装をした実行ファイルかを忘れてしまうので、何を実行したかをきちんと残すようにしたい

  • 実行中にも他の実装を試したりするので、ビルドで実行ファイルを変に上書きしないよう、別途避けておきたい

そんな感じで以下のようになりました。

#!/bin/bash

# 引数チェック
if [[ ! $# -eq 1 ]]; then
  echo "error: batch_exec ['full'|'middle'|'single']"
  exit 1
fi

# 並列実行する数。nprocコマンドで事前に割り当て上限を確認する。
# arm系のmacだとnprocコマンドがないため直接割り当て
# brew install coreutilsでnprocを使えるようになる模様。
case "$1" in
  full)
    # CORE_NUM=$(nproc)
    CORE_NUM=10
    ;;
  middle)
    CORE_NUM=6
    ;;
  single)
    CORE_NUM=1
    ;;
  *)
    echo "error: batch_exec ['full'|'middle'|'single']"
    exit 1
    ;;
esac

PWD=$(pwd)

# in ディレクトリ存在チェック
IN_DIR=${PWD}/in
if [[ ! -d $IN_DIR ]]; then
  echo "error: in directory does not exist."
  exit 1
fi
# 入力ファイルチェック。面倒なのでinディレクトリには
# 0000.txt ~ (ファイル数-1).txtのファイルしか存在しない前提
FILE_NUM=$(ls -1 ${IN_DIR} | wc -l)
if [[ $FILE_NUM -eq 0 ]]; then
  echo "error: in directory is empty."
  exit 1
fi

# ソースコードと生成される実行ファイル
SRC_FILENAME=main.rs
SRC_FILE=${PWD}/src/${SRC_FILENAME}
EXEC_FILENAME=main
EXEC_FILE=${PWD}/target/release/${EXEC_FILENAME}

# ソースコードの存在チェック
if [[ ! -e $SRC_FILE ]]; then
  echo "error: ${SRC_FILE} does not exist."
  exit 1
fi

# コンパイル実行 & CEチェック
cargo build --release
if [[ ! $? -eq 0 ]]; then
  echo "error: compile error."
  exit 1
fi
# 生成される実行ファイルについては存在チェックはしない

# 出力先ディレクトリ
RESULT_DIR=${PWD}/result
OUTPUT_DIRNAME=$(date '+%Y%m%d_%H%M%S')
DEST_BASE_DIR=${RESULT_DIR}/${OUTPUT_DIRNAME}
OUT_DIR=${DEST_BASE_DIR}/out
ERR_DIR=${DEST_BASE_DIR}/err

# 出力先ディレクトリがない場合は作る
if [[ ! -d $RESULT_DIR ]]; then
  mkdir $RESULT_DIR
fi
mkdir $DEST_BASE_DIR
mkdir $OUT_DIR
mkdir $ERR_DIR

# 出力先ディレクトリに必要なものコピー & 移動
cp ${EXEC_FILE} ${DEST_BASE_DIR}/${EXEC_FILENAME}
cp ${SRC_FILE} ${DEST_BASE_DIR}/${SRC_FILENAME}
cd $DEST_BASE_DIR

# 実行
seq -f %04g 0 $((FILE_NUM - 1)) \
  | xargs -I @ -P ${CORE_NUM} bash -c "./${EXEC_FILENAME} < ${IN_DIR}/@.txt > ${OUT_DIR}/@.txt 2> ${ERR_DIR}/@.txt"

# 実行ファイルの削除
rm $EXEC_FILENAME

ざっくりと書くと、

  • 前提として、このシェルスクリプトは作業ディレクトリで実行する

    • 作業ディレクトリには入力用のinディレクトリがある

    • inディレクトリの中は"(4桁の数字).txt"形式の、0000からの連番の入力ファイルのみ

    • ソースコードの場所、ファイル名は決め打ち

  • 並列に実行する数は前述の通り3パターンしか利用しないので、バッチの引数としてfull / middle / singleのいずれかを与えれば並列実行数が決まるようにしている

  • 作業ディレクトリにresultディレクトリがなければ作成、そこにyyyyMMdd_HHmmSS形式のディレクトリを作成する。

    • このディレクトリに実行ファイルをコピーしてそのまま移動して実行

    • このディレクトリに元となったソースコードを残しておく <- 何のバッチかわかる！

    • このディレクトリの標準出力結果がoutディレクトリに、標準エラー出力がerrディレクトリに出力される

    • 実行終了すればここにコピーした実行ファイルを削除

なかんじです。
最初のシェル実装なので細かく書きますが、

$ vim batch_exec # 前述のスクリプトをbatch_execファイルに記載
$ chmod +x batch_exec # 作成直後だと実行権限がないはずなので与える
$ mv batch_exec $HOME/bin # 所定の位置におく
$ cd work_dir # 作業ディレクトリに移動
$ batch_exec full # 全力で終わらせるパターンで実行
$ batch_exec middle # PCが必要以上に重くならないようにしたパターンで実行
$ batch_exec single # 並列ではない。ファンは静かなパターンで実行

のような感じで実行すれば、

.
├── Cargo.lock
├── Cargo.toml
├── gen
├── in
│   ├── 0000.txt
│   ├── ... # 多いので省略
│   └── 2999.txt
├── result
│   └── 20240409_032439 # 実行した日時がyyyyMMdd_HHmmSS形式で残る
│       ├── err # 各テストケースの標準エラー出力結果が入ったディレクトリ
│       │   ├── 0000.txt
│       │   ├── ... # 多いので省略
│       │   └── 2999.txt
│       ├── main.rs # 実行結果の元になったソースコード
│       └── out # 各テストケースの標準出力結果が入ったディレクトリ
│           ├── 0000.txt
│           ├── ... # 多いので省略
│           └── 2999.txt
├── rust-toolchain
├── seeds.txt
├── src
│   └── main.rs
└── vis

な感じでresultディレクトリに実行ログとして残ります。

●スコア一致チェック

AHCでは提出してテストケースごとに得点がつきますが、その得点がそのまま目的関数となる場合が多く、そのため提出プログラム内でもその得点の計算を行うことが多いです。
その計算にバグがあれば得点が伸びない＆得点計算自体はビジュアライザの方に入っているので、前提に記載した通りにビジュアライザのスコア計算部分だけを出力するプログラムを用意し、得点計算を行なって提出プログラムの得点計算が正しいかを確認したいです。
そのため以下のような流れでチェックをします。

  • 提出用プログラムは標準エラー出力で得点計算の結果を出力しておく。文言は"Score = %d"形式で出力しておく。

  • ビジュアライザから作成したスコア計算プログラムは標準出力形式で得点を出力しておく。こちらも文言は"Score = %d"形式で出力しておく。

  • 前述の「一括実行」の項目で標準エラー出力してあるので、それに対してチェックをかける

  • 提出用プログラムの標準出力、標準エラー出力のファイル数は入力ファイルと同じことを前提としている

初期の簡単な動作確認段階であればビジュアライザを使うでしょうし、そこで得点確認もできるので、大量のテストケースでも問題がないことを担保したい、という気持ちで行います。
こちらは処理時間もそんなにないはずなので並列実行数に${nproc}を指定しています。コマンドを入れていない場合は、coreutilsを入れるか適当な数値に変更して実行します。

#!/bin/bash

# score_check ./result/(yyyyMMdd_HHmmSS) で利用
if [[ ! $# -eq 1 ]]; then
  echo "error: score_check [log(result/yyyyMMdd_HHmmSS) directory] "
  exit 1
fi

# ビジュアライザから作ったスコア計算用ファイル
PWD=$(pwd)
SCORE_CHECK_FILE=vis
OUT_DIR=$1/out
SCORE_DIR=$1/err
if [[ ! -e ${PWD}/${SCORE_CHECK_FILE} ]]; then
  echo "error: score check file does not exist."
  exit 1
fi
if [[ ! -d $OUT_DIR ]]; then
  echo "error: out directory does not exist."
  exit 1
fi
if [[ ! -d $SCORE_DIR ]]; then
  echo "error: err directory does not exist."
  exit 1
fi

# in ディレクトリ存在チェック
IN_DIR=${PWD}/in
if [[ ! -d $IN_DIR ]]; then
  echo "error: in directory does not exist."
  exit 1
fi
# 入力ファイルチェック。面倒なのでinディレクトリには
# 0000.txt ~ (ファイル数-1).txtのファイルしか存在しない前提
FILE_NUM=$(ls -1 ${IN_DIR} | wc -l)
if [[ $FILE_NUM -eq 0 ]]; then
  echo "error: in directory is empty."
  exit 1
fi

# 

# チェック処理
check_func()
{
  # 処理速度によっては進捗がないように見えるので、どの処理をしているかみたい場合は下記コメントアウトを外す
  # echo "check $1 start!"
  # ビジュアライザの方のスコア
  local ACT_LINES=$(./$2 $3/$1.txt $4/$1.txt | grep "^Score = ")
  local ACT_VAL=$(echo $ACT_LINES | head -n 1 | awk '{ print $3 }')
  local ACT_WORD_CNT=$(echo $ACT_LINES | wc -w | tr -d ' ')
  # 提出プログラムが計算したスコア
  local EST_LINES=$(cat $5/$1.txt | grep "^Score = ")
  local EST_VAL=$(echo $EST_LINES | head -n 1 | awk '{ print $3 }')
  local EST_WORD_CNT=$(echo $EST_LINES | wc -w | tr -d ' ')
  local ok=true
  if [[ ! $ACT_WORD_CNT -eq 3 ]]; then
    echo "$1.txt: vis score data line count is not 1."
    ok=false
  fi
  if [[ ! $EST_WORD_CNT -eq 3 ]]; then
    echo "$1.txt: main.rs score data line count is not 1."
    ok=false
  fi
  if [[ ! $ok ]]; then
    return 1
  fi
  if [[ ! $ACT_VAL -eq $EST_VAL ]]; then
    echo "$1.txt: score unmatched!!"
  fi
}

# awkでcheck_funcを使いたいのでexport
# nprocコマンドが入っていることが前提。なければ$(nproc)を並列して実行したい数に設定
export -f check_func
seq -f %04g 0 $((FILE_NUM - 1)) \
  | awk '{ print $1, "'$SCORE_CHECK_FILE'", "'$IN_DIR'", "'$OUT_DIR'", "'$SCORE_DIR'" }' \
  | xargs -I @ -P $(nproc) bash -c 'check_func @'

echo "finish"

最後にfinishと出力しているのは、エラーがない場合に何も表示されなくて寂しいためです。
提出用プログラム側で大量に標準エラー出力していると、こちらも処理が重くなるため一応注意しておいた方がいいです。

■最後に

今回の構成のメリット：

  • 上記のようにテストケースごとの標準エラー出力も保存しておけば、複数の実装で得点の比較や実装ごとの入力に対する得点の傾向など調べやすくなります。

  • resultディレクトリ以下に出力結果をまとめてしまえば、.gitignoreに記載するのはresultディレクトリだけでよくなります。resultディレクトリのネーミングは考え直した方がいいかもしれませんが。

今回の構成の特殊なところ：
今回作成したスクリプトは作業ディレクトリ前提(= 現在のディレクトリから特定のパスに特定のファイルがある前提)で実装しているので、作業ディレクトリにスクリプトファイルをおいた方が良いと思います。
ただ、私は同じ構成の複数の作業ディレクトリとか割と作るので、都度スクリプトファイルをコピーするより、もう固定でやってしまおうという気持ちから$HOME/binに置いています。