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 toO(n log n)
via divide-and-conquer strategies (see GMP's algorithm overview). The performance of squaring can be doubled by recognising thatai*bj == aj*bi
ifa == 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.
[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.