競プロの入力自動生成器とオブジェクト指向のはなし

33470 ワード

競技プログラミングオブジェクト指向 Python 自動化 Python テキストリンク

概要

競プロの入力テストケースをランダムに自動生成します

実装方法を紹介し、オブジェクト指向の恩恵を確認します

自動生成機能を使いたい方はもちろん、競プロから一歩踏み込んだプログラミングについても知ってみたい方、
オブジェクト指向について勉強中の方にも読んでいただける内容だと思います。
ソースコード全体はこちらにあります。

できたもの: 入力テストケースの自動生成

こんな入力マクロを用意すると→

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)

↓

文字列:

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に出力を生成してもらい、結果をスペースでつないで返す

ということをしています。
クラス名を読み取って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()))

のような形です。

乱数が必要なところは外部で定義した乱数生成器に投げています:

utils.py

import numpy as np
SEED = 0
rng = np.random.default_rng(SEED)

乱数を使う場合は都度都度関数を呼ぶのではなく、このように乱数性正器を(必要に応じて複数個)用意し、スコープによって使い分けるのが正しい作法です。
ただし今回の場合、乱数を固定する(再現性が得られるようにする)のが望ましいか、実行ごとに結果が変わるのが望ましいかは場合によるので、ユースケースによって書き直す必要もあるかもしれません。

その他のマクロも同様にひとつひとつ対応していきます。例えばグラフであればnetworkxのランダムグラフの生成や、文字列であればrstrによる正規表現パターンに合う文字列のランダム生成などの機能を使って実現しています。
いずれにしてもやるべきことは

from_str()
generate()

を実装するだけ、なので機能追加の手間は少なくなっています！

まとめ

競プロの入力テストケースをランダムに自動生成しました

実装としては概念をクラスに切り分け、共通の機能を同じ名前のメソッドで実装しました。

TODO

同じやり方で「入力を受け取るソースコードの自動生成」もできるはずです。各クラスにgenerate()に加えてgenerate_source()のようなメソッドを持たせて、処理の委譲関係は今と同様で。

Author And Source

この問題について(競プロの入力自動生成器とオブジェクト指向のはなし), 我々は、より多くの情報をここで見つけました https://qiita.com/shotoyoo/items/dc474c33f0f661628f55

著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。

Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .

yii 2権限管理の使い方~

python-操作DB