ランダムテストケース生成をしよう

この記事は、競プロ Advent Calendar 2021の24日目の記事です。

はじめに

みなさん、ランダムテストケース生成してますか？私はしています。

提出コードのバグがどうしてもわからない場合はかなり有効な手です。

今回の記事では私が普段やってるランダムテストケース生成の方法を紹介します。

1. 愚直解を書く

O(N³)でもO(2^N)であろうがO(N!)であってもとりあえず書いてください。

このコードがバグっているといけないのでサンプルは確認しましょう。

提出した言語と愚直解の言語が異なっていても構いません。

2. ランダムテストケース生成 & 実行

Pythonを使ってランダムテストケース生成 & 実行します。

以下では提出したコードの実行ファイルをmain.exe、愚直解のコードの実行ファイルをsimple.exeとします。

Pythonの場合は hoge.exeの部分をpy hoge.pyに置き換えてください。(他のスクリプト言語の場合も同様に実行コマンドスクリプトファイルに置き換えてください。)

ランダムテストケース生成コード

A - Welcome to AtCoderを例にとって説明します。

import random

def generate():
  with open("input.txt",mode="w")as input_file:
    a=random.randint(1,100)
    input_file.write(f"{a}\n")
    b=random.randint(1,100)
    c=random.randint(1,100)
    input_file.write(f"{b} {c}\n")
    s=[]
    length=random.randint(1,100)
    for i in range(length):
      s.append(chr(random.randint(ord("a"),ord("z"))))
    s="".join(s)
    input_file.write(f"{s}\n")
  return

愚直解で瞬時に終わる程度のランダムテストケースを生成します。

各行の改行を忘れないようにしましょう。

実行 & 比較

import os
import filecmp

def is_same():
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

普通は上のコードでいいのですが、セキュリティソフトが勝手に実行ファイルを削除してくる場合は以下のコードを使います。

import os
import filecmp

def is_same():
  if not os.path.isfile("main.exe"):
    os.system("g++ main.cpp -o main")
  if not os.path.isfile("simple.exe"):
    os.system("g++ simple.cpp -o simple")
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

ファイル全体

まとめると以下のようになります。

import random
import os
import filecmp

def generate():
  with open("input.txt",mode="w")as input_file:
    a=random.randint(1,100)
    input_file.write(f"{a}\n")
    b=random.randint(1,100)
    c=random.randint(1,100)
    input_file.write(f"{b} {c}\n")
    s=[]
    length=random.randint(1,100)
    for i in range(length):
      s.append(chr(random.randint(ord("a"),ord("z"))))
    s="".join(s)
    input_file.write(f"{s}\n")
  return

def is_same():
  if not os.path.isfile("main.exe"):
    os.system("g++ main.cpp -o main")
  if not os.path.isfile("simple.exe"):
    os.system("g++ simple.cpp -o simple")
  os.system("main.exe < input.txt > out1.txt")
  os.system("simple.exe < input.txt > out2.txt")
  if filecmp.cmp("out1.txt","out2.txt"):
    return True
  else:
    return False

def main():
  while True:
    generate()
    if not is_same():
      break

main()

ランダムテストケースでもバグが見つからないときは

コーナーケースを見逃している可能性

例えば、N=1のときなどを試してみるといいかもしれません。

そもそも誤読している可能性

一度心を落ち着かせて問題文を声に出して読んでみましょう

図を紙に書いて確認してみても良いです。

おわりに

この記事ではランダムテストケース生成について書きました。

読んで頂いた方ありがとうございました。

harurun競プロ

python勢