10
\$\begingroup\$

Some challenges have restrictions that apply to the program's source code, rather than the program's behaviour. These challenges are generally tagged with or or both.

I have a vague idea of what the difference is in obvious cases (e.g. "write a program without using e" is , "write a program that does something else when run backwards" is ), but there are plenty of cases which are somewhere in between, and I'm not sure where the boundary is (or what sort of challenges would fit in both). At the time of writing, the tag wikis don't really help clarify where the "edges" of the tags are:

  • The stated requirement of (that there's a restriction on the source code) applies to all challenges (even the least restricted-sourcey of these, the challenges where the program has to output some property of its source code, are still restricted in the sense that the program's source has to be written in a way that makes the program's output correct – in practice these programs are often written by sculpting the source to the output rather than the other way round).
  • The stated requirement of (that the physical arrangement of characters in the source code matters) applies to all challenges: if the source layout didn't matter, there'd be no way to define a restriction on it.

I have a feeling that having two tags might be useful – there does seem to be some difference in nature between them – but at present, the usage is unclear, and the tags seem to be used inconsistently in practice (e.g. this challenge is not even though the number of the bytes in the source code has to match the program output).

(Also to note: , and its opposite , are also source-dependent types of challenge, but tend to not be tagged with either nor , although they are sometimes. This means that challenges with a -like requirement that doesn't match the tag exactly sometimes end up with no source-dependency tags at all. is a subset of , and was originally intended to be used without it, but is sometimes used together with or even in practice.)

So my questions are:

  • What is the intended difference between these tags, if any?
  • Should we (and how should we) clarify the tag wikis in order to make the the difference clearer?
  • Is it possible to maintain a distinction, or should the tags be merged on the basis that it's too difficult to tag challenges with the correct tag, and thus they aren't useful for differentiating two different types of source-dependent challenge?
\$\endgroup\$
2
  • \$\begingroup\$ Related. \$\endgroup\$
    – ais523
    Commented Jun 20, 2022 at 15:43
  • 1
    \$\begingroup\$ IMO, source-layout does not, as you suggest, apply to all restricted-source challenges: for example, the restriction "no digits in code" doesn't have anything to do with the broader spatial layout of the source, it matters only on the individual character/byte level. \$\endgroup\$
    – pxeger
    Commented Jun 20, 2022 at 15:59

2 Answers 2

Reset to default
8
\$\begingroup\$

First things first here's how I currently interpret these tags:

Restricted source

is pretty simple, there is black box function1 which can take the source of a program and "decides". If the decision fails your answer cannot be valid, if it passes your answer is subject to further conditions (i.e. doing some task).2

Some examples of restricted source are:

  • The character e must not appear in the source.
  • For every pair of characters adjacent in your program the number of times each appears in your program must have opposite parity.

Some non examples of restricted source are:

  • No builtins are allowed. (not a formal restriction)
  • No recursion allowed. (not a formal restriction)
  • Program must run without errors when reversed. (requires information other than the source )

1: Usually this is computer decidable, but technically I suppose the property could be something that's not computer decidable but still objective and formally defined.
2: There's a little bit of nuance here where "trivial" decisions procedures, e.g. procedures that eliminate nothing, or disallow only the empty program, don't count.

Source layout

Source layout is the tough one. Based on the way I've seen it being used: Source layout for me means that there is some property that has to do with the arrangement of bytes / characters. Unlike this property can be related to the behavior of the program or the compiler. As a rule of thumb, if making your program valid involves moving stuff around then it's .

This makes it a very broad tag. Most falls under this umbrella. The exception would be problems which only disallow specific characters, since these are not about arrangement; there's nowhere you can move an e that makes it allowed.

And I think this broadness makes it so it isn't applied very evenly and is often omitted when there is a more specific tag applicable.

So yeah this is bad. is an overly broad tag with inconsistent application as you have pointed out. However I do think it fills a useful niche. I actually do browse pretty frequently looking for challenges. , etc. are fun but there is a lot of room for fun challenges that have a unique spin that doesn't fall under those tags.

My proposal is as follows: We define the tags in question roughly as follows (* indicates that this requires changing the wiki.)

Then we scale back to catch all the scraps (By my estimations approximately 150 questions). Just as means any challenge that isn't covered by a more specific scoring criterion, we would have a tag for challenges where the structure of the source code matters but isn't covered by any of the 5 tags above. This gives a way to find these challenges but doesn't create a overly broad tag that's bound to be applied to too many challenges.

For the sake of transparency, I have been working towards the silver badge in for a while now and I am quite close, so I do have a conflict of interest here.

\$\endgroup\$
1
\$\begingroup\$

Thoughts on how to objectively categorise this sort of challenge

After thinking about this for a while, I think there are three main sorts of source-dependent challenges that we have:

  1. There is a requirement on the source code that's independent of the rest of the task (apart from possibly being thematically linked to it); what the program has to do is the same regardless of the characters that make it up. This is a more restrictive version of , and also covers . For example, Print all ASCII alphanumeric characters without using them – although the requirement and task are thematically linked, they are conceptually independent of each other, and you could change either to something arbitrary and still have a meaningful challenge (e.g. "Print all ASCII alphanumeric characters" would be a viable challenge in its own right).

    As a side note, I've noticed that is also being used on challenges which ban programs that are longer than a given length (this is discouraged in , but makes sense in "do as much as you can in X bytes" s). Although that technically falls into this category, it's different enough in nature that we might want to consider making a new tag for it (maybe even a new scoring criterion tag).

  2. There is a requirement for the program to do something that depends on its own source code, i.e. the program's behaviour and source code must match in some way (and it's possible to create a match, completing the challenge, via changing the program's source or behaviour or both). Many of these challenges are covered by (e.g. "print your own source backwards" would be a challenge, despite not technically being a quine). However, some can be solved without the need for the source code to be able to even approximately reproduce itself, e.g. Print every character your program doesn't have; the tag (which I hadn't even realised existed immediately before writing this answer) appears to exist for this.

    Often these tasks have a trivial solution in which a program's source code can be designed in such a way that it makes the task very easy, but the scoring system is typically designed so that this type of solution scores badly.

  3. There is a requirement to, effectively, write multiple programs whose source codes are related in some way, with a task for each of those programs (which might be similar or the same). Special cases of this are (where the programs are the submission, together with all the programs formed via doing minor damage to the submission, and the task for all the programs is usually the same), and (where the programs are the submission, together with all the programs formed by deleting substrings from it, and the task for the reduced programs is "produce an error"); arguably (where the programs are the same but in different languages) is also related. However, there are lots of more general problems that fall into this category, such as I double the source, you double the output!. The vast majority of existing challenges appear to fall into this category.

(Have I missed any cases? Although these are objective definitions, I'm worried that there might be a challenge of this general nature that doesn't match any of them.)

None of these categories are mutually exclusive. If a program has two restrictions on the source, one which is has an effect on the task and one which doesn't, it can be in categories 1 and 2. If we restrict two programs to match each other, and also some additional restriction that's independent of the task, that's in categories 1 and 3. And if the additional restriction affects how the task works, that's in categories 2 and 3. You can even imagine a task that fits into all three categories, e.g. "write a quine that's still a quine when reversed, but is not a palindrome".

It's therefore tempting to decide "OK, let's tag these three categories as , , respectively". This would have three main effects:

  • would be narrowed somewhat in definition, but a quick check shows that it'd likely only affect a small proportion of the tag (although probably quite a large number in absolute terms). For some challenges, like Output your Score!, it appears at first that they wouldn't qualify (because the source restriction is intended as "you can't use any characters from the number in your output), but they still fall into the category because the restriction can be seen as "the program cannot contain any characters which match a digit from its byte count", which is a restriction that could meaningfully be applied regardless of the task.
  • would be considered a special case of , rather than the other way round. This probably doesn't affect anything other than their tag wikis (although we would likely need to think about "proper quine rules" in the context of ).
  • would change the most, being removed from some challenges (e.g. The Most Palindromy Code to Calculate Palindromy Numbers (this has no restriction at all, it's just ) and its newest challenge Gray coded Gray code convertor (this is )), and added to others (e.g. Alphabet printing challenge, Autogrammatic pairs).

I'm overall not sure whether these changes would be a net positive – it'd certainly make it easier to decide when to use which tag, but I'm not convinced that these categories are the most useful from a searching / "looking for challenges to answer" point of view, and the amount of retagging required would likely be quite disruptive. As such, this post isn't suggesting that we actually use these categories for a mass retagging effort – it's intended as more of a starting point to inspire other people who are thinking about the tags in question.

One other possibility, which would likely be helpful regardless, would be to pull out common source restrictions into their own tags. For example, the above-mentioned restriction on program length doesn't really feel like it belongs in , and not all objective restrictions that try to get at the notion of "your program can't contain unnecessary code" fall into (and yet they don't conceptually feel like they belong in either). "Do not use digits / specific digits in your program" is also a special case, which comes up so often (possibly due to one well-known broken window) that a tag for that restriction might actually be useful, if only so that people can choose to avoid it if they wish – its popularity likely exceeds the actual interest in working around that particular restriction, and a tag wiki talking about that sort of challenge in particular would probably be helpful.

\$\endgroup\$

You must log in to answer this question.

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