トップ > Julia > Julia - Aizu Online Judge の問題を Julia で解く

Julia - Aizu Online Judge の問題を Julia で解く

Julia

Aizu Online Judge (AOJ) を Julia で遊ぶための野良パッケージを作ったので使い方を紹介します。

AOJ とは？

AOJ（Aizu Online Judge：onlinejudge.u-aizu.ac.jp/home）は誰でも無料で利用できるプログラミング問題のオンライン採点システムです。

第１回 オンラインジャッジシステムを知ろう｜Tech Book Zone Manatee より

AOJ を使ってアルゴリズムとデータ構造について学ぶ本もあるので、プログラミングをしている人ならば一度は聞いたことがあると思います。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

具体的な問題を解きながら楽しくプログラミングについて学べるので利用している方も多いことでしょう。

そんな楽しい AOJ なのですが残念ながら Julia には対応しておりません。対応してくれると大変嬉しいのですが、R にも対応していないので Julia が対応されることはおそらくないでしょう。

一応テストケースはダウンロードしてこられるので、テストケースを入力しては模範解答と比較するということをひたすらすれば、どんなプログラミング言語でも遊べると言えば遊べます。誰もやらないと思いますが。

もちろんそんな単純で面倒な作業は人間がやるべきではないので、自動的に採点するためのパッケージを作成しました。

github.com

一応言っておきますと、このパッケージは AOJ 非公式のパッケージです。 問題がありましたら AOJ でなく、私にご連絡ください。

このパッケージで出来ること・出来ないこと

  • ローカル環境の Julia を使って AOJ の問題を採点することができます。
  • AOJ が Julia に対応していないので提出などは出来ず、またどの問題が解けたかなどの記録を残すことは出来ません。

元々、私が個人的に遊ぶために作ったパッケージなので過度の期待は禁物です。

環境

対応する Julia のバージョン

  • Julia 0.7
  • Julia 1.0

OS は Linux, Mac, Windows のいずれでも動くはずです。

インストール

野良パッケージなので Julia を起動し、以下のコマンドを実行してください。

using Pkg
Pkg.pkg"add https://github.com/goropikari/AizuOnlineJudge.jl"

使い方

実際にこのパッケージを使って問題を解いている様子を動画にしてみました。 雰囲気はこんな感じです。

問題を選ぶ

ここでは例として「アルゴリズムとデータ構造入門」にある ALDS1_1_B 最大公約数 を解いていきます。

プログラムを作る

ALDS1_1_B 最大公約数 は gcd を実装する問題です。*1

問題文には出力の最後に改行を入れろという指示はありませんが、私のパッケージでは改行がないと正しく評価できないので最終行には改行を入れてください。

こんな感じに実装してファイルに保存します。

# gcd.jl
x, y = parse.(Int, split(readline()))
mygcd(x,y) = y == 0 ? x : mygcd(y, mod(x,y))
println(mygcd(x,y))

サンプルでテストする

実装ができたらまずはページ記載のサンプルでテストしてみましょう。

作ったファイルを julia gcd.jl や include で取り込んで、自力でキーボードから入力例を入力するのでもよいですが、test_sample を使うと自動で全てのサンプルに対してテストできます。

test_sample の第一引数は解いている問題の ID、第二引数には作ったプログラムを入れてください。

using AizuOnlineJudge

test_sample("ALDS1_1_B", "gcd.jl")

問題の ID はページ上部に書いてあります。

f:id:goropikarikun:20181025142652p:plain

実行するとこんな感じです。 f:id:goropikarikun:20181025143332g:plain

正しい結果が得られると AC が出ます。

判定する

サンプルで問題なさそうなら judge を使って本格的に判定します。使い方は test_sample と一緒です。

judge("ALDS1_1_B", "gcd.jl")

正しい実装が出来ているとこんな感じ f:id:goropikarikun:20181025144623g:plain

間違えるとこんな感じ f:id:goropikarikun:20181025145003g:plain

その他に実行時にエラーが出ると RE、制限時間を超過すると TLE が出ます。デフォルトでは制限時間は3秒に設定しています。

メモリ制限には対応していないので ulimit 等を使って自分で制限を掛けてください。

テストケースやプログラムの出力結果は ~/.juliaAOJ に保存されています。 大した容量ではないですが消したい場合や判定が正しく動作しない場合は直接消すか、

AizuOnlineJudge.clean()

を実行してください。

制限時間を変える

制限時間を変えたい場合は第三引数に希望の制限時間を入れてください。単位は秒です。

judge("ALDS1_1_B", "gcd.jl", 5) # 制限時間を5秒に設定

注意点

解答の最終行では常に改行するようにしてください。そうしないと正しい評価が得られません。

既知の問題

仕様という名のバグ (私の技術不足に起因)

  • 浮動小数点数を含む問題では正しく評価されない
  • 解が一意に決まらない問題では正しく評価されない

このパッケージでは出力の値を比較しているのではなく、出力を保存したファイルと模範解答のファイルのハッシュ値を比較して正誤を決めているため浮動小数点数を含む問題では正しく評価できません。
解が一意に定まらない問題も同様の理由で正しく評価できません。 そのため、正しいプログラムが書けていたとしても WA となることがあります。

この種の問題では判定結果を信用しないでください。

  • 実行時にエラーが起きているのに RE でなく TLE が出る

Julia のエラー処理は意外に時間が掛かるらしく制限時間を厳しく設定していると RE でなく TLE が出ることがあります。その場合は制限時間を伸ばしてください。

AOJに起因する問題

  • AOJ が提供しているテストケースが完全でない

出力結果が長い問題だと、AOJ からダウンロードできる出力結果自体が完全でない場合があるのでこれらの問題も正しく評価することはできません。

例えば、「プログラミング入門:トピック 3 テストケースの出力」など。

https://judgedat.u-aizu.ac.jp//testcases/ITP1_3_B/1

浮動小数点数を使用しておらず、プログラムを完璧に書いたはずなのに WA が出る時は、~/.juliaAOJ にあるテストケースを直接確認してみてください。

実行時間が掛かり過ぎじゃないの？

内部的には判定するプログラムを run(`julia gcd.jl`) で実行しているために各テストケース毎に Julia の起動時間 + コンパイル時間が上乗せされ実行時間が長くなっています。

現状は Julia という言語の仕様上これらの無駄に掛かる時間は回避できない (と思う) ので我慢してください。 回避方法があれば是非ご連絡ください。

終わりに

何か不具合が有りましたら GitHub に Issue を立ててください。

また、このパッケージを作成する時に他の既存の採点システムを参考にしようと思っていたのですが、慣れない言語で結局何書いてあるのか理解できず。。。 結局勢いで実装したため変な処理や無駄な部分が含まれている可能性が多分にあります。そういった報告もしていただけると泣いて喜びます。

特に結果の判定をハッシュ値で判断するのが一番簡単そうだったのでそうしましたが、もっといい方法があればぜひ教えてください。

github.com

デバッグがてら 「プログラミング入門」 のうち浮動小数点数を使わない問題は全問解いたので、どうしても WA になってしまう場合は参考にしてください。（プログラミング入門コースだから自力で実装するべきか、はたまた言語仕様として使える関数はどんどん使っていくべきか、どちらの方が教育的なのかと自問しながら解いていたので迷走したコードになっています。）

github.com

*1:Julia では標準で gcd 使えますけどね