(Sorry this is long. I tried to gather many examples, and honestly I would have liked to include more.)
Background
The code-challenge tag captures many different kinds of creative challenges that are not covered by code-golf. 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:
- Best Scoring Scrabble Board asks for a Scrabble board. It is apparently the oldest unanswered question on the site.
- (-a) × (-a) = a × a asks for a proof. A meta post from earlier said proof golf is on-topic. This question is the highest-voted in the tag atomic-code-golf.
- Build a working game of Tetris in Conway's Game of Life asks for a configuration in Conway's Game of Life. It is the highest-voted question of all time, and it was unanswered for many years.
- Machine Learning Golf: Multiplication asked for a neural network. Despite being asked after the neural network question above, with comments saying that it had the same issues, this question remained open without having defined "neural network". The question became a hot network question and is the second highest-voted in the tag atomic-code-golf.
- Plight of the Concorde asks for a set of points that make a specific program run slowly. Somehow it avoided being closed; perhaps it wasn't noticed by enough of the people that like to close code-challenge questions.
- Build a multiplying machine using NAND logic gates and Drive a hexadecimal 7-segment display using NAND logic gates ask for circuits.
- Get Two from One asks for a certain kind of graph that encodes some logic. An earlier related question, Hexcellent Minesweeping, attracted the comment "This isn't really code or programming related is it? It looks more like something Puzzling.SE would have", as many of these questions do.
- Shortest universal maze exit string asks for a string using the four characters
NESWsatisfying a nontrivial constraint. This is a good example of a question where using the word "witness" makes a lot of sense.
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" code-golf 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 kolmogorov-complexity 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 code-challenge 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.)
