競プロ用ランダムテストのコード紹介(C++・Python)

本記事はこの記事の下位互換です

競プロでWAが出たときのランダム入力データ生成入門

本記事を書いている時に見つけました。
もっと多くの人に見つかりますように(調査不足でした、ごめんなさい)。

これを踏まえて、本記事の差別化ポイントとしては、 Python ユーザ向けのランダムテストとして 「Python コードだけでランダムテストができる」手順が整っていることでしょうか。

あとは特にない気がします・・・

目次

はじめに

競プロにおいて考察結果を全くミスなく実装し続けられる人はいないでしょう。 我々は人間なのでミスをします。考察は正しいはずなのに、出力される答えが合わない。 そんな時、皆さんはどうするでしょうか?

  • コードを読み直してバグを探す
  • 計算過程を出力して確認する
  • 経験則や直感を利用する
  • 典型バグ(?)のガチャをする
  • 最初から書き直す

色々あると思います。 答えが合わないテストケース(サンプルケースなど)が分かっている場合、時間をかければ大抵は解決できるでしょう。 そうでない場合(ジャッジに投げて WA が返ってくる場合)、一体どこが間違っているのか突き止める、つまりデバッグするのは難しくなります。

そんなとき、最後の手段として使えるのが「ランダムテスト」です。 ランダムテストは下記のようなステップによって行われ、 「自分の書いたコードが WA になるケース(以下、撃墜ケース)を見つけ出すこと」を目的として行われます。

  1. 計算量を無視して愚直解を求めるコード(以下、愚直コード)を書く
  2. 小規模な入力ケースをランダムに生成するコードを書く(以下、入力生成コード)
  3. 入力生成コードに対して、「WA になるコード」と「愚直コード」の2つの答えを突き合わせる
  4. 撃墜ケースが見つかるまで繰り返す

以上のことは、特に緑コーダー以上の人たちのほとんどは聞いたことがあると思いますし、既に実践している人も少なくないと思います。 しかし、ランダムテストの重要性が言及されることはあっても、具体的なコードを紹介する記事は見かけません。 これが本記事を書こうと思ったモチベーションです。 本記事の冒頭に書いたように上位互換の記事が既に存在します。

動作環境

本記事でご紹介するコードは下記の動作環境でのみ確認しています。

ランダムテストのコード(C++

シェルスクリプトを利用した C++ 用のランダムテストです*1。 用意するのは下記の4つです。

入力生成コードは Python としています(楽なので)。 問題の入力に合わせて入力生成コードを実装して、入力サイズ( N など)を小さめにしておきます。 愚直コードも実装しておきます。そうしたら、下記のようにしてランダムテストを行います。

# g++ main.cpp -o a.out
g++ greedy.cpp -o b.out
bash random_test.sh
  • main.cpp
// 絶賛バグらせ中のコードです
  • generate.py
import random
# random.seed(777)

# 1 <= K <= N <= 5
N = random.randint(1, 5)
K = random.randint(1, N)
print(f"{N} {K}")

# for _ in range(N):
#     a = random.randint(-10, 10)
#     print(a)

A = " ".join(map(str, list(random.randint(-10, 10) for _ in range(N))))
print(A)
  • greedy.cpp
// 愚直コードを書きます
  • random_test.sh
while true; do
    python3 ./generate.py > random.in
    A=$(./a.out < random.in)
    B=$(./b.out < random.in)
    if [ "$A" != "$B" ]; then
        echo "----------------------------------------"
        echo "Wrong Answer"
        echo "[test case] "
        cat random.in
        echo "[./a.out] "
        echo "$A"
        echo "[./b.out] "
        echo "$B"
        echo "----------------------------------------"
    fi
done

ランダムテストのコード(Python

Python 用のランダムテストです*2。 用意するのは下記の3つです。

C++ の方にあった generate.pyrandom_test.sh が、こちらでは random_test.py として一体になっています。

  • greedy.py
# 愚直コードを書きます
  • main.py
# 絶賛バグらせ中のコードです
  • random_test.py
import random
import subprocess

TESTCASE_FILE = "random.in"
MAIN_FILE = "main.py"
GREEDY_FILE = "greedy.py"


def read_random_case():
    with open(TESTCASE_FILE, "r", encoding="utf-8") as f:
        return "".join(map(str, f.readlines()))


# NOTE: 問題に合わせてランダムテストケースを作成する
def write_random_case():
    with open(TESTCASE_FILE, "w", encoding="utf-8") as f:
        lines = []

        # 1 <= N, K <= 10
        N = random.randint(1, 10)
        K = random.randint(1, 10)
        lines.append(f"{N} {K}")

        # N = random.randint(1, 10)
        # K = random.randint(1, 10)
        # lines.append(f"{N}")
        # lines.append(f"{K}")

        f.write("\n".join(lines))


def solve(proc_name):
    with open(TESTCASE_FILE, "r", encoding="utf-8") as f:
        res = subprocess.run(
            ["python3", proc_name], stdin=f, stdout=subprocess.PIPE, encoding="utf-8")
        return res.stdout


def main():
    while True:
        write_random_case()
        A = solve(MAIN_FILE)
        B = solve(GREEDY_FILE)
        if A != B:
            print("----------------------------------------")
            print("Wrong Answer")
            print("[test case]")
            print(read_random_case())
            print(f"[{MAIN_FILE}]")
            print(A, end="")
            print(f"[{GREEDY_FILE}]")
            print(B, end="")
            print("----------------------------------------")


if __name__ == "__main__":
    main()

ランダムテストのコードの詳細(共通)

  1. 入力生成コードから得たケースを random.in に書き込みます。
  2. 2つのコードに対してそれぞれ入力して答えを突き合わせます。
  3. 答えが一致すれば、入力ケースを作り直します(無限ループ)
  4. 答えが一致しなければ、入力ケースとそれぞれの答えを標準出力して、新しい入力ケース生成に戻ります。

挙動としては、一致しないケースが見つかるごとに詳細が標準出力に出てきます。 停止したければ [Ctrl] + [C] をしてください。

想定質問

それ別の記事にも紹介されてるよ!

二番煎じになってすみません。リンクを貼っておくので教えてください…

冒頭に書いたとおりです… 他にもあれば教えてください。

こうした方が便利だよ!

そうですね、ランダムテストの方法は色々あると思います。 いま僕はこの方法で満足していますが、より良い方法は人によって異なるため、 本記事の内容をベースに各自で使いやすいように改造してもらえればと思います。

改造などの案としては・・・

  • ビルドも組み込んで自動化する
  • alias を利用する
  • コンテスト用ディレクトリに一式コピーするようにする

それ oj にあるよ!

そうなんですよね、ランダムテストの仕組みは実は oj にも存在します。

online-judge-tools: ランダムテスト

こちらを使うことも十分に考えられます。

どのレベルから使ったほうがいいの?

これは難しいところですが、僕は青コーダーになってから使うようになりました。 僕は業務経験もそれなりにあるのでデバッグには少し自信があって、 青になるまでは特に困ることはありませんでしたが、 解くべき問題が複雑になっていくにつれてランダムテストの必要性を感じるようになりました。

個人的には、水色あたりから持っておけばよいのではないかと思います。 ただ、ランダムテストは「愚直コード」「入力生成コード」の2つを書き上げる必要があり、 実装スピードが低い人や不慣れな人がやると結構な時間を消費します。 そういう意味でも、水色くらいのレベルになってきてから導入するのがコスパがいいのかなと思います。

もしくは、必要性に駆られた時に導入する、の方が分かりやすいかもしれません。

ご参考

謝辞

  • 僕がランダムテストのコードを書くキッカケになったのは、TL に流れてきたのいみさんのツイートでした。 この場を借りてお礼申し上げます。のいみさん、ありがとうございます。

  • シェルスクリプトは露草さんの指摘によって頑健なものになりました。ありがとうございます。

  • Python 用のコードはそーさんがキッカケで作成しました。ありがとうございます。

*1:のいみさんのコードを一部改変したものです

*2:のいみさんのコードを一部改変して Python に移植したものです。random_test.py の中で C++ と被っていない部分は自分で書きました