6
\$\begingroup\$

To cite a recently sandboxed challenge by l4m2:

Solution win if there's no strictly better solution, aka. no solution that take less or same amount of items in mapping table, less or same amount of instrucions, and at least one of amounts of items and instructions is less.

I understand this statement as

A solution is measured in two ways: the number of items in the mapping table, and the number of instructions. A solution wins if no other solution is strictly better; solution A is strictly better than solution B if A is strictly better in one measure and at least as good in the other, i.e. (A[1]<B[1] && A[2]<=B[2]) || (A[1]<=B[1] && A[2]<B[2]) (assuming lower score is better in both measures).

I'm worried about this winning criterion because it permits many "winners" and we don't know which measure to primarily optimize for. The worst part is that, given an existing "winning" solution, one can tweak a little bit and post another "winning" solution, and then we have "another winner", not "the latter winning against the former".

On the other hand, l4m2 claimed that multiple winners is not a problem because we already have something like "shortest code in each language wins", and we can get a collection of, say, "an exact bound of table size for each instruction count".

Is the proposed winning criterion valid?

Related: Why do we have objective winning criteria?

\$\endgroup\$
8
  • \$\begingroup\$ Not a complete answer, but we already have some challenges with similar winning criteria. In that particular challenge there's a "combining function" (L, E) -> 2*L+E which determines which one is better if one has better L and worse E and another has better E and worse L; \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 9:35
  • \$\begingroup\$ (the solution with smallest L and huge E ended up getting the most upvotes (and probably the most down votes too, I don't know) --) \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 9:37
  • \$\begingroup\$ In some other cases, it can be hard to determine a good combining function, and may even unnecessarily penalize a possibly-interesting solution. On the other hand, there will not be 1000 submissions because assumes that the problem can be solved with -- say, table size 20 and lookup size 20, then there will be only at most 40 solutions. Also it's not as trivial as you think to tweak an existing solution, because (as far as I can see) you can't easily reduce the size of lookup table just by increasing the number of instructions, and even removing one instruction translates to a \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 9:43
  • \$\begingroup\$ huge increase of the table lookup size (as far as I can see, you can replace two instructions that uses A and B entries respectively with one instruction with at least AB entries if they are somehow related, AB is much larger than A+B) \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 9:45
  • \$\begingroup\$ given an existing "winning" solution, one can tweak a little bit and post another "winning" solution this always happen when porting others' answer to different language \$\endgroup\$
    – l4m2
    Jun 16 '20 at 9:46
  • \$\begingroup\$ (regarding the comment above: I think Bubbler was afraid that if the range of the score is about 10^6, there would be about 10^6 possible best answers, while for languages there are only about 100 of them. But as I've demonstrated above, there isn't that many answers -- for this particular challenge at least) \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 9:50
  • \$\begingroup\$ FWIW, I always thought "shortest code in each language wins" isn't the real winning criterion (shadowed by the tag code-golf), but just a nice note to prevent(?) users from getting discouraged by the golfing languages. It might be just me though. \$\endgroup\$
    – Bubbler
    Jun 16 '20 at 12:46
  • \$\begingroup\$ Thinking about it a little bit more, I think that either that a solution doesn't have a trivial tweak (like the /// answer in the Moby Dick question), or it can be parametrized (like the perl answer that uses arithmetic coding). In either case there's no way to post "boring but win" answers. \$\endgroup\$
    – DELETE_ME
    Jun 16 '20 at 14:13
2
\$\begingroup\$

Yes, it is valid

After having some discussion with multiple users, I now feel like it should be a valid winning criterion.

The "winning criterion" is there mostly to motivate the answerers to optimize the code further. While the proposed winning criterion does not give one objective to optimize for, one can choose one of two objectives (or both at once), so that the new answer strictly beats the previous one.

@tsh's is probably not a good fit here because the relationship between \$O(VE^2)\$ and \$O(V^2 E)\$ can be resolved by specifying the relationship between \$V\$ and \$E\$ in the challenge (e.g. by saying \$E=O(V \log{V})\$ which makes \$O(V^2 E)\$ superior); IIRC lack of such relationship is considered unclear.

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

\$\require{begingroup}\begingroup \newcommand{xx}{\color{red}{\textsf{x}}} \newcommand{oo}{\color{green}{\textsf{o}}} \newcommand{slash}[2]{ #1\overset{\LARGE\backslash}{\phantom{.}}\overset{\Large #2}{\phantom{l}} } \$ (this is not really an answer, rather it's a way to show what else can be done if the consensus is that it is not allowed), given the current situation that people don't like for some reasons (*); personally I think that even if some people don't like it, it causes no harm (unlike what would happen if challenges without winning criteria are posted) and doesn't have any reason to be prohibited)

Assume that in the original challenge, there are two positive-integer scores A and B, which should be minimized, and in a reasonable program, they both does not exceed some easy-to-calculate threshold -- in the example above, 5 is used.

Solution 1

Parametrize the solution space. For example, programs have to minimize A+2B.

This is not very interesting, because there can be interesting solutions that trades A for very good B, or vice versa.

Solution 2

Assume that if a solution with a score (A, B) is possible, then (A+1, B) and (A, B+1) are both possible. (i.e., smaller scores are strictly better)

Assume that someone have a solution with score (4, 2). So the solution can be represented with this table

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \xx & \xx & \xx \\ 3 & \xx & \xx & \xx & \xx & \xx \\ 4 & \xx & \oo & \oo & \oo & \oo \\ 5 & \xx & \oo & \oo & \oo & \oo \\ \end{array} $$

Where \$\xx\$ denotes impossible scores, \$\oo\$ denotes possible scores.

Obviously, better solutions have less \$\xx\$. So let the score of a submission to be the number of \$\xx\$ in the table, assume that both coordinates are constructed from 1 to 5. The score of this solution would be 17.

Now assume that someone else have another solution with score (2, 3). The table would be:

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \oo & \oo & \oo \\ 3 & \xx & \xx & \oo & \oo & \oo \\ 4 & \xx & \xx & \oo & \oo & \oo \\ 5 & \xx & \xx & \oo & \oo & \oo \\ \end{array} $$

and the final score would be 13.

Observe that both answers can be combined:

$$\begin{array}{c|ccc} \slash{A}{B} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \xx & \xx & \xx & \xx & \xx \\ 2 & \xx & \xx & \oo & \oo & \oo \\ 3 & \xx & \xx & \oo & \oo & \oo \\ 4 & \xx & \oo & \oo & \oo & \oo \\ 5 & \xx & \oo & \oo & \oo & \oo \\ \end{array} $$

and it results in a better score, 11.

This is a simple relatively-efficient implementation of the score calculation algorithm: Try it online! (input format: first line: dimension of the board, remaining lines: the reachable points, any format is accepted)

Of course, with this, the score of the answers posted later will always be strictly better than the score of the older answers. Nevertheless, it still encourages creativity (to find good answers), the same thing as what winning criteria does.

Besides, we already have .

(*): nobody who downvoted left any comment. \$\endgroup\$

\$\endgroup\$
0
\$\begingroup\$

Allow multiple winners

We already had a tag .

Consider there is a challenge which input a graph \$ G(V, E) \$ and output something. The big-O notation may be measured in both V, and E. Someone may come up with an algorithm \$O(V^2E)\$ while others provide \$O(VE^2)\$ algorithm. Without given the assumption of the relation of \$V\$ and \$E\$, there is no way to tell which algorithm is better.

The above example not only happened when writing challenges on this site. But also happened in the real world. Most real-world libraries provide these functional by including both algorithm so caller may chose which one to use. Both algorithm could be considered good enough in such case.

We should also allow multiple winners as they are both good but no one better.

\$\endgroup\$

You must log in to answer this question.

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