sheep-random-test

これは

ランテス支援スクリプト。 入力生成プログラム、愚直プログラム、検証対象プログラムをループで回し、WAとなるテストケースを吐き出す。

基本的には競技プログラミングコンテスト中などに「計算量は悪いが正確な愚直コード」と「計算量は妥当だが正当性の不明な検証対象コード」に対して用いることを想定している。 もちろんupsolve時や教科書の演習問題で「正しい解答」と「正しいか分からない自分の実装」を比較するために用いることもできる。

2ファイルモード

愚直コードと検証対象コードの出力を比較し、出力が異なればWA

1ファイルモード

検証対象コードのみ実行し、正常終了しなければWA。

• コンテスト中に2ファイルに切り分けるのが面倒な場合
  • プログラム内でassert(smartAns == naiveAns)のように判定してWAなら異常終了させる
• 少数誤差や構築判定など、特殊なジャッジの場合
  • プログラム内でassert(judge())のように判定してWAなら異常終了させる
• 大きな入力に対して実行時間計測してTLEしないかチェックしたい場合
• 投げたらREが出た場合

用語

• GENERATOR：ランダムテストの入力を生成するプログラム
  • 「入力生成プログラム」なども同様の意味で用いる
• NAIVE：計算量度外視で出力の正しいプログラム。
  • 「愚直コード」も同様の意味で用いる
• SMART：ランダムテストで正しさを検証したいプログラム
  • 「検証対象コード」も同様の意味で用いる
• AC、WA、RE、TLE：競プロのジャッジステータス用語から流用

実行手順

1. 実行権限を付与する（初回のみ）

chmod +x random_test.sh

2. random_test.shのパラメータを変更する

プログラム中のコメント通り。

GENERATOR

入力生成プログラムを指定する

NAIVE

愚直プログラムを指定する。TEST_MODEが1の場合は実行されないので何でもよい

SMART

検証対象コードを指定する

LOOP_COUNT

ループ回数を指定する

STOP_THREASHOLD

WAを特定回数検出した時点で停止したい場合に使用する。停止させる必要がなければLOOP_COUNTより大きい値を指定すればよい

OUTPUT_MODE

ファイル出力モードの切り替え。 1を指定するとACでもWAでも出力し、2を指定するとWAのみ出力する。

TEST_MODE

1, 2で1ファイルモードか2ファイルモードか切り替える。

3. 実行する

./random_test.sh

その他よく使うコマンド

resultフォルダの一括削除

find -name "result_*" -exec rm -rf {} \; 2>/dev/null

future works

• generatorの充実
• 少数誤差などのサンプル
• スモールケース全探索、コーナーケース対策
• WAになったケースの網羅実行

not future works

• シェルスクリプト以外の実装の提供（Pythonなど）
  • random_test.shが安定したらやるかも
• 「出力が等しい」以外のジャッジへの対応
  • とりあえず1ファイルモードで実装可能なため
• パラメータの外部化（tomlから読み込むなど）
  • 広く公開するならやってもいいけど、可搬性のためできるだけライブラリを使わずやる（AWK芸とか？）
• 生成プログラムにオプション引数を付けてコンパイル不要で制約を変える、helpを付ける
  • C++の場合、boost::program_optionsなどでやる
  • 広く公開するならやってもいいけど、自分で使う分には困りづらい

運用tips

自分のフォルダ構成

相対パスで指定しやすいように競プロフォルダの隣に置いている。 遠いところに競プロフォルダがあり絶対パスが長い場合、random_test.shの別の変数に格納して結合するなど。

$ tree -L 2
.
├── Competitive
│   ├── AtcoderContest
│   ├── a.out
│   ├── ac-library
│   ├── input.txt
│   ├── output.txt
└── RandomTest
    ├── README.md
    ├── gens
    ├── random_test.sh
    └── sample

スクリプトの連続実行

RESULT_FOLDERの命名は1秒単位なので、スクリプトを1秒間に複数実行すると困る。

• 単にテスト回数を増やしたいのであれば1回の実行におけるLOOP_COUNTを増やすべき
• 並列実行したい場合は改造が必要

テストファイルの固定

始めから固定したいのであれば入力生成側で乱数シードを固定する。 一度使ったテストケースを後から再利用したくなった場合は現在対応していない（手動でやりたければ入力生成をコメントアウトしてRESULT_FOLDERを定数にすれば可能）。WAケースを全て再実行してACになったか確認したいニーズはありそうなのでfuture work。

生産者の顔

https://twitter.com/BinomialSheep