この記事はAtCoder関連サービス Advent Calendar 2018 17日目の記事です． adventar.org
大変遅くなりました。@kyuridenamidaです。よろしくお願いします。
atcoder-toolsというものを開発しています。 atcoder-toolsの主要な機能を一言で言えば問題文に基づいた入力コードの自動生成機能です。
実際にはそれだけではなくサンプル入出力のダウンロード機能・サンプルテスト機能もあるのでAtCoderのコンテスト用ひな型作成ツールととらえてもらったほうが良いかもしれません。
歴史
2年前
エイプリルフールに初期バージョンをリリースしました。 しかし当時はソフトウェア開発初心者にもほどがあったのでコードはひどいしテストもないしカスタマイズも効かないし、なんなら簡単なインストール方法もありませんでした。 それでも使ってくれていた人が少しいたのが嬉しかったですね。
去年
結局自分としては現状に満足していた＆書いたコードが読めずにメンテする気がなくなってたというのが理由で半ば放置気味になっていました。 @asi1024がCIツール(Travis CI)を導入してくれたりしたけど、僕がガバガバだったのであんまり機能してませんでした。
今年
10月くらいにそろそろメンテしないとやばいなと思い始めました。かなりだらだら型アノテーションを追加したり、コード構造を変えたりしていました。
そうこうしてるうちに同僚の@blue_jamさんとかがコントリビュートしてくれて、こんなひどいクオリティのコードを読んでPR出してもらうのかなり申し訳ないなと思ったのでリファクタを終わらせようと思いました。
結局自分に発破をかけるためにアドベントカレンダーに登録したはいいものの遅刻してしまい、12/25にようやくリファクタが終わって、12/26にPyPIデビューしpip install atcoder-toolsできるようになりました。そして今アドベントカレンダーを書いています。
使い方
インストール
pip intall atcoder-tools
サンプルダウンロード・入力部分つきコードを生成する
atcoder-tools gen [contest_id]でできます。
例えばatcoder-tools gen arc001でARC 001のコンテストデータがダウンロードできます。
デフォルトの格納先ルートは{$HOME}/atcoder-workspace/になっています。そこの下に{コンテスト名}/{問題番号}/で保存します。これは--workspace引数で変更できます。
以下に実行時引数の詳細を書いておきます。
--without-login 練習時に自分のアカウントでログインする必要がない時に指定する。
--lang cpp or java。自動生成に使うコードの言語設定。
--template 入力フォーマットを推定できたときに使うテンプレートコードのパス。デフォルトは適当にリポジトリに存在する僕が書いたやつが使われます。
--replacement これは入力フォーマットを推定できなかったときに代用として生成されるコードのパス。
--parallel 問題ダウンロードの並列化。手元のmacでは動かなかった。
--save-no-session-cache クッキーをローカルに保存しないようにする
カスタムテンプレートを使う
--templateと--replacementにテンプレートを指定できます。
ジェネレータ部分のpythonコードをカスタムするとかは今のところできません。PR送ってほしいです。
テンプレート内では以下のPlaceholderが使えます。コードの例
- ${input_part} e.g. 生成された入力コードを格納するところです。 例↓
int N; cin >> N; vector<int> A(N-1+1); for(int i = 0 ; i <= N-1 ; i++) cin >> A[i]; string B; cin >> B;
${actual_arguments}型なし実引数列です。例↓
N, A, B
${formal_arguments}型つきパラメータ列です。例↓
int N, vector<int> A, string B
サンプルの一括テスト
atcoder-tools testで今いるディレクトリ内の実行ファイルとサンプル入出力に対してのテスト結果を出力できます。
引数はないです。実行ファイルが複数あった場合は警告しつつどれか一つを選んで実行します。
現状の入力フォーマット解析の仕組み
備忘録もかねて書いておきます。 基本的な方針としては、頑張って入力フォーマットを型なしの中間形式に変換した上でサンプルを流し込んで型推論をします。
パターン
解析する入力形式は次に述べる三種類の入力パターンの連接(列)として表現可能だと仮定してパターン列を推論することを目論見ます。 表現できない場合は残念ですが推論失敗です。今後のパターン追加に期待です。
単一パターン
一度しか現れないパターンです。NとかMとかです。
変数名を一つだけ持ちます。
タプル列パターン
タプル的な入力の繰り返しに対する入力パターンです。 入力の順に並んだ変数名のリストと一つのインデックス(*)を持ちます。
(*) インデックス ここでのインデックスは添え字としてありうる最小の値と最大の値を持つデータです。
たとえば、
a_1 b_1 a_2 b_2 : a_n b_n
を変数a,bに対しての入力がこの順に添え字が[1,n]の範囲で繰り返されていると表現するパターンです。
a_1 a_2 ... a_n
とか
a_1 a_2 : a_n
とかはタプル列で変数の数が1である特殊ケースとして扱っています。
二次元パターン
二次元配列に対する入力パターンです。
変数名と行と列に対する二つのインデックスを持ちます。
c(1,1) c(1,2) ... c(1, W) : c(H,1) c(H, 2) ... c(H, W)
をcが [1,H]×[1,W]の範囲で繰り返されているふうに表現するパターンです。
パターン列の探索
全探索です。でもインデックス部分には必ずそれまでに入力した変数もしくは定数しか現れないという妥当な仮定をおくと早く終わります。 とりあえず擬陽性を許す方針でありえそうなパターン列を列挙して、そのあとサンプルを流し込んで整合性を確かめる感じですね。 それでほとんど一意に定まるか解なしで終わります。
精度
入力とサンプル入出力が取得できた問題かつABC, ARC, AGCの問題に絞ってプログラムが推論に成功したと主張した判断したケースは93.8%(976/1041)でした。 一つ一つの推論結果が正しいかどうかについては手間を惜しんで精査していません。なので本当は正しくないけど正しいと判断されているケースもあって、実は93.8%は精度の上界であるという主張しかできません。とはいえ、定性的にはおおむね正しそうに見えます。
不正解なのに正解と判断されてしまう例は型に関するものが特に多くて、例えば整数っぽい見た目の文字列(ビット列とか)が与えられる問題でそれを単なる整数として解釈しているケースなどがありますが、それをなんとかするのは今後の課題です。
各問題に対するその推論結果のテスト結果が以下のURLから参照できます。
atcoder-tools/answer.txt at master · kyuridenamida/atcoder-tools · GitHub
今後やりたいこと
中間形式の仕様策定
現状コードを生成するに当たって
- (入力フォーマット, サンプル群)→中間形式
- 中間形式→コード生成
というふうに処理を分離しています。 この分離そのものはよいと思うんですが、肝心の中間形式の仕様をもう少しまともに策定しておくと他の人もそれに則ることができて便利なのかなって思ってます。区切り文字情報とか。
- 問題文から中間形式への変換を頑張る人は、何かしらの形で各コンテストサイトの問題からその中間形式に落とし込むロジックを作るのに集中すればよい。
- コード生成をしたい人は中間形式からのコード変換だけに集中すればよい。
提出機能の復活
ペナルティがモリモリ増えるけどそれはそれとして自動提出は便利なので復活させたい。
online-judge-tools へのコード自動生成機能マージ
online-judge-toolsは@kimiyukiさんが作っている問題URLを指定するとよしなにサンプルとかが入ったディレクトリを作ってくれるツールです。
きちんとメンテされているしAtCoder以外のサービスにも対応しているので、データのダウンロード部分とか自動テスト部分は正直atcoder-tools側で独立に開発する必要はないのかなって思ったりしています。
ただ、submit機能とかは積極的に廃止予定らしいのでそのへんの思想の違いを理由に機能としてはatcoder-toolsにも残り続けるかもしれない。
リポジトリを英語にする
英語でREADME.md書くの意味ねーなって思って全消ししたけど、やっぱりAtCoderは海外ユーザー増えているし海外ユーザーにも使ってもらいたいから英語にしたい。
個人的にやってみたいこと
他のコンテストサイトにおける入力コードの自動生成
機械学習とかパターンマッチングを使ってCodeforcesの入力自動生成にチャレンジしてみたいというのが今の野望です。
