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:
- Area of a Self-Intersecting Polygon (10 second limit)
- Fraction to exact decimal (10 second limit)
- Compute the inverse of an integer modulo 100000000003 (30 minute limit)
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. fastest-code 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:
- Are you/we happy with the example challenges listed above as they are currently? Or...
- Should we have a new tag for this type of question? Or...
- Is there another better solution?
For what it is worth, I vote for 1 but I wouldn't mind if people wanted 2.