0
\$\begingroup\$

In my dream world, I would rather have code challenges generate a code that's actually useful in the real world, a code that makes its way to be an idiom, to be used in real world projects, and put in a language's standard library.

The prime criterion for a piece of code to be re-used is its readability, then complexity. Additionally, it's important that the code makes sparing use of third party libraries, as library writers and commercial language users are usually reluctant to burden their code with dependencies.

For this end, I propose the following scoring system:

  1. Every language has its winner, no competition between languages.

  2. The score is counted against the code. That is, the less the score -- the better.

  3. The scoring rewards terseness, but in a sense of lexemes rather than characters, so readable names and nice layout do not impair the code. I believe lexemes are a well defined concept for any language. For a high level language, it's any unit of syntax, an identifier, or a literal. For machine code, it's a machine instruction. Clearly higher level languages with less visual noise are at advantage here, but we shall not have direct competition between different languages.

    1. For every lexeme that's built in the language, add 1 point.
    2. For every lexeme found in standard libraries for the language, add 2 points. If a language doesn't have a prevalent standard library, no lexeme is considered as a part of standard library for that language.
    3. For every lexeme that's in some other published library, add 10 points.

    The statements that bring the necessary lexemes into scope are not counted.

  4. The scoring encourages efficient algorithms. For simplicity, the largest of time and space complexities is considered, so an algorithm that's balanced between time and space is scored more favorably than a specialized algorithm that wastes one for the sake of maximizing the other.

    The author of the code must attribute complexity to the algorithms they have explicitly encoded, and justify their attribution. Anyone who believes the attribution of complexity to an algorithm is justified insufficiently or wrongly, is encouraged to speak up, and the issue clarified until there are no more objections outstanding.

    In this way, builtin or library procedures can be of any complexity (I assume the authors of the library are incentivized to choose the algorithms as best they can, and, in any case, providing better replacements for library functions is not the point of our exercise), but adding complexity on top of them is discouraged.

    If a library of a language is closed source, official documentation may serve as justified attribution of complexity. (Again, I presume the authors of the documentation are incentivized to be honest and state the correct complexity.) If the complexity is not documented, it is considered unknown and this is as bad for the score as it gets.

    1. For every explicitly encoded algorithm of logarithmic complexity, add the exponent over logarithm + 1. (That is, for O(log n) add 2 points, for O(log^2 n) add 3 points.
    2. For every explicitly encoded polynomial algorithm, add as many points as its exponent * 2 + 1. (That is, for O(n^2) add 5 points, for O(1), one point.)
    3. For every explicitly encoded sub-exponential algorithm, add 8 points.
    4. For every explicitly encoded exponential or factorial algorithm, add 10 points.
    5. For algorithms of compound complexity, add scores together. (For example, O(n log n) is 5 points.)
    6. For algorithms of unknown complexity, add 11 points. This is as bad as it gets, because one must know one's algorithms' complexity.

Can this work?

\$\endgroup\$
  • \$\begingroup\$ Is it objective? \$\endgroup\$ – user202729 Jan 28 '18 at 10:36
  • \$\begingroup\$ Well, if you can define it so that it holds for all the >400 languages on TIO, fine. \$\endgroup\$ – user202729 Jan 28 '18 at 10:36
  • \$\begingroup\$ What about "unknown complexity"? \$\endgroup\$ – user202729 Jan 28 '18 at 10:38
  • \$\begingroup\$ (1) already applies, actually. \$\endgroup\$ – user202729 Jan 28 '18 at 10:41
  • 2
    \$\begingroup\$ Complexity already has a really nice solution: If complexity matters to an OP, then place restrictions on the complexity, not bonuses. \$\endgroup\$ – Nathan Merrill Jan 29 '18 at 18:55
  • 2
    \$\begingroup\$ There's also another solution for scoring lexemes: Limit the competition to a single language. For that language its far easier to count lexemes (and you are able to ban stuff like eval() easier). (This is atomic-code-golf) \$\endgroup\$ – Nathan Merrill Jan 29 '18 at 18:59
  • \$\begingroup\$ @NathanMerrill And you will get many downvotes... \$\endgroup\$ – user202729 Jan 31 '18 at 2:59
  • \$\begingroup\$ @user202729 I disagree. You get downvotes for arbitrary language restriction. When the language restriction is actually fundamental to the challenge, people go along with it. \$\endgroup\$ – Nathan Merrill Jan 31 '18 at 3:28
  • \$\begingroup\$ @NathanMerrill Isn't "you can't use this language because I don't know it and can't count number of lexemes" arbitrary? \$\endgroup\$ – user202729 Jan 31 '18 at 3:32
  • \$\begingroup\$ @user202729 When counting the lexemes in a particular language becomes the scoring mechanism, it is a fundamental part of the challenge. An atomic-code-golf in Python requires drastically different solutions and golfing than one in Brain-Flak. \$\endgroup\$ – Nathan Merrill Jan 31 '18 at 4:12
  • \$\begingroup\$ That said, if you're banning all languages except for a few of them, then I agree, that's likely to be closed. Any language-specific challenge should be centered around one language. \$\endgroup\$ – Nathan Merrill Jan 31 '18 at 4:13
12
\$\begingroup\$

In my dream world, I would rather have code challenges generate a code that's actually useful in the real world, a code that makes its way to be an idiom, to be used in real world projects, and put in a language's standard library.

The first and foremost problem with this is that real-world solutions require real-world problems, which usually aren't a good fit for our site.

  • You shouldn't override the defaults, but they're made for competing, not real-world problems. In practice, you won't be able to use a function that reads from STDIN and prints to STDOUT; you need one that returns a value.

  • Portability costs, whether it's bytes or lexemes. As long as program length is part of the score, writing non-portable code will always be encouraged. This is especially true in C, where relying on undefined behavior is a common code golf practice. A challenge that enforces portability would have to specify exactly how portable solutions must be.

  • We don't like input validation or complicated number types.

  • Many languages we like to use on PPCG aren't meant for real-world usage in the first place.

That said, there are also numerous problems with your proposed scoring.

  • Simply counting lexemes is broken. Any languages in that eval and strings count as 1 point each, eval("<actual code here>") is a solution scoring 2 points.

  • Rewarding a lower complexity may make sense for some problems, but since the complexity is only an upper bound, O(n) can very well be slower that the higher-scoring alternatives.

    Other approaches may not even fit into your scoring model. For example, there are sorting algorithms that depend both on the length of the list and the largest number in it, so if n is the length of the input, there's no f that makes the complexity O(f(n)).

  • Your balance between length and complexity may work for one problem, but certainly not all. A penalty of only 2 points for turning an O(n) algorithm into an O(n²) algorithm will prevent a clever golf or two, but it won't make me rethink my entire approach.

  • Complexity analysis works well for algorithms, not so much for implementation. A function that can take only 64-bit integers as input is always O(1), no matter which algorithm it implements.

In general, any scoring mechanism that combines different aspects (e.g., length and speed) of the solutions needs to be tailored exclusively to that challenge if you want it to work.

In my opinion, good scoring mechanisms are simple, so I'd stick to (or ) and (or ), instead of trying to create a hybrid.

\$\endgroup\$
  • \$\begingroup\$ "For example, there are sorting algorithms that depend both on the length of the list and the largest number in it, so if n is the length of the input, there's no f that makes the complexity O(f(n))." Usually computational complexity is measured with n being the size of the input in bits, in which case f should exist. \$\endgroup\$ – Wheat Wizard Jan 29 '18 at 0:00
  • \$\begingroup\$ Should for out site not rather read either for the outside or for our site? \$\endgroup\$ – Jonathan Frech Jan 31 '18 at 22:37
  • \$\begingroup\$ @JonathanFrech The latter. Fixed. \$\endgroup\$ – Dennis Jan 31 '18 at 22:52
6
\$\begingroup\$

It's complicated...

There are a couple of reasons why I would vote against this proposal (in ascending order of importance):

  • This makes assumptions about language features, which isn't desirable at all. Not all languages have the concept of "Standard Library" or "Library" in general, and it might be hard to draw the line in the sand as to whether a submission uses these features or not. This might disadvantage certain languages or classes thereof.

  • It's hard to score the program – You have to analyse each "lexeme" and determine its complexity, and there might appear some disagreements regarding that (e.g. when using built-ins in closed-source programming languages like Mathematica).

  • In my opinion, and are better alternatives for this, and if you really want to have things balanced, you could just write a with a special winning criterion that advantages implementations that are both time and memory efficient. This has the advantage of not having to write a fancy scoring algorithm and is also more objective (depending on how you'd write the challenge).

  • How would you objectively define a "lexeme"? Because different languages have different paradigms and syntaxes, I find it hard to come up with an universally accepted definition.

  • General programming questions might invade the site. Everyone seeking programming help could be able to post it under this tag to make it on-topic. And after all, this is not a Q&A site.

\$\endgroup\$
  • \$\begingroup\$ I added some clarifications. Maybe there will be less reasons now? \$\endgroup\$ – Ignat Insarov Jan 28 '18 at 11:57
0
\$\begingroup\$

In my dream world, I would rather have code challenges generate a code that's actually useful in the real world, a code that makes its way to be an idiom, to be used in real world projects, and put in a language's standard library.

I'm not entirely sure what you mean by "makes its way to be an idiom", but note that for the other practical purposes you mention the licensing of code on this site may not be ideal. Stack Exchange has attempted to resolve this issue, but the way they went about it caused much kerfuffle and ended up being put on ice.

Note that in a site-specific discussion of that proposal I did bring up one case of code I wrote for a PPCG question which might have practical use. You could look to that question for inspiration.

\$\endgroup\$

You must log in to answer this question.

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