1/N probability

Question

Because there are not enough simple code-golf 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.

Answer 1

MediaWiki templates with ParserFunctions, 48 bytes

{{#ifexpr:1>{{#time:U}} mod {{{n}}}|true|false}}

Answer 2

Pyth, 3 bytes

!OQ

Try it online

Simple inversion of random choice from 0 to input

Amusingly in Pyth it is not possible to make a function that does this without $ because Pyth functions are automatically memoized.

Answer 3

CJam, 5 bytes

Gotta be quick with these ones...

rimr!

Test it here.

Explanation

ri e# Read input and convert to integer N.
mr e# Get a uniformly random value in [0 1 ... N-1].
!  e# Logical NOT, turns 0 into 1 and everything else into 0.

Answer 4

TI-BASIC, 4 bytes using one byte tokens

not(int(Ansrand

Determines if the integer part of the input times a random number in [0,1) is zero. Ansrand<1 also works.

Answer 5

MATL, 5 bytes

Three different versions of this one, all length 5.

iYr1=

which takes an input (i), generates a random integer between 1 and that number (Yr), and sees if it it is equal to 1 (1=). Alternatively,

li/r>

make a 1 (l, a workaround because there is a bug with doing 1i at the moment), take an input (i), divide to get 1/N (/), make a random number between 0 and 1 (r), and see if the random number is smaller than 1/N. Or,

ir*1<

take and input (i), and multiply by a random number between 0 and 1 (r*), and see if the result is smaller than 1 (1<).

In Matlab, not MATL, you can do this anonymous function

@(n)n*rand<1

for 12 bytes, which is used by doing ans(5), for example.

Answer 6

Julia, 17 16 15 bytes

n->2>rand(1:n)

This is a function that generates a random integer between 1 and n and tests whether it's less than 2. There will be a 1/n chance of this happening, and thus a 1/n chance of returning true.

Saved 1 byte thanks to Thomas Kwa!

Answer 7

JavaScript ES6, 15 bytes

-5 bytes thanks to Downgoat.

x=>1>new Date%x

Based off (uses) of this answer's technique.

Answer 8

Microscript II, 3 bytes

NR!

Reads an integer n, generates a random integer between 0 and n-1 (inclusive), then applies a boolean negation to that value.

Answer 9

Candy, 2 bytes

Hn

H stands for Heisen-double

n stands for not

The 'n' is passed with the -i flag as numeric input. Values left on the stack are printed on exit.

"Long" form:

rand   # number between 0 and pop()
not    # cast to int, invert non-zero to zero, and zero to one

Answer 10

R, 30 22 bytes

code

cat(runif(1)<1/scan())          #new
f=function(N)cat(runif(1)<1/N)  #old

It generates a number from a uniform distribution (0 to 1) and should evaluate to true 1/n of the times.

Answer 11

Seriously, 3 bytes

,JY

0 is falsey and 1 is truthy. Try it online

Explanation:

,JY
,    get input
 J   push a random integer in range(0, input) ([0, ..., input-1])
  Y  logical not: push 0 if truthy else 1  

Answer 12

APL, 6 3 bytes

+=?

This is a function train that takes an integer and returns 1 or 0 (APL's true/false). We generate a random integer from 1 to the input using ?, then check whether the input is equal to that integer. That results in a 1/input chance of true.

Saved 3 bytes thanks to Thomas Kwa!

Answer 13

Japt, 6 bytes

1>U*Mr

Try it online!

Mr is equivalent to JS's Math.random. The rest is pretty obvious. I could probably add a number function that generates a random float between 0 and the number. When this happens, two bytes will be saved:

1>Ur    // Doesn't currently work

Alternate version:

1>Ð %U

Ð is equivalent to new Date(, and the Date object, when asked to convert to a number, becomes the current timestamp in milliseconds. Thus, this is entirely random, unless it is run multiple times per ms.

Answer 14

PlatyPar, 3 bytes

#?!

#? gets a random number [0,n) where n is input. ! returns true if the number before it is 0, else it returns false.

Using more recent features that were implemented (but unfortunately for me not committed) before this question was asked I can get it down to 2 with ~! Try it online!

Answer 15

Marbelous, 21 bytes

}0    # takes one input n
--    # decrements n
??    # random value from range 0..n (inclusive)
=0?0  # push right if not equal to 0, fall through otherwise | convert to zero
++    # increment | no-op
{0//  # output | push left

I've taken 0 to be falsey and 1 to be truthy, though there is no real reason for that seeing as Marbelous doesn't really have an if. More Marbelousy would be output to {0 for true and {> for false. This would look like this:

}0
--
??
=0{>
{0

But I'm not sure that's valid.

Answer 16

Java, 43 bytes

boolean b(int a){return a*Math.random()<1;}

Answer 17

C, 24 bytes

f(n){return!(rand()%n);}

Answer 18

><>, 27 + 3 for -v = 30 bytes

Here is a not-uniform-at-all solution where I mod N the sum of 15876 random picks of 0 or 1 :

0"~":*>:?vr%0=n;
1-$1+$^-1x

N must be input on the stack with -v flag, output is 0 for falsey and 1 for truthy.

A much smarter and uniform solution that work for 1/2^N instead :

4{:?!v1-}:">"$2p:"x"$3p:"^"$4p1+:">"$3p1+!
   ^1<
0n;
1n;>
 

For an input 3 you've got 1/8 chances of getting 1 and 7/8 of getting 0.

Explanation :

I append as much x as needed on the 4th line and surround them with directions so there is only two ways out of the x: either the falsey output or the next x. If all x go in the right direction, the last one will route to the truthy output.

For example for N=5, the final codespace is the following :

4{:?!v1-}:">"$2p:"x"$3p:"^"$4p1+:">"$3p1+!
   ^1<
0n; > > > > >
1n;>x>x>x>x>x>
    ^ ^ ^ ^ ^

Answer 19

Mathematica, 18 16 bytes

#RandomReal[]<1&

Basic solution. The unnamed Function creates a random number in [0, 1), multiplies it by its argument, and checks if it is still less than 1.

Answer 20

Python, 42 bytes

import random
lambda n:1>random.random()*n

Edit: Removed the time.time() answer because of the distribution.

Answer 21

TeaScript, 3 bytes

!N×

Try it here.

Explanation

 N  maps to Math.rand which is a utility function that returns an integer
    between `arg1` and `arg2` or `0` and `arg1` if only one argument is
    provided.
  × is expanded to `(x)`, where `x` is initialised with the value provided
    in the input boxes; × represents byte '\xd7'
!   negate the result, 0 results in true, anything else false

Answer 22

Fuzzy Octo Guacamole, 10 bytes

^-!_[0]1.|

Explanation:

^-!_[0]1.|

^          # Get input.
 -         # Decrement, so we can append <ToS> zeros and a 1 to the stack.
  !        # Set loop counter.
   _       # Pop, since we are done with the input.
    [      # Start loop
     0     # Push 0
      ]    # End for loop. We have pushed input-1 0s to the stack.
       1   # Push a single 1 to the stack.
        .  # Switch stacks
         | # Pick a random item from the inactive stack, which has n-1 falsy items and 1 truthy item, so the truthy probability is 1/n.
           # (implicit output)

Answer 23

Perl 6,  10  8 bytes

!(^*).pick
#  ^- The * is the argument

This code creates a Range from 0 up-to but excluding the input *. It then picks one at random and the ! returns True when it receives a 0.

1>*.rand
# ^- The * is the argument

This takes the input * and multiplies it by a random Num from 0..^1 then returns True if it was smaller than 1.

# store it in a lexical code variable for ease of use
my &code = 1>*.rand;

die "never dies here" unless code 1;

for ^8 { say code 4 }

False
True
False
False
False
True
False
False

Answer 24

C#, 56 45 bytes

Thanks to, pinkfloydx33 it's 45 now.

bool b(int n){return new Random().Next(n)<1;}

Old 56 bytes

Generates random positive integer bigger or equal to 0 and smaller than n and checks if it's smaller than 1 and return comparison result.

bool a(int n){Random r=new Random();return r.Next(n)<1;}

Answer 25

PHP, 22 bytes

<?=2>rand(1,$argv[1]);

Reads n from command line, like:

$ php probability.php 4

Outputs (false is cast to an empty string in PHP) or 1 (in case of true).

Answer 26

Prolog (SWI), 24 bytes

Code:

p(N):-X is 1/N,maybe(X).

maybe(+P) is a function which succeeds with probability P and fails with probability 1-P

Example:

p(4).
false

p(4).
false

p(4).
true

Answer 27

PowerShell, 25 Bytes

!(Random -ma($args[0]--))

The Get-Random function when given a -Maximum parameter n returns a value from the range [0,n). We leverage that by subtracting 1 from our input $args[0], so we're properly zero-indexed, and get a random value. Precisely 1/nth of the time, this value will be 0, so when we Boolean-not it with ! it will return True. The other times will return False.

Answer 28

Scratch, 63 bytes

Try it online!
Picture:

Scratchblocks code:

when gf clicked
ask[]and wait
say<(pick random(1)to(answer))=[1

Answer 29

J, 3 bytes

0=?

This is a monadic fork that takes an argument on the right. Similarly to APL, ? generates a random integer; however, J arrays are zero-based. So we compare to 0 instead of to the input.

Answer 30

Minkolang 0.14, 7 bytes

1nH1=N.

Try it here.

Explanation

1          Pushes 1
 n         Takes number from input
  H        Pops b,a and pushes a random integer between a and b, inclusive
   1=      1 if equal to 1, 0 otherwise
     N.    Output as number and stop.

Answer 31

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.)

Answer 32

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!

Answer 33

Ruby, 14

Function

->n{rand(n)<1}

Program is slightly longer

p rand(gets.to_i)<1

Answer 34

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]}

Answer 35

, 3 chars / 6 bytes

!⁇ï

Try it here (Firefox only).

The punctuation is strong with this one.

Answer 36

Racket, 21 bytes

(λ(x)(=(random x)0))

Answer 37

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!

Answer 38

><>, 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 m^k-sided die by rolling it k times, and you can make m^k 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 2^N-sided die, by getting N random 1s or 0s and reading them in binary. The number 2^N 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.

Answer 39

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] >_<.

Answer 40

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.

Answer 41

Keg, 6 bytes

¿~$%2<

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

Answer 42

Perl 5, 10 bytes

A subroutine:

{1>rand@_}

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

Hat-tip.

Answer 43

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.

Answer 44

GolfScript, 8 bytes

~rand 0=

Try it online!

Answer 45

J, 6 bytes

?&0:<%

explanation

A J fork:

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

Try it online!

Answer 46

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 

Answer 47

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