1

I would like to create a code-competition in Java. The basic plan is:

  • Each competitor submits a class that implements the Function interface.
  • I apply the function of each submitted class on a set of pre-made inputs.
  • The grade of each submission is its number of correct outputs.

Now, I want to add a timeout: each class is allowed to run for at most 1 second on each input. If a class runs for more than one second, it should be stopped and graded 0 on that input.

My initial idea was to run each test in a separate thread, and stop the thread after a second. However, to stop a thread in Java, it is required to change its code. Here, the code is submitted by other people and I do not want to read all the submissions to verify that they allow interruption.

How can I implement such a competition?

Erel Segal-Halevi
  • 33,955
  • 36
  • 114
  • 183

3 Answers3

2

Threads are not guaranteed to share resources fairly. Therefore, wall clock time in a "online judge" should be suspect, especially with the upper limit set in the second or minute range.

If you want to determine if people are using optimized solutions, perhaps you could set the limit a lot higher and add a few test cases with data sets that assured one was using a reasonable algorithm. With a ten minutes to compete, the odds of small scheduling differences is average out in ways that obliterate the need for more sophisticated CPU time measurements.

As for the Thread safety, you'd probably want to not use Threads in this case. Spawning a process would offload the online judge, prevent one contestant from possibly inspecting / interfering with another, provide an obvious means of termination (by the kill signal), and permit better bench marking of time (akin to the Unix command "time").

When something goes wrong in a threaded environment, it has the potential to destabilize the program, by using processes, extra barriers will prevent any such destabilization from impacting your online judge.

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138
  • Interesting. So if I understand correctly, instead of letting each contestant write a class that implements an interface, I should let each contestant write a whole program (that e.g. reads from stdin and writes to stdout), and test each program in a Process. Is this correct? – Erel Segal-Halevi Nov 28 '17 at 06:44
  • *Therefore, wall clock time in a "online judge" should be suspect*. Exactly! There was a thread! in one of these *code-competition* websites discussing this in response to a request from users to implement a similar feature. Basically, measuring execution time for algorithms with similar time complexity does not yield meaningful results. The only viable option seems to be scoring submissions by comparing their asymptotic time complexity. – jrook Nov 28 '17 at 06:45
  • 1
    @ErelSegal-Halevi You can still have them write a class, you just provide the framework (program wrapper) in which the class must fit. in any case, think about jrook's comment. You can't control the scheduling of other things on the CPU, so if you want to have some sort of timing, it must be either over a long enough time that "launching it at the wrong time" has little impact, or you somehow have a customized operating system (real time OS) that assures nothing else can steal the timed process's time slices. – Edwin Buck Nov 28 '17 at 06:55
  • 1
    If I was going to deploy any system that executed arbitrary Java classes uploaded by strangers, I would have it execute the foreign code in a separate process in a [sandbox](https://en.wikipedia.org/wiki/Sandbox_(computer_security)). – Solomon Slow Nov 28 '17 at 14:08
1

Using Junit? You could give this a try: https://github.com/junit-team/junit4/wiki/timeout-for-tests

Axel Jacobsen
  • 148
  • 10
  • Interesting. But still, the runaway test is not stopped unless it is interruptible: "If a test times out while executing an interruptible operation, the thread running the test will exit (if the test is in an infinite loop, the thread running the test will run forever, while other tests continue to execute)." – Erel Segal-Halevi Nov 28 '17 at 06:38
  • Ooop, I missed that - sorry. Perhaps something like this may help? Although I admit that I am out of ideas https://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ExecutorService.html Best of luck! – Axel Jacobsen Nov 28 '17 at 06:43
1

So One way that you could implement this would be to use two separate threads for 1 competitor. A ThreadTimer and A ThreadHelper

    public class ThreadTimer extends Thread {

    public ThreadTimer() {

    }

    @Override
    public void run() {

        try {

            Thread.sleep(1000);

        } catch (InterruptedException ex) {
            Logger.getLogger(ThreadTimer.class.getName()).log(Level.SEVERE, null, ex);
        }

    }

}

And ThreadHelper Which runs the function

    public class ThreadHelper extends Thread {

    Calculator c;

    public ThreadHelper(Calculator c) {
        this.c = c;
    }

    public Calculator getC() {
        return c;
    }

    public void setC(Calculator c) {
        this.c = c;
    }

    @Override
    public void run() {

        long startTime = System.nanoTime();
        long plus = c.add();        
        long endTime = System.nanoTime();


        long duration = (endTime - startTime); 
        long seconds = duration / 1000000000;

        System.out.println("Add Time: " + seconds);

    }

}

Your interface you created I am calling Calculator in my code.

This is calculating how long add takes and outputs the duration. I am sure the calculations are much more complex, but a potential answer to your question would come in the startup class:

public class Competition {

    public static void main(String[] args) throws InterruptedException, Exception {
        Calculator jim = new JimSmithsCalculator();
        Calculator john = new JohnDoesCalculator();

        ThreadHelper jimsThread = new ThreadHelper(jim);
        ThreadTimer time1 = new ThreadTimer();
        ThreadHelper JohnsThread = new ThreadHelper(john);
        ThreadTimer time2 = new ThreadTimer();

        time1.start();
        jimsThread.start();

        //This will run a loop ensuring both of the above threads are terminated...
        checkSeconds(time1, jimsThread);//This also does the time check

        //...Before moving on to these threads.
        time2.start();
        JohnsThread.start();


        checkSeconds(time2, JohnsThread);


    }

    public static void checkSeconds(ThreadTimer time, ThreadHelper t) throws Exception {

        while (t.isAlive()) {
            if (time.getState() == Thread.State.TERMINATED) {

                throw new Exception(t.getName() + " >> " + t.getClass() + " Failed!!!");
            }

        }

    }

}

Since You can not use the stop() method anymore, you could throw an exception if ThreadTimer completes before ThreadHelper does.

This will output an exception and continue the program. You could then see that a competitors thread failed with the exception.

The main point to all of this random code and my answer to your question is this method :

    public static void checkSeconds(ThreadTimer time, ThreadHelper t) throws Exception {

    while (t.isAlive()) {
        if (time.getState() == Thread.State.TERMINATED) {

            throw new Exception(t.getName() + " >> " + t.getClass() + " Failed!!!");
        }

    }

}

I don't know if this would work exactly as you would want it.

I hope this at least sparks an idea.

SynchroDynamic
  • 386
  • 2
  • 14