29
\$\begingroup\$

Quite often I find that I am repeating myself when creating a challenge. For example, usually I have to retype the definition of "random" in all of my posts, or I have to specify the same thing about how reasonable input and output can be provided in every challenge.

This post is meant to be a collection of "standard" definitions that may be assumed in every question, and do not need to be specified within the challenge. Definitions will apply once the post with the defintion has a score of +5 or more, and it has at least twice as many upvotes as downvotes.

\$\endgroup\$
  • \$\begingroup\$ I don't think the "at least twice as many upvotes as downvotes" is a good idea - if a comment has only one upvote but no downvotes, does that mean it should be considered as a standard definition? \$\endgroup\$ – ace Mar 24 '14 at 2:44
  • \$\begingroup\$ @ace "...has a score of +5 or more, and..." \$\endgroup\$ – Doorknob Mar 27 '14 at 14:58
  • \$\begingroup\$ Oops... sorry, I somehow read this as "+5 or more, or..." My bad. \$\endgroup\$ – ace Mar 27 '14 at 15:16
  • \$\begingroup\$ @Doorknob: You typed defintions in the title. \$\endgroup\$ – A.L Mar 28 '14 at 2:48
  • 16
    \$\begingroup\$ For users like me, I don't know if a definition has twice as many upvotes as downvotes. We either need to have "Accepted" next to the title, or not include that requirement. \$\endgroup\$ – Nathan Merrill Aug 5 '14 at 16:05
21
\$\begingroup\$

"random"

The term "random" means that you may:

  1. Use your language's built-in random number generator,
  2. Use /dev/random, or
  3. Create a RNG that is equivalent to a standard RNG (such as the Mersenne Twister).
\$\endgroup\$
  • 3
    \$\begingroup\$ How about mandating a call to srand() or its equivalent? By default, I always get 16807 from the first call to rand(), which is obviously quite the opposite of random. \$\endgroup\$ – squeamish ossifrage Mar 24 '14 at 9:17
  • 3
    \$\begingroup\$ I've seen some people using Date() as random() because it is shorter, is there any consensus about that? Whether it is right or not? \$\endgroup\$ – Washington Guedes Jun 21 '16 at 12:35
  • 1
    \$\begingroup\$ @WashingtonGuedes Just to let you know, that has now been asked as a separate meta question. \$\endgroup\$ – trichoplax Jun 22 '17 at 22:24
15
\$\begingroup\$

"uniformly random"

There are two distinct things to define for "uniform" (in the context of uniformly distributed random variables).

  1. If "uniform" is not specified, then "random" does not imply uniformly random.
  2. If "uniform" is specified, the standard PRNG (pseudo random number generator) of your programming language can be assumed uniform.

Examples

  • Output a random integer from 1 to 5:
    It does not matter if 2 is output with higher probability than 3.
  • Output a uniformly random integer from 1 to 5:
    The probability of each of 1, 2, 3, 4, and 5 must be 0.2, but a slight deviation from this due to the implementation of random is fine (provided that the implementation is not of a different distribution - you can't use a normal distribution to save bytes).
  • Output a uniformly random point on a disk:
    Choosing random cartesian coordinates (x,y) and rejecting if outside the disk is fine.
    Choosing random polar coordinates (r, theta) is not acceptable even though r and theta can be assumed uniform, because the distribution in 2D is no longer uniform (even with perfectly uniform r and theta).

If a challenge specifies statistical tests as part of the validity criteria, then that overrides these allowances.

\$\endgroup\$
  • 3
    \$\begingroup\$ But if you choose r as sqrt(x) * (radius of disk), where x is uniformly distributed between 0 and 1 (e.g. (r * math.sqrt(random.random()))), and with theta between 0 and 2 pi, it is a uniformly random point on a disk. \$\endgroup\$ – Artyer May 11 '17 at 12:42
  • \$\begingroup\$ Choosing random cartesian coordinates (x,y) and rejecting if outside the disk is fine. What does it mean by rejecting? \$\endgroup\$ – Keyu Gan Oct 26 '17 at 20:20
  • \$\begingroup\$ @KeyuGan this means repeatedly choosing (x,y) randomly, until a pair inside the disk is found. \$\endgroup\$ – trichoplax Oct 26 '17 at 20:30
  • 1
    \$\begingroup\$ I'm surprised that this doesn't mention that, even when uniform is not specified, all values within the range must be possible. Relevant XKCD \$\endgroup\$ – Kamil Drakari Feb 20 '18 at 16:23
  • \$\begingroup\$ @kamil that might be more relevant to the general definition of random ://codegolf.meta.stackexchange.com/a/1325/20283 \$\endgroup\$ – trichoplax Feb 20 '18 at 18:57
  • \$\begingroup\$ Just say "theoritally same size same probably"? \$\endgroup\$ – l4m2 Mar 12 '18 at 1:46
14
\$\begingroup\$

"input" and "output"

Any of these are acceptable for input/output respectively:

  • STDIN/STDOUT
  • function argument/return value (within a complete program)
  • reading from/writing to a file
  • dialog boxes
  • popping from/pushing to the stack (for stack-based languages like GolfScript; this is essentially the equivalent of a function's arguments/return values for those languages)
\$\endgroup\$
  • \$\begingroup\$ I thought the default was "full program required" for code-golf? \$\endgroup\$ – John Dvorak Mar 23 '14 at 6:07
  • \$\begingroup\$ @Jan Yes, it is. \$\endgroup\$ – Doorknob Mar 23 '14 at 14:12
  • \$\begingroup\$ in which case, point two should probably be clarified as "if a function is requested" \$\endgroup\$ – John Dvorak Mar 23 '14 at 15:24
  • \$\begingroup\$ @JanDvorak Well, by "function" I was referring to a function within a complete program. I shall edit to clarify. \$\endgroup\$ – Doorknob Mar 23 '14 at 15:27
  • 2
    \$\begingroup\$ I'm not clear on the function option "within a complete program". If asked to "square a number", could you write f=lambda x:x*x? Would you then need to invoke the function like f (y) in addition? \$\endgroup\$ – xnor Aug 19 '14 at 23:58
  • 3
    \$\begingroup\$ No command-line args as way of input? \$\endgroup\$ – Dennis Oct 2 '14 at 17:49
  • 3
    \$\begingroup\$ Maybe add a link to this: meta.codegolf.stackexchange.com/questions/2447/… \$\endgroup\$ – mbomb007 Dec 16 '16 at 16:30
14
\$\begingroup\$

"Black-Box-Functions"

The content (i.e. the code) of black-box-functions may not be accessed, you can only call them (passing arguments if applicable) and observe their output.

They should also have no side effects, except for e.g. accessing RNGs or time, but no communication with the rest of the program should take place other than through the input arguments and the output.

This term is used in the list of default IOs in a number of suggestions. (1),(2),(3)

\$\endgroup\$
  • \$\begingroup\$ I don't understand what you mean, idempotence has nothing to do with the definition of black box functions. \$\endgroup\$ – flawr Aug 14 '17 at 19:23
  • \$\begingroup\$ Your second paragraph basically describes idempotence... \$\endgroup\$ – Poke Aug 14 '17 at 19:27
  • 6
    \$\begingroup\$ Please explain what you mean by idempotence. I only know the mathematical meaning of an operation where a function f is called idemptotent if its composition with itself is itself again, i.e. f(f(x)) = f(x) for all x, and this certainly does not apply here as far as I understand. \$\endgroup\$ – flawr Aug 14 '17 at 19:38
  • \$\begingroup\$ At least in computer science a function is idempotent if it produces the same results when invoked many times. I suppose this doesn't actually exclude "side effects" depending on your definition. For example an HTTP PUT is supposed to be idempotent because it will always "set" the value to your parameter. However an HTTP POST is not because you're always adding something new. \$\endgroup\$ – Poke Aug 14 '17 at 19:52
  • 2
    \$\begingroup\$ Ok I see, but I think the usage of that term in this context is misleading. Usually something like that is called pure or deterministic but I think the current description is sufficient. \$\endgroup\$ – flawr Aug 14 '17 at 20:18
  • \$\begingroup\$ Okay. I upvoted this before I commented anyway. \$\endgroup\$ – Poke Aug 14 '17 at 20:46
9
\$\begingroup\$

"Positive", "Negative", "Non-Negative", "Non-Positive"

Positive, by default, means strictly positive, ie. all N larger than zero. Zero is not a positive number.

Negative means all N less than zero. Zero is not a negative number.

Non-negative means all N larger than or equal to zero. Zero is a non-negative number.

Non-Positive means all N smaller than or equal to zero. Zero is a non-positive number.

\$\endgroup\$
  • 3
    \$\begingroup\$ These are standard mathematical terms, but posting them here is still a good idea. You should add non-positive to complete the set. \$\endgroup\$ – Mego Feb 19 '18 at 20:12
  • 1
    \$\begingroup\$ Note that some places, such as France, consider positive to include 0, which is why I felt this needed to be included in the standard definitions. \$\endgroup\$ – Jo King Feb 20 '18 at 2:52
  • 5
    \$\begingroup\$ That's weird. France is silly and wrong \$\endgroup\$ – Mego Feb 20 '18 at 3:06
  • \$\begingroup\$ @JoKing I've heard people in England use them as loanwords: positif = non-negative; négatif = non-positive, pronounced [pɒzɪˈtiːf] and [nɛɡəˈtiːf], but this is not mainstream \$\endgroup\$ – ngn Apr 23 '18 at 4:56
  • 1
    \$\begingroup\$ As ngn pointed out, this is not mainstream, in France we often use "positif ou nul" to say non-negative which is different from "positif" alone \$\endgroup\$ – Rafalon Aug 22 '18 at 8:32
6
\$\begingroup\$

Universally testable answers

An answer will be considered to be universally testable if:

  1. It is written in a programming language which has a compiler/interpreter available on Windows, Linux & Mac where said compiler/interpreter can be downloaded from the web free of charge (not including free trials) and does not require sign up/registration.
  2. or it is written in a programming language that has an online compiler/interpreter such as http://ideone.com/, which is available free of charge and does not require sign up/registration, where the answer may be fully tested within the online compiler/interpreter i.e. doesn't need access to local resources.

Additionally, if the behaviour of the answer is different on different platforms/architectures, it should still meet the question criteria on all platforms/architectures.

\$\endgroup\$
  • 1
    \$\begingroup\$ doesn't this exclude .net and thus C#? \$\endgroup\$ – John Dvorak Aug 17 '14 at 18:14
  • 1
    \$\begingroup\$ Mono is an open source implementation (and is available on ideone) \$\endgroup\$ – rdans Aug 17 '14 at 18:28
  • 3
    \$\begingroup\$ This also excludes powershell and bash \$\endgroup\$ – John Dvorak Aug 17 '14 at 18:28
  • 2
    \$\begingroup\$ This restriction would only apply if a question asker specifies it. This is just to provide the definition. Personally, i would prefer to verify whether an apparently winning answer actually works and meets the question criteria, which is only possible if i can test it. \$\endgroup\$ – rdans Aug 17 '14 at 18:49
  • 4
    \$\begingroup\$ @JanDvorak, how does it exclude bash? Cygwin is free to download without registration. \$\endgroup\$ – Peter Taylor Aug 17 '14 at 18:56
  • 4
    \$\begingroup\$ Well I hope including this doesn't become the default, or there won't be any more Mathematica answers until there's an open source implementation of Wolfram Language. ;) \$\endgroup\$ – Martin Ender Aug 18 '14 at 8:08
  • 2
    \$\begingroup\$ That would be unfortunate, however, a question asker should be able to test an answer, otherwise they may not always be able to choose a winner due to not being able to verify it as a valid entry. \$\endgroup\$ – rdans Aug 18 '14 at 17:47
  • 2
    \$\begingroup\$ I think answers should be testable, but I don't agree that registration/trial-only should disqualify. \$\endgroup\$ – Adám Oct 13 '15 at 20:09
  • \$\begingroup\$ @JohnDvorak also, there are online bash and powershell interpreters \$\endgroup\$ – Jacob Garby Dec 10 '17 at 17:07
2
\$\begingroup\$

Write a function

I propose this as the default for code golf questions that as for a function rather than a full program. I'm sorry if this all seems overly pedantic, but I've seen every single one of these points come up in actual questions and answers, and I'd like to have comprehensive rulings on them available.

I must admit I have a limited knowledge of languages, especially esoteric ones, so I welcome suggestions to make this more accessible to a wide class of languages.

Specification

1) The code must result in a named function (or analogous execution unit in your language) that fits the specifications.

2) The function, when called by name on its inputs, must evaluate to the desired outputs.

3) There can be code outside the function definition, whose characters are also counted.

4) Calling the function multiple times must produce the right answer each time.

5) Optional additional parameters are acceptable; mandatory additional parameters are not.

Explanations

The spec is meant to capture the idea that a function, once created, should be usable to transform inputs to outputs in the fashion asked for.

1) The code must result in a named function (or analogous execution unit in your language) that fits the specifications.

While in C-style languages, the function is usually created by a function definition, this allows for other methods such as a lambda-expression like f=lambda x:x*x or a composition f=compose(g,h) or a decoration f=memoize(f) as long as the result is saved to a variable.

2) The function, when called by name on its inputs, must evaluate to the desired outputs.

This captures the requirement that the function be a function. Its inputs should be passed in, rather than taken through STDIN or taken from a global valuable. Its value must be returned, rather than saved to a variable or printed. To be clear, this does not mean an invocation of the function by included in the code, but that the function must behave as desired in invoked.

3) There can be code outside the function definition, whose characters are also counted.

This rule is an assurance that even if asked for a function, your code doesn't entirely have to do that function. Programs might make imports, saved global variable, and define auxiliary functions outside that function.

4) Calling the function multiple times must produce the right answer each time.

In other words, it's not acceptable to have your function only work the first time. Subsequent calls within a single run should also work according to the spec. This could come up if the function modifies a global value.

This does not preclude the function modifying the value it was passed in. So, the function f should print the same output twice on print f(1,2); print f(1,2) but not necessarily l=[1,2]; print f(l); print f(l).

Here's an answer where this question can up in practice, with Falko's suggestion to save a character by defining the initial list as an optional parameter def f(a,b=[0]*1000): causes it to be overwritten for subsequent runs.

5) Optional additional parameters are acceptable; mandatory additional parameters are not.

In other words, if asked for a function that takes two numbers, it's fine to have one that takes two numbers and an optional third number, as long as it behaves as asked when given only two numbers. The reasoning is that this would pass any test according to the specs, so it can behave arbitrarily in the non-spec case of three numbers. However, having a mandatory additional parameter and saying "call f as f(a,b,0) does not fit the spec.

An optional additional parameter might be useful for golf to define a recursive function or to save a method name to a variable before the function body.

Things not addressed

Input/outputs formats: If asked for a function that takes no numbers, can yours instead take a list/array/tuple of two numbers? Can you output a float if asked for a whole number?

Fallbacks: What should a language that does have functions do? I think this should be addressed with a general convention of "Do the closest you can, but only if what was required was impossible in the language.

\$\endgroup\$
  • \$\begingroup\$ Point 1 as written seems to preclude languages which don't have function types. A more language-independent way of phrasing it would be to talk about names rather than variables. \$\endgroup\$ – Peter Taylor Aug 24 '14 at 7:50
  • \$\begingroup\$ Point 3 gets a bit problematic when it talks about imports. An answer which is a program should include imports, but I'm not sure that requirement makes sense for a function (or code snippet) unless you also require that e.g. Java answers to a "write a function" questions include a wrapping class A{}. Otherwise there's no way to have both imports and a function which makes any syntactic sense. \$\endgroup\$ – Peter Taylor Aug 24 '14 at 7:52
  • \$\begingroup\$ @PeterTaylor Could you give me an example of a language that uses names rather than variables so I can look into it? \$\endgroup\$ – xnor Aug 24 '14 at 16:25
  • \$\begingroup\$ @PeterTaylor I'm confused -- I intended to make Point 3 exactly to allow things like imports. \$\endgroup\$ – xnor Aug 24 '14 at 16:27
  • \$\begingroup\$ Languages which don't have function types include Java (pre-8, at least; I'm not sure what the implementation details of lambdas are) and PHP. With respect to point 3, what I'm trying to say is that a Java answer which begins import java.math.BigInteger;BigInteger f(BigInteger x){... is syntactic nonsense, and I think that if people want to ask for functions rather than full programs then they should give you imports for free. \$\endgroup\$ – Peter Taylor Aug 24 '14 at 16:40
  • \$\begingroup\$ Would replacing "variable" with "name" solve the type issue, or is the term "function" itself problematic? Is is standard for Java golfs to allow certain libraries for free? Python golfs would certainly be a lot different if given a free import itertools as i. \$\endgroup\$ – xnor Aug 24 '14 at 17:14
  • \$\begingroup\$ The term "function" isn't ideal: some languages don't use the term. But it's not nearly as bad as "variable", which has a defined meaning in nearly every mainstream language and plenty of esoteric ones. If you want to be particularly clear you could say "named function, named verb, named block, or other named execution unit as appropriate to your language". \$\endgroup\$ – Peter Taylor Aug 24 '14 at 17:30
  • \$\begingroup\$ As for allowing libraries for free: there is at least one example of a Java function golf which doesn't mention its import, but Java function golfs are so rare that I don't think there's much "standard" to talk about. There may be a case to be made that if you're asking people to do a task which is going to require imports then you should ask for a full program, not a function, although predicting which tasks will benefit from imports in which languages isn't easy. \$\endgroup\$ – Peter Taylor Aug 24 '14 at 17:33
  • \$\begingroup\$ OK, I broadened the language a bit for function and variable. For the Java issue, do you think there would be support for a rule that code length = import length + function length for function questions? \$\endgroup\$ – xnor Aug 24 '14 at 20:59
  • 4
    \$\begingroup\$ Consensus seems to be that functions don't have to be named unless the OP explicitly asks for it. \$\endgroup\$ – Martin Ender Oct 30 '14 at 8:30
-6
\$\begingroup\$

"N random X"

Where N denotes a natural number and X denotes (members of) a set with finite cardinality.

The standard definition for "N random X" is "N independent identically distributed uniform (pseudo-) random samples from the space of all X".

As a concrete case "generate 3 random printable ASCII characters" could be satisfied by [1,2,3].map(_=>String.fromCharCode(Math.random()*95+32)) in JavaScript (ES6).

\$\endgroup\$
  • 1
    \$\begingroup\$ I am quite willing to work on the wording if anybody has a better suggestion. \$\endgroup\$ – Lmis Nov 23 '16 at 8:26
  • \$\begingroup\$ Question codegolf.stackexchange.com/q/100729/56071 asks for "N random printable ASCII characters" and it seems clear from the answers that the common interpretation is the one above, so I think it best to resolve any ambiguities with a standard definition. \$\endgroup\$ – Lmis Nov 23 '16 at 8:32
  • 5
    \$\begingroup\$ I disagree with having this as a standard definition — instead my opinion is that questions should always specify what they mean by N random X \$\endgroup\$ – Lynn Nov 27 '16 at 1:12

You must log in to answer this question.

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