31
\$\begingroup\$

Your task is simple: output the letter x a random number of times. Every possible length of xs must have a non-zero probability of being output.

Of course, there must be some lengths whose probabilities tend to \$ 0 \$, in order for the total probabilities to sum to \$ 1 \$, but all must still be theoretically possible.

  • You may choose whether to include the empty string as a possible output
  • You may have any consistent separator between the xs, and you may output the separator more than once. The separator may not contain the unary character
  • You may use any other consistent single character instead of x
  • Per standard rules, your program must always halt in finite time. (Terminating "with probability 1" is allowed, though)
  • You can assume your language's random number generator is perfectly random. If it is supposedly continuous, you may assume it has infinite precision.

This is , so the shortest code wins.

\$\endgroup\$
15
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Mar 1 at 11:33
  • 10
    \$\begingroup\$ I'd like to emphasize how well specified this challenge is. This is not common for challenges involving randomness \$\endgroup\$
    – Luis Mendo
    Mar 1 at 16:25
  • 2
    \$\begingroup\$ @DominicvanEssen "You may choose whether to include the empty string as a possible output" \$\endgroup\$
    – pxeger
    Mar 1 at 16:31
  • 6
    \$\begingroup\$ @LuisMendo A sandbox success story! It went through several revisions there. \$\endgroup\$
    – DLosc
    Mar 1 at 17:21
  • 4
    \$\begingroup\$ "Of course, there must be some lengths whose probabilities tend to 0" This is a bit of an odd phrase. The probability of a single event can't really tend towards anything. But if we are talking about sequences, for every sequence of lengths whose probabilities don't tend towards zero that sequence must repeat some length an infinite number of times. :) \$\endgroup\$
    – Wheat Wizard
    Mar 1 at 17:33

45 Answers 45

12
\$\begingroup\$

><>, 3 bytes

x7n

Terminates on an error once x sends the IP left.

Try it online!

4 bytes:
x7
n

Try it online!

This will terminate with an error when n has been executed more times than 7, which has probability 1 of eventually occurring, thought there is no upper limit on how many times 7 will be executed first.

\$\endgroup\$
9
\$\begingroup\$

MATLAB, 28 25 bytes

while rand<.5 disp(1),end

Outputs "1" a random number of times, with newline in between. Each length l of has half the probability of length l-1.

Thanks @Luis Mendo for the 3 bytes!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Nice first answer! Thanks for fixing it :) \$\endgroup\$
    – pxeger
    Mar 1 at 14:19
9
\$\begingroup\$

Vyxal 2.4.1, 6 bytes

{×₴₀℅|

Try it Online!

We use v2.4.1 because it seems in 2.6 and later there's no way to get a random bit in two bytes.

{      # Forever...
 ×₴    # Print an asterisk
     | # While...
   ₀℅  # A random bit is nonzero
\$\endgroup\$
9
+50
\$\begingroup\$

Pari/GP, 43 bytes

setrand(getwalltime)
while(random,print(1))

(Don't) Try it online! This version is very likely to time out on TIO; here's a slightly longer version that produces nicer results: Try it online!

Explanation

setrand(getwalltime)

Seed the random number generator with getwalltime, which is "time in ms since UNIX Epoch."

while(random,print(1))

While a random integer in the range \$[0,2^{31})\$ is not equal to zero, print 1 with a trailing newline.

\$\endgroup\$
4
  • \$\begingroup\$ I suppose the first line is because there's a default fixed random number seed, meaning the number of 1's would actually not be random? \$\endgroup\$
    – Sundar R
    Mar 1 at 19:05
  • \$\begingroup\$ I think you don't need the %9. \$\endgroup\$
    – Sundar R
    Mar 1 at 19:08
  • 1
    \$\begingroup\$ Yeah, it gave the same result every time when I didn't seed the generator. I agree that the %9 is theoretically not necessary, but since the odds of getting exactly a zero are so astronomically small (1 in 2^31, apparently), it simply timed out on TIO. I guess I can change the code, add an explanation, and give the longer-but-more-usable version in the TIO link. \$\endgroup\$
    – DLosc
    Mar 1 at 19:18
  • \$\begingroup\$ i was 2 days too late to post a PARI/GP post :( took me 2 days to find out how to actually use this lang specifically for this qns \$\endgroup\$
    – DialFrost
    Mar 4 at 1:02
9
\$\begingroup\$

R, 20 bytes

while(rexp(1))cat(1)

Try it online!

3 bytes longer than Giuseppe's R answer, but can output unary values greater than 2147483647.

In fact, it will nearly always output unary values that are significantly greater than 2147483647, since the chance of stopping after any outputted 1 character is about 1e-324 (the lower limit of R's double-precision numeric type, below which values are truncated to zero).
This will also nearly always exceed the output limit on TIO, so here is a link using a modified version of the rexp function with only 1 decimal place of precision.

\$\endgroup\$
8
\$\begingroup\$

MathGolf, 4 3 bytes

⌂v▲

Pushes * with a probability of \$\frac{4\text{,}294\text{,}967\text{,}294}{4\text{,}294\text{,}967\text{,}295}\$ (99.999999999767%) each iteration, and won't include the empty output (so will always output at least one *).

Don't try it online.

Previous 4 byter:

⌂v¶▼

Pushes * with a probability of \$\frac{837\text{,}973\text{,}946}{858\text{,}993\text{,}459}\$ (~97.55%) each iteration, and won't include the empty output (so will always output at least one *).

Try it online.

Explanation:

  ▲   # Do while falsey with pop:
⌂     #  Push character '*'
 v    #  Push a random integer in the range [-2³¹, 2³¹)
      #  (only 0 is a falsey integer in MathGolf)
      # (after which the entire joined stack is output implicitly as result)
   ▼  # Do while truthy with pop:
⌂     #  Push character '*'
 v    #  Push a random integer in the range [-2³¹, 2³¹)
  ¶   #  Pop and check if this integer is a (positive) prime number
      # (after which the entire joined stack is output implicitly as result)

The mentioned probability is basically the amount of non-prime numbers within the range \$[-2^{31},2^{31})\$ (which is \$4\text{,}189\text{,}869\text{,}730\$ according to WolframAlpha) as numerator and total amount of integers within the range \$[-2^{31},2^{31})\$ (basically \$2^{32}-1=4\text{,}294\text{,}967\text{,}295\$) as denominator (and then simplified by dividing both by their greatest common divisor \$5\$).

\$\endgroup\$
6
\$\begingroup\$

JavaScript (Node.js), 30 bytes

f=_=>Math.random()>.5?'':1+f()

Try it online!

Simple

JavaScript (Node.js), 30 bytes

_=>'x'.repeat(1/Math.random())

Try it online!

Alternate

\$\endgroup\$
8
  • \$\begingroup\$ AH! Beat me to it, was thinking of this ever since I first saw it in the sandbox \$\endgroup\$
    – ophact
    Mar 1 at 11:55
  • \$\begingroup\$ Math.random() may output 0. So you may omit the >.5 in first program. \$\endgroup\$
    – tsh
    Mar 2 at 3:39
  • \$\begingroup\$ you can also omit the f= on the first one \$\endgroup\$
    – CreaZyp154
    Mar 3 at 7:47
  • \$\begingroup\$ @CreaZyp154 It's required for recursion \$\endgroup\$ Mar 3 at 10:11
  • \$\begingroup\$ @EnderShadow8 ah yes, didn't see \$\endgroup\$
    – CreaZyp154
    Mar 3 at 10:19
6
\$\begingroup\$

Pip, 4 bytes

1X/r

Outputs one or more 1s (usually not very many of them). Attempt This Online!

Explanation

   r  Random number in [0, 1)
  /   Invert
1X    Repeat 1 that many times

Theoretically, I think it's possible for this to output nothing if r returns exactly 0, but that's within the rules anyway.

\$\endgroup\$
3
  • \$\begingroup\$ (Repeating from elsewhere) Because r has finite precision technically it cannot output every number. In theory some kind of lazy evaluator with arbitrary precision could do it. \$\endgroup\$
    – Real
    Mar 4 at 3:15
  • \$\begingroup\$ Curiosity: if we chose a certain function instead of 1/r, the program could halt with probability 1 and still have average runtime infinity. \$\endgroup\$
    – Real
    Mar 4 at 3:19
  • \$\begingroup\$ Correct; however, for this particular challenge, "You can assume your language's random number generator is perfectly random. If it is supposedly continuous, you may assume it has infinite precision." \$\endgroup\$
    – DLosc
    Mar 4 at 15:05
6
\$\begingroup\$

Haskell, 56 bytes

import System.Random
main=print 1>>randomIO>>=([main]!!)

Try it online!

Random improvements applied to AZTECCO's answer. Halts by non-recoverable error, so it needs to be a full program. Prints at least once, but has \$\frac{1}{2^{64}}\$ chance of continuing to print. (The return type of randomIO is inferred to be Int, which is a signed 64-bit integer in TIO's environment.)

Haskell, 59 bytes

import System.Random
f=do print 1;n<-randomIO;mapM_ id[f|n]

Try it online!

A function that terminates gracefully and has 1/2 chance of continuing. [f|n] becomes [f] or [] with 1/2 chance each, and mapM_ id (one byte shorter than sequence_) runs all monads in the list sequentially. Deleting _ results in a type inference error.

\$\endgroup\$
6
\$\begingroup\$

Random Brainfuck, 7 6 bytes

-1 byte thanks to je je's observation that Null bytes are accebtale as output.

+[>.?]

Try it online!

Outputs at least 1 0x01 character, and terminates each iteration with a 1/256 chance. ? sets the current cell to a random byte, and this will only terminate when that byte is 0.

Detailed Explanation

+       set first cell to 1
[       while the current cell is non-zero:
  >         move right one cell
  .         output it (0x00)
  ?         set current cell to a random byte from 0 to 255
]       end while
\$\endgroup\$
2
  • \$\begingroup\$ Is the second plus necessary? I'm not aware of a specification that would prevent the null byte being a valid output character. \$\endgroup\$
    – je je
    Mar 3 at 19:07
  • \$\begingroup\$ @jeje True! Great observation. \$\endgroup\$ Mar 3 at 21:45
5
\$\begingroup\$

R, 19 17 bytes

strrep(1,rexp(1))

Try it online!

Samples from an \$Exp(1)\$ distribution to determine the length. This allows any positive real number to be generated, which strrep truncates, though most of them will be rather small.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Nice. Or +5 bytes to get a non-zero probability of outputting unary values greater than 2147483648... \$\endgroup\$ Mar 1 at 14:00
  • \$\begingroup\$ I was more worried about the result of strrep(1,x) when x is greater than 2^32... although obviously this will be rather a rare event... \$\endgroup\$ Mar 1 at 15:02
  • \$\begingroup\$ oh, true. well, I take it back, you can post your 22 byter if you'd like. \$\endgroup\$
    – Giuseppe
    Mar 1 at 15:03
  • 1
    \$\begingroup\$ I realised that I could shave-off 2 more bytes (I think...), so I've posted it as a 'very large output' version... \$\endgroup\$ Mar 2 at 16:05
5
\$\begingroup\$

Python 3, 46 bytes

lambda:'x'*int(1/random())
from random import*

Try it online!

Thanks to users pxeger and DominicVanEssen for their clarifications.

Outputs the character x a random number of times. Random sequences of xs are separated by the newline character.

\$\endgroup\$
2
  • \$\begingroup\$ Not valid because random() has finite precision, hence not all numbers could be generated, unfortunately. \$\endgroup\$
    – Real
    Mar 4 at 3:08
  • 1
    \$\begingroup\$ @Real OP explicitly states infinite precision may be assumed. \$\endgroup\$
    – loopy walt
    Mar 4 at 6:35
5
\$\begingroup\$

Thue, 20 bytes

x::=xx
x::=~x
::=
x

Try it online! (I'm not sure why the final blank line is necessary, but the program doesn't output anything if I delete it.)

Explanation

Thue starts with an initial string and executes rewriting rules nondeterministically until it cannot execute any more, at which point it halts. This program consists of two rules:

x::=xx

Replace an x in the string with xx.

x::=~x

Delete an x from the string and output x.

The program's starting string is:

x

Thus, at each stage of execution, the string consists of one or more xs; it can either get longer by one x, or get shorter by one x and output an x. Once all the xs have been output, the program halts. This occurs with probability 1, although in practice sometimes the interpreter segfaults.

\$\endgroup\$
5
\$\begingroup\$

Python 3, 62 60 59 45 43 41 bytes

import os
while os.urandom(1)[0]:print(1)

Try online!

Thanks to @pxeger, @mvirts, @MarcMush and @loopywalt.

\$\endgroup\$
14
  • 2
    \$\begingroup\$ Using a * import is 1 byte shorter: ato.pxeger.com/…. You can also initialise s to an empty string, since you're allowed to choose whether or not to include the empty string as an output. It will also be shorter to use a random integer in the range 0 to 2 instead, because there's no negative sign (but still with the same random effect): ato.pxeger.com/… \$\endgroup\$
    – pxeger
    Mar 2 at 20:06
  • 1
    \$\begingroup\$ Also FYI, you can generate a template for your answer on ATO, including the language header and try-it-online link, by clicking the blue clipboard button in the top right corner and choosing "CGCC post" \$\endgroup\$
    – pxeger
    Mar 2 at 20:08
  • 2
    \$\begingroup\$ The wildcard import is the same length as it is, but you can remove the space before the * to get the improvement. \$\endgroup\$
    – pxeger
    Mar 2 at 20:22
  • 2
    \$\begingroup\$ Agreed, cut out s and use random with no args? 45 bytes? \$\endgroup\$
    – M Virts
    Mar 3 at 3:49
  • 3
    \$\begingroup\$ -2 bytes: print(1) instead of print('x') \$\endgroup\$
    – MarcMush
    Mar 3 at 12:52
4
\$\begingroup\$

Jelly,  7  6 bytes

2ȮX$’¿

A niladic Link that prints 2s as a side-effect (it also yields 1). Only prints strictly positive numbers (as allowed in the specification).

Try it online! (The footer suppresses the printing of 1 that a full program would otherwise do implicitly.)
Or see forty at once (plus a single trailing newline).

How?

2ȮX$Ḋ¿ - Link: no arguments
2      - two - let's call this V
     ¿ - while...
    ’  - ...condition: decrement V (V=2 -> 1 (truthy); V=1 -> 0 (falsey))
   $   - ...do: last two links as a monad - f(V):
 Ȯ     -   print V, yield V
  X    -   random integer in [1,V] -> next V = 1 or 2 (probability = 0.5)

Previous @ 7 bytes:

2XȮß$Ị¡

A niladic Link that prints 1s as a side-effect (it also yields 2). This one includes the empty output (i.e. zero).

Try it online! (The footer suppresses the printing of 2 that a full program would otherwise do implicitly.)

\$\endgroup\$
4
\$\begingroup\$

MATL, 5 bytes

`1rEk

Outputs 1 separated by newlines n times, where n is a (shifted) geometric random variable with parameter 1/2. This means n is 1,2,3... with probability 1/2,1/4, 1/8 ... The program halts with probability 1.

Try it online!

`     % Do...while
  1   %   Push 1
  r   %   Push uniform random number in the interval (0,1)
  E   %   Multiply by 2
  k   %   Round down. This gives 0 or 1 with probability 1/2
      % End (implicit). The top of the stack is used as loop condition
      % If 1 a new iteration is executed, otherwise the loop is exited
      % Display stack (implicit)
\$\endgroup\$
2
  • \$\begingroup\$ I believe `1rYo also works (I like it because it says "Yo" at the end). \$\endgroup\$
    – Sundar R
    Mar 1 at 18:40
  • \$\begingroup\$ @SundarR Good point! Yes, that also works \$\endgroup\$
    – Luis Mendo
    Mar 1 at 21:16
4
\$\begingroup\$

Factor + random.c, 26 25 21 bytes

[ 1 . rand 9 > ] loop

Try it online!

This uses similar logic as flipping a coin until it lands on tails. Only you're using a severely weighted coin, so you usually get heads, leading to fairly long runs. rand is C's rand() function, returning an integer between 0 and 2147483647 (probably, though it doesn't matter). Each iteration of the loop, print 1 followed by a newline. If the output of rand is greater than 9, perform another iteration; otherwise, end the program.

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 5 bytes

[?₄Ω#

Outputs 0s with a probability of \$\frac{3}{4}\$ each time. Could be a probability of \$\frac{2}{3}\$ or \$\frac{1}{2}\$ for the same byte-count by replacing the with т or T respectively.

Try it online.

Explanation:

[      # Loop indefinitely:
 ?     #  Print an empty string without newline in the first iteration,
       #  or the 0 that was previously on the stack in other iterations
  ₄    #  Push 1000 (or 100 for `т` or 10 for `T`)
   Ω   #  Pop and push a random digit from this integer
    #  #  If it's 1: stop the infinite loop
\$\endgroup\$
4
\$\begingroup\$

Pure Bash (no external utilities), 30 26

for((;RANDOM;));{ echo x;}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

TI-Basic (TI-84), 11 10 bytes

Repeat checkTmr(startTmr
Disp 1
End

the program can only end when the check checkTmr(startTmr happens between two seconds (checkTmr(startTmr) = 1 instead of 0). This way, any number of ones is possible (the shortest I got was 3 ones, the longest printed during approx 10 seconds)

Repeat always executes the loop the first time, so the empty string is not included (repeat until or do while not)

For calculators without time (TI-83), replace checkTmr(startTmr with rand>.9 but it's not true randomness (same output on each reset of the calculator)

\$\endgroup\$
2
  • \$\begingroup\$ You can assume your language's random number generator is perfectly random. If it is supposedly continuous, you may assume it has infinite precision. The 10 byte solution using rand is perfectly acceptable per the rules of the challenge \$\endgroup\$
    – des54321
    Apr 12 at 23:10
  • \$\begingroup\$ the problem with rand in TI-Basic is that the same numbers will happen when the calculator is reset, which is the default. I can't find a meta answer about it though, so maybe it can be discussed \$\endgroup\$
    – MarcMush
    Apr 13 at 20:03
3
\$\begingroup\$

Charcoal, 4 bytes

W‽φx

Try it online! Link is to verbose version of code. Prints an average of 999 xs. (Other average counts from 1 to 9 are also possible by substituting an appropriate character for φ.)

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 29 bytes

f(){putchar(63)&rand()&&f();}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ putchar(1) or puts("?") or even puts("") would be shorter, and technically abiding by the requirements \$\endgroup\$ Mar 2 at 18:33
  • \$\begingroup\$ @Conor O'Brien I haven't seen the separator specs, so f(){rand(puts("1"))&&f();} should be ok, there's near 0% of possibilities of having a short output but it may be fine \$\endgroup\$
    – AZTECCO
    Mar 2 at 19:34
3
\$\begingroup\$

Batch, 28 bytes

@if %random% gtr 9 echo x&%0

Outputs an average of about 3276 xs, assuming CMD.EXE doesn't stack overflow first.

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 7 bytes

9w9ṙ9|↰

Try it online!

Explanation

9w         Write 9
  9ṙ       Pick a random integer in 0..9
    9      If it is 9, terminate
     |↰    Else, recurse
\$\endgroup\$
1
  • \$\begingroup\$ Should be able to drop the | for failure-terminated recursion, unfortunately sacrificing longer strings being reasonably likely (doesn't seem likely there's a way to boost the chance of success over 1/2) \$\endgroup\$ Mar 2 at 21:32
3
\$\begingroup\$

Alchemist, 14 bytes

_->Out__+_
_->

Try it online!

Breaks the loop with probability \$\frac12\$ at each iteration.

Explanation

The program starts with a single _ atom. Since both instructions consume only a _ atom, they are both satisfied and one is chosen randomly. The first outputs the number of _ atoms remaining (0) and produces another _ atom to continue the loop. The second just consumes the atom, ending the loop.

\$\endgroup\$
3
\$\begingroup\$

Cascade, 6 bytes

$/
.x/

Try it online!

Cascade, 6 bytes

\$
.|x

Try it online!

Likely optimal, considering one row has to have width at least 3 for $ to produce distinct random outcomes.

Both programs consist of two random branches from $, one of which returns the codepoint of x, and the other of which prints (the character value of) and returns the return value of (a fresh evaluation of) the $.

\$\endgroup\$
3
\$\begingroup\$

Julia 1.0, 22 bytes

!_=.1<rand()&&!show(1)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ This seems similar to the javascript solution, but I'm not quite sure how it works \$\endgroup\$
    – Krish
    Mar 3 at 19:14
3
\$\begingroup\$

Java, 58 45 44 bytes

String f(){return.5<Math.random()?"":1+f();}

Attempt This Online!

-1 thanks to @Kevin Cruijssen

Same strategy as the NodeJS answer. Previous answer did not fit challenge spec, this version turned out to be shorter as well.

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by changing return Math.random()>.5 to return.5<Math.random() \$\endgroup\$ Mar 3 at 16:00
3
\$\begingroup\$

Wolfram Language (Mathematica), 28 24 bytes

Dot@@Table[x,1/Random[]]

Thanks to att for –4!

Try it online!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ 25 bytes if a list output is allowed: x~Table~Floor[1/Random[]] \$\endgroup\$ Mar 1 at 23:47
  • \$\begingroup\$ Yes I had that one too but decided against it because of the curly braces. \$\endgroup\$
    – Roman
    Mar 2 at 6:08
  • \$\begingroup\$ @GregMartin Even better, Floor isn't needed in Table, so we can have Sequence output in 24 bytes with ##&@@Table[x,1/Random[]] \$\endgroup\$
    – att
    Mar 2 at 22:55
  • \$\begingroup\$ @att this generates Sequence[x, x, x, x] which I find even less appealing than Table[x,1/Random[]] (19 bytes). \$\endgroup\$
    – Roman
    Mar 3 at 8:45
  • \$\begingroup\$ I'd argue to the contrary that Sequence is the most natural head (besides String) for such an output, as it fills in arguments when under any head. If you don't like it Dot is the same length as ##&. \$\endgroup\$
    – att
    Mar 3 at 17:41
3
\$\begingroup\$

C++, 112 86 bytes

-26 bytes thanks to Unrelated String

#include<iostream>
main(){srand(time(0));for(int i=0;i<rand()%100;i++){std::cout<<1;}}

Try It Online!

\$\endgroup\$
2
  • \$\begingroup\$ Shorter without the #define and typedef (and you can even remove the return type of main for a warning). \$\endgroup\$ Mar 4 at 3:08
  • \$\begingroup\$ 81 bytes \$\endgroup\$
    – ceilingcat
    Mar 6 at 9:05

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.