13
\$\begingroup\$

My first meta question here, so please be gentle.

I'd like to know what the prohibition on "hard-coding the output" means.

Background: I answered this question: Sudoku Compression

The question concerns producing a minimal size compressed output for a sudoku board. Unfortunately, the scoring is such that the score is calculated as the sum of the compressed size for 10 inputs. As there is no limit on program size, trivially this can be accomplished by hard coding the 10 input cases to one byte, and handling all others as 81 bytes.

Fortunately, we have the standard loopholes to prevent this. My understanding is that they are here: Loopholes that are forbidden by default

What that says is:

Hard-coding the output

Unless the question is an obvious exception (the primary exception being those tagged kolmogorov-complexity), your program is expected to do work, not just print a pre-calculated result. If the question doesn't require input and so a solution which just prints the answer would seem to meet the spec, downvote the question rather than post a protest answer consisting of the literal output.

Now, what I did was produce a real answer that compresses any Sudoku board to 12 characters (or fewer), but then optimise it so that one of the input boards produces a zero size output (details are irrelevant but I've clearly marked how it does it in the code). Clearly it meets the criterion of "expected to do work" and it does not "just print a pre-calculated result". It works on every Sudoku grid.

In my view it's a good question (I certainly enjoyed producing the code), but the scoring is faulty. But it's too late to change that.

I'm not asking for special treatment as far as my answer's concerned. But I would like to understand what "no hardcoding" means. I'd read this as a ban on trivial solutions which do no calculation, but merely print the test output. Does the ban in fact mean one is not allowed to optimise for test data? If so, I'd suggest the loophole document needs updating. Is there some other general prohibition against taking advantage of weak scoring algorithms?

\$\endgroup\$
  • \$\begingroup\$ That's why I suggested scoring by worst-case size. ;) In any case, I don't think optimising for the test cases necessarily falls under that loophole, but it's rarely "in the spirit of the question" or good sportsmanship or whatever you want to call it. In fact, I'll definitely add a standard loophole for this, because it should be one. In the end, what you're doing is exploiting the challenge's scoring, i.e. the challenges spec - and that's a loophole, if not a standard one. And I think PPCG has outgrown the days where rule-lawyering was funny. \$\endgroup\$ – Martin Ender Nov 17 '14 at 18:43
  • \$\begingroup\$ Done. (It's not an accepted loophole yet, and it wouldn't affect your answer retroactively anyway.) \$\endgroup\$ – Martin Ender Nov 17 '14 at 18:50
  • \$\begingroup\$ @MartinBüttner scoring by worst case would have been fine, as would scoring on an average of 1,000 random cases. However, those weren't the rules. Mine scored 10% different if I did a sort rather than a sort reverse deep inside the algorithm. Is choosing the better option to improve the score on the test data cheating? If it makes the worst case no worse? I'm less concerned as to this specific question than to what "in the spirit of the question" means here, given OP had ample opportunity to change the scoring or clarify. \$\endgroup\$ – abligh Nov 17 '14 at 18:54
  • \$\begingroup\$ Changing the order of the sort is one thing, hardcoding one of the test cases into the solution is another. You're abusing the spec in a way that is clearly not the OPs intention. Even if it's not a standard loophole, that doesn't seem like a nice thing to do. \$\endgroup\$ – Martin Ender Nov 17 '14 at 18:57
  • \$\begingroup\$ Fair enough - I'll revert that edit in this case. But I still maintain it was not clear until your proposed new loophole. \$\endgroup\$ – abligh Nov 17 '14 at 18:58
  • 2
    \$\begingroup\$ In my opinion the question asker is probably at fault if hard-coding is the optimal solution. They should have provided more cases or a random input generator. \$\endgroup\$ – feersum Nov 18 '14 at 8:48
  • \$\begingroup\$ Since the formulation of the loophole allows for exceptions, one would have to figure out if the particular question is one of those exceptions. Anything tagged kolmogorov-complexity would be an exception, but that is just given as an example, not a complete list. Based on that I'd say any Kolmogorov complexity challenge would be an exception, regardless of whether it was tagged as such or not. I think every compression challenge is a Kolmogorov challenge because to the best of my knowledge there is no other way to score such challenge without having flaws in the scoring. \$\endgroup\$ – kasperd Nov 24 '14 at 0:04
  • \$\begingroup\$ @feersum For a moment I thought one could create a bullet proof input generator by using the decompression code itself as seed for a random number generator. But now I am not so sure about it. Maybe I should just create that as a question where the real challenge is to find and abuse a flaw in the input generator. \$\endgroup\$ – kasperd Nov 24 '14 at 0:07
  • \$\begingroup\$ @kasperd I was thinking something similar myself - that it would be a good code-challenge scoring system to have the score based on random input seeded by some cryptographically secure hash of the source code. \$\endgroup\$ – feersum Nov 24 '14 at 5:14
6
\$\begingroup\$

I agree that the challenge's scoring wasn't very good, but including one of the test cases in the code is definitely hardcoding in my opinion. But we've discussed this in the comments. Let's just agree that you abused a bad part of the spec, which certainly a loophole, standard or not.

Anyway, I want to use this answer to suggest a scoring mechanism for future challenges, which should a) reduce the problem and b) make it detectable.

  • The OP provides a reasonably large, randomly generated set of test cases. The sets should be sampled uniformly from all inputs that answers should be able to handle. The OP may or may not provide the script for generating them.
  • Answers are scored on this set of test cases only. This ensures that we have an objective winning criterion that doesn't depend on undisclosed or fluctuating test sets.
  • If the OP suspects an answer of optimising towards the given test cases, he can compare the score with another randomly generated set. An answer that optimises for general input will perform similarly on all large, uniformly random test sets. If an answer somehow optimises towards the given inputs, that should be noticeable. Likewise, this allows an answer to optimise towards some subset of inputs, e.g. ignoring some rare edge cases, because the average number of such edge cases will be consistent across multiple random test sets.

I think this should fix most of the problems, and avoid a lot of subjective discussion. It also avoids undisclosed benchmarks and hard character limits on submissions.

\$\endgroup\$
1
\$\begingroup\$

This answer is a list of several different ideas... It's not really giving a specific solution.

  1. Puzzles measuring performance on only a few (<100) test cases
    • An advantage is that they are easier to self-score
    • These are the most vulnerable to hard coding
    • If there is any way to generate a larger, random test set, that should be done
    • I think a program's score should NOT simply be the total output length
      1. Otherwise, the most difficult test case would determine the winner
      2. The score for each test case could be (best solution)/(my solution) to get a number between 0 and 1. Add these up to form an overall score.
  2. Puzzles measuring performance on a test set whose answers are already known.
    • The test set must be large (>1000)
      1. Direct hard-coding is a major threat to small test sets. The challenge would reduce to a .
    • Similarly, the score for each test case should be within a very limited range, so that no single test case is worth a lot more than others.
      1. When some test cases are major outliers and thus much more important, it encourages hard-coding of those cases. You reduce the "effective size" of the data set.
    • I think binary classification is a good idea. This makes it so that each test case is worth the same.
      1. The first option is that the score is the %correct.
      2. The next is the phi-coefficient, which I prefer.
  3. Puzzles whose test set is randomly generated from some problem space.
    • A large test set is needed to overcome the inherit randomness in the scores.
    • A decent scoring statistic, given a large enough number of test cases, is average score.
      1. A "statistical" method is to calculate the standard deviation of the test results and divide it by the square root of the number of test cases to get the standard deviation of your average score. The data set should be large enough such that the standard deviation is small.
    • The author should provide a large list of test cases, as well as the method of generation.
  4. Problems in which the actual test set is not known yet
    • This would occur if the challenge is to predict some future events
    • The author should provide a large amount of historical data
    • At a certain date, submissions are closed. Then, the submissions are judged according to the new data set.
\$\endgroup\$

You must log in to answer this question.

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