[contest-control-systems] VIVA

Jaap Eldering eldering at a-eskwadraat.nl
Mon Jul 9 04:04:01 CDT 2012


Hello David, 

[CC-ing to Contest Control Systems list FYI]

On Sun, Jul 08, 2012 at 10:59:13AM +0200, Thijs Kinkhorst wrote:
> Hi David,
> 
> On Fri, July 6, 2012 16:34, David Van Brackle wrote:
> > Have you had a chance to take a look at the VIVA system for verifying
> > judge
> > input?
> >
> > vanb
> 
> I know that at least I haven't, but I'm CC'ing Jan and Jaap: as the
> authors of our 'checktestdata' they are likely candidates to say something
> useful about this.
> 
> Cheers,
> Thijs

Jan and I have looked at the specification of your language, and I
looked at the testdata specifications of a couple of contests to see
what is useful in practice. Below is a report I sent to some other
people earlier. Comments and criticism welcome, especially ideas on
how to improve upon these languages.

=================

VIVA [1] (VanBrackle's Input Validator Assistant) is more expressive
in that it allows more general constraints, and for example the
ability to express that a sequence of numbers is increasing. These
constraints can be formulated rather concisely, but on the other hand,
the language is more complex and obscure (a la Perl). VIVA implicitly
assumes that tokens are single whitespace separated and it uses
standard types: i.e. the default integer type is 32bit. Our
"checktestdata" language [2] is more verbose (a la Pascal), and
integer and float types are arbitrary precision/size by default (using
libgmp/libfmpr).

I've analyzed the NWERC'08-'11 and 2012 WFs problemsets to see how
much of the input specification our language can describe. Slightly
less than half of the problems can be completely encoded in our
language. Some problems have non-encodable input specifications like
graph-connectedness and epsilon precision of the corresponding output.
The most useful features that could be added to our language are:
1 formulation of an additional constraint, e.g. two numbers 1 <= a,b
<= n with constraint a != b.
2 formulation of (non)strictly increasing sequences.
3 formulation of uniqueness, e.g. of a list of points in the plane.

1 could easily be fixed for our language by adding an ASSERT statement.
2 is nicely handled by VIVA using implicitly defined array indices
within a loop. I personally don't like that syntax, though.
3 is handled by VIVA, but in a hacky way: it can only check such
things if the data of these objects (say x,y coords of a point) are
read in the same loop.
 
Best, Jaap

[1] http://sourceforge.net/projects/vanb-viva/files/
[2] http://home.a-eskwadraat.nl/~domjudge/docs/judge-manual-6.html


More information about the Contest-Control-Systems mailing list