Replace simple_patterns.py with more theoretical parser about template-generator HOT 1 CLOSED

記録用

競プロの問題文を解析して入出力パートを自動生成しています。特にこどふぉなどだと「自然言語解析する」or「サンプルから推測する」になって、後者の方針は最小化問題に落ちます
詳細:https://t.co/zAMaiUSDmc

— kimiyuki@うさぎ🐇 (@kimiyuki_u) September 7, 2020

仕様はあるので書くだけなら書けても、背景の数学的構造への理解が甘いと実装が汚くなって壊れがちなんだよね

— kimiyuki@うさぎ🐇 (@kimiyuki_u) September 7, 2020

proconio の input マクロみたいなのに大きさ持たせればいいのかな

n: Int m: Int
[Int; n]
[Int; m]

みたいな
でも結局頻出をまとめてるのと本質的に変わらなそうで難しい

— 熨斗袋 (@noshi91) September 7, 2020

本当に零からやると (.*) が最小ですみたいになりそう

— 熨斗袋 (@noshi91) September 7, 2020

それはそうで、マッチしてはいけない例が与えられないので言語を制限することになります。「完全一致しないとだめ」「選言がない」で考えると、たとえば `3 1 2 3` と `1 1` にマッチするのは n: Int; a: [Int; n] しかないはず

— kimiyuki@うさぎ🐇 (@kimiyuki_u) September 7, 2020

・1 トークン読んで変数を導入
・導入済みの変数 x について、x 回構文を読む
から構成される構文で導入する変数の数を最小化とかになるんでしょうか
頻出パターン列挙を本質的に超える何かがあるとして、どんな形になるか想像もつかないです

— 熨斗袋 (@noshi91) September 7, 2020

はい。いまのところ、まさにその形の最小化を考えてます
(ところでいままで私は形式言語やオートマトン方面しか考えてなかったんだけど「頻出パターン列挙」って言うとデータ圧縮ぽさありますね。文法圧縮ってのが近そう？)

— kimiyuki@うさぎ🐇 (@kimiyuki_u) September 7, 2020

from template-generator.