入出力解析

[kmyk]

この issue の主目的: 解析器の設計や解析結果のフォーマットについての正解を探す

設計方針について

入出力フォーマット解析について。
まず <pre>N a_1 ... a_N</pre> みたいなやつが与えられていることを仮定する場合 (主に AtCoder) は、基本的にコンパイラに寄せていくのがよいと考えています。

1. HTML 解析 (HTML parser + XPath/CSS selectorss)
2. 字句解析 (lex)
3. 構文解析 (yacc? PEG?)
4. 意味解析 (ad-hoc)
5. コード生成 (template engine (mako?) + ad-hoc)

(2.) と (3.) を lex と yacc でやることなどの利点は、処理内容をコードに埋め込むのでなく、BNF などの形で明確に定義できることです。この戦略は結果の解釈性が高く保守性に優れるのでうれしい。ただし失敗時のフォールバックとして完全 ad-hoc 解析器を用意する可能性はある。
(4.) の意味解析はつまり変数の型の決定をする。別枠で持ってきたサンプルと突合するなど。
(5.) はできるだけ計算能力の高い template engine を採用するのが望ましい。本体にプルリクを出さなくても好きな言語に対応できるようにしたいため。

<pre>N a_1 ... a_N</pre> みたいなやつが与えられていることを仮定しない場合 (主に Codeforces + AtCoder の出力フォーマット) は難しい。選択肢はいくつか。

1. 自然言語解析 (ad-hoc パターンマッチごり押し無理矢理)
2. サンプルから入力フォーマットを復元
3. ユーザに入力フォーマットを入力してもらう (Rust や Python で前例あり 例)

その他の部分 (制約、グラフ判定、MOD、YES/NO、リアクティブ判定) は自然言語解析するしかなさそう。

解析結果のフォーマットについて

解析結果として得られる情報は以下になります:

• 入力
  • どのような変数が存在するか
  • どのような定数 (MOD) が存在するか
  • 変数はどのような順で入力されるか
  • 変数の制約 (10^9 以下、0 以上 MOD 未満) や意味 (グラフである等) はどのようになっているか
• 出力
  • どのような変数が存在するか
  • どのような定数 (YES/NO) が存在するか
  • 変数はどのような順で出力すればよいか
• その他
  • 時間制限
  • メモリ制限
  • 許容誤差
  • リアクティブかどうか

議論が必要なのは「どのような変数が存在するか」「変数はどのような順で入力/出力されるか」部分の中間形式でしょう。
論点はいくつか。

1. 「どのような変数が存在するか」の情報と「変数はどのような順で入力/出力されるか」の情報を分けるか分けないか
2. 「変数はどのような順で入力/出力されるか」の情報をどう表現するか
   • パターンマッチにするか (TwoDimensionalPattern("a", "h", "w") みたいなのを並べる)
   • 構造的にする (REP(y, "h", REP(x, "w", input("a[y][x]"))) のような感じに)
3. 変数についてどれくらい解釈を済ませるか (たとえば a_1 a_3 ... a_{2n-1} という指定がされていたときどうするか)
   • a_0 a_1 ... a_{n-1} に正規化しない
   • a_0 a_1 ... a_{n-1} に正規化する (+ 元の情報をどこかに残す / 残さない)
4. 改行や空白の情報を保つか
   • 改行は保たれていてほしい。いくつかの言語 (主に Python) では、入力中の改行の位置がかなり重要になるため
   • 空白は暗黙に挿入されるとしてよさそう

現状は「変数の宣言の情報と入力順の情報は分離」「入力は構造的に」「できるだけ正規化する」「改行は保ち、空白は忘れる」がよいかなと思っています。具体的には JSON で以下のようなものを考えています。

{
    "input": {
        "vars": [
            { "name": "n", "type": "int", "raw": ["n"] },
            { "name": "a", "type": "int", "dimension": ["n"], "raw": ["a_1", "a_3", "...", "a_{2n-1}"] },
        ],
        "format": [
            { "type": "input", "dest": ["n"] },
            { "type": "newline" },
            { "type": "loop", "variable": "i", "body": [
                { "type": "input", "dest": ["a", "i"] },
            ]},
            { "type": "newline" },
        ],
    },
    ...  // 同様
}

他にも微妙なとこあるけどひとまずは置いておく。

コマンドラインインターフェースの設計について

入出力解析+コード生成はそれ単体で完結したひとまとまりの機能なので、独立したコマンドを与えておくべきだろう。
これはできるだけ設定ファイルに依存せず、template file ひとつで完結するようにするのがよさそう。
理由はふたつです。

1. template はライブラリの一部なので GitHub とかに公開されてほしい。たぶんされます。しかしこのとき設定ファイルがないと動かないようでは、公開されても使えないので意味がない。
2. どうせ結局外部からコマンドを直で叩かれる (あまり推奨したくないけど) のは見えていて、このとき設定ファイルに依存してるとその外部コマンドの可搬性が無になる。

たぶん具体的には以下のようになります。

$ oj-template [-f path/to/template.file] URL > output.file

---

@kyuridenamida 設計方針とフォーマットとそれぞれ意見ください
私も一度は PoC レベルのものは書いたのでやばい見落としはないはずだけど、実際に保守をした経験がないと分からないような落とし穴はあるはずなので

[kmyk]

online-judge-tools/oj#687

[conao3]

こんにちは。急な発言、失礼します。
現在、入力解析に失敗した場合に3文字のランダムな名前が与えられるようですが、このように生成された文字列はタイプしずらいです。
変数の名前を制御する方法はありますでしょうか?

$ oj-template https://codeforces.com/contest/1349/problem/A
INFO:onlinejudge._implementation.logging:[x] load cookie from: /home/conao/.local/share/online-judge-tools/cookie.jar
INFO:onlinejudge._implementation.logging:[x] problem recognized: CodeforcesProblem.from_url('https://codeforces.com/contest/1349/problem/A'): https://codeforces.com/contest/1349/problem/A
INFO:onlinejudge._implementation.logging:[x] GET: https://codeforces.com/contest/1349/problem/A
INFO:onlinejudge._implementation.logging:[x] 200 OK
INFO:onlinejudge._implementation.logging:[x] save cookie to: /home/conao/.local/share/online-judge-tools/cookie.jar
ERROR:onlinejudge_template.analyzer.combined:input analyzer failed: 
ERROR:onlinejudge_template.analyzer.combined:output analyzer failed: 
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;


int64_t solve(int vch, const vector<int64_t> & txg) {
    // TODO: edit here
}

// generated by online-judge-template-generator v4.1.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    constexpr char endl = '\n';
    int vch;
    cin >> vch;
    vector<int64_t> txg(vch);
    REP (i, vch) {
        cin >> txg[i];
    }
    auto ans = solve(vch, txg);
    cout << ans << endl;
    return 0;
}

[kmyk]

現在、入力解析に失敗した場合に3文字のランダムな名前が与えられるようですが、このように生成された文字列はタイプしずらいです。
変数の名前を制御する方法はありますでしょうか?

いまのところ制御する方法はありません。

単にまじめな実装が後回しになっているだけなので、誰かが実装してくれれば解決します。もしよければプルリクエストをください。
次の (1.) のみあるいは (1.), (2.) の両方をやる必要があります。

1. 入力の変数の名前のランダム化をやめる
   • 入力部分がランダムでなくても出力部分がランダムなら変数名は衝突しない
2. 出力の変数の名前を適切に決定する
   • 入力部分で使われた名前の集合を渡し、被りがあれば適切に修正する

template-generator/onlinejudge_template/analyzer/simple_patterns.py

Lines 290 to 306 in acd1b45

	def randomize_variables(node: FormatNode) -> FormatNode:
	return _randomize_variables_dfs(node, mapping={})
	def guess_format_with_pattern_matching(*, instances: List[bytes]) -> Optional[FormatNode]:
	found: List[FormatNode] = []
	for pattern, variables in list_all_patterns():
	try:
	for data in instances:
	match_format(pattern, data.decode(), variables=variables)
	found.append(pattern)
	except FormatMatchError:
	pass
	if len(found) == 1:
	return randomize_variables(found[0])
	else:
	return None

なぜ現在こうなっているか

フォーマット情報が直接には得られない場合は、サンプルケースからフォーマット情報を復元しています。復元のアルゴリズムはいくつか考えられます (現在のもの: simple_patterns.py) が、何を選択したとしても変数名の復元は原理的に不可能です。
このとき、入力のフォーマット情報と出力のフォーマット情報は互いに独立に復元されるので、変数名にありがちなもの (n とか a とか) を使うと、入力と出力で変数名の衝突が発生します。
これを最も簡単に (確率的に) 回避する方法として、変数名がランダマイズされています。

[kmyk]

scope が曖昧な issue なので混乱を防ぐため閉じておく