An Online Programming Judge System

This page chronicles the design of an online programming judge system. The system consists of a web interface that allows user to view problems, submit solution programs, and view reports on how the programs performed. This document also includes a specification of the grading process and how to specify programming problems.

Candidate Tools

• Ruby as glue.
• Ruby on Rails for the web interface.

Programming Problem Specification

A programming problem is specified a collection of files contained inside a directory. The structure of the director is as follow.

<problem_id>/
    public_html/                --- All the files that the user can see and download via the Internet.
        index.html              --- The problem statement.
    test_cases/                 --- Contains all test data.
        all_test.cfg            --- A configuration file for all the test data.
        <test_number>/          --- Contain files related to a particular test data.
            test.cfg            --- A configuration file specific to this test data.
            <other files #1>
            <other files #2>
                 .
                 .
                 .
    script/
        compile                 --- A shell or ruby script that compiles a source code.
        run                     --- A script that runs and grade the programming solution.
        grade                   --- A script that collects information from various runs and tally the points.

The Scripts

Overall process

The script judge is the main runner here. It works by:

• Calls compile script
• Reads test_cases/all_tests.cfg
• For each test case:
  • Calls run script, which
    • Executes the compiled code (using box)
    • Checks the output, usually by calling the check script.
• After all test cases are run and checked (by the check script called by the run script), it calls the grade script.

Running the Scripts

It is guaranteed that when the above 4 scripts are being run, the environment variable PROBLEM_HOME will be set to the problem's directory.

Compile Script

The compile script receives one input: the language that the solution is written in. So, it can be invoked as follows:

$PROBLEM_HOME/script/compile <language> [<input-file>] [<output-file>] [<compile-result>]

For examples

$PROBLEM_HOME/script/compile c
$PROBLEM_HOME/script/compile c++ problem.cpp 
$PROBLEM_HOME/script/compile pascal abcdef.cpp abcdef 
$PROBLEM_HOME/script/compile haskell Test.hs Test report.txt

Before the script runs, the current directory will have the file <input-file>, the source submitted by the user. If <input-file> is not specified, it is assumed to be "source".

After the compile script finishes running, it must create the file <compile-result> in the current directory. The file is empty if the compilation is successful, and contains the compiler's error message otherwise. If compile_result is not specified, it is assumed to be "compiler_message".

If the compilation is successful, the result of the compilation should be contained in the file <output-file>, which, again, should reside the current directory. If <output-file> is not specified, it is assumed to be "a.out".

Run Script

The run script receives two inputs: the language the solution was written in and the test case number. It can be invoked as follows:

$PROBLEM_HOME/script/run <language> <test case number> [<program-name>]

For examples,

$PROBLEM_HOME/script/run c++ 1
$PROBLEM_HOME/script/run pascal 10 problem.exe

Before the script runs, the current directory will contain the file <program-name> that was created by the compile script. If <program-name> is not specified, it is assumed to be "a.out".

After the run script finishes running, it should leave two files in the current directory.

• result: The file must have the following format.

<the status of the testing, such as "Correct" or "Incorrect">
<the point gained through this test data>
<the time used by the solution program in milliseconds, as outputted by /usr/bin/time under format %Er%Uu%Ss>

For examples,

Correct
10
0:00.00r0.00u0.00s

or

Time limit exceeded
0
0:05.00r4.00u0.50s

or

Exited with error status 10.
0
0:00.00r0.00u0.00s

• comment: Any diagnostic messages the script wishes to output. Useful for comparing differences between the correct output and the submitted program's output.

Check Script

The check script is usually called by the run script. If the run script checks the output itself, the check script is not needed.

It receives three inputs: (1) the language the user's program was written in, (2) the test case number, and (3) the output file the user program produced. (Note that the output file can be just a dump of the program's output to the standard output.) The check script can be invoked as follows:

$PROBLEM_HOME/script/check <language> <test-number> [<output-file>]

<output-file> is optional. If it is not specified, then it is assumed to be output.txt. The followings are some examples of valid invocations of the check script.

$PROBLEM_HOME/script/check c 1
$PROBLEM_HOME/script/check c++ 2 output-2.txt
$PROBLEM_HOME/script/check pascal 2 problem.out

Before the check script is run, the current directory must contain the file <output-file> or the file output.txt if the former is not specified.

After the check script finishes running, it will write the file check.result to the current directory. The file has the following format:

• The first line contains a message from the check script. Most of the time, the message is simply Correct, Incorrect, or Time limit exceeded.
• The second line contains the score the program gets.

For examples,

Correct
10

or

Incorrect
0

Grade Script

The grade script receives no input. It can be invoked as follows:

$PROBLEM_HOME/script/grade

Before the script runs, the current directory has the following structure:

<pwd>/
    1/
        result          
        comment
    2/
        result
        comment
    3/
        result
        comment
        .
        .
        .

The result and comment files are those produced by the run script for the corresponding test case.

After the script runs, it should leave the following files in the current directory.

• result: Must have the following format.

<the total points earned by the solution program for the problem>

• comment: Any message the grade script wants to output. Useful for messages like "You suck!" or "Kanat would have done it 10 times faster than you did!". Currently the default grade script summarizes all the comments from the check script, by concatenating all shorten messages under this mapping: Correct -> "P", Incorrect -> "-", Time out -> "T", and x for any other error messages. The check script can explicitly specify the message for each test case by printing Comment:your-comment on the first line.
• For each test run, the grade script should produce two files

• result-#, where # is the number of the run: Must have the following format:

<the points earned by the program for this test run>

• comment-#. where # is the number of the run: Any message the grade script wants to output. Useful for messages like "Can't finish this test run? What a n00b."

For example, if a problem has 3 test cases and 2 test runs, the directory structure after may look like the following:

<pwd>/
    result
    result-1
    result-2
    comment
    comment-1
    comment-2
    1/
        result          
        comment
    2/
        result
        comment
    3/
        result
        comment

Test Data Configuration Files

all_tests.cfg

The file should look something like this:

 problem do
   num_tests 12
   full_score 120
   time_limit 1 # in seconds
   mem_limit 1 # in megabytes

   run 1 do
     tests 1, 2, 3, 4
     scores 10, 10, 5, 15
     time_limit 1, 1, 2, 1               # This line is optional.
     mem_limit 1, 2, 1, 32               # This line is also optional.
   end

   run 2 do
     tests 5, 6, 7, 8, 9, 10
     score_each 10
     time_limit_each 1                   # This line is optional.
     mem_limit_each 2                    # This line is also optional.
   end

   run 3 do     
     tests 11, 12
     score_each 10
   end

   test 10 do
     score 10
     time_limit 1
     mem_limit 32
   end
 end

test.cfg

The file may or may not exist. The setting in the file overrides the setting in all_test.cfg. The file should look something like this:

score 10
time_limit 1
mem_limit 2

Database Structure

users

• login (string)
• full_name (string)
• hashed_password (string)
• salt (string)
• alias (string)

problems

• name (string)
• full_score (integer)
• date_added (datetime)
• available (boolean)

test_runs

• problem_id
• test_run_num

test_cases

• problem_id
• test_case_num

test_run_test_cases

• test_run_id
• test_case_id

languages

• name (string)
• pretty_name (string)

submissions

• user_id (integer)
• problem_id (integer)
• language_id (integer)
• source (text)
• binary (blob)
• submitted_at (datetime)
• compiled_at (datetime)
• compiler_message (text)
• graded_at (datetime)
• points (integer)
• grader_comment (text)

test_case_results

• submission_id (integer)
• test_run_test_case_id (integer)
• status (string)
• points (integer)
• time_elapsed (integer)
• graded_at (datetime)
• comment (text)

test_run_results

• submission_id (integer)
• test_run_id (integer)
• points (integer)
• comment (text)