14
\$\begingroup\$

(Sorry this is long. I tried to gather many examples, and honestly I would have liked to include more.)

Background

The tag captures many different kinds of creative challenges that are not covered by . One frequent feature is asking for what I might call an artifact—or what one might call a witness for certain applications in computer science. For example, one might ask for an input to a program that causes some behavior, or for the output of a hard-to-compute process, or just a witness of some property.

It's apparently a common concern whether such challenges are on-topic for the site, but luckily we already have a meta post that addresses this issue. The aptly-named meta post "Objective computational challenges without “code”" has a consensus answer that "We should allow computational challenges of all sorts".

Examples with moderation

Nonetheless, questions of this kind are routinely closed (or put on hold) as off-topic. I've collected some instances, together with a history:

  • Thwart Lepton compression asked for a JPEG that compresses poorly. The question was closed (with three moderators among the votes), prompting the meta post mentioned above. The question was re-opened (with two of the same moderators from before) after the question was changed to require a program that outputs a JPEG.
  • Most Populated WordSearch asked for a grid of letters. The question was closed, a meta question was asked, and the question was re-opened. The consensus seemed to be that the post should be downvoted instead of closed, and so until recently it had a negative score.
  • Generate the best boggle board you can [dead link] also asked for a grid of letters. The question was closed and the user left the site for a while. Best Scoring Boggle Board was asked by another user and presumably kept open because it forbade hard-coding the answer? The first user returned to ask Find The Wordiest Combination Lock, which was spared from closure despite essentially asking for an artifact in the same way.
  • Can a neural network recognize primes? asked for a neural network. The post was closed ("unclear what you're asking"), but re-opened after "neural network" was narrowly defined.
  • Create a uniquely solvable crossword ... without clues [closed] asks for a crossword grid (no letters). The question was put on hold, after which it was edited to require code with every answer. Nonetheless, it was automatically closed after five days, in part because thus far no one has acknowledged the existence of the meta post mentioned above.

Examples without moderation

Here are some other questions that did not have moderation activity but are of similar type:

What is a "computational challenge"?

A persistent issue in the moderation discussion for these questions is whether the challenge is "about programming puzzles" / a "computational challenge". How can we help clarify these decisions?

"Programming languages"

One possible criterion is whether the answer is in a (perhaps non-obvious) "programming language". For example, one may say that Conway's Game of Life "is a well-defined computational model which is Turing complete". As such, configurations in the Game of Life are programs in themselves.

Unfortunately, this criterion is tricky to apply and people get it wrong. While the Game of Life was explicitly designed with the intention of being Turing complete, actually demonstrating this fact is highly nontrivial and took many years. What are we to do in the intervening years where the status of this conjecture is unknown? (The question is not merely hypothetical. For example, the Esolang wiki page for Bubblegum says that "While Bubblegum is Turing complete, programs with non-constant output are hard to write." In reality, it is not known that one can even write more than a single non-constant program in Bubblegum.)

Luckily, we have an important meta post to guide us, defining a programming language: it must be able to add natural numbers and test primality. Even so, the criterion is nontrivial to apply. For example, the book "Games, Puzzles, and Computation" by Robert A. Hearn and Erik D. Demaine (the former's thesis) argues that "games should be thought of as a valid and important model of computation, just as Turing machines are". This perspective (which incidentally includes the Game of Life as an example) would conclude that many puzzles are programming languages. For example, any NP-complete problem (like crosswords or minesweeper) can encode any problem from NP, and so in fact can go further than testing primality by even factoring.

A similar sentiment is expressed in the meta post regarding proof golf, namely “let's not call something "not programming" for not looking like a typical programming language”. Incidentally, the game in Get Two From One strongly resembles the main game in "Games, Puzzles, and Computation", which is called "Constraint Logic"/constraint graphs. Different versions of this logic encode different complexity classes/computational models, from polynomial time to undecidable.

Relationship to computer science theory

Another motivating concern might be theorems from computer science. For example, part of the justification for proof golf is that "the Curry-Howard correspondence, aka the proofs as programs interpretation, gives a formal mathematical equivalence between proofs and programs".

As another example, "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Michael Garey and David S. Johnson is the most-cited reference in computer science literature, and the theory of NP-completeness is one the most-taught parts of computer science theory. Garey and Johnson note that "CROSSWORD PUZZLE is NP-complete". Does that mean that crossword puzzles are more likely to be on-topic?

Neural networks also have a shiny theorem, the universal approximation theorem. While this doesn't put them (ordinary, feedforward/non-recurrent nets) in the same class as "Turing-complete", it does mean they can approximate any function on a compact subset of real space. This is analogous to the functional completeness of NAND in the context of circuits. This latter theory prompts questions like Build a multiplying machine using NAND logic gates.

As a follow-up, one might ask whether it matters whether the theorem in question actually applies. For example, the Curry-Howard correspondence does not mean proofs in very weak systems correspond to a Turing-complete programming language, or even a programming language as defined above. For example, propositional logic is completely decidable (ie, not Turing complete), using the straightforward (but not historically obvious) technique of truth tables. Does that mean that (A → B) → (¬B → ¬A) is off-topic? The consensus meta opinion is "proof golf questions are on-topic", and indeed the Curry-Howard correspondence is a rich source of inspiration to answer literally that question.

For the second example, instances of Garey and Johnson's CROSSWORD PUZZLE provide both a crossword grid and a word list ("dictionary"). If the word list is fixed, then the puzzle need not be NP-complete. Nonetheless, experience shows that with a sufficiently rich word list, it's very likely that filling crossword grids is NP-complete. As an example of a concern raised above, does it matter that this is not known for a particular word list (with rigorous proof) at the moment?

Relationship to programming culture

Another thing that might make these questions on-topic is that they deal with topics that are central to the culture of computer science, of programming, or of code golf. For example, many programmers have played with Conway's Game of Life. People sometimes even claim (falsely) that "since 1970, more computer time worldwide has been devoted to the Game of Life than any other single activity". At the very least, some people started programming and perhaps their career in computer science due to the Game of Life.

(Also, does this mean that topics that are popular but not exclusively among programmers or in a computer science context are less likely to be on-topic? For example, crosswords are much more well-known in the general population than Conway's Game of Life. The situation is complicated a bit by the fact that some people like all sorts of puzzles, including both crosswords and code golf. Similarly, gerrymandering is a hot political topic. How does that affect questions like Gerrymandering with Logic Gates, which is an "ordinary" question, but plausibly could have asked for a single circuit?)

Along the same vein, neural networks are currently very widely-discussed, and many software engineers use them in practical applications. Does that mean that exploring the limits of "machine learning golf" makes questions about neural networks more appropriate here? One might be hesitant in saying "yes" to some of these questions, but I do think it's likely that culturally-relevant topics (to programming culture) are much less likely to be closed as "off-topic".

Difficulty

Does it matter how difficult it is to make a submission? What if the submission itself does not require any code, but it is probable that the best solutions will be found using significant programming? (That is, we could measure "difficulty" here by simply considering coding time.)

For example, Build a working game of Tetris in Conway's Game of Life required an enormous amount of what could only be called software engineering, involving a team of multiple people, even though in principle it could have been solved by a single person scribbling in a paper notebook. Some comments on the answer to the meta post above regarding te JPEG challenge wrestle with this question: "If the optimal JPEG was likely to be found by hand, would you consider the challenge on-topic?"

In some challenges, like Most Populated WordSearch or Shortest universal maze exit string, making a valid submission is not difficult and can be done by hand, but making a good or optimal submission is difficult and likely requires code. In other challenges, like Create a uniquely solvable crossword ... without clues, making a valid submission at all is difficult. It is theoretically possible to make a submission by hand, but in practice I expect it is not possible to create or even verify any submission without programming. Does that matter?

Ancillary demands to include code

Suppose we have a challenge that asks for an artifact, and it's at danger of being closed because it's not on-topic. One potential way out of the problem is simply by requiring the submission of code along with each answer. Is that sufficient? Or on the flip side, is that required to be on-topic?

In practice, it seems that this technique has been highly successful at getting questions re-opened (but not universally so). For example, the JPEG question requires code now, as does the Boggle question. There are plenty of examples also of where the question could have originally been written without a demand for code (only demanding the final artifact), but from the very beginning was culturally biased towards asking for code.

If one does require code, should the post also demand that the answer not be hard-coded? The Boggle question does so, and even imposes a runtime limit. On the other hand, the word search question does not include such a restriction, leading to some awkward "code golf" (ostensibly but really just dictionary-based compression in practice) after having solved the main part of constructing a grid of letters.

Synthesis

I would appreciate hearing people's guidance on what they believe makes a code challenge on-topic. I am especially interested because I like to ask and answer questions, but other people like to close them instead.

Users other than myself are also interested in knowing what restrictions need to met to be on-topic, especially because constructing such a challenge is often hard work in and of itself. (For example, I have spent over 10 hours on writing my crossword grid challenge, not counting any of the ensuing moderation discussion and this meta post.)

\$\endgroup\$
  • 2
    \$\begingroup\$ I do have a Sandboxed submission (that will probably never be posted) with GOL submissions \$\endgroup\$ – Jo King Sep 24 at 4:53
  • \$\begingroup\$ If you're looking for more examples, I posted a few 4 years ago. The first was a disaster that I posted knowing it had an optimal solution, not realising how quickly that would be found. The next 2 I put a lot of effort into ensuring could not be solved optimally, with help from the community. In all cases while I required the code used be included in the answer, the score was based purely on the artifact presented, and there was no proof required that the artifact came from that code. This seemed in the spirit of the friendly, supportive community, and they were received well. \$\endgroup\$ – trichoplax Sep 24 at 21:58
  • \$\begingroup\$ My 3 code challenges: codegolf.stackexchange.com/… \$\endgroup\$ – trichoplax Sep 24 at 22:00
  • 5
    \$\begingroup\$ I'd love to see more challenges of this type. If there are restrictions that they need to meet to be on topic, I'd like to see these made as clear as possible, especially as these types of challenge can be hard work to fine tune even before considering any extra work to make them on topic \$\endgroup\$ – trichoplax Sep 24 at 22:03
  • 4
    \$\begingroup\$ @trichoplax: Thanks for pointing me to your code challenges. I have added "Shortest universal maze exit string" to the list of examples, especially because I have spent some time trying to solve it! It's a good question. Thinking in retrospect now -- given my experience with asking code challenges and the research I've done for this post, I'm amazed it hasn't been closed. From my recent moderation discussions, I don't imagine anyone who closed my question considering yours even remotely on-topic. \$\endgroup\$ – A. Rex Sep 25 at 0:34
  • 1
    \$\begingroup\$ Lots of questions that should be closed in some users' eyes slip through the cracks. \$\endgroup\$ – pppery Sep 25 at 11:41
  • \$\begingroup\$ Yes I agree the decisions on which challenges to close have been very inconsistent - I'm not sure mine would be accepted if posted today rather than 4 years ago. I'd definitely like to see some clear guidance to avoid this inconsistency \$\endgroup\$ – trichoplax Sep 25 at 20:18
  • 2
    \$\begingroup\$ I've voted to reopen your recently closed crossword code challenge. It still needs a couple more votes, but I believe you are able to cast a reopen vote on your own challenge, if that helps (and if that hasn't changed since last time I tried it). I don't believe that's a bug - you are able to vote to close a challenge of your own too so it seems intentional. \$\endgroup\$ – trichoplax Sep 25 at 21:07
  • 1
    \$\begingroup\$ There are a few problems with the list of examples. Most Populated Wordsearch was reopened after it was edited to require code, and in fact used the code length as a tiebreaker. Best Scoring Boggle Board asks for a search program. Wordiest Combination Lock asks for a program. Can a neural network recognise primes? wasn't closed as off-topic as you claim; and asks for a program in a particular computational model. Best Scoring Scrabble Board asks for a program. Tetris in GoL asks for a program in a particular computational model. \$\endgroup\$ – Peter Taylor Sep 27 at 8:47
  • \$\begingroup\$ Machine Learning Golf: Multiplication should be closed as "Unclear what you're asking", not as off-topic. NAND gates are a computational model. So I think that more than half of your examples are actually not examples of what you claim they are. \$\endgroup\$ – Peter Taylor Sep 27 at 8:49
  • 2
    \$\begingroup\$ @PeterTaylor: I think you're answering the question, under the guise of arguing with my list of examples. There are entire sections on computational models and on including code!! If you think that "Most Populated WordSearch" is an example of asking for an artifact before it was closed (because an answer was just "X"), but now it isn't asking for an artifact anymore (because it requires you to write "print X"), then that's the kind of opinion I'm looking for. If you think whether something is a computational model matters, then that's the kind of opinion I'm looking for. \$\endgroup\$ – A. Rex Sep 27 at 10:54
  • \$\begingroup\$ Also, I state the EXACT close reason when I say that "Can a neural network recognize primes?" was closed. \$\endgroup\$ – A. Rex Sep 27 at 11:14
  • \$\begingroup\$ "The question contradicts itself" is not a defence of the question. \$\endgroup\$ – Peter Taylor Sep 27 at 11:24
-6
\$\begingroup\$

Challenges should require submitters to write code

This is the core requirement. This is the core purpose of this site. We are a site about code challenges.

So, in regards to artifact-based challenge, my position here is nuanced. I would not allow a challenge that requires any SHA-1 hash collision. This certainly requires code, but it doesn't require the submitter to write code, as it only requires a Google search.

Therefore, all challenges should require evidence that the submitter has written code. For unique challenges (such as the crossword challenge), posting a solution feels like sufficient evidence that code has been written. However, the final say of whether a particular challenge requires enough evidence is up to the close voters.

\$\endgroup\$
  • 1
    \$\begingroup\$ If this becomes consensus, I'd like to see a tag for artifact/evidence based challenges \$\endgroup\$ – Nathan Merrill Sep 26 at 1:36

You must log in to answer this question.

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