This will eventually stop…

Question

Given an input string S, print S followed by a non-empty separator in the following way:

• Step 1: S has a 1/2 chance of being printed, and a 1/2 chance for the program to terminate.

• Step 2: S has a 2/3 chance of being printed, and a 1/3 chance for the program to terminate.

• Step 3: S has a 3/4 chance of being printed, and a 1/4 chance for the program to terminate.

• …

• Step n: S has a n/(n+1) chance of being printed, and a 1/(n+1) chance for the program to terminate.

Notes

• The input string will only consist of characters that are acceptable in your language's string type.

• Any non-empty separator can be used, as long as it is always the same. It is expected that the separator is printed after the last print of S before the program terminates.

• The program has a 1/2 chance of terminating before printing anything.

• A trailing new line is acceptable.

• Your answer must make a genuine attempt at respecting the probabilities described. Obviously, when n is big this will be less and less true. A proper explanation of how probabilities are computed in your answer (and why they respect the specs, disregarding pseudo-randomness and big numbers problems) is sufficient.

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Pyth, 7 bytes

WOh=hZQ

Try it online!

How it works

Pseudocode:

while rand_int_below(1 + (Z += 1)):
    print(input)

Answer 2

C#, 94 85 bytes

My first answer!

using System;s=>{var r=new Random();for(var i=2;r.Next(i++)>0;)Console.Write(s+" ");}

Previous attempt (I liked that goto):

using System;s=>{var i=2;var r=new Random();a:if(r.Next(i++)>0){Console.Write(s+" ");goto a;}}

Ungolfed:

using System;
class P
{
    static void Main()
    {
        Action<string> f = s =>
        {
            var r = new Random();
            for (var i = 2; r.Next(i++) > 0;) Console.Write(s + " ");
        };

        f("test");

        Console.ReadKey();
    }
}

Note: in C# the Random.Next(N) method returns a nonnegative integer in the [0, N-1] range, so we can just check that the number returned is greater than 0.

Answer 3

R, 47 46 43 bytes

43 bytes due to Robin Ryder in the comments.

s=scan(,"")
while(sample(T<-T+1)-1)print(s)

Try it online!

Explanation

s=scan(,"")  # Takes input from stdin.
             T<-T+1    # T is 1 by default, so this
                       # evaluates to 2, and will increment
                       # at each step.
      sample(T<-T+1)   # Take a sample of size 2, i.e. generate
                       # a list of integers from 1 to 2 in random order
      sample(T<-T+1)-1 # Subtract one from every element of this list.
while(sample(T<-T+1)-1)# while() will treat the first value in this list
                       # as a logical value, i.e. FALSE for zero and TRUE
                       # for nonzero values. The other elements of the list
                       # are ignored, triggering a warning.
                       print(s) # print s

Answer 4

05AB1E, 8 bytes

[NÌL.R#,

Try it online!

Explanation

[         # start loop
 NÌL      # push range [1 ... current_iteration+2]
    .R    # pick a random number
      #   # if true (1), exit loop
       ,  # print input

Answer 5

Javascript, 60 58 54 bytes

f=(s,n=1)=>Math.random()<n/++n?console.log(s)+f(s,n):0

Will output string s. The seperator which is printed if the program terminates is NaN or 0.

f=(s,n=1)=>Math.random()<n/++n?console.log(s)+f(s,n):0

f('test')

Math.random() returns a value between 0 and 1. If that value is under n/(n+1), then s will be pritned.

4 bytes saved thanks to @Neil

Answer 6

Java 8, 72 62 61 bytes

s->{for(int n=2;Math.random()<1f/n++;System.out.println(s));}

-10 bytes thanks to @cliffroot.
-1 byte thanks to @JollyJoker.

Delimiter is a new-line.

Explanation:

Try it here.

s->{                          // Method with String parameter and no return-type
  for(                        //  Loop
    int n=2;                  //   Start `n` on 2
    Math.random()<1f/n++;     //   Continue loop as long as a random decimal (0.0-1.0)
                              //   is smaller than 1/`n` (and increase `n` by 1 afterwards)
    System.out.println(s)     //   Print the input-String
  );                          //  End of loop
}                             // End of method

Answer 7

Mathematica, 43 bytes

(n=1;While[RandomInteger@n>0,Print@#;n++])&

JungHwan Min saved 1 byte (above) and suggested something better (below)

Mathematica, 37 bytes

For[n=1,RandomInteger@n++>0,Print@#]&

Answer 8

Clojure, 61 56 bytes

Oh why didn't I go with a for in the first place? But actually to be pedantic doseq has to be used as for is evaluated lazily.

#(doseq[n(range):while(>(rand-int(+ n 2))0)](println %))

Original:

#(loop[n 2](if(>(rand-int n)0)(do(println %)(recur(inc n)))))

Answer 9

><>, 124 112 bytes

i:0( ?v
 &5a ~/
&p0[^ >"\_\^x0!>"0&1+:&p1&:&p2&:&p3&:&p4&:&p0&1+:&p3&:&p4&:
=?v[/!}l]:?!;1
{:   ?^  >
:o>_ {:?!^

Try it online! (You can also watch it at the fish playground, but due to some bugs you have to add a } after the l in the fourth line and add a bunch of newlines after the code to make it work properly.)

Randomness is tricky in ><>. The only random instruction is x, which picks the fish's direction randomly from four choices (left, right, up and down), so turning that into something with probability 1/n is not straightforward.

The way this code does it is by using ><>'s self-modifying capabilities to build a Tower of Randomness below the code, so at the fourth stage, for example, the code looks like:

i:0( ?v
 &5a ~/
&p0[^ >"\_\^x0!>"0&1+:&p1&:&p2&:&p3&:&p4&:&p0&1+:&p3&:&p4&:
=?v[/!}l]:?!;1
{:   ?^  >
:o>_ {:?!^
>!0x^
\  _\
>!0x^
\  _\
>!0x^
\  _\
>!0x^
\  _\

The fish starts at the bottom of the tower. At each level of the tower, the x is trapped between two mirrors, so the fish can only escape by going left or right. Either of these directions sends the fish up to the next level of the tower, but going left also pushes a 0 to the stack. By the time the fish gets to the top of the tower, the stack contains some number of 0s, and this number follows a binomial distribution with n trials and p = 1/2.

If the length of the stack is 0 (which has probability 1/2ⁿ), the program halts. If the length is 1 (with probability n/2ⁿ), the fish prints the input and a newline and builds another level of the tower. If the length is anything else, the fish discards the stack and goes back to the bottom of the tower. In effect, out of the possibilities that actually do something, n of them print the input string and one of them halts the program, giving the required probabilities.

Answer 10

Python 3, 72 69 66 bytes

• Saved 3 bytes thanks to Jonathan Allan: Import shorthand and start count from 2.
• Saved 3 bytes thanks to L3viathan : Pointed randint() was inclusive and also shortened while condition.

from random import*
s=input();i=1
while randint(0,i):print(s);i+=1

Try it online!

Answer 11

QBIC, 19 17 bytes

Dropped =1, switched conditionals, saved 2 bytes

{p=p+1~_rp||?;\_X

Explanation

{       Infinitely DO
p=p+1   Add 1 to p (p starts as 0, so on first loop is set to 1, then 2 etc...)
~       IF
  _rp|| a random number between 0 and p
        (implicitly: is anything but 0)
?;      THEN print A$ (which gets read from the cmd line)
\_X     ELSE QUIT
        END IF and LOOP are auto-added at EOF

Answer 12

Braingolf, 23 bytes

#|V12[R!&@v!r?<1+>1+]|;

Try it online!

Generates random number x where 0 <= x < n+1, terminates if x is 0, otherwise increments n and loops. Separator is |

Explanation:

#|V12[R!&@v!r?<1+>1+]|;  Implicit input of commandline args to stack
#|                       Push |
  V                      Create stack2 and switch to it
   12                    Push 1, then 2
     [..............]    Do-While loop, will run indefinitely unless conditional skips
                         Closing bracket
      R                  Return to stack1
       !&@               Print entire stack without popping
          v              Switch to stack2
           !r            Generate random number 0 <= x < n where n is last item on stack
             ?           If last item is greater than 0..
              <          ..Move first item to end of stack
               1+        ..and increment, this is the loop counter number
                 >       ..Move back
                  1+     ..and increment, this is the upper range of the RNG
                    ]    ..end loop
                     |   Endif
                      ;  Suppress implicit output

Answer 13

Alice, 18 bytes

/?!\v
\iO/>]qhUn$@

Try it online!

Explanation

/     Reflect to SE. Switch to Ordinal.
i     Read all input as a string and push it to the stack.
!     Store the string on the tape.
/     Reflect to E. Switch to Cardinal.
>     Ensure that the IP moves east. This begins the main loop.

  ]   Move the tape head to the right. We'll be using the tape head's 
      position as a counter variable. Note that this tape head is independent
      of the one used in Ordinal mode to point at the input string.
  q   Push the tape head's position to the stack.
  h   Increment it (so that it's 2 initially).
  U   Get a uniformly random number in [0,n).
  n   Logical NOT. Gives 1 with probability 1/n and 0 otherwise.
  $@  Terminate the program if we got a  1.
  \   Reflect to NE. Switch to Ordinal.
  ?   Retrieve the input from the tape.
  O   Print it with a trailing linefeed.
  \   Reflect to E. Switch to Cardinal.

v     Send the IP south where it runs into the > to start the next
      loop iteration.

Answer 14

PHP, 31 bytes

for(;rand()%~++$c;)echo$argn._;

Try it online!

Answer 15

Perl, 26 bytes

24 bytes code + 2 for -nl.

print while rand++$i+1|0

Try it online!

Answer 16

Charcoal, 14 bytes

Ａ²γＷ‽γ«θ_Ａ⁺γ¹γ

Try it online! Link is to verbose version of code. Uses _ as the separator. Note: output caching is disabled, so please don't hammer Dennis's server!

Answer 17

MATL, 9 bytes

`G@QYrq]x

Try it online!

Explanation

`        % Do...while
  G      %   Push input
  @      %   Push iteration index k, starting at 1
  QYrq   %   Random integer uniformly distributed in {0, 1, ..., k}. This is the
         %   loop condition. If non-zero (which occurs with probability k/(1+k))
         %   proceed with next iteration; else exit loop
]        % End
x        % Delete, as there are one too many strings. Implicitly display the stack

Answer 18

Perl 6,  50 41 38 36  26 bytes

{put $_//last for (($,$_),*⊎$_...*).map(*.pick)}

Try it

{eager ->{(++$).rand>.5??.put!!last}...*}

Try it

{eager ->{(++$).rand>.5??.put!!0}...0}

Try it

{eager ->{(++$).rand>.5&&.put}...!*}

Try it

.put while (++$/).rand>.5

(with -n commandline argument)

Try it

Answer 19

Python 3, 55 bytes

v=s=input();i=2
while hash(v)%i:print(s);i+=1;v=hash(v)

Explanation

To save having to import random, I've exploited the fact that the hash built-in is randomly seeded each time a python process is fired up (at least in MacOS). Each hash of the last hash should generate a series of pseudo-random integers.

If the hash is pseudo-random enough, the modulo with i is zero with probability 1/i.

Notes

I'm a little bothered by the redundant hash, but without a do-while, or in-condition assignment in Python, I'm a little stuck.

Answer 20

C#

This is same length as the top C# answer, but:

using System;s=>{var x=(1<<31)/new Random().Next();for(;++x>0;)Console.Write(s+" ");}

Just wanted to point out that some math can produce the correct probability.

int.MaxValue/new Random().Next()-1

Is equivalent to

(int)(1 / new Random().NextDouble()) - 1;

And the function f(x)=1/x-1 is:

f(1) = 0

f(1/2) = 1

f(1/3) = 2

f(1/4) = 3

So 1/2 a chance to be rounded down to 0, 1/6 a chance to be rounded down to 1, and 1/(n+1)(n+2) a chance to be rounded down to n.

Maybe some other language could capitalize on this.

EDIT: Fixed my mistake

I thought of something to make it smaller.

EDIT EDIT: I am just all kinds of wrong. Pulled the Random out of the loop because if it's evaluated multiple times, it won't work.

EDIT EDIT EDIT: I got rid of the variable i. I'm going to stop trying to shrink it now. Nope, lied. Got rid of another byte.

Answer 21

Charcoal, 17 bytes

ＳαＡ²βＷ‽β«⁺α¶Ａ⁺β¹β

Try it online! Verbose code included. Respects specs because it uses a random range from 0 to n.

Answer 22

C++, 97 96 57 bytes

Here my first try on codegolf :)

#include<iostream>
int main(){std::string S;std::cin>>S;int i=1;while(rand()%++i)puts(S.data());}

I saved one byte by using for

#include<iostream>
int main(){std::string S;std::cin>>S;for(int i=1;rand()%++i;)puts(S.data());}

Saved 39 bytes since nobody seems to count the includes

void p(string S){for(int i=1;rand()%++i;)puts(S.data());}

ungolfed

#include <iostream>
int main()
{
  // Create and read string from inputstream
  std::string S;
  std::cin >> S;       

  // rand % i: create random int in range [0, i-1]
  // Zero is seen as false and all positive int as true
  int i = 1;
  while (rand() % ++i) 
    puts(S.data());    
}

Answer 23

braingasm, 22 bytes

edit: Same byte count, but I realized I could sneak in the new tape Limit feature.

,[>,]>L+[+$rzQ>[.>]:>]

Uses 0 as separator. Works like this:

,[>,]                   Read a byte and move to next cell until end of input.
     >                  After the loop we're in an empty cell;
                          Leave it empty and move to the next.
      L                 Set tape limit here:
                          The tape will then wrap around if we move further.
       +                Increase current cell by one.
                          This cell will be our counter.
        [            ]  Loop until the counter is zero.
                          That won't happen, so it's an infinite loop.
         +              Increase again, so the first time the counter is 2.
          $r            Get a random number, 0 <= r > current cell
            zQ          Quit the program if that random number was 0
              >         Wrap around to the start of the tape.
               [.>]     Print the input stored on the tape
                          The loop will stop at the blank cell.
                   :    Print the blank cell as a number ("0")
                    >   Go to the next (last) cell

Answer 24

C, 41 bytes

n;f(char*s){for(n=1;rand()%++n;puts(s));}

Assumes rand is seeded. Try it online!

Answer 25

Python, 54 bytes

lambda s:int(1/random()-1)*(s+'|')
from random import*

Try it online!

Generated the number of copies as floor(1/p)-1 with p uniformly chosen from the unit interval. The number of copies is n when 1/p-1 falls between n and n+1, which happens when 1/(n+2) < p < 1/(n+1). This happens with probability 1/(n+1)-1/(n+2) or 1/((n+1)*(n+2). This is the desired probability of outputting n copies: 1/2 prob of 0, 1/6 prob of 1, 1/12 prob of 2,...

Answer 26

F#, 161 bytes

Definitely not the best language to golf, but I decided to give it a try (besides, I do not know anything about F#, so any tips on how to improve my answer will be welcome).

let f s=
 let r,z=System.Random(),(<>)0
 let p _=printfn"%s"s
 seq {for i in 2|>Seq.unfold(fun i->Some(i,i+1))do yield r.Next(i)}|>Seq.takeWhile z|>Seq.iter p

Execute with:

[<EntryPoint>]
let main argv =
    "test" |> f
    0

Writes a new line as separator.

Answer 27

Ruby, 29+1 = 30 bytes

Uses the -n flag.

i=1;puts$_ while i>rand(i+=1)

Try it online!

Answer 28

JS (ES6), 47 bytes

x=>{for(i=1;Math.random()<i/(i+1);i++)alert(x)}

Unlike the other ES6 answer, this uses a for loop and alert bombs instead of recursion. The seperator that is printed when the program stops is undefined.

Answer 29

PowerShell, 31 bytes

for($i=2;random($i++)){"$args"}

Get-Random $i outputs an n where 0 <= n < $i, separator is implicit newline.

Answer 30

Python, 75 bytes

The other Python answer is shorter, but I wanted to try it a different way:

from random import*
f=lambda d=1,s=input():randint(0,d)and s+'!'+f(d+1)or''

Answer 31

Dart - 73 chars

import"dart:math";p(s,{i=2}){while(new Random().nextInt(i++)>0)print(s);}

This function implements the algorithm by taking a string as input and printing it as necessary. The separator is obviously newline. To run it, you need a main method like main(){p("foo");}.

It's hard to be small when you need to import the math library and instantiate the Random class.

Try it online

Answer 32

APL (Dyalog), 17 bytes

Requires ⎕IO←0 which is default on many systems.

{⎕←⍺⋄×?⍵:⍺∇1+⍵}∘2

This is a monadic function derived from a dyadic function by currying the right argument.

{ anonymous function

 ⎕←⍺ print ⍺ (the string)

  ⋄  then

 ×?⍵: if the signum of a random int in the range [0,⍵-1] is 1, then:

 ⍺ ∇ 1+⍵ recurse with 1+⍵ as new right argument

 (implicit, else: stop)

}∘2 with 2 as bound right argument

Try it online! Sets ⎕RL←0 (Random Link) to avoid TIO's regeneration of the same random number.)

Answer 33

C# 79 bytes

does a divide by 0 error count as terminating?

using System;s=>{for(int i=1;2>1/new Random().Next(++i);Console.Write(s+' '));}

Answer 34

Scala 76 72 Bytes

def w[T](s:T)={var x=2;while(Random.nextFloat>1f/x){x=x+1;print(s+" ")}

This uses a template because it works fine for strings, and saves a character. Other than that, it's a pretty basic implementation. Scala picks up a couple bytes by not having a proper++ operator. Random.nextFloat returns a random value between 0 and 1, and 1f/x forces float division. This implementation uses a space as a separator, with no trailing newline.

Answer 35

Lua, 50 46 bytes

i=2while 1<math.random(i)do i=i+1print(...)end

Assumes that it is already seeded

Try it online!

Answer 36

k, 20 bytes

`0:((*1?2+)(1+)/0)#,

Explanation:

`0:((*1?2+)(1+)/0)#,
                0    /set x to 0
           (1+)      /add 1 to x...
    (*1?2+)    /     /...while randint [0,2+x) is > 0
   (             )#, /make array with that many copies of the string
`0:                  /output array line by line

Probabilities:

 5#{(((#:'=x{(*1?2+)(1+)/0}\0)@!x))%x}2000000      /experimental
0.5001625 0.1667005 0.083024   0.050034 0.0333645
 {(1%x)*-1_1.,*\{(x-1)%x}x}2+!5                    /calculated
0.5       0.1666667 0.08333333 0.05     0.03333333

Answer 37

Forth (gforth), 71 bytes

include random.fs
: f 1 1 do i 1+ random i = ?leave 2dup type cr loop ;

Try it online!

Technically will end after the [maximum single-cell number]th iteration, but the chance of that happening is at least 2^-64 on most systems (and likely 2^-32 on others)

Code Explanation

include random.fs  \ load the random library to generate random numbers

: f                \ start a new word definition
  1 1 do           \ loop from 1 to 0 (start at 1 stop when we reach 0 via integer overflow)
    i 1+ random    \ get a random integer from 0 to n
    i =            \ check if the value equals n
    ?leave         \ end the loop if true
    2dup type cr   \ otherwise, print the input string followed by newline
  loop             \ go back to beginning of loop
;                  \ end the word definition

Answer 38

Bash, 71 59 bytes

i=1;while((0<`shuf -i0-$i -n1`));do echo $1;i=$((i++));done

Try it online!

While is a better tool for this job

Answer 39

TI-BASIC, 24 22 bytes

-2 thanks to @lirtosiast

:Prompt Str1           //4 bytes
:While randInt(0,Ans+1 //9 bytes
:Disp Str1             //4 bytes
:Ans+1                 //4 bytes
:End                   //1 byte

Since all non-zero values are truthy, taking a random integer in between 0 and n-1 will give a random boolean with the correct probability.

Answer 40

Runic Enchantments, 20 bytes

i0q11+:'RA0=?;S:$S4?

Try it online!

Note that input is implicitly split on whitespace characters, so they need to be escaped.

Explanation

>                        Implicit entry
 i0q1                    Read input and set up stack
     1+                  Increment counter (value needs to be 2 for first loop)
       :'RA0=            Generate random value (non destructive to stack) and compare with 0
             ?;          If *not* 0, terminate
               S:$S      Otherwise duplicate and print string
                   4?    Skip next 4 instructions (implicit loop)

Newline variant, as printing a whitespace character as a separator costs an extra byte.