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

## 概要

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

<!-- * ついでに入力を受け取るための(Python)ソースコードも自動生成します -->

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

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


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

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

```python
Int(N,2,5)
Float(a,1,100,5) Perm(1,N+4)
Str([a-z]{3,2*N})
*N(2)
```

入力が出てきます→ 

```python
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
```

他にも色々

重み付きグラフ: 

```python
Int(N,3,5) Int(M,N-1,N*(N-1)//2)
Graph1(N,M,0,1000)
```

↓

```python
output:
4 5
1 2 392
1 3 328
1 4 891
2 3 264
3 4 227
```

文字列:  

```python
Int(N,4,6) Int(M,4,6)
Str([.#]{M})
*N(1)
```

↓

```python
output:
4 5
###.#
#.#.#
#..##
.###.
```

などなど。

機能そのものに興味がある方は、[こちら][1]に一覧があります。

<!-- ## できたもの: 入力を受け取るソースコードの自動生成

入力を吐かせる代わりにPythonのinput()関数を用いて入力を受け取るソースコードを生成することもできます: 

```

``` -->

※ 今の所内部クラスを定義しただけなので、一括でたくさんテストケースを生成したい、ファイルに書き出したいなどの場合はこのクラスを使ってPythonコーディングする必要があります。

## 実現方法

オブジェクト指向な実装になっています。  
おおまかには、

1. マクロ全体の読み込みを担うクラス (LineCollection)
1. マクロの1行ずつの読み込みを担うクラス (Line)
1. マクロの1行の中のスペース区切り部分を担うクラス (Itemとそのサブクラス群)

に分かれています。iがi+1を管理し、必要な仕事を投げるイメージです(i=1,2)。  
すべてのクラスは共通して以下のメソッドを持っています: 

1. from_str(): 入力マクロ文字列をパースし、クラスの初期化を行います。

1. generate(): 自身が管理している範囲について、ランダム入力テストケースを生成します。

まとめると、以下の表のようになります: 

||LineCollection|Line|Item|
|---|---|---|---|
|from_str()|マクロ全体の読み込み|1行の読み込み|1単語の読み込み|
|generate()|マクロ全体に対する出力生成|1行に対する出力生成|1単語に対する出力生成|

<!-- |generate()/generate_source()|マクロ全体に対する出力生成|1行に対する出力生成|1単語に対する出力生成| -->


要点としては、

* 全体の使い方としてはLineCollection.from_str(入力マクロ)→ generate()すればよい

<!-- * 全体の使い方としてはLineCollection.from_str(入力マクロ)→ generate()/generate_source()すればよい -->

* 新しくマクロの種類を増やしたいときは上記3つのメソッドを持ったItemクラスのサブクラスを定義するだけで良い(LineやLineCollectionを変更する必要は無い)

といったところでしょうか。  

## ソースコード

具体的にソースコードで確認していきます。

### LineCollection

||<font color=green> LineCollection|Line|Item|
|---|---|---|---|
|from_str()|<font color=green>マクロ全体の読み込み</font>|1行の読み込み|1単語の読み込み|
|generate()|<font color=green> マクロ全体に対する出力生成|1行に対する出力生成|1単語に対する出力生成|

<!-- |generate()/generate_source()|<font color=green> マクロ全体に対する出力生成|1行に対する出力生成|1単語に対する出力生成| -->


self.lsにマクロの各行のLineのリストを持っています。
「*N(1)」のようなマクロに対応するため少し複雑になっていますが、やっていることは

* from_str()=マクロ全体の読み込み: 各行に相当するLineの初期化を行い、self.lsにまとめる
* generate()=マクロ全体に対応する出力の生成: self.lsの各Lineに出力を生成させて、改行文字でつないで返す

だけです。

```python
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|<font color=green> Line|Item|
|---|---|---|---|
|from_str()|マクロ全体の読み込み|<font color=green> 1行の読み込み|1単語の読み込み|
|generate()|マクロ全体に対する出力生成|<font color=green> 1行に対する出力生成|1単語に対する出力生成|

<!-- |generate()/generate_source()|マクロ全体に対する出力生成|<font color=green> 1行に対する出力生成|1単語に対する出力生成| -->


self.lに自身が見ている行に存在するItemのリストを管理しています。
LineCollectionとおなじような感じで、

* from_str(): 1行ぶんの読み込みをスペース区切りにして、各々についてクラス名と引数を読み取ってItemを初期化し、self.lにまとめておく
* generate(): self.lの各Itemに出力を生成してもらい、結果をスペースでつないで返す
<!-- * generate_source() -->

ということをしています。
クラス名を読み取ってItemを初期化するところではPythonの組み込み関数globals()からクラスオブジェクトを取得しています。

```python
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|<font color=green> Item|
|---|---|---|---|
|from_str()|マクロ全体の読み込み|1行の読み込み|<font color=green> 1単語の読み込み|
|generate()|マクロ全体に対する出力生成|1行に対する出力生成|<font color=green> 1単語に対する出力生成|

<!-- |generate()/generate_source()|マクロ全体に対する出力生成|1行に対する出力生成|<font color=green> 1単語に対する出力生成| -->

最後にItemですが、これは対応したいマクロごとに定義していきます。  
このような場合、ひとつの基底クラスを作ってそれを継承するのが可読性・保守性・コーディング効率の面から優れていると思います。  
ベースクラスとして次のようにItemクラスを用意しました: 

```python
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であれば

```python
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の順列であれば

```python
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()))
```

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

```python:utils.py
import numpy as np
SEED = 0
rng = np.random.default_rng(SEED)
```

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

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

* from_str()
* generate()

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


## まとめ

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

<!-- * ついでに入力を受け取るための(Python)ソースコードも自動生成します -->

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


## TODO

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


[1]:https://github.com/shotoyoo/competitive-programming-input-generator