29
\$\begingroup\$

Because there are not enough simple challenges:

Create an optionally unnamed program or function that, given (by any means) an integer 1 ≤ N ≤ 10000, outputs your language's True value with a pseudo-random probability of 1/N, False otherwise.

Please note that the requirement for naming has been removed. Feel free to edit answers and scores accordingly.

Some languages use 1 (or -1) and 0 for True and False, that is fine too.

Example:

Example input tests:

4 -> True
4 -> False
4 -> False
4 -> False
4 -> False
4 -> True
4 -> False
4 -> False

I.e. given 4; it returns True with a 25% chance and False with a 75% chance.

\$\endgroup\$
  • 2
    \$\begingroup\$ Relevant meta post \$\endgroup\$ – FryAmTheEggman Dec 17 '15 at 19:38
  • 1
    \$\begingroup\$ Also relevant meta post. \$\endgroup\$ – AdmBorkBork Dec 17 '15 at 19:40
  • \$\begingroup\$ As not all languages have built in "pseudorandomness" is it possible to get a seed as second argument? (E.g. Brainfuck) \$\endgroup\$ – flawr Dec 22 '15 at 21:59
  • \$\begingroup\$ @flawr use current millisecond... \$\endgroup\$ – Adám Dec 23 '15 at 2:17
  • 1
    \$\begingroup\$ What's the largest N we have to accept? \$\endgroup\$ – Toby Speight Apr 12 '16 at 16:20

47 Answers 47

2
\$\begingroup\$

Ruby, 14

Function

->n{rand(n)<1}

Program is slightly longer

p rand(gets.to_i)<1
\$\endgroup\$
2
\$\begingroup\$

Perl, 18 12 bytes

$_=1>rand$_

That is 11 bytes + 1 for the -p commandline argument.
Save in a file (any name, say, 16.pl) and run as: echo 4 | perl -p 16.pl.
It will print an empty line for false, and 1 for true.

As a function: 18 bytes

sub f{1>rand$_[0]}
\$\endgroup\$
  • \$\begingroup\$ Would it still be valid if "sub f" was removed? (Updated OP: Naming is not required anymore.) \$\endgroup\$ – Adám Dec 18 '15 at 14:25
2
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 3 chars / 6 bytes

!⁇ï

Try it here (Firefox only).

The punctuation is strong with this one.

\$\endgroup\$
2
\$\begingroup\$

Racket, 21 bytes

(λ(x)(=(random x)0))
\$\endgroup\$
2
\$\begingroup\$

Reng v.3.3, noncompeting, 6 bytes

iu0en~

i takes input, u pushes a random integer in [0,i), 0e checks if the value is equal to 0, n outputs that value, and ~ terminates the program.

Try it here!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 2 bytes

XỊ

Try it online! (contains a footer that runs the program 100 times and reports the results)

I had to triple-check to make sure that Jelly wasn't here yet; it's a popular language, after all. But it turns out it wasn't.

X picks a random element from a list. Because it's at the start of the program but requires an input, it'll implicitly take the first command line argument as input. Most commands, when they expect a number but are given a list, convert the number into a range from 1 to that number; thus, for example, an input of 4 will pick a random element from [1, 2, 3, 4]. (Actually, Jelly has a special case to optimise this internally by not constructing the list.) Note that for an input of n, this means that there's a 1 in n chance of picking 1 as our element.

Once we have our element, we run on it. That's a test for a small value, i.e. no higher than 1 or smaller than -1. The only element that we can produce that matches this condition is 1, so we get an output of true (expressed as 1 in Jelly) with 1/n probability, and false (expressed as 0 in Jelly) the rest of the time. The output then gets printed implicitly.

(This submission also works as a function rather than a full program, exactly the same way; the implicit input is then taken from the function argument, and the implicit output used as the function's return value.)

\$\endgroup\$
2
\$\begingroup\$

Befunge-93, 99 98 96 95 92 90 84 bytes

<vp90:g80<p80 &
v?v>v>9g1-:0`|
0^1-:0v\g80:$<
>v<10^ +*2p90<
@>\^`$`  >!.
 v  _^>  |

Try it online!

This deserves a separate spot from my other answer, as I did this from scratch.

This generates an integer (x) in the range [0,2^n) using random binary digits, then redoes the program if x>=n (Actually by checking !(n>x), because befunge). Then, it tests if x=0, outputting the result.

Any ways to knock off bytes are wanted!

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

Perl 5, 10 bytes

A subroutine:

{1>rand@_}

It takes input as a list of 1s of the appropriate length.

Hat-tip.

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

><>, 44 + 3 = 47 bytes

&v<
0x1v
?^0\l&:&-
1=?\2*+l
?!v\:&:&(
n;~>0=

Try it online, or watch it at the fish playground!

Input is taken on the stack, with the -v flag (hence the +3 bytes). Unlike the other ><> answer, this has a theoretically correct distribution, not just an approximately correct one (assuming the pseudo-random stuff behind the scenes is uniform).

Randomness is tricky in ><>: the only non-deterministic instruction is x, which sets the fish's direction randomly from four choices.

If you want a uniform random number from 1 to N but you only have a (fair) m-sided die, where m > N, you can do it by rolling the die, checking if the result is in the right range, and re-rolling if it isn't until you get a number between 1 and N. There's a probability of exactly 0 that you'll keep rolling the die forever without end, and the result you get (if the process terminates) is uniformly distributed. Also, if 1 < m < N, you can simulate an mk-sided die by rolling it k times, and you can make mk larger than N by picking k large enough. Thus you can simulate any rational probability using any die with more than 1 side (if you don't mind a vanishingly small chance of rolling the die forever).

This program rolls a 2N-sided die, by getting N random 1s or 0s and reading them in binary. The number 2N is always bigger than N for N ≥ 1, although it's usually a LOT bigger, so for large N you'll be waiting a while. TIO handles up to about N = 16.

\$\endgroup\$
  • \$\begingroup\$ The idea of using a random number in the range of [1,2^n] definitely works in other languages, (e.g. my Befunge answer) \$\endgroup\$ – Zacharý Nov 23 '17 at 22:03
1
\$\begingroup\$

Befunge-93, 185 171 169 142 125 124 121 118 116 113 124 bytes

 &v>:00pv _v>v>\v
 > ^<  v?v:$1-+ :
@g:    1^2-1^   _$v>g`| @.0_1.
.$1    >v<1-\2*v+1<   >00g-^
 ^-     >\^>^>^>:00^  >
^#_#^

Try it online!

This uses the exact same strategy as this ><> answer (generate an integer in the range [1,2^n] by generating n random binary digits then converting it, then try again if the resulting integer is outside of the range [1,n]), but with two modifications:

  • Separate case for n=1
  • The binary digits are at first generated with 1s and 2s, since Befunge pops 0 off of the stack when empty. After the digits are generated, they are decremented to their normal binary and converted to an integer in place.

This is surprisingly fast!

Anything that will reduce the bytecount are welcome, considering I'm not a good befunge-golfer (especially when it comes to g and p)

I apparently am horrible at reading directions, as I originally only outputted a random integer in the range [1,n] >_<.

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

SmileBASIC, 15 bytes

INPUT N?!RND(N)

RND(n) generates a random number from 0 to n-1, so there's a 1/n chance that it will be 0. Then it just uses ! (logical not) to convert this to a 1/n chance of generating 1 (true), and prints the result.

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

Keg, 6 bytes

¿~$%2<

Takes random number & input, modulos them and checks whether the result is less than 2.

\$\endgroup\$
0
\$\begingroup\$

GolfScript, 8 bytes

~rand 0=

Try it online!

\$\endgroup\$
0
\$\begingroup\$

J, 6 bytes

?&0:<%

explanation

A J fork:

      ?&0:                <               %
NB. uniform float    is less than?    1 / input

Try it online!

\$\endgroup\$
0
\$\begingroup\$

MY, 5 bytes

ω0x=←

Try it online!

How it works:

Generates a random integer in the range [0,n), then tests for equality with 0.

\$\endgroup\$
  • \$\begingroup\$ I assume you meant [0,n-1] since [1,n] does not include 0. \$\endgroup\$ – 12Me21 Mar 31 '18 at 21:16
  • \$\begingroup\$ Yes, thank you! Lol. \$\endgroup\$ – Zacharý Mar 31 '18 at 21:21
0
\$\begingroup\$

x86, 10 bytes

Apparently there's a fairly new instruction called rdrand which makes this program pretty trivial.

Input in ecx, output in ZF. I consider one of x86's flags as a valid return value, which is arguably more useful than setz and returning in eax. It would've been very convenient if div set ZF.

5:  0f c7 f0                rdrand %eax
8:  31 d2                   xor    %edx,%edx
a:  f7 f1                   div    %ecx
c:  85 d2                   test   %edx,%edx
e:  c3                      ret 
\$\endgroup\$
0
\$\begingroup\$

Gol><>, 7 bytes

ISx*1(h

Try it online!

How it works

ISx*1(h

I        Take input as number
 Sx      Generate random number in [0,1)
   *     Multiply the two
    1(   Is it less than 1?
      h  Print the result as number and halt
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.