Restricting depth of test data tree

[Matistjati]

During the Stockholm workshop, I got the impression that we had reached consensus on limiting the depth on the test data tree to 2. This means that

.
└── secret
    ├── 1.ans
    └── 1.in

and

.
└── secret
    ├── group1
    │   ├── 1.ans
    │   └── 1.in
    └── group2
        ├── 2.ans
        └── 2.in

is allowed, but not any deeper than that. I am personally not opposed to this change, as there is no real reason to have anything deeper. In fact, I suspect that most judging systems does not support anything deeper in their UI.

The one reasonable usage I have heard of was using folders to categorize test cases among the groups. So it functionally equivalent to flattening the structure up until depth 2. However, this is not common, and I would not be against not supporting this special case.

Any other opinions?

[evouga]

The current spec does limit the depth to 2, no?

The secret group may be further split into subgroups (each a subdirectory of secret).

which I guess doesn't explicitly say there can be no other subgroups, but that was the intent.

[niemela]

I think the current wording is a little unclear, we should clarify that the depth is only 2.

[niemela]

A slightly related question is, do we need to allow both cases and groups in the same group?

I.e. we should allow

.
└── secret
    ├── 1.ans
    └── 1.in

and

.
└── secret
    ├── group1
    │   ├── 1.ans
    │   └── 1.in
    └── group2
        ├── 2.ans
        └── 2.in

but should we also allow

.
└── secret
    ├── group1
    │   ├── 1.ans
    │   └── 1.in
    └── group2
    │   ├── 2.ans
    │   └── 2.in
    ├── 3.ans
    └── 3.in

?

I don't know of any problem where this has been used of would make sense, and disallowing it would simplify the verdict/score aggregation section further.

[RagnarGrootKoerkamp]

I'm pretty sure that in BAPC we've had some problems like that last example, where the groups are just for organisation purposes.

For pass-fail problems, I generally don't see much reason to restrict the hierarchy.
Any UI can just show them by their full name group1/1, group2/2, 3 and it should be fine.

No opinions for scoring problems. If more levels of aggregation are never used/needed, then I'd be OK dropping that.

(I guess we could in theory still allow subdir nesting inside an aggregated group for organisation purposes, but that sounds complicated and unnecessary.)

[thorehusfeldt]

I don’t understand this at all. data is a tree structure.

Here’s https://open.kattis.com/problems/alcohol :

➜  alcohol git:(master) ✗ tree data -d
data
├── invalid_inputs
├── sample
└── secret
    ├── alcohols
    │   ├── 1-primary
    │   ├── 2-secondary
    │   └── 3-tertiary
    ├── edgecases
    ├── nonalcohols
    └── other

I think it would be a real shame to restrict this; the submissions.yaml framework allows us to target specific subtrees, and the generators.yaml framework allows fine-grained subtree inclusions into other parts of the data tree. (For instance data/secret/group3/greedy/ may want to include data/secret/group4/connected/dags/ or something similar. During development, you might want to run your fledgling submission against a specific of those carefully-designed subtrees.

Suddenly forbidding that only decreases problem quality and makes many tools less useful.

[thorehusfeldt]

On the other hand, I enthusiastically support the idea of having testcases never be a sibling to a test group. (In other words, either all or none of the descendants of a test node are test cases.)

Just do it; the world will immediately improve.

[niemela]

I don’t understand this at all. data is a tree structure.

Here’s https://open.kattis.com/problems/alcohol :

Funny, I had mentioned this very problem to @Matistjati when discussing this :). That said, I believe that of the ~7000 problems in the Kattis DB only 3 has ever used this.

➜  alcohol git:(master) ✗ tree data -d
data
├── invalid_inputs
├── sample
└── secret
    ├── alcohols
    │   ├── 1-primary
    │   ├── 2-secondary
    │   └── 3-tertiary
    ├── edgecases
    ├── nonalcohols
    └── other

I think it would be a real shame to restrict this; the submissions.yaml framework allows us to target specific subtrees, and the generators.yaml framework allows fine-grained subtree inclusions into other parts of the data tree. (For instance data/secret/group3/greedy/ may want to include data/secret/group4/connected/dags/ or something similar. During development, you might want to run your fledgling submission against a specific of those carefully-designed subtrees.

Yes, but if the structure was instead:

➜  alcohol git:(master) ✗ tree data -d
data
├── invalid_inputs
├── sample
└── secret
    ├── alcohols-1-primary
    ├── alcohols-2-secondary
    ├── alcohols-3-tertiary
    ├── edgecases
    ├── nonalcohols
    └── other

You would be able to do all the same things, just as easily.

Suddenly forbidding that only decreases problem quality and makes many tools less useful.

[evouga]

The issues with floating-point precision do become more relevant if there are nested test groups, each worth fractions of fractions of points. It's not impossible to implement correctly (compute integer weighting factors for each test group and avoid division until the very end when computing secret's score) but it does complicate things.

submissions.yaml says nothing about test groups and generators.yaml is not in the spec, so I don't understand the concerns there.

If (a) only 3 existing problems have nested subgroups and (b) real contests are not asking for this feature and (c) contest systems don't/aren't going to implement rendering of arbitrary trees, then this smells a lot like overengineering/YAGNI to me.

[niemela]

The issues with floating-point precision do become more relevant if there are nested test groups, each worth fractions of fractions of points. It's not impossible to implement correctly (compute integer weighting factors for each test group and avoid division until the very end when computing secret's score) but it does complicate things.

True.

submissions.yaml says nothing about test groups

It does say some: https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#groups

and generators.yaml is not in the spec, so I don't understand the concerns there.

I believe this is a BAPCtools thing?

If (a) only 3 existing problems have nested subgroups and (b) real contests are not asking for this feature and (c) contest systems don't/aren't going to implement rendering of arbitrary trees, then this smells a lot like overengineering/YAGNI to me.

Well, regarding (b), @thorehusfeldt does run real contests, and he is asking for it. But I believe all 3 problems using that comes from that same contest.

There is yet another alternative simplification possible (that I also believe we discussed in Stockholm). We could allow arbitrary deep directory structures (which is all @thorehusfeldt is actually asking for) while only defining that to be only 2 levels of test groups.

If we go to the example from above (and add some actual test case files) we get something like this (the real problem obviously has more and better named test cases than this, but I think it conveys the point):

├── sample
└── secret
    ├── alcohols
    │   ├── 1-primary
    │   │   ├── A.in
    │   │   └── B.in
    │   ├── 2-secondary
    │   │   ├── C.in
    │   │   └── D.in
    │   └── 3-tertiary
    │       ├── E.in
    │       └── F.in
    ├── edgecases
    │   ├── G.in
    │   └── H.in
    ├── nonalcohols
    │   ├── I.in
    │   └── J.in
    └── other
        ├── K.in
        └── L.in

So, we have 7 directories under /secret with 12 .in files, but these only comprise 4 test groups as follows:

• group: secret/alcohols
  • secret/alcohols/1-primary/A.in
  • secret/alcohols/1-primary/B.in
  • secret/alcohols/2-secondary/C.in
  • secret/alcohols/2-secondary/D.in
  • secret/alcohols/3-tertiary/E.in
  • secret/alcohols/3-tertiary/F.in
• group: secret/edgecases
  • secret/edgecases/G.in
  • secret/edgecases/H.in
• group: secret/nonalcohols
  • secret/nonalcohols/I.in
  • secret/nonalcohols/J.in
• group: secret/other
  • secret/other/K.in
  • secret/other/L.in

[thorehusfeldt]

while only defining that to be only 2 levels of test groups.

I have no opinion on that. (In fact, I would welcome the introduction of a strict distinction between [test groups] and [internal nodes in the test data tree], by whatever names the latter shall be known. I feel we are often talking past each other because of this and add unnecessary tensions to our conversation.)

[evouga]

So if I understand correctly, the proposal is:

1. secret may either contain:
   -- one or more test cases (and optionally, a static validation test case);
   -- one or more subdirectories (and zero normal or static validation test cases). All subdirectories of secret are test data subgroups.
2. All test data subgroups:
   -- may contains a test_group.yaml and a static validation test case;
   -- may contain test cases, subdirectories, or both;
   -- must contain either a static validation test case, a normal test case, or a subdirectory. All subdirectories of a test data subgroup are test data subgroup subdirectories.
3. All test data subgroup subdirectories:
   -- may not contain a test_group.yaml or any other trappings of a test data (sub)group;
   -- may contain test cases, subdirectories, or both;
   -- must contain either a test case or a subdirectory. Subdirectories are also test data subgroup subdirectories.
4. All test cases in all descendant directories of a test data subgroup are considered test cases of that subgroup.
   -- the path, relative to the test data subgroup directory, of each test case is prepended to the name of the test case when determining lexicographic ordering of the test cases.
5. sample, if it exists:
   -- may contain a test_group.yaml and a static validation test case;
   -- may be empty;
   -- may contain test cases, subdirectories, or both; All subdirectories of sample are test data subgroup subdirectories (not test data subgroups).

Does that sound right?

[RagnarGrootKoerkamp]

SGTM. My only remark is that for pass-fail problems, i'd just say that test data subgroups do not exist, and everything is a test data subdirectory or so?

Are there scoring problems without subdirectories of secret/? What if one makes a scoring problem with directories that are not subgroups? I guess those subgroups have default assumed behaviour right, even without a test_group.yaml present. So this is something that explicitly will not be supported. (that's OK)

[Tagl]

SGTM. My only remark is that for pass-fail problems, i'd just say that test data subgroups do not exist, and everything is a test data subdirectory or so?

Are there scoring problems without subdirectories of secret/? What if one makes a scoring problem with directories that are not subgroups? I guess those subgroups have default assumed behaviour right, even without a test_group.yaml present. So this is something that explicitly will not be supported. (that's OK)

Yes, I have made plenty of scoring problems with test cases immediately within secret/