18
\$\begingroup\$

One of the more recent things to avoid that's coming up a lot is the use of non-observable requirements. The most common incarnations of this are things like "no hardcoding", "implement this algorithm" or "don't use integer types". I find that these are sufficiently problematic that we should think about disallowing them outright, and close corresponding challenges as "unclear what you're asking".

The main problem with these is that they depend on properties of the program that are highly subjective. Just how much do I need to calculate in order for a result not to be hardcoded? If I need to implement a given algorithm, can I swap two independent operations? How many other deviations are allowed? What does "implement this algorithm" even mean in non-imperative languages? And so on.

So, should we disallow these? If so, what makes a requirement observable (valid) or non-observable (invalid) and what should we do about the exception proposed by feersum in the linked answer (the exception being bans on built-ins that solve the challenge)?

\$\endgroup\$
  • \$\begingroup\$ The widely-used definition of truthy-falsey is arguably unoberservable -- feersum thinks so. What would you say about this? \$\endgroup\$ – xnor Jan 8 '17 at 18:50
  • \$\begingroup\$ @xnor I think it's a decent definition because it works in most languages, but you're right that the fact that it doesn't work in all languages is problematic. It should probably be augmented by case-by-case definitions for languages where the default definition doesn't make sense. \$\endgroup\$ – Martin Ender Jan 8 '17 at 18:52
  • \$\begingroup\$ Also, I presume this is for code golf? Code challenges and programming puzzles often make requirements on the source. Restricted code too. \$\endgroup\$ – xnor Jan 8 '17 at 18:53
  • 1
    \$\begingroup\$ @xnor I consider restrictions on the source code to be observable if a program can be used to check them (in which case they're still objective). See my answer. \$\endgroup\$ – Martin Ender Jan 8 '17 at 18:54
  • \$\begingroup\$ @xnor I think the truthy/falsey idiom is more of a "DISTINCT RESULT A/DISTINCT RESULT B" thing, as long as your code can give a consistent result for truthy and a different consistent result for falsey I accept the answer as valid even if you're not just outputting 0 or 1. \$\endgroup\$ – Magic Octopus Urn Jan 11 '17 at 17:56
12
\$\begingroup\$

Only for code golf

I think disallowing non-observable requirements is good, but should be limited to pure code golf (without for instance). As Nathan Merrill points out, many well-accepted challenge of other genres rely on unobservable requirements, and they shouldn't be accidental casualties of this rule.

This leaves requiring "no built-ins" as a point of contention. I'd be fine with either banning them or not. Or perhaps banning built-ins will be moot if we go with combining built-in-only answers? I'd like to hear people's thoughts on this.

("Submissions must be competitive" could be seen as a non-observable requirement for code golf, but I think it's rather a meta policy covered elsewhere.)

\$\endgroup\$
  • \$\begingroup\$ What's your stance on "No hardcoding"? It's not as relevant for non-fastest-code challenge, but it's worth mentioning, I think. \$\endgroup\$ – Nathan Merrill Jan 11 '17 at 3:00
  • \$\begingroup\$ @NathanMerrill For what kind of pure code golf would you want a "no hardcoding" rule? \$\endgroup\$ – xnor Jan 11 '17 at 3:17
  • \$\begingroup\$ Some sort of code-golf challenge that wants a maximum runtime (without hardcode) perhaps? I'm not thinking of a particular challlenge, but since it's been a point of debate here, I think its worth mentioning. \$\endgroup\$ – Nathan Merrill Jan 11 '17 at 3:22
  • 2
    \$\begingroup\$ @NathanMerrill I think if a code golf can be solved competitively by hardcoding, that's a problem of the challenge. Disallowing hard-coding is not going to fix the challenge. \$\endgroup\$ – Martin Ender Jan 11 '17 at 9:35
  • \$\begingroup\$ I've thought about this answer a lot: I think it solves most of the issues I bring up, but the biggest issue is that non-observable requirements should be an issue for any challenge. Like, I shouldn't be able to post a fastest code challenge that requires you to use a for loop, because that isn't observable \$\endgroup\$ – Nathan Merrill Jan 11 '17 at 14:06
  • \$\begingroup\$ But in practice, this may end up being the best solution because it addresses nearly all of the non-observable requirements we see, even if it leaves a gaping hole on other challenge types. \$\endgroup\$ – Nathan Merrill Jan 11 '17 at 14:10
  • \$\begingroup\$ @NathanMerrill Yes, I wish this rule could cover more but it's too hard not to rule out legitimate uses by mistake. \$\endgroup\$ – xnor Jan 11 '17 at 22:56
6
\$\begingroup\$

This is a bad idea.

I like the sentiment of challenges being completely observable. I think that we should aim for questions to be as close to observable as possible, but I don't think it would be good for this site to require complete observability.

As it stands, there are lots of challenges that would become trivial/impossible if we disallowed non-observable requirements.

  1. No built-ins. I think this is obvious how this makes things trivial in some languages. If a builtin is shorter than any possible algorithm, then submissions in that language have no choice but to submit that built-in (to stay competitive).
  2. No hard-coding. While this is a problematic statement in certain scenarios, we need it to keep some fastest-code challenges non-trivial. Primes become a lot easier to generate if you have the first 10K of them in your source code. Some sequences become exponentially harder to calculate the higher you go, which means that it is feasible to hard-code all answers.

    The following challenges (as well as others) would all become off-topic:

  3. No retaining state and No reflection/modifying other submissions. Both of these are essential for running all of my KoTHs. I don't want people storing static variables to remember data from game to game, and I don't want reflection to cheat at the game. This would close nearly every KoTH challenge

  4. Submissions must be competitive. There is a requirement we place on every challenge by default and is non-observable. Mego brought up in chat that the more specific meta ruling wins, so this wouldn't actually close any questions, but this would make for two rules that conflict with each other.

  5. Asymptotic complexity restrictions. This includes all questions from and other challenges where we put a complexity requirement to prevent brute-forcing.

  6. "You cannot use multiple version of the same language". This is relevant to answer-chaining or multi-language answers. A program cannot tell if two languages are multiple version of the same language, so it wouldn't be observable.

Unless we are able to define all of the above non-observable requirements for every language we use on this site, we're going to kill so many challenges here.

\$\endgroup\$
  • 1
    \$\begingroup\$ "No retaining state and No reflection/modifying other submissions." This only seems to be relevant for language-specific scenarios in which case it should be possible to check this requirement objectively. \$\endgroup\$ – Martin Ender Jan 9 '17 at 16:20
  • \$\begingroup\$ Not really. Even if I restrict the language to Java, I could ban the word 'static', but people could use a library that has a static variable to store their static data. I could ban reflection libraries, but somebody could find a flaw in my code, and use it to cheat. If I do allow multiple languages, they could start another thread, write to a file, or do a gazillion other things I can't think of. \$\endgroup\$ – Nathan Merrill Jan 9 '17 at 16:22
  • \$\begingroup\$ Also, I think that the algorithm can be observable if it's an iterative algorithm and you're outputting intermediate information as well. If I ask you to sort a list using bubble sort and say "output all iterations of the sort", it becomes observable. Whereas saying "calculate pi using X" would be a non-observable algorithm. There's some grey area here and handling it on a case-by-case basis seems to work decently. \$\endgroup\$ – Magic Octopus Urn Jan 11 '17 at 17:59
  • \$\begingroup\$ Outputting iterations works only if you want to enforce the algorithm you want them to use. If I simply want to set a maximum complexity, but there are a variety of algorithms that work under that complexity, then "output all iterations" is really vague. \$\endgroup\$ – Nathan Merrill Jan 11 '17 at 18:06
3
\$\begingroup\$

Yes, challenges with non-observable requirements should be closed

I would consider a requirement observable if it's fulfilment can be (in theory) be determined by a program by looking at some or all of the following information:

  • The source code of the program.
  • The output of the program.
  • The runtime of the program (or the timing of several outputs of the program).
  • The memory usage of the program.
  • Interaction of the program with various external systems like the file system, other process it's communicating with or various hardware.

Note in particular, that it must be possible for a program to determine a submission's validity in any language that can be used on that challenge. This makes requirements like "does not use loops" non-observable because the concept of loops might not be well-defined in all languages.

I'm not making any statement about the exception of banning built-ins in this answer, because I'm not 100% sure about them yet. I'd rather find a way to specify the ban in an objectively observable than make an exception.

\$\endgroup\$
  • \$\begingroup\$ -1 You've already identified the flaw: builtins and hardcoding. I don't see any way to objectively define them, and I don't think its a good idea to make this change unless we can come up with an objective way to define them. \$\endgroup\$ – Nathan Merrill Jan 9 '17 at 15:43
  • \$\begingroup\$ @NathanMerrill I get your point about built-ins, but I don't see what you mean about hardcoding. This is intended to disallow rules like "no hardcording", precisely because there's no way to specify them objectively. \$\endgroup\$ – Martin Ender Jan 9 '17 at 15:46
  • 1
    \$\begingroup\$ For fastest-code challenges, "no hardcoding" can be a really hard requirement not to add. Like, for example, generating primes. I definitely think that disallowing hardcoding can be a good thing. \$\endgroup\$ – Nathan Merrill Jan 9 '17 at 15:47
  • 4
    \$\begingroup\$ @NathanMerrill I don't see how such a rule is any less problematic for fastest code if you can't specify it in an objective way. \$\endgroup\$ – Martin Ender Jan 9 '17 at 15:49
  • \$\begingroup\$ Because if I don't say it, then the challenge becomes trivial, and I might as well not post it. If I do say it, then we have a slightly-non-objective challenge that people simply need to judge whether answers are hard-coding. Sure, that may cause debates, but I'd rather have a under-specified prime challenge than no challenge at all. \$\endgroup\$ – Nathan Merrill Jan 9 '17 at 15:51
  • 2
    \$\begingroup\$ Maybe this is too pedantic, but the requirement that the code implements the operation the spec asked for is not program-checkable. Maybe it is if you assume some memory and time bounds. We generally require though that code works for any input in theory. \$\endgroup\$ – xnor Jan 9 '17 at 16:09
  • 2
    \$\begingroup\$ All asymptotic complexity properties are also not observable by any program, which would make restricted-complexity challenges off topic. If we want to be pedantic, this suggestion is too restrictive. \$\endgroup\$ – Zgarb Jan 9 '17 at 17:56
  • \$\begingroup\$ @Zgarb The runtime of the program (or the timing of several outputs of the program) is sufficient for determining the complexity (empirically), or source code analysis can be done. \$\endgroup\$ – Mego Jan 9 '17 at 18:19
  • \$\begingroup\$ Source code analysis is not objective, and the runtime is only an estimate, and may be wrong. \$\endgroup\$ – Nathan Merrill Jan 9 '17 at 18:24
  • 1
    \$\begingroup\$ A concern Nathan brought up in chat is that your stance on hardcoding is directly opposed to a popular standard loophole - one that you proposed over two years ago. \$\endgroup\$ – Mego Jan 9 '17 at 18:36
  • \$\begingroup\$ I think this rule is useful enough to have in general that I'd support a modified version that gerrymanders in the things we want to be exceptions. \$\endgroup\$ – xnor Jan 10 '17 at 1:03
  • 2
    \$\begingroup\$ @Mego I guess I'd rather see challenges find an objective way to disallow hardcoding (or make it unfeasible) than having to rely on a subjective standard loophole. \$\endgroup\$ – Martin Ender Jan 10 '17 at 8:06
  • \$\begingroup\$ @xnor I'd love to see some alternative proposals for the rule, so feel free to make a separate answer. :) \$\endgroup\$ – Martin Ender Jan 10 '17 at 8:06
  • \$\begingroup\$ @xnor I agree with Martin. I could completely get behind a "Acceptable non-observable requirements" post, similar to our "Acceptable IO formats". If you don't post it, I will :) \$\endgroup\$ – Nathan Merrill Jan 10 '17 at 14:36
  • 1
    \$\begingroup\$ @MartinEnder I feel like your "Counting Diamond Tilings" is a great example of a needs-hardcoding-restriction challenge. As proof of concept, how would you modify it to not need hardcoding? \$\endgroup\$ – Nathan Merrill Jan 10 '17 at 15:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .