Scoring that rewards useability

Question

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?

Answer 1

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 code-golf (or atomic-code-golf) and fastest-code (or fastest-algorithm), instead of trying to create a hybrid.

Answer 2

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, fastest-code and fastest-algorithm are better alternatives for this, and if you really want to have things balanced, you could just write a code-challenge 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.

Answer 3

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.