10
\$\begingroup\$

Sometimes, on challenges with a constant output, we get extremely boring answers that make absolutely no effort to compress the output whatsoever, and instead just literally dump the exact output the challenge asked for. For example, if the challenge was:

Print the following text:

aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa

and someone submitted this python answer:

print'''aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa'''

or this HTML answer:

<pre>aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa</pre>

Generally, this is done in a non-programming language, such as HTML. There is a consensus for allowing non-programming languages in constant output challenges, but these answers are so low-quality, I see no reason to allow them.

Now keep in mind, I am not trying to ban HTML as counting as a programming language, especially since it can be used creatively. However, if we allow purely dumping the output into the answer box, that paves the way for extremely low-quality non-answers such as this one (Deleted answer, only visible to users with 2K or more reputation)

I don't feel the need to link to all of them, but I've seen plenty of answers like that recently, especially with the recent influx of challenges with a constant output.

Do we have a stance on answers like this? More importantly, should we?

I can think of a couple solutions to this.

  1. Directly dumping the output into an answer is off-topic and disallowed.

    I'm a little bit hesitant to say all answers like this should be disallowed, since this is just one more of our endless meta rules to enfore, and because sometimes this approach is optimal (although that usually indicates a bad challenge). Especially since we allow bubblegum, which is arguable less of a language then HTML+CSS.

  2. Answers that directly dump the output into an answer are not a serious contender.

    Like I said above, sometimes they are a serious contender. Plus, where do we draw the line between users not being extremely good at code-golf, and telling them they are breaking the rules?

  3. Do nothing.

    Answers like this are rare enough, that they could be handled with downvotes when they come up, and it's not worth having an official stance on this.

\$\endgroup\$
  • 2
    \$\begingroup\$ HTML […] can be used creatively. I don't think so. HTML + CSS is another story though. \$\endgroup\$ – Dennis Aug 6 '16 at 21:22
  • \$\begingroup\$ Isn't this akin to hard coding the answer, and so is a standard loophole? \$\endgroup\$ – Beta Decay Aug 6 '16 at 21:28
  • 1
  • \$\begingroup\$ There are plenty of legitimate programming languages that allow you to dump the output too, such as PHP or ///. \$\endgroup\$ – feersum Aug 6 '16 at 21:34
  • 4
    \$\begingroup\$ "they could be handled with downvotes" usually these bad quality answers can be made quickly, and as a result get upvotes due to FGITW, and because such questions tend to be easy get onto HNQ quickly and get upvotes from there too, quickly canceling out any downvotes. So I'd say #3 is not good solution (i have no citation though) \$\endgroup\$ – Downgoat Aug 6 '16 at 21:39
  • 1
    \$\begingroup\$ @Downgoat Citation-Needed \$\endgroup\$ – DJMcMayhem Aug 6 '16 at 21:41
  • \$\begingroup\$ I have abused this. I can say that I deserved the downvotes, but interestingly enough I did gain rep from this answer. Personally I feel we should ban just "dumping" the answer. \$\endgroup\$ – Rohan Jhunjhunwala Aug 7 '16 at 12:27
  • \$\begingroup\$ If you see a shorter solution in the same language, add a comment linking to it so upvotes can go where they are more deserved. If you don't see a shorter solution in the same language, add one yourself. If you can't think of a shorter one, consider complaining about the challenge instead. \$\endgroup\$ – trichoplax Aug 7 '16 at 14:20
4
\$\begingroup\$

Here's my thoughts on the matter:

Let's say the challenge in question asks for N constant bytes to be printed to STDOUT. Every language has some overhead C for printing this constant output. Some examples:

  • Python 2, no newlines in output: print'X' (C = 7)
  • Python 2, with newlines in output: print'''X''' (C = 11)
  • C, no newlines: main(){puts("X");} (C = 17)
  • JavaScript, no newlines: alert("X") (C = 9)

Thus, an upper bound on the Kolmogorov complexity of a string X of length N in a language with overhead C is N+C. Note that this is an upper bound - for any non-random string, the actual Kolmogorov complexity is almost certainly shorter.

Our challenges are intended to have solutions which find and exploit patterns in the desired output, allowing those solutions to be shorter than the naïve upper bound of N+C. Thus, in my opinion, it's fair to say that a submission that does not exploit these patterns to be as short as possible, instead going with the trivial, naïve N+C approach, is not a serious contender, because it does not make any attempt to improve upon the upper bound. This is in accordance with the current community consensus on what constitutes being a serious contender.

That being said, there's still the issue of languages whose optimal solution is that naïve solution. I am strongly against allowing languages that do not satisfy our definition of a programming language to be used in challenges (unless explicitly allowed by the challenge author, of course), and I do not believe that fixed-output challenges should be any different in that regard. Simply printing out a string is not interesting. It's trivial, and anathema to the point of Kolmogorov complexity - exploiting patterns within a string to create a program that outputs the string, in less bytes than the original string. Disallowing non-programming languages in these challenges would be a huge step in solving this problem. I am also in favor of disallowing solutions which simply dump the output, with no extra processing, since these are extremely trivial and don't add anything to the challenge by being present.

\$\endgroup\$
  • 1
    \$\begingroup\$ HTML/CSS (sadly) does satisfy this definition :( \$\endgroup\$ – Rohan Jhunjhunwala Aug 7 '16 at 12:28
  • \$\begingroup\$ @RohanJhunjhunwala HTML+CSS is Turing-complete, so it can take advantage of patterns in the output to achieve a better-than-naive score (assuming the output is large enough that it would be better to add the extra overhead necessary to not just dump the output). \$\endgroup\$ – Mego Aug 7 '16 at 19:27
  • \$\begingroup\$ getting to that point to perform interesting computations with the turing complete aspects of html/css would require an incredibly large overhead (much larger than most kolmogorov complexity challenges). \$\endgroup\$ – Rohan Jhunjhunwala Aug 7 '16 at 22:12
  • \$\begingroup\$ The "Turing-completeness" of HTML-CSS is a dubious one. Can you even use those to, say, repeat a string 10 times without writing it 10 times? \$\endgroup\$ – feersum Aug 7 '16 at 23:17
  • 1
    \$\begingroup\$ @feersum It's not dubious at all. \$\endgroup\$ – Mego Aug 7 '16 at 23:18
  • 2
    \$\begingroup\$ @Mego I say that because of the requiring clicking thing and, more importantly, that the amount of memory a program can utilize is linearly bounded by the source code length, making it more like a state machine than a Turing machine. Edit: There is a number of states exponential in the length, so it is better than a state machine, but weaker than a normal programming language. \$\endgroup\$ – feersum Aug 7 '16 at 23:33
  • \$\begingroup\$ @feersum My computer requires me to press a button to make it start. Is it not Turing-complete? \$\endgroup\$ – Mego Aug 7 '16 at 23:35
  • 1
    \$\begingroup\$ @Mego Any program requires an O(1) effort to start. \$\endgroup\$ – feersum Aug 7 '16 at 23:35
2
\$\begingroup\$

I think that option 3 (Do nothing/Downvote) is the best option. Here's my case for it:

I feel that this is not really a problem specifically with Kolmogorov complexity but rather with easy or trivial challenges in general. Every easy challenge can potentially have really boring, low effort, answers. Often these are not serious contenders, sometimes they are.

Our site policy for such answers at the moment seems to be just to downvote them. I don't see why a special exception should be made for Kolmogorov complexity.

I think that this issue is less prevalent on questions than elsewhere. On Kolmogorov questions, the answer is either

  • Not competitive, which is grounds for deletion

  • Competitive, meaning the challenge is probably bad anyway.

I think that there is not much of an issue with the way things are being handled now. I think that just downvoting boring answers will promote fewer bad answers and downvoting challenges that allow bad answers to be competitive will promote fewer of those types of challenges.

\$\endgroup\$

You must log in to answer this question.

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