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

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 2

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 3

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 4

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 5

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 6

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 7

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 8

Scala 76 72 71 Bytes

def w[T](s:T)={var x=2;while(Random.nextFloat>1f/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 9

Thunno 2, 7 bytes

(ṅƙɼḅ;£

Attempt This Online!

Explanation

(ṅƙɼḅ;£  # Implicit input
(        # while
 ṅ       # (condition)  0-based iteration index
  ƙ      #              increment twice
   ɼ     #              random item from [1..that]
    ḅ    #              equals one?
     ;£  # (body)  print input string with newline
         # Implicit output

Answer 10

Trilangle, 104 bytes

'0.<_.<.>i.S)#..\_/.L',z$)<.Se(*8'.3....LS:.)~<#+7....@..^.-/...,>j))2<.L,z,<......><#(,.#o.....\",o,../

Try it on the online interpreter!

The random number instruction $ creates a random number along the whole range of integers. This program uses the sign of \$\left|rand\left(\right)\right|+\frac{INT\_MIN}{i+1}\$ to determine whether to terminate.

I don't currently have the ability to create the colorized drawing I normally do, but here's an annotated disassembly. I created this first, then wrote the program, and then tweaked this to match the output of the disassembler.

; Get the string and its length. Pretty standard.
    PSI #0
input_loop: ; 0.2
    GTC
    BNG input_cleanup
    SWP
    INC
    JMP input_loop
input_cleanup: ; 2.0
; Put the iteration number on top of the stack. Rather than popping the -1 to
; push 0, just increment it.
    INC
; These swaps happened to be here, and they don't do anything
    SWP
    SWP
; Increment the iteration number and check whether to terminate
check_term: ; 2.10
    INC
    RND
; RND gives a number in [-0x800000, 0x7fffff].
; Terminate with probability 1/(i+1).
    DP2
    POP
; Get INT_MIN as 2^23. This overflows and becomes a negative number.
    PSI #3
    PSI #8
    MUL
    DEC
    EXP
; then do the division and compare
    SWP
    INC
    DIV
    SWP
    BNG rand_neg
; Stack: [...s, s.length, i, INT_MIN/(i+1), rand]
; Terminate when rand + INT_MIN/(i+1) < 0
    ADD
compare: ; 3.2
; Flip the sign, then end when it's positive instead of negative. It turned out
; to save room to make the positive branch terminate.
    NOT
    BNG print_begin
    JMP end ; disassembler quirk ¯\_(ツ)_/¯
rand_neg: ; 4.0
; Stack: [...s, s.length, i, INT_MIN/(i+1), rand]
; Terminate when INT_MIN/(i+1) - rand < 0
    SUB
    JMP compare
end: ; 5.0
    EXT
print_begin: ; 6.0
    POP
; Print the string.
; DP2 + POP is shorter than PSI #1 + IDX
    DP2
    POP
print_loop: ; 6.6
    BNG print_done
    DUP
; INC + INC is shorter than PSI #2 + ADD
    INC
    INC
    IDX
    PTC
    POP
    DEC
    JMP print_loop
; Print a separator, then loop back.
print_done: ; 8.0
    PSC ','
    PTC
    POP
    POP
    JMP check_term

I have a feeling that this can be shrunk, as there's a significant amount of unused space, but I haven't figured anything out yet.

Answer 11

JavaScript (Node.js), 40 bytes

x=>Array(0|.5/Math.random()).fill(x)+','

Try it online!

Act same

Answer 12

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 13

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 14

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.