-20

tl;dr: I'd like to propose a new tag [programming-challenge], and an unusual type of 'question' that serves as an overview and index to the various contributions/answers. Hence the implied question would be "This is the overview over the solutions and approaches to this challenge, and here are the links to contribution elucidating specific facets. Have I missed anything important?". This might be overly broad under current rules and anyway the style/culture deviates from standard SO format.

Motivation + Explanation

We get a lot of repeated questions regarding solutions for programming challenges like those of Project Euler, SPOJ and numerous other sites. Many of those are from people who are just too lazy to search SO or the 'net; while these people usually get some answer, the average quality tends be meh - the good answers are difficult to find among the accumulated cruft and the many repeated topics about one and the same problem.

This may be in part because there is no [programming-challenge] tag like over on Code Review, or something along those lines. The questions simply get lost in the murderous traffic on SO as a whole and in the most relevant tags.

Also, the average set of answers turned up by the search engine will likely be unsatisfactory for someone who has solved a problem in some way or other and now is curious what the combined wisdom of SO has to say on the topic. Googling is not really an alternative - usually it will turn up some half-assed blog by someone with poor algorithmic and coding skills, with no particular interest in any given problem, and with no particular expertise or ambition to give either a good solution or at least a good overview.

This is actually a strength of Stack Overflow and Code Review: answers often come from people who not only do have a particular interest in the problem at that moment in time, but who actually know what they're doing and want to share their knowledge (and enthusiasm). It's just that these answers are isolated and scattered high and wide.

In bulletin boards a common solution is to maintain the top post (which would be the question here on SO) as an overview and index with links to the various relevant contributions in the thread. This maps nicely to the SO format. A given topic would thus become a knowledge base on the given problem, something that is currently impossible to find anywhere on the 'net (with the exceptions of some rare topics in some of the boards specific to individual challenge sites). This would put some burden on the maintainer of the question to respond with timely edits to accommodate new relevant contributions, but apart from that it would be business as usual.

In particular, individual respondents would treat invidual facets according to their expertise and inclination, just as usual. But the sum total would be bigger than anything found elsewhere on the 'net, as long as the maintainer does a reasonably good job. No one has to be the wiki maintainer with responsibility for everything, no one has to maintain a global index of categories and topics; a maintainer need not care about more than one single topic. The rest would be simply the normal SO infrastructure working as it already does.

Such topics could be recognised (and searched for) by their subject. The general format could be:

"Solution approaches for $(site) $(problem id): $(very brief description)"

E.g.

Solution approaches for SPOJ PRIME1: find primes in a given interval

or

Solution approaches for Euler #16: digit sum of 2^1000

One possible consequence might be the natural growth of subtopics like "Solution approaches for primality testing" and so on, since these would be shared by many challenges and electing one particular programming challenge as the 'container' of that knowledge would be awkward.

Another possible issue is that the choice of description needs some care: mentioning the limit of 1,000,000,000 in the PRIME1 subject could restrict the usefulness of the topic needlessly, but mentioning the 2^1000 for Euler #13 makes sense because that is the basis for some specific approaches (e.g. repeated doubling) and typical solutions are made simple by being tailored to the specific base 2. Saying only '2^x' would require re-mentioning the exponent anyway because it is relevant that 2^x far exceeds typical machine word sizes.

The desired 'singularity' of such topics would be an implicit result of the normal duplicate detection/elimination process, made somewhat easier by the prefix. The subject prefix and the main idea could be mentioned in the description of the hypothetical [programming-challenge] tag, which would automatically be visible to anyone filtering on it (rather than only buried somewhere in the help system).

I guess such a posting could be made 'legally' sort of on topic by appending: "Have I missed anything important?" after the body of the overview, but would such postings be wanted here?

This posting is the result of my failure first to find and - several days and lots of research later - to give some kind of overview for Euler #16, as an answer to one of the many questions about that Euler task. That attempt might serve as an indicator for the kinds of information/knowledge that are expected to accumulate in a 'knowledge base' topic, though curated by different people in separate answers. There is some similarity to what Code Review does, but the focus would be on algorithmics in a largely language-agnostic way, with renderings in specific languages serving merely as examples and for documenting how benchmark timings were arrived at.

EXAMPLE

Here is an example of what the overview/TOC post would look like after being amended to accommodate several individual contributions (which would all be linked from the appropriate phrases):

There seems to be no way of getting the sum of the decimal digits of 2^1000 without computing the actual digits in a base that is some power of 10.

The computation can be done in two fundamentally different ways:

  • native computation followed by radix conversion to get the decimal digits

  • computation in a base that is some power of 10 (decimal digits available without conversion)

    • powering via repeated doubling (base 2 only)
    • powering via repeated squaring (any base, not just 2)

The most important optimisation technique is choosing suitably large 'digits' for the computation and using them without conversion to characters or strings. This also makes the code simpler. Up to 9 decimal digits can be processed in one go with 32-bit integer types, up to 19 with 64-bit types.

Solutions via radix conversion and repeated squaring have comparable performance, which can easily exceed that of naive solutions using builtin big integer types because of the aforementioned techniques. Repeated doubling is only competitive for very small exponents.

Radix conversion and repeated squaring are both O(n^2) and thus quickly run out of steam for exponents much bigger than 10^5. This can be improved to O(n log n) via divide-and-conquer strategies (see GMP's algorithm overview). The performance of squaring can be doubled by recognising that ai*bj == aj*bi if a == b, which cuts the number of necessary multiplications in half.

See benchmarks.

The point is that the top post (a.k.a. question) is a heavily condensed summary of all relevant/significant contributions to the topic, which can be extended if new significant contributions arrive. A mathematically inclined respondent might prove the first sentence wrong, for example.

14
  • 2
    Making your question longer by adding long examples doesn't make it easier to understand. On the contrary.
    – Cerbrus
    May 3, 2016 at 12:48
  • 1
    Please not even more of this SPOJ and CodeChef crap questions. May 3, 2016 at 12:55
  • There are sh*tloads of them out there already and they will probably keep coming regardless - and they can already be nuked under current rules I think. It is the good answers that are lost forever in the mire, unless something is done.
    – DarthGizka
    May 3, 2016 at 13:01
  • @Cerbrus: your answer talked about 'programming courses', so the clarification seemed necessary.
    – DarthGizka
    May 3, 2016 at 13:04
  • DarthGizka, We don't need to add some kind of overview, since the contents of the suggested overview are off-topic for SO.
    – Cerbrus
    May 3, 2016 at 13:08
  • 2
    Nearly all such questions are a waste of space on SO servers and a gross abuse of contributors' time. There is already too much effort wasted on crap. Many such posts are not even worth the effort of reaching for the down/close vote widgets May 3, 2016 at 13:35
  • @Martin: Obviously, the non-existence of a [programming-challenge] tag doesn't keep the garbage from coming - but if such a tag existed then the garbage might be easier to hunt down and eliminate.
    – DarthGizka
    May 3, 2016 at 15:06
  • On SE an executive summary is called "tl;dr"
    – user1228
    May 3, 2016 at 16:29
  • There's Code Golf, but you'll want to check their on-topic and off-topic help center pages or ask on their meta to see if these are answerable on their site. May 3, 2016 at 17:46
  • @Mike: PPCG are about posing & doing challenges; this would be wrong there. It's like SO, just with a high-quality summary as the top item instead of a hapless question. You (in general, not just Mike) trust people with 1.5k rep to have enough categorising ability to create new tags - so trust them with writing a good subject line and and the initial overview for a single knowledge base article. The bar for contributions could be lower, like 500 or 1k (just to keep out low-quality noise).
    – DarthGizka
    May 3, 2016 at 18:26
  • Maybe you could create a new site at Area 51? I just don't see it as a good fit for SO, as there's no single "correct" answer, and the question itself is somewhere in an offsite location, with all of the problems that come with that. May 3, 2016 at 18:32
  • @Mike: the question should be given in concise form at the top of the overview post (copied if brief, synthesised unequivocal summary if not), just like now in regular question. I overlooked that when cooking up the example. The solution space is fairly tightly bounded because usually only one or very few algorithms are applicable; one advantage over the current state of affairs would be that unfounded myths like that the Sieve of Atkin is good for anything (which grow wild on SO, because unchallengeable) could be buried once and for all, unless and until someone actually comes up with proof.
    – DarthGizka
    May 3, 2016 at 18:56

1 Answer 1

10

Stack Overflow is not a help site for programming courses. SO is meant to be a repository of quality questions / answers about programming issues.

Tags like project-euler got burninated for that reason. Those questions were often along the line of: "Please solve this for me: <Euler question>".

"How do I solve this challenge" Is not a programming issue, the issue is a lazy programmer. Those questions are generally off-topic for SO.

The "Too broad" close reason is a good fit:

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.

(Emphasis mine)

13
  • Not everyone who does programming challenges is a beginner taking part in some programming course. Not every programmer is an expert in all fields of algorithmics. While the motivation for doing challenges may partly be motivated by picking up a new language, the focus while solving a problem is on algorithmics. The question is not "How do I solve this challenge"; it is "What are other approaches?", and "What is the lie of the land?". Textbooks and wikipedia tend to be both impractical and out of date.
    – DarthGizka
    May 3, 2016 at 11:38
  • 1
    "What are other approaches?", and "What is the lie of the land?" Are both typically too broad. They are not suitable SO questions.
    – Cerbrus
    May 3, 2016 at 11:39
  • That's why I came here instead of floating trial balloons.
    – DarthGizka
    May 3, 2016 at 11:40
  • Then what exactly are you trying to achieve here?
    – Cerbrus
    May 3, 2016 at 11:41
  • 2
    the difference as always is scope and clarity of the question, not where the question came from. So a blanket " we don't want questions asked on programming contest sites" is a terrible rule because it conflicts with our "we want reasonably scoped and well asked questions." There's a definite Venn diagram where good questions can inhabit both worlds. May 3, 2016 at 11:44
  • @GeorgeStocker: Good point, I'll try to clarify this answer a bit.
    – Cerbrus
    May 3, 2016 at 11:48
  • I'm trying to find a way to unite the scattered gold nuggets about a specific challenge under a single roof; to make them easily findable and to provide a place where they can be posted without getting lost. Outside of our specific fields of expertise we all amateurs and need the guidance offered by the best. Hence the allure of programming challenges even after 30 years in the trenches...
    – DarthGizka
    May 3, 2016 at 11:50
  • Okay, while I can sympathize with that, I'd argue that these "challenge questions" are off-topic on SO. Maybe they will have a place in the documentation feature.
    – Cerbrus
    May 3, 2016 at 11:53
  • 4
    @DarthGizka I understand what you're trying to do, and we already have something like that at puzzles.stackexchange.com or codegolf.stackexchange.com; but as far as Stack Overflow goes; we try only to segment based on language; not on meta tags like "this is a programming challenge". Stack Overflow isn't the place to go to find a programming challenge, although you could go here for help with one. May 3, 2016 at 11:54
  • 4
    ... provided the help you need isn't "solve this for me", but something like "I can't figure out this specific aspect after trying X"
    – Cerbrus
    May 3, 2016 at 11:55
  • @Cerbrus yeah, but as you know, it's nearly always like that. That, or some ridiculous set of brute-force nested loops and 'takes too long, plz fix' :(( May 3, 2016 at 13:34
  • @Cerbrus umm... I think so:) May 3, 2016 at 13:37
  • I don't quite get what you're trying to say, @MartinJames.
    – Cerbrus
    May 3, 2016 at 13:38

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