13
\$\begingroup\$

I like to ask code-golf questions but I typically don't want to see brute force solutions. The challenge I like to pose is to golf any reasonably fast solution for a (possibly hard) problem that will actually terminate in a reasonable amount of time. Examples of such questions (not all by me) include:

Some people don't like the code-golf tag to be used when there is also a time limit.

I on the other hand am very fond of this sort of question as I think it makes for an interesting sort of challenge.

Why not just use fastest code?

Fastest code questions are quite different. First of all the lowest level language tends to win so it's really a race between C/C++/Rust/nim and maybe Java. They are also a pain as you have to run everyone's code. A time limited code-golf on the other hand balances the fast running speed of verbose languages (such as C etc.) against the need for compactness (which also benefits languages such as Jelly).

At a more basic level, the type of questions I am talking about ask you to minimize code size subject to a restriction on running time. of course doesn't do anything of the sort. We could also imagine questions that ask you to minimize running time (as in fastest-code) subject to a maximum code size, but that is for a different discussion.

Why not just use restricted-complexity?

The restricted-complexity tag specifies an asymptotic time complexity. For practical coding this is potentially something that can't be computed (e.g. integer factoring) or is not practically relevant for the problem sizes being considered. It also excludes lots of talented people who are not used to this sort of math. Sometimes it's just very hard to work out the asymptotic time complexity of some code you have written. As a simple example, what if the running time of your code depends on the unknown distribution of the primes for example. Questions that just allow you to run it and see how fast it is seem to have some value.

Fundamentally, restricting the asymptotic time complexity of code and specifying a maximum running time are just two very different things with each having its place. There are plenty of algorithms with worse time complexity which are faster in practice (linear programming is a great example where the simplex algorithm has exponential worst case complexity but is often the fastest method in practice) and if you have specific test cases in mind this is particularly true.

If there is a time limit doesn't it have the same problems as fastest-code?

The time limits of the sort I am discussing are set to be sufficiently loose that any sensible implementation of the right algorithm will fit into it. For example, where I have set a 10 second limit, there is a python solution that completes instantly. The intention is really just to exclude brute force solutions.

In order to make the question I am asking clear, here are two options to choose from:

  1. Are you/we happy with the example challenges listed above as they are currently? Or...
  2. Should we have a new tag for this type of question? Or...
  3. Is there another better solution?

For what it is worth, I vote for 1 but I wouldn't mind if people wanted 2.

\$\endgroup\$
16
  • 3
    \$\begingroup\$ Just my two cents, I think giving a maximum order notation, and tagging the question as restricted-complexity is the better option. Its much less ambiguous than time limits and doesn't unfairly penalize languages with slow implementations. I feel if your intention is just to block brute forcing, this is absolutely the best way to go about it. Time limits are two ambiguous and relative to practically enforce and I feel as if you are putting yourself through more trouble than is needed, while a very nice alternative exists. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 7, 2017 at 14:28
  • 1
    \$\begingroup\$ @WheatWizard How would you do that with integer factorization or discrete log for example where no one has proved the running time of the known fast algorithms? Also, if you only want it to be fast only on the test cases then the worst case running time isn't relevant. \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 14:39
  • \$\begingroup\$ As I see it you want to ban the brute force solution. You don't need to know the order notation of an algorithm to know that its better than the brute force solution. The order notation for those algorithms is not known but we do have upper bounds. If you don't like the worst case approach (I don't see why it needs to be practical, but ok) you can use a different order notation, like average or worst run time. If your problem is, as you stated, that you want to exclude brute force solutions, restricted complexity does that to a t. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 7, 2017 at 14:44
  • 1
    \$\begingroup\$ @WheatWizard I take your point. The only issues are a) that one then has to guess what the maximum asymptotic complexity is that you want to exclude and b) the answerer has to know the asymptotic complexity of their code. \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 15:11
  • \$\begingroup\$ @Wheatwizard Is your suggestion of worst run time the same as the suggestion in the question? \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 16:01
  • \$\begingroup\$ @WheatWizard Sorry for being unclear. I was referring to "[...]you can use a different order notation, like average or worst run time" If that is measured in seconds and is used to exclude answers that are too slow, that seems to be exactly the method used in the three challenges linked in this question. \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 16:09
  • \$\begingroup\$ Ah that should have said best not worst. I see how that was confusing \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 7, 2017 at 16:10
  • \$\begingroup\$ @WheatWizard Sorry but I still don't understand. What does measuring best run time mean? Are we still running the code, seeing how long it takes and if it is more than 10 seconds say, saying it is too slow? \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 16:44
  • \$\begingroup\$ order notation can be measured in a number of ways typically it is done so in worst case, but it can also be measured in best case or average case. Best is very rarely used for good reason. I'm just saying there are a lot of options available when choosing a complexity (O,Ω,Θ) all you have to do is select the one that captures what you want to measure. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 7, 2017 at 16:57
  • \$\begingroup\$ Banning brute force can just be a rule, e.g. "Brute force solutions doing X are banned". \$\endgroup\$
    – Erik the Outgolfer
    Commented Jul 7, 2017 at 17:56
  • 3
    \$\begingroup\$ @Eriktheoutgolfer The problem is that it's hard to define brute force. There are often many dumb ways to solve a problem. \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 17:58
  • \$\begingroup\$ Brute force seems decently defined to me. \$\endgroup\$
    – Poke
    Commented Jul 7, 2017 at 18:36
  • \$\begingroup\$ @Poke It's not so simple. This is an example of an answer I would like to exclude codegolf.stackexchange.com/a/129731/9206 \$\endgroup\$
    – user9206
    Commented Jul 7, 2017 at 18:37
  • \$\begingroup\$ To me, that's very obviously a brute force algorithm with a small quality of life update. It's like checking to see if a list is sorted before doing a bubble sort... it's still a bubble sort. \$\endgroup\$
    – Poke
    Commented Jul 7, 2017 at 18:52
  • 4
    \$\begingroup\$ Code golf is a winning criterion (a scoring mechanism). A time limit is a requirement (it's met or it isn't - it can't be used for distinguishing answers by score). A new winning criterion tag doesn't make sense for something that isn't a winning criterion. If there were a tag for time-limited, the challenge would still need to be tagged code-golf since that's how the score is measured. \$\endgroup\$
    – trichoplax is on Codidact now
    Commented Jul 8, 2017 at 18:21

2 Answers 2

Reset to default
19
\$\begingroup\$

PPCG has two types of tags: Winning condition tags, and everything else. For this type of challenge, the winning condition is clear: .

However, we should still have a tag to indicate what's going on in this type of problem, so that people know what to expect when looking at the question in the list.

I suggest creating the tag , parallel to , and using it to tag such questions. I'm open to suggestions for other tag names.

\$\endgroup\$
2
  • \$\begingroup\$ I would vote for that. What is the process to get a new tag approved? \$\endgroup\$
    – user9206
    Commented Jul 11, 2017 at 7:58
  • 3
    \$\begingroup\$ @Lembik There's no process. I went and made the tag, and also gave it a description. I stuck it on the modular square root challenge. Feel free to put it on all of the challenges you think it's appropriate on. \$\endgroup\$
    – isaacg
    Commented Jul 11, 2017 at 8:30
8
\$\begingroup\$

Trichoplax has already said in comments what I was going to reply, but since it belongs in an answer rather than in comments:

If the winning criterion is "shortest answer in bytes" then it's . It's as simple as that. If you want a meta-tag to indicate that the validity criterion includes a timed component, that's a different question.

\$\endgroup\$
2

You must log in to answer this question.