45
\$\begingroup\$

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 , so the shortest answer in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ Can the separator be an empty string? \$\endgroup\$
    – rturnbull
    Commented Jun 12, 2017 at 7:13
  • 18
    \$\begingroup\$ @rturnbull Well no, because in that case there is no separator. \$\endgroup\$
    – Fatalize
    Commented Jun 12, 2017 at 7:18
  • \$\begingroup\$ Do we have to print these one after the other, or can we just print all of them when the program terminates? \$\endgroup\$
    – Dennis
    Commented Jun 12, 2017 at 18:21
  • \$\begingroup\$ @Dennis One after the other. \$\endgroup\$
    – Fatalize
    Commented Jun 13, 2017 at 6:42

44 Answers 44

1
2
1
\$\begingroup\$

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

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

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

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

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+' '));}
\$\endgroup\$
1
\$\begingroup\$

Lua, 50 46 bytes

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

Assumes that it is already seeded

Try it online!

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

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.

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

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
\$\endgroup\$
2
  • \$\begingroup\$ @ValueInk Oh, I believe I misread! Fixing this now... \$\endgroup\$
    – zgrep
    Commented Jun 15, 2017 at 22:44
  • \$\begingroup\$ @ValueInk Fixed. \$\endgroup\$
    – zgrep
    Commented Jun 15, 2017 at 23:12
1
\$\begingroup\$

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
  
 
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can use x+=1 to save a byte \$\endgroup\$
    – user
    Commented Jul 24, 2021 at 19:33
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

JavaScript (Node.js), 40 bytes

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

Try it online!

Act same

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

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

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ Why not Ans instead of A? \$\endgroup\$
    – lirtosiast
    Commented Jul 11, 2017 at 1:30
  • \$\begingroup\$ @lirtosiast Either works, but they have the same byte count and there is no reason to use Ans over A. A takes up less screen space, so I chose it. \$\endgroup\$ Commented Jul 15, 2017 at 16:41
  • \$\begingroup\$ I was thinking you could avoid the →A, since you don't use Ans for anything else, and both Ans and A default to 0. \$\endgroup\$
    – lirtosiast
    Commented Jul 15, 2017 at 22:40
  • \$\begingroup\$ @lirtosiast Ah, OK, thanks. \$\endgroup\$ Commented Jul 16, 2017 at 0:36
0
\$\begingroup\$

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.

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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