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?

  • \$\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\$ – user202729 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\$ – user202729 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\$ – user202729 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\$ – user202729 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\$ – user202729 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\$ – user202729 Jun 16 '20 at 14:13

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.


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.


You must log in to answer this question.

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