Multipass problem Support

mzuenni commented 5 months ago

Description of the enhancement request

In multipass problems the submission gets started multiple times and is fed with the output of the output valdiator from the previous run (but besides that the new run has no knowledge of any prior run). This allows some new types of problems about information theory and some other fields.

Expected behaviour

The submission is run on the test input (like for normal problems)
The output Validator is run on the submission output (like for normal problems)
The output Validator either accepts, rejects or indicates that the submission should be run again with a new input that it provides

Any other information that you want to share?

Multipass seems to also get added to the kattis problem package format: https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#multi-pass-validation Maybe it would also be nice to run the output validator with an argument which indicates which iteration this is or provide a way for the output validator to keep information between invocations.

vmcj commented 5 months ago

Could you provide a minimal problem we can test this with?

vmcj commented 3 months ago

@mzuenni as discussed in person, I'll close this issue as this requires the problemspec to first have a definition for this. Please re-open when that is in a reasonable state so we can start implementing this.

mzuenni commented 3 months ago

Just a small update:

A multi-pass validator can be used for problems that should run the submission multiple times sequentially, using a new input generated by output validator during the previous invocation of the submission.

To signal that the submission should be run again, the output validator must exit with code 42 and output the new input in the file nextpass.in in the feedback directory. Judging stops if no nextpass.in was created, or the output validator exited with any other code.

It is a judge error to create the nextpass.in file and exit with any other code than 42.

multipass can be combined with validation set to custom or custom interactive.
Regarding the timelimit, it should be checked per invocation of the submission.
The judgemessage.txt and judgeerror.txt should not be removed between invocations of the output validator i.e. the validator is responsible for appending/overwriting to the files in there
The feedbackdir should persist between invocations

Comments:

If the validator uses stdout and stderr you likely want to display that per invocation

Are there more things that need to be properly defined?

mzuenni commented 2 months ago

Maybe these are helpful for testing: https://github.com/RagnarGrootKoerkamp/BAPCtools/tree/master/test/problems/multipass https://github.com/RagnarGrootKoerkamp/BAPCtools/tree/master/test/problems/interactivemultipass

meisterT commented 1 month ago

Example interactive problem on Kattis: https://open.kattis.com/problems/guessinggame2

meisterT commented 1 month ago

To summarize my understanding of the spec:

the submission is first called with the given input
the validator can decide whether another pass is needed
if so, it needs to exit with 42, and put the new input in feedback/nextpass.in
if no new input is created, then the typical 23/42 exit codes indicate WA/AC

IMHO, the spec should be extended to include a required upper bound of passes. @mzuenni was this considered?

The following changes are likely required in DOMjudge:

in the judging backend, we probably could get away with some modifications to https://github.com/DOMjudge/domjudge/blob/main/judge/testcase_run.sh
in the database/schema, we have to think about how to represent the multiple answers, probably having a list of https://github.com/DOMjudge/domjudge/blob/main/webapp/src/Entity/JudgingRun.php per judging
in the UI, we have to see, how to represent things in the UI
no actual scoring changes

All in all doable, but still touches more than just the backend.

mzuenni commented 1 month ago

I think an upper bound was not considered (it is intended that the number of passes is variable so the validator is responsible for deciding the number of passes)... still an upper bound might be a good safeguard against bugs in the validator that result in an infinite loop... ~but not sure if that should be part of the spec or just a domjudge thing (is the maximum runtime of the output validator specified for normal problem?).~ maybe a new entry in limits should be added

DOMjudge / domjudge