Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 63 ยท Real-World Projects

Project: A Local Contest Judge

Build a small online-judge clone: run solutions on sample tests, compare outputs with a checker, count work with a line budget, and report AC, WA, PE, RE and TLE verdicts.

When you submit to Codeforces or AtCoder, a program called the judge does four things: it runs your code on hidden inputs, stops it if it takes too long or crashes, compares its output with the correct answer, and prints a verdict such as "Accepted" or "Wrong answer on test 3". In this project you build a miniature judge in Python. You will use it to test your own solutions before submitting, and building it makes the verdicts from verdicts and debugging feel concrete instead of mysterious.

A real judge starts a separate process for every submission and measures wall-clock time and memory. The browser cannot start processes, so this version runs the solution inside the page and replaces the clock by a deterministic line budget: it counts executed lines of the solution and stops it when the budget is spent. That is honest, repeatable (the same code always gets the same verdict), and good enough to separate an O(n) solution from an O(n^3) one. Along the way you reuse the habits of templates and habits and the checker idea from stress testing.

flowchart LR
  S["Solution source"] --> R["Runner:<br/>fake stdin, captured stdout,<br/>line budget"]
  T["Test input"] --> R
  R --> V{"Status"}
  V -->|"budget exceeded"| TLE["TLE"]
  V -->|"exception"| RE["RE"]
  V -->|"finished"| C["Compare with<br/>expected output"]
  C --> AC["AC / PE / WA"]

Every test ends in exactly one verdict.

Design

The judge is three small functions plus a report.

  1. run_solution(code, input_text, line_limit) runs the program text with the given input. It returns a status (OK, TLE, or RE:<ErrorName>), the captured output, and how many lines were executed.
  2. verdict(expected, got) compares outputs. We use the three classic outcomes: AC when the text matches (ignoring trailing spaces and blank lines at the end), PE (presentation error) when the tokens match but the spacing does not, and WA otherwise.
  3. judge(code, tests) runs every test, stops at the first failure like most judges, and returns a summary.

Two ideas deserve a closer look. To feed input, the runner passes a replacement input() function into the program's globals and also puts a StringIO into sys.stdin, so both input() and sys.stdin.read() style programs work. To stop an endless or slow loop, sys.settrace installs a hook that counts every line event in code compiled with the file name <solution>. When the count passes the budget, the hook raises a TimeLimit exception. It derives from BaseException on purpose: a solution containing except Exception: cannot swallow it.

A line budget measures work, not seconds. It does not know about slow built-ins: sum(range(10**8)) is a single line. A real judge also measures real time, and the estimating habits from estimating time and memory still apply.

Step 1: run one solution

Python The runner: input, output, errors and a line budget

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The four calls show the four main outcomes: a normal run (OK), a runtime error (RE:ZeroDivisionError), an endless loop stopped by the budget (TLE), and a program that reads with sys.stdin. Notice how little code the whole sandbox is.

Step 2: compare outputs

Trailing whitespace is almost never meaningful, so judges ignore it. Whitespace inside the answer is a different matter: strict judges say "Presentation error" or "Wrong answer", lenient ones compare token by token. Our verdict tells the two apart so you can see which problem you have.

Python
def normalize(text):
    return "\n".join(line.rstrip() for line in text.rstrip().split("\n"))

def verdict(expected, got):
    if normalize(got) == normalize(expected):
        return "AC"
    if got.split() == expected.split():
        return "PE"
    return "WA"

For problems with more than one valid answer, exact comparison is the wrong tool. Replace verdict with a checker that receives the input and the output and decides whether the output is valid, exactly like the checker in stress testing. The judge below accepts an optional checker for that reason.

Step 3: the judge and its report

Python Judge five submissions on the same problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each verdict teaches something. The correct solution reaches AC and shows how many lines it needed at most. The zero bug version fails the all-negative test (test 2), exactly the bug that stress testing found earlier. The cubic version passes the three small tests and then hits TLE on test 4: it is correct but too slow, the same story as a hidden large test on a real judge. The crash reports RE:IndexError on test 1, and the spacing variant gets PE because its tokens match while its spacing does not.

Order your tests like a judge does: samples first, then edge cases (n = 1, all negative, duplicates), then one big test for speed. Failing at the earliest test gives you the smallest case to debug, as discussed in edge cases and pitfalls.

Step 4: a checker for multiple valid answers

Suppose a problem asks for any two positions i < j (1-based) whose values add up to a target. Several pairs may be correct, so the expected output cannot be compared by text. The checker reads the input and the output, then tests the property.

Python A checker for 'print any valid pair'

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Test 2 has two correct answers: positions 1 2 (3 + 3) and positions 3 4 (1 + 5). The checker accepts both and rejects 1 4 (3 + 5 = 8) and 4 5 (5 + 2 = 7). A text comparison could never express that. In the full judge, pass checker=two_sum_checker and the loop calls it in place of verdict.

Ideas to extend it

  • Timing. Wrap exec with time.perf_counter() and report milliseconds beside the line count. Remember that timing varies between runs and machines, so keep the line budget for tests that must be repeatable.
  • Memory. Real judges limit memory. In this sandbox you could compare len(str(...)) of big structures, but the honest answer is that the browser gives no process-level numbers.
  • Test files. Store tests as a list of (input, expected) pairs per problem and run all your saved solutions after changing a helper, as a regression suite.
  • Stress mode. Plug in the generator and brute force from stress testing: generate input, run the fast solution through run_solution, and compare with the brute force's answer.
  • Scoring. Give partial credit by subtask, like the IOI, by counting passed tests per group.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the TimeLimit exception derive from BaseException?

    Most contest solutions never catch BaseException. Deriving from it lets the judge stop a program even if the program has a broad except Exception handler.
  2. 2. A solution prints the right numbers but separates them with two spaces instead of one. What does our verdict function return?

    The token lists are equal but the text is not, so it is a presentation error. Many real judges would still accept it, which is why you should read each problem's output rules.
  3. 3. Why use a line budget rather than the clock in this project?

    Wall-clock time varies between runs and machines. Counting executed lines gives a repeatable measure of work, good enough to tell O(n) from O(n^3).
  4. 4. When must you use a checker instead of comparing text?

    A checker validates the property of the answer (such as 'the two values add up to the target'), so any correct output is accepted.
  5. 5. What is a known blind spot of the line budget?

    The tracer counts Python lines, not machine time. A line such as sum(range(10**8)) is one line but takes a long time, so real judges also measure time.

Summary

  • A judge runs a solution on tests, stops runaways, compares output and reports one verdict per submission.
  • The runner swaps input() and sys.stdin for fake input, captures print output and counts executed lines with sys.settrace.
  • Verdicts: AC for a match, PE when only the spacing differs, WA otherwise, RE for exceptions and TLE when the budget runs out.
  • Judges stop at the first failing test, so put samples and edge cases before large tests.
  • Use a checker when many outputs are valid; combine the judge with the stress-test loop for strong self-testing.

Next: Project: A Stress-Testing Framework