雪の中でハーゲンダッツを食うのは最高ですよね。 どうも、54代プロ研のHarrisonKawagoeです。
競技プログラミングって結構流行っていますね。僕も一時期Atcoderに参加していました。 しかし、自分はほとんど精進していなかった為冷えることもしばしばありました。
ワイ「レートがあんまり伸びないな…そうだ！コンテストサイトを自作したら(自分のサイトで)赤コーダーになれるじゃん！」
ということで、自分が半年前に開発したオンラインジャッジシステムについて話していこうと思います。
オンラインジャッジシステムとは
AtcoderやAOJなどのサイトで問題を解いたことがある人ならわかると思いますが、コードを提出した後、出力結果が合ってる場合はAC、違う場合はWAが出力されますよね。
このように、提出したコードが正しく動いてるかどうかを検証するシステムがオンラインジャッジシステムとなります。
AC(Accepted)が出るまで
まずは、プログラムを実行してから提出するまでの流れを考えてみましょう。 RubyやPythonなどのスクリプト型言語はそのままプログラムを実行することができますが、CやC++などのコンパイル型言語は実行する前にコードをコンパイルする必要があります。 コンパイルが通らなかった場合(CE)、コードを修正しなければなりません。 実行ファイルが作成されたら、プログラムを実行して出力結果を確認します。 出力結果があってる場合(AC)、そのままコードを提出しても構いませんが、結果がサンプルケースと一致しない場合(WA)、あるいは例外が発生してしまった場合(RE)、色々試しながら修正する必要があります。
自分が作成したジャッジシステムは、上記のAC、WA、REとCE以外にTLE(制限時間超過)を判定できるようになっています。 ジャッジシステムがプログラムを実行してから結果を検証するまでの流れをフローチャートにまとめると:
こんな感じになります。
実行環境の構築
ジャッジシステムはDjangoとMySQLで構築しました。 自分はよくシロフクロウの人と認知されているのでアプリ名はOwlJudgeにしました。
UIはかなり雑に実装しましたが大目に見てくれるとありがたいです。
まず、GCCなどプログラムを実行するにあたって必要なパッケージを導入します。
自分はUbuntuを使っていたので下記のコマンドを使いました。
sudo apt install gcc g++ python3 ruby bf python3 python3-pip openjdk-8-jdk pip3 install django psutil
ログイン機能と各画面の実装についてはOwlJudgeのGithubリポジトリに公開してあるので、ここでは割愛させていただきます。
次に、models.pyに下記のコードを記述します。
from django.db import models class SubmittedCode(models.Model):#ユーザーが提出したコード judgeid = models.IntegerField(primary_key=True) userid = models.IntegerField() questionnumber = models.IntegerField() username = models.TextField(null=True) language = models.CharField(max_length=20)#提出言語 code = models.TextField(null=True)#コード status = models.CharField(max_length=20)#ステータス casenum = models.IntegerField() ac = models.IntegerField() wa = models.IntegerField() tle = models.IntegerField() re = models.IntegerField() class Case(models.Model): id = models.IntegerField(primary_key=True) questionnumber = models.IntegerField() sinput = models.TextField(null=True)#入力 answer = models.TextField(null=True)#答え class Question(models.Model): id = models.IntegerField(primary_key=True) title = models.TextField(null=True) content = models.TextField(null=True)
当時はこんな感じで構築しましたが、今見返すとテーブルの構成はあんまり良くないですね。
models.pyを保存した後、下記のコマンドを実行するとDBにテーブルを作成することができます。
python3 manage.py makemigrations python3 manage.py migrate
これで、ユーザーが提出したコードとWriterが作成したサンプルケースをDBに保存できるようになりました。
コードのコンパイルと実行
Python3で外部のShellコマンドを実行する場合、subprocessクラスを使います。 subprocessクラスはShellコマンドの終了コードと出力結果を取得することができるので、これを利用するとプログラムをコンパイルする機能と出力結果を判定する機能を実装することができます。 以下はコードをコンパイルする時に使われるメソッドです。
lang = ["C","C++","Java","Python3","Ruby","Brainfuck"] COMPILE_INDEX = 2 C_INDEX = 1 cmp = ["gcc","g++","javac"] code = ["/main.c","/main.cpp","/Main.java","/main.py","/main.rb","/main.bf"] execfile = ["/main","/main","/Main","/main.py","/main.rb","/main.bf"] exec1 = ["./judge/","./judge/","cd judge/","python3 judge/","ruby judge/","bf judge/"] exec2 = ["/main","/main"," ; java Main","/main.py","/main.rb","/main.bf"] def subresults(request): kill = lambda process: process.kill() status = 'WJ' if request.method == 'POST': if request.user.username == "": return redirect('/login') error = '' process = '' os.makedirs("judge", exist_ok=True) folder = str(SubmittedCode.objects.all().count()) i = 0 for l in lang: if request.POST['language'] == l: os.mkdir("judge/" + folder) text_file = open("judge/" + folder+code[i], "w") text_file.write(request.POST["code"]) #コードをファイルに書き込む text_file.close() if i <= COMPILE_INDEX: #コンパイル型言語であるかどうかを判断する bashCommand = "" if i <= C_INDEX: bashCommand = cmp[i]+" judge/"+folder+code[i]+" -o judge/"+folder+execfile[i] #コンパイル命令(CとC++ の場合) else: bashCommand = cmp[i]+" judge/" + folder+code[i]#コンパイル命令(Javaの場合) logging.debug(bashCommand) process = subprocess.Popen(bashCommand.split(), stdout=subprocess.PIPE,stderr=subprocess.PIPE) output, error = process.communicate() #出力結果とエラー情報の取得 if 'error' in str(error): #コンパイルに失敗したらエラー情報がerrorに書き込まれる。 status = 'CE' dirpath = Path("judge", folder) logging.debug(dirpath) if dirpath.exists() and dirpath.is_dir(): shutil.rmtree(dirpath) #一時ファイルの削除 break i+=1 else: raise Http404 obj = SubmittedCode.objects.create(judgeid=int(folder),language=request.POST['language'],userid = request.user.id,username = request.user.username,questionnumber=int(request.POST['problemid']), code = request.POST["code"],status = status,casenum = Case.objects.filter(questionnumber = int(request.POST['problemid'])).count(), ac = 0,wa = 0,tle = 0,re = 0) if status == 'WJ': return render(request, 'subresults.html',{ 'problemnumber':request.POST['problemid'], 'status':"WJ...", 'currentuser':request.user.username, 'message':error, 'number':Case.objects.filter(questionnumber = int(request.POST['problemid'])).count(), 'range':range(Case.objects.filter(questionnumber = int(request.POST['problemid'])).count()), 'id':folder, 'initnumber':Case.objects.filter(questionnumber = int(request.POST['problemid']))[0].id, 'language':request.POST['language'] }) else: return render(request, 'subresults.html',{ 'problemnumber':request.POST['problemid'], 'status':"Compile Error!", 'currentuser': request.user.username, 'message':error.decode('UTF-8') })
コンパイル型言語であるかどうかはCOMPILE_INDEXで判断しています。 コンパイル型言語の場合、コンパイル命令はSubprocessから実行されます。 エラーが発生していなかったら実行ファイルは作成されているはずなので、次の処理を行う為にSubmittedCodeオブジェクトを作成します。
スクリプト言語の場合はそのままSubmittedCodeオブジェクトを作成する過程に入ります。
次に、プログラムを実行して出力結果を判断する部分を見てみましょう。
kill = lambda process: process.kill() status = 'WJ...' output = '' error = '' case = Case.objects.filter(questionnumber = int(request.GET.get('problemid', None)))[int(request.GET.get('casenumber', None))]#条件に対応しているCaseオブジェクトを呼び出す datetime1 = 0 datetime2 = 0 memoryusage = 0 i = 0 for l in lang: if request.GET.get('language', None) == l: bashCommand = exec1[i]+request.GET.get('submissionid', None)+exec2[i]#プログラム実行するコマンド process = psutil.Popen(bashCommand,shell=True, stdin=subprocess.PIPE, stdout=subprocess.PIPE,stderr=subprocess.PIPE) break i+=1 memoryusage = max(memoryusage, process.memory_info().rss / 1024 * 35) datetime1 = datetime.datetime.now().timestamp() * 1000#開始時間 my_timer = Timer(2.1, process.kill)#制限時間の設定 try: my_timer.start() flag = False while True: memoryusage = max(memoryusage, process.memory_info().rss / 1024 * 35) logging.debug(case.sinput) if flag == False: output, error = process.communicate(case.sinput.encode()) flag = True retCode = process.poll() if retCode is not None: break finally: my_timer.cancel() datetime2 = datetime.datetime.now().timestamp() * 1000#終了時間 data = SubmittedCode.objects.filter(judgeid = request.GET.get('submissionid', None))[0]
先ほど作成した実行ファイルを利用してプログラムの計測を行います。 Timerで制限時間と制限時間を超えた後の動作を定義してあるので、実行中に制限時間を超えた場合、プログラムは強制終了されます。 Subprocessを起動する前と終了時の現在時刻を取得することで、プログラムの実行時間を算出することができます。
TLE(Time Limit Exceed)の判定
OwlJudgeの実行制限時間を2.1sに設定してあります。
制限時間を超えた場合、process.kill() を呼び出すことでプログラムを強制終了することができますが、プログラムは終了命令を受け取ってからすぐ止まれる訳ではないので、実際に得られる実行時間は2.1sより長くなります。
if datetime2-datetime1>2.1*1000: status = 'TLE' data.tle+=1 data.status = 'TLE'
RE(Runtime Error)の判定
プログラムが終了した時は、stdoutとstderr以外に、終了コードが戻り値として返されます。
通常だと0が終了コードとして出力されますが、例外が発生した場合は0以外の数値が返ってきます。
Subprocessクラスは外部プロセスの終了コードをreturncode変数に保存してくれるので、それを利用して判断します。
elif process.returncode != 0: status = 'RE' logging.debug(error) data.re += 1 data.status = 'RE'
AC(Accepted)とWA(Wrong Answer)の判定
これは単純にoutputに保存された出力結果とサンプルケースの答えを照合するだけですね。
elif output.decode('UTF-8') == case.answer+"\n": status = 'AC' data.ac += 1 else: status = 'WA' data.wa += 1 data.status = 'WA'
非同期通信を利用してユーザー画面に結果を反映する
コードを提出してから結果が出るまでは結構時間がかかりますよね。
しかし、HTMLを反映する為にページを頻繁にリロードするとユーザー体験がかなり悪くなってしまうので、非同期通信でHTML要素を更新できるようにしました。
まず、View側の戻り値をJSONにします。
if data.ac == data.casenum: params = {"result":status,"timeusage":str(datetime2-datetime1),"memoryusage":str(memoryusage),"ac":"true"} else: params = {"result":status,"timeusage":str(datetime2-datetime1),"memoryusage":str(memoryusage),"ac":"false"} json_str = json.dumps(params, ensure_ascii=False, indent=2) return HttpResponse(json_str)
次に、Ajax通信を使ってHTML要素を更新できるようにします。
$(document).ready(function() { judge(0,$('.caseclass').length); }); function judge(n,max){ $.ajax({ 'type': 'get', 'url': '/judgecode', 'data': { 'initnumber':$("#initnumber").text(), 'casenumber': n, 'submissionid':$("#submissionid").text(), 'problemid':$("#problemid").text(), 'language':$("#language").text() }, 'success': function(data){ const obj = JSON.parse(data); $('#casestatus'+(n+1)).text(obj.result); $('#timeusage'+(n+1)).text(obj.timeusage+'ms'); $('#memoryusage'+(n+1)).text(obj.memoryusage+'KB'); if(obj.result=='AC'){ $('#casestatus'+(n+1)).css('color','green'); if(obj.ac == "true"){ $('#finalstatus').text('Status: AC'); $('#finalstatus').css('color','green'); } }else{ $('#casestatus'+(n+1)).css('color','red'); if($('#finalstatus').text()=='Status:WJ...'&&obj.result=='TLE'){ $('#finalstatus').text('Status:TLE'); $('#finalstatus').css('color','red'); }else if(obj.result!='AC'){ $('#finalstatus').text('Status:'+obj.result); $('#finalstatus').css('color','red'); } } if(n+1<max){ judge(n+1,max); } } }); }
リクエストを一回で全部送ったらサーバーに結構重い負担をかけてしまうので、Ajax通信は一つずつ行うようにしました。
さいごに
Djangoを勉強し始めてからジャッジ機能が完成するまで一週間ぐらいかかりました。 こういうシステムを作るにはフレームワークを使ったほうが早いですね。 RailsのノリでDjangoの勉強をしたらすぐ開発に取り組むことができましたが、テーブルの構成やメモリ使用量など色々改善しなければならない点がまだまだ多いです。
いつか、コンテスト機能とレートを実装して赤コーダーになってみたいです。
ソースコードはGithub上に公開されているので、興味ある人はそちらを見ていただけれると幸いです。
明日は55代T_SUM_Uくんの記事ですね。お楽しみに！
