This answer is a fairly extreme example. For the largest input it would create an array with 1.048576e+26 elements which is not going to fit in RAM anytime soon (maybe not even physically possible).

However given enough time and memory it would reach the answer eventually

In the case the the practical answers are not able to be made shorter, how should a winner be chosen?

There are already questions on meta about explicit extra conditions, but I am asking about implicit limitations here.

  • \$\begingroup\$ Here's another example for you. \$\endgroup\$
    – smci
    Commented Jan 21, 2012 at 10:33

3 Answers 3

  • If the question is 'sort a list', slow solutions are fine.
  • If the question is 'sort this list of 1000 elements', and the PC seems to run forever, the poster has to make plausible, that he produced the solution with his program.
  • I would prefer in general precise questions. But in general, performance isn't the issue, but code size is.
  • 3
    \$\begingroup\$ This makes sense. If there is a test case that takes 20 million years to run on your computer you shouldn't post the the code as an answer until it has completed running. This means it's still reasonably practical to have code that takes a few hours or even days to run, but it's unlikely that someone would run something for longer than that for the sake of a code-golf \$\endgroup\$
    – gnibbler
    Commented Apr 13, 2011 at 6:10

I tend to judge such issues subjectively.

For a run of the mill, not particularly interesting approach, I wouldn't vote for a solution that won't fit in a modern desktop's ram or would take days to do something modest.

But for something really clever, I'd probably cut some more slack.

But there have to be limits.

Note that I probably wouldn't down vote even then. I just won't vote for them and would accept them if it was my question.


Mostly I'd say it's something the asker should define, preferably when the question is asked.

As for combinatorics, brute force solutions will almost always be the shortest ones, allowing them really just ruin the mathematical aspect of the question.

  • 1
    \$\begingroup\$ I agree that it should be defined, but explicitly "no brute force" rather than defining inputs to make BF impractical \$\endgroup\$
    – gnibbler
    Commented Mar 31, 2011 at 17:54
  • 2
    \$\begingroup\$ Note that BF tends to be tricky to define strictly. \$\endgroup\$
    – J B
    Commented Apr 2, 2011 at 7:56
  • \$\begingroup\$ This question took a good approach. Rather than defining brute force, he gave a large example (N=99) which is impossible at O(2^N). Unfortunately, he made that clarification after several brute force answers were present (including mine) and voters didn't distinguish between them. \$\endgroup\$ Commented Apr 20, 2011 at 17:56

You must log in to answer this question.

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