DOMjudge-devel May 2017

domjudge-devel@domjudge.org

5 participants
4 discussions

Checktestdata as EDSL
by Jeroen Bransen 30 May '17

30 May '17

Hi all, Checktestdata is a nice DSL and has proved helpful in many situation, but from the moment I used it I was missing features and wondering why it wasn't implemented as an EDSL (Embedded Domain Specific Language). Now, many years later, I've finally found some time to create it. I've implemented a little library in Haskell, and as a sneak preview I've taken the interception problem from NCPC 2016 as referenced to in [1] and attached it. The first question is: where shall I put the sources to the library? Somewhere in the checktestdata repository (and if so, where), or maybe create a checktestdata2 repository? Let me give a little more information on why I think an EDSL is a good idea here, and why I choose for Haskell (other than my background): + With an EDSL, you get so much for free from the underlying language, such as (typed) variables, all sorts of abstraction mechanisms, compiler optimizations, etc. For example, some testdata script may consist of some repeated parts, which in an EDSL can simply be given a name to get rid of the duplication. + Compiler optimizations, which of course also exist for C++ in which checktestdata is built now, don't only optimize the checktestdata runtime, but also the script itself since it is just a program and not some custom script anymore. Especially with a functional language such as Haskell this means definitions of primitives can be inlined and whole parts of the script may get fused to a very efficient version. + Maintainability: my library is now +- 200 LOC, including docs and empty lines, and contains quite a lot of the checktestdata language already. Because Haskell has many well optimized parsing libraries, we get a lot for free, and only have to create a nice generalization for this particular use case. + Efficiency: the current checktestdata is just too slow, as mentioned in [1]. As a reference, on my machine the checktestdata script for interception 09.max_ans.in takes 35.5s, the python script takes 2.2s, and the attached version only 2s. And I haven't done anything to optimize specifically for this case, I've just translated the ctd script to the syntax of my EDSL. + With this, the script can do more than just checking the syntax. I.e. when the problem specifies that it contains a connected graph, one can check the syntax, but also the connectedness of the graph, while still separating concerns, i.e. the syntax of the input can be separated from the semantic checks, but the semantic checks don't need to come in a separate program which also has to read the input again, like we should now. All can be combined naturally. + Create your own combinators: the primitives can be easily combined into more complex combinators which you can then reuse. I.e. think of a 'point2d' combinator that reads two space separated integers. - Haskell Platform needs to be available, this is easy on all major OS, but is a quite large dependency. Then again, GCC and Boost are large as well, and are less Windows-friendly. - Slighly different syntax: although Haskell is quite liberal in its syntax for EDSL's, users have to get used to particularities of the language/ - Data generation is not easily possible, if not infeasible. There should be some way of embedding the language to make this possible, and this is actually what I've been working on for the past few years when thinking about this problem, but since we mostly use it for checking data I went with a monadic embedding which is very easy for data checking. - Backwards compatibility: parsing existing scripts and running it with the new backend is not going to be easy. I don't expect show stoppers, but it definitely won't be as efficient as writing scripts within the language because of variable bindings. I need to work on this a bit to be sure though. That's it, of course my libary is not done yet (no good error messages, no regex yet), but it's a proof of concept that is already usable for simpler problems. I hope to convince you that this is the way to go, and to get some ideas to create the POC into a working tool. Also, suggestions on 'interesting use cases' are welcome, the interception is a nice one but I am sure there are many more problems for which the standard checktestdata just not works. Yours truly, Jeroen [1] https://github.com/DOMjudge/checktestdata/issues/3

2 10

Storing participant program in execdir after judging is complete
by Parth Mittal 28 May '17

28 May '17

Hello We run an instance of domjudge for our university courses, which has a lot of submissions (the judging run table has almost a million rows now). I was exploring ways to reduce the disk usage of the judge, and I found that in the directory for every judging run, we store a copy of the executable under execdir under every testcase. Each executable is > 1 MB, and when this multiplies with number of test cases * number of judgings, this becomes very large in our use case. Is there a reason why the executables are stored after judging is complete? Thank you Parth Mittal

2 1

Option to stop judging when met WA
by Phúc Khang Nguyễn 27 May '17

27 May '17

Hi, I'm wondering if there are any options that can stop the judge when it met a Wrong Answer verdict like Time-limit Exceed or not? (maybe change the code perhaps) If yes, please show me how to do it. Best regards, Khang

2 1

Presence at the World Finals
by Jaap Eldering 13 May '17

13 May '17

Hi all, Most of the DOMjudge developers will again be present at the ICPC World Finals, starting in a week in Rapid City, USA. If anyone else is interested to talk and meet, please do get in touch or simply find us at the WFs! We love to talk and get feedback, discuss your use cases, issues, feature (requests), etc. See you in Rapid City! Jaap

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

DOMjudge-devel May 2017