16
\$\begingroup\$

There are lots of of challenges involving randomness. However, not all languages have a built-in method for randomness. Some languages, like python or most golfing languages make it really easy. You can simply call some built in function that will return a pseudo-randomly generated number. There is no boilerplate needed to seed the PRNG.

Other languages make it harder.

  • C/C++ has builtin PRNGs, but in order to get truly unpredictable results, you must call srand(time(NULL));, which seeds the PRNG with the current time. This is essentially an 18-byte penalty. As far as I know, Go works the same way.

  • Turing tarpits and esolangs, such as brainfuck and Brain-Flak have the algorithmic capabilities to create a PRNG, but no way to get an unpredictable starting seed (such as OS utilities or time).

One potential solution is to allow the seed to come from user input. But this opens up a new can of worms. Imagine the hypothetical (underspecified) challenge:

Print the letter 'a' a random number of times.

If user input counts as a valid source of randomness in Brain-Flak, one could argue that I could simply do print('a'*input()) in python. Or even the equivalent in Brain-Flak:

{
  ({}<
    ((((((()()()){}){}){}){}){}())
  >[()])
}{}

(For those who don't read Brain-Flak, this is basically the exact same thing as the python answer). Now, this hypothetical challenge is horribly underspecified, but the underlying problem is still there.

Now, it has been discussed before that time is a valid source of randomness for one value, not multiple. This post also addresses the meaning of the term "random". But neither of these address all of the potential problems with answers. I'd like to get a definitive answer to all of these potential loopholes:

  1. Is it valid for a challenge to use an unseeded PRNG? (This would affect answers such as this one)

  2. Is user input a valid source of randomness? (This would affect this answer which was deemed invalid and deleted)

  3. Is it valid to use user input to seed to a PRNG?

  4. Should we treat all languages the same in this regard, or is it OK to use more forgiving rules for languages with less randomness capabilities?

\$\endgroup\$
  • \$\begingroup\$ It's fairly well-established that user input is not acceptable. \$\endgroup\$ – Mego Mar 14 '18 at 23:58
  • \$\begingroup\$ NULL is defined as 0. \$\endgroup\$ – user202729 Mar 15 '18 at 8:30
  • \$\begingroup\$ What is an "unseeded" PRNG? All PRNG has its internal state (=seed) \$\endgroup\$ – user202729 Mar 15 '18 at 8:31
  • \$\begingroup\$ @user202729 Unseeded means not giving the PRNG a value for the seed to start at. Without seeding a PRNG, the sequence of random results will always be the same. As for NULL, you're right that it means 0. That's the standard way to call time \$\endgroup\$ – DJMcMayhem Mar 15 '18 at 21:10
  • \$\begingroup\$ @DJMc How is that random? Especially if the program only request 1 random number... | print(1234) and print(random()) has the same observable behavior. Should we allow them? \$\endgroup\$ – user202729 Mar 16 '18 at 14:01
  • \$\begingroup\$ @user202729 srand(time(NULL));print(random()) is no more random either. It's simply maps each time to a different output. \$\endgroup\$ – DJMcMayhem Mar 16 '18 at 14:54
3
\$\begingroup\$

My opinions on the matter(s):


  1. Is it valid for a challenge to use an unseeded PRNG?

Yes. The seed for a PRNG doesn't matter within a single invocation.

  1. Is user input a valid source of randomness?

No. It's not acceptable to take any more inputs than specified in the challenge, as the linked loophole makes clear.

  1. Is it valid to use user input to seed to a PRNG?

No (see above). This is effectively the same thing. This differs from asking for an additional input (such as the length of an array along with the array), since you can seed your PRNG without user input.

  1. Should we treat all languages the same in this regard, or is it OK to use more forgiving rules for languages with less randomness capabilities?

All languages should be treated equally.


That being said, challenge authors should be able to override these defaults if they deem it necessary (especially #1).

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't see how that loophole you have linked answers your question 2 or 3. And you explanation of "No." doesn't make it any clearer. \$\endgroup\$ – Wheat Wizard Mar 15 '18 at 0:38
  • \$\begingroup\$ @user56656 Using user input as a source of randomness or a seed is taking additional unspecified input, which is forbidden by that loophole. \$\endgroup\$ – Mego Mar 15 '18 at 0:40
  • \$\begingroup\$ I think you are misinterpreting that loophole. If we truly consider a seed to be "additional input not specified by the challenge" then I don't see how taking the time or other pieces of information about the system state could not be additional input as well. [We already allow] (codegolf.meta.stackexchange.com/questions/13210). taking the length of an array along with the array itself is permitted as part of input So there is a precedent that your reading is wrong. \$\endgroup\$ – Wheat Wizard Mar 15 '18 at 0:44
  • 3
    \$\begingroup\$ I neither agree or disagree with or agree with the conclusions but I feel that simply putting "No." and defering to a tenuously relevant loophole is harmful to the discussion. \$\endgroup\$ – Wheat Wizard Mar 15 '18 at 0:49
  • 2
    \$\begingroup\$ @user56656 The seed is being taken as an input from the user. This is an additional unspecified input. The reason for the length of an array along with the array is because the language can not read the input otherwise. \$\endgroup\$ – fəˈnɛtɪk Mar 15 '18 at 0:50
  • 1
    \$\begingroup\$ @fəˈnɛtɪk The languages that would benefit from user input are the ones that can't read information from the system such as time. I don't see how the two are different. \$\endgroup\$ – Wheat Wizard Mar 15 '18 at 0:55
  • 2
    \$\begingroup\$ @user56656 It's fine that not every language can solve every challenge. Making easily-abusable exceptions is not a good idea. And the loophole's applicability is self-explanatory: it's additional user input not specified by the challenge, which is expressly prohibited. The reason we allow array length as an additional input is to avoid situations where it is necessary but impossible to know the length of the array, and because an array's length is an intrinsic property of the array. \$\endgroup\$ – Mego Mar 15 '18 at 1:05
  • \$\begingroup\$ I edited to flesh out the reasoning for #2, rollback if you disagree. \$\endgroup\$ – Rɪᴋᴇʀ Mar 20 '18 at 19:59
  • \$\begingroup\$ #1 should only be valid for functions - if a complete program uses that, it'll always produce the same output (i.e. not random). Suppose the task was to roll 5 dice - invocations of a function (within the same program) would produce random outputs, but invocations of a program would always produce the same output. \$\endgroup\$ – user77406 Mar 30 at 10:58

You must log in to answer this question.

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