概要
- 競プロの入力テストケースをランダムに自動生成します
- 実装方法を紹介し、オブジェクト指向の恩恵を確認します
自動生成機能を使いたい方はもちろん、競プロから一歩踏み込んだプログラミングについても知ってみたい方、
オブジェクト指向について勉強中の方にも読んでいただける内容だと思います。
ソースコード全体はこちらにあります。
できたもの: 入力テストケースの自動生成
こんな入力マクロを用意すると→
Int(N,2,5)
Float(a,1,100,5) Perm(1,N+4)
Str([a-z]{3,2*N})
*N(2)
入力が出てきます→
output:
4
54.81887 3 2 4 7 1 8 5 6
yyl
4.32497 4 1 6 5 3 8 7 2
yziuqiac
42.84603 3 2 4 7 8 6 5 1
vsjajs
65.07176 7 5 8 3 4 6 1 2
rbq
他にも色々
重み付きグラフ:
Int(N,3,5) Int(M,N-1,N*(N-1)//2)
Graph1(N,M,0,1000)
↓
output:
4 5
1 2 392
1 3 328
1 4 891
2 3 264
3 4 227
文字列:
Int(N,4,6) Int(M,4,6)
Str([.#]{M})
*N(1)
↓
output:
4 5
###.#
#.#.#
#..##
.###.
などなど。
機能そのものに興味がある方は、こちらに一覧があります。
※ 今の所内部クラスを定義しただけなので、一括でたくさんテストケースを生成したい、ファイルに書き出したいなどの場合はこのクラスを使ってPythonコーディングする必要があります。
実現方法
オブジェクト指向な実装になっています。
おおまかには、
- マクロ全体の読み込みを担うクラス (LineCollection)
- マクロの1行ずつの読み込みを担うクラス (Line)
- マクロの1行の中のスペース区切り部分を担うクラス (Itemとそのサブクラス群)
に分かれています。iがi+1を管理し、必要な仕事を投げるイメージです(i=1,2)。
すべてのクラスは共通して以下のメソッドを持っています:
from_str(): 入力マクロ文字列をパースし、クラスの初期化を行います。
generate(): 自身が管理している範囲について、ランダム入力テストケースを生成します。
まとめると、以下の表のようになります:
| LineCollection | Line | Item | |
|---|---|---|---|
| from_str() | マクロ全体の読み込み | 1行の読み込み | 1単語の読み込み |
| generate() | マクロ全体に対する出力生成 | 1行に対する出力生成 | 1単語に対する出力生成 |
要点としては、
- 全体の使い方としてはLineCollection.from_str(入力マクロ)→ generate()すればよい
- 新しくマクロの種類を増やしたいときは上記3つのメソッドを持ったItemクラスのサブクラスを定義するだけで良い(LineやLineCollectionを変更する必要は無い)
といったところでしょうか。
ソースコード
具体的にソースコードで確認していきます。
LineCollection
| LineCollection | Line | Item | |
|---|---|---|---|
| from_str() | マクロ全体の読み込み | 1行の読み込み | 1単語の読み込み |
| generate() | マクロ全体に対する出力生成 | 1行に対する出力生成 | 1単語に対する出力生成 |
self.lsにマクロの各行のLineのリストを持っています。
「*N(1)」のようなマクロに対応するため少し複雑になっていますが、やっていることは
- from_str()=マクロ全体の読み込み: 各行に相当するLineの初期化を行い、self.lsにまとめる
- generate()=マクロ全体に対応する出力の生成: self.lsの各Lineに出力を生成させて、改行文字でつないで返す
だけです。
class LineCollection:
def __init__(self, ls, s=None):
"""ls: list of Line
"""
self.ls = ls
self.s = s
@classmethod
def from_str(cls, s):
lines = s.split("\n")
i = 0
ls = []
for i in range(len(lines)):
if lines[i].startswith("*"):
name, num = lines[i][1:].split("(",1)
num = int(num[:-1])
ls.append((name, num))
else:
l = Line.from_str(lines[i])
ls.append(l)
return cls(ls, s)
def generate(self):
i = 0
prv = 0
output = []
while i<len(self.ls):
while i<len(self.ls) and not isinstance(self.ls[i], tuple):
i += 1
if i<len(self.ls) and isinstance(self.ls[i], tuple):
m, num = self.ls[i]
i += 1
else:
m = 0
num = 0
for j in range(prv, i-num-1):
if isinstance(self.ls[j], tuple):
continue
output.append(self.ls[j].generate())
if num!=0:
try:
m = Item.names[m]
except KeyError:
raise ValueError("テストケース数が未定義: 上何行見るかの指定が間違っていません？")
for _ in range(m):
for j in range(i-num-1, i-1):
if isinstance(self.ls[j], tuple):
continue
output.append(self.ls[j].generate())
prv = i
return "\n".join(output)
Line
| LineCollection | Line | Item | |
|---|---|---|---|
| from_str() | マクロ全体の読み込み | 1行の読み込み | 1単語の読み込み |
| generate() | マクロ全体に対する出力生成 | 1行に対する出力生成 | 1単語に対する出力生成 |
self.lに自身が見ている行に存在するItemのリストを管理しています。
LineCollectionとおなじような感じで、
- from_str(): 1行ぶんの読み込みをスペース区切りにして、各々についてクラス名と引数を読み取ってItemを初期化し、self.lにまとめておく
- generate(): self.lの各Itemに出力を生成してもらい、結果をスペースでつないで返す <!-- * generate_source() -->
ということをしています。
クラス名を読み取ってItemを初期化するところではPythonの組み込み関数globals()からクラスオブジェクトを取得しています。
def evaluate_item(ss):
cc, tmp = ss.split("(", 1)
vv = tmp[:-1]
return globals()[cc].from_str(vv)
class Line:
def __init__(self, l, s=None):
"""
correspond to a line of input file
l: list of Item
"""
self.l = l
self.s = s
@classmethod
def from_str(cls, s):
l = []
for ss in s.split():
l.append(evaluate_item(ss))
return cls(l)
def generate(self):
return " ".join([item.generate() for item in self.l])
Item
| LineCollection | Line | Item | |
|---|---|---|---|
| from_str() | マクロ全体の読み込み | 1行の読み込み | 1単語の読み込み |
| generate() | マクロ全体に対する出力生成 | 1行に対する出力生成 | 1単語に対する出力生成 |
最後にItemですが、これは対応したいマクロごとに定義していきます。
このような場合、ひとつの基底クラスを作ってそれを継承するのが可読性・保守性・コーディング効率の面から優れていると思います。
ベースクラスとして次のようにItemクラスを用意しました:
class Item:
names = {}
def __init__(self, s=None, **keys):
self.s = s
@classmethod
def from_str(cls, s):
pass
def evaluate(self, s):
for k in Item.names.keys():
if k in s:
s = s.replace(k, str(Item.names[k]))
return eval(s)
def generate(self):
pass
def __str__(self):
if hasattr(self, "s"):
return self.s
Itemはそのままでは使えないクラスなので、それを表すおまじないを入れたほうが良いのですが今回は省略しています。
「これらのメソッドを持つ」ということを宣言しておくだけでも、他の人が機能追加する場合に分かりやすくなるなど、恩恵が大きいです。
これの下に実現したいマクロごとのクラスを作っていきます。
例えばIntであれば
class Int(Item):
def __init__(self, name, low, high, s=None, **keys):
"""
correspond to the input value between two spaces
name: str
name of variable
low/high : str
min / max (inclusive)
"""
self.name = name
self.low = low
self.high = high
self.keys = keys
Item.__init__(self, s)
@classmethod
def from_str(cls, s):
name, low, high = s.split(",")
return cls(name, low, high, s=s)
def generate(self):
low, high = self.evaluate(self.low), self.evaluate(self.high)
value = utils.rng.integers(low, high+1)
Item.names[self.name] = value
return str(value)
1...Nの順列であれば
class Perm(Item):
"""permutation of [low, low+1, ..., high-1, high]
"""
def __init__(self, low, high, s=None):
self.low = low
self.high = high
self.s = s
@classmethod
def from_str(cls, s):
low, high = s.split(",")
return cls(low, high, s=s)
def generate(self):
low, high = self.evaluate(self.low), self.evaluate(self.high)
return " ".join(map(str, (utils.rng.permutation(high-low+1) + low).tolist()))
のような形です。
乱数が必要なところは外部で定義した乱数生成器に投げています:
import numpy as np
SEED = 0
rng = np.random.default_rng(SEED)
乱数を使う場合は都度都度関数を呼ぶのではなく、このように乱数性正器を(必要に応じて複数個)用意し、スコープによって使い分けるのが正しい作法です。
ただし今回の場合、乱数を固定する(再現性が得られるようにする)のが望ましいか、実行ごとに結果が変わるのが望ましいかは場合によるので、ユースケースによって書き直す必要もあるかもしれません。
その他のマクロも同様にひとつひとつ対応していきます。例えばグラフであればnetworkxのランダムグラフの生成や、文字列であればrstrによる正規表現パターンに合う文字列のランダム生成などの機能を使って実現しています。
いずれにしてもやるべきことは
- from_str()
- generate()
を実装するだけ、なので機能追加の手間は少なくなっています！
まとめ
- 競プロの入力テストケースをランダムに自動生成しました
- 実装としては概念をクラスに切り分け、共通の機能を同じ名前のメソッドで実装しました。
TODO
- 同じやり方で「入力を受け取るソースコードの自動生成」もできるはずです。各クラスにgenerate()に加えてgenerate_source()のようなメソッドを持たせて、処理の委譲関係は今と同様で。