28
\$\begingroup\$

Output the numbers 1-16 (or any other set of 16 distinct items). Then, repeatedly, output a random value chosen uniformly from the last 16 items outputted.

After the same item is printed 16 times in a row, halt.

If a number appears multiple times in the last 16 values, it should have proportionally more chance to be chosen as the next number. If a number did not appear in the last 16 elements, it can't be chosen ever again.

0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.

\$\endgroup\$
16
  • 1
    \$\begingroup\$ Can the first 16 items be separated with a space, and then the rest separated with a newline (like this)? \$\endgroup\$
    – The Thonnu
    Commented Feb 1, 2023 at 12:45
  • 2
    \$\begingroup\$ @TheThonnu No, I don't think that would feel like "one sequence" \$\endgroup\$
    – mousetail
    Commented Feb 1, 2023 at 12:48
  • 5
    \$\begingroup\$ After the same item is printed 16 times in a row or more, halt. How could the same item be printed more than 16 times if we halt as soon as it has appeared 16 times? \$\endgroup\$
    – Arnauld
    Commented Feb 1, 2023 at 12:49
  • 2
    \$\begingroup\$ @KevinCruijssen probably yes, because OP suggested a version which outputs a list on my Python answer. \$\endgroup\$
    – The Thonnu
    Commented Feb 1, 2023 at 16:33
  • 4
    \$\begingroup\$ For 0 bonus points the odds of numbers 1, 2, 3, ... , 16 being the last one standing are 1 : 2 : 3 : ... : 16 \$\endgroup\$
    – AndrovT
    Commented Feb 1, 2023 at 18:41

32 Answers 32

10
\$\begingroup\$

Python, 102 88 86 85 84 bytes

from random import*;*t,=range(16)
while~-len({*(x:=t[-16:])}):t+=choice(x),
print(t)

Attempt This Online!

  • -14 thanks to mousetail
  • -1 thanks to loopy walt

Prints a list of numbers from 0 to 15.

Commented

from random import*;     # Import the random module for later
*t,=range(16)            # Set t equal to [0, 1, ..., 15]
                         # ([* ... ] unpacks it into a list)
while~-len(              # Loop while the number of unique items
      {*(x:=t[-16:])}):  # in the last 16 elements of t is not 1
                         # (setting x to the last 16 elements of t)
    t+=choice(x),        # Append a random element of x to t
print(t)                 # At the end, output t
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 88 bytes \$\endgroup\$
    – mousetail
    Commented Feb 1, 2023 at 13:32
  • 2
    \$\begingroup\$ @mousetail thanks! I removed the space after import and changed the +=[...] to +=..., for another two bytes saved. \$\endgroup\$
    – The Thonnu
    Commented Feb 1, 2023 at 13:35
  • 2
    \$\begingroup\$ I think t=[*range(16)] can be *t,=range(16) for -1. \$\endgroup\$
    – loopy walt
    Commented Feb 2, 2023 at 2:54
10
\$\begingroup\$

Ruby, 55 51 48 bytes

puts x=[*1..16];_,*x=x<<p(x.sample)while(x|x)[1]

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ That's beautiful. \$\endgroup\$ Commented Feb 2, 2023 at 16:46
9
\$\begingroup\$

R, 66 61 bytes

x=Map(show,L<-1:16)
while(sd(L))L=c(L[-1],print(sample(L,1)))

Try it online!

Explanation outline:

  1. Map the show function over 1:16 (and save the vector to variable L).
  2. We assign the result of the Map to x to avoid outputting its value (ugly list of nulls).
  3. Then we sample one element from L and append to L[-1] (L without the first element).
  4. Loop until sd(L)==0 (this means that the last 16 numbers are all the same).
\$\endgroup\$
2
  • \$\begingroup\$ I don't think this stops when the same value is output 16 times in a row \$\endgroup\$
    – The Thonnu
    Commented Feb 1, 2023 at 12:47
  • 1
    \$\begingroup\$ @TheThonnu right, I didn't read the specs carefully enough. Thanks! \$\endgroup\$
    – pajonk
    Commented Feb 1, 2023 at 12:52
8
\$\begingroup\$

R, 52 bytes

a=b=16:1;while(sd(a[b]))a=c(sample(a[b],1),a);rev(a)

Try it online!

Full program that yields an R vector containing the sequence of values.
R displays this by default with index numbers (in square brackets) at the start of each line. If this is annoying, add 5 bytes more to wrap the output into a call to cat() like this.

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

JavaScript (ES7), 74 bytes

Same algorithm as the other version, but using the weirder set "5368709124,false".

f=(s=2**29+[4,k=!1])=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

Try it online!

How?

\$2^{29}=536870912\$ contains all digits from \$0\$ to \$9\$ exactly once, except \$4\$. Adding [4,!1] forces a coercion to a string and appends "4", followed by a comma, followed by "false".


JavaScript (ES6), 83 bytes

Uses the hexadecimal characters 0-9 and A-F.

f=(s=(k=0)+'123456789ABCDEF')=>/(.)\1{15}/.test(s)?s:f(s+s[Math.random()*16+k++|0])

Try it online!

Commented

f = (                 // f is a recursive function taking:
  s = (k = 0) +       //   s = output string
    '123456789ABCDEF' //   k = counter
) =>                  //
/(.)\1{15}/.test(s)   // if s contains the same character repeated
?                     // 16 times in a row:
  s                   //   stop and return s
:                     // else:
  f(                  //   do a recursive call:
    s +               //     append to s
    s[                //     the character from s
      Math.random()   //     whose index is randomly chosen in
      * 16 + k++ | 0  //     [k .. k+15] (increment k afterwards)
    ]                 //     i.e. one of the last 16 characters
  )                   //   end of recursive call
\$\endgroup\$
8
\$\begingroup\$

Vyxal, 15 13 12 9 bytes

k6≬℅+Ḣ↔ƒ⋎

Try it Online! Outputs characters from the string "0123456789abcdef"

-3 thanks to emanresu

Explained (old)

k6≬℅+Ḣ↔ḣvt∑+
k6           # The string "0123456789abcdef"
  ≬   ↔      # apply the following and collect results while invariant:
   ℅+        #  append a random item of the string to the string
     Ḣ       #  remove the first character
       ḣvt   # separate the first item from that list and get the tail of each remaining item
          ∑+ # join that into a single string and append to the previously separated head
\$\endgroup\$
3
7
\$\begingroup\$

Brachylog, 18 bytes

15⟦ẉ₂ᵐ{=|ṛRẉ&b,R↰}

Try it online!

15⟦                  The list [0, …, 15]
   ẉ₂ᵐ               Map writeln
      {           }  If
       =               All elements of the list are equal, then stop
        |            Else
         ṛR            R is a random element of the list
          Rẉ           writeln R
            &b         Remove the first element of the list
              ,R       Append R to the list
                ↰      Recursive call on this list
\$\endgroup\$
6
\$\begingroup\$

C (gcc), 105 bytes

j,k;a[16];f(i){for(k=i=16;a[--i]=i;);for(;k;j-(a[i++%16]=a[rand()%16])?k=16:--k)printf("%d ",j=a[i%16]);}

Try it online!

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

Japt, 20 19 bytes

Far too long but seeing as Japt has no infinite loops and can't loop until invariant, it'll have to do for now.

Go
@òÎÌʨG}a@pUsX ö

Test it

Go\n@òÎÌʨG}a@pUsX ö
G                        :16
 o                       :Range [0,G)
  \n                     :Assign to variable U
    @                    :Left function
     ò                   :  Partition U between elements where
      Î                  :    Sign of difference is truthy (non-zero)
       Ì                 :  Last element
        Ê                :  Length
         ¨G              :  >=16
           }             :End function
            a            :Run right function until left function returns true and return final result
             @           :Right function, taking 0-based iteration index X as argument
              p          :  Push to U
               UsX       :    Slice U from index X
                   ö     :    Random element
\$\endgroup\$
1
  • \$\begingroup\$ I never knew you could use a that way, I'll have to see if I can use that next time I try a "repeat until condition" challenge. \$\endgroup\$ Commented Feb 1, 2023 at 21:10
5
\$\begingroup\$

05AB1E --no-lazy, 15 14 bytes

16L€=[DΩ=ª¦DË#

Try it online!

  • -1 thanks to Kevin Cruijssen

Alternative 15 bytes solution (thanks to Kevin Cruijssen)

16L[D16.£©Ωª®Ë#

Try it Online!

Explanation

16L             # Push [1..16]
   €=           # Print each item
     [          # Start an infinite loop:
      DΩ        #  Duplicate and push a random element of the list
        =ª      #  Print and append to the list
          ¦     #  Remove the first item
           DË#  #  If all items are equal, break
\$\endgroup\$
2
  • \$\begingroup\$ Outputting as a list is apparently 15 bytes as well: 16L[D16.£©Ωª®Ë# \$\endgroup\$ Commented Feb 1, 2023 at 16:34
  • \$\begingroup\$ You can golf D», to €= (although does require the --no-lazy flag since we're printing inside a map) for -1 byte: try it online. \$\endgroup\$ Commented Feb 1, 2023 at 16:35
5
\$\begingroup\$

Python, 77 bytes

from random import*
t=range(16)
while t:T,*s=*t,choice(t);t=s[t==s:];print(T)

Attempt This Online!

Prints one number per line.

How?

The two mildly clever bits are

  1. the rolling tail end of the sequence is all equal if and only if it's equal to its next iteration
  2. for the winding down it doesn't matter whether we truncate from the right (more logical) or the left (shorter) since all elements are equal
\$\endgroup\$
5
\$\begingroup\$

Nibbles, 10 bytes (20 nibbles)*

/`.,16>>:$=`#$16$:/

*Nibbles is a pure functional language and has no random number capability.
So, this program uses the hash-modulo-16 of the last 16 values after each pick to select the next index. This is pseudo-random, but obviously will be the same on each run of the program.
To more-closely mimic PRNGs from other programming languages, we can select a 'salt' value for the hash, to act as a 'seed': this needs to be appended to the program, and, additionally, the otherwise-implicit variables of the program then need to be explicitly specified, costing +3 nibbles (+1.5 bytes, so 11.5 bytes not including the 'seed' itself).

/`.,16>>:$=`#$16$:/
 `.                     # iterate while unique
   ,16                  # starting with 1..16:
        :$              #   join the last list to
          =     $       #   its element at index
           `#$          #   itself hashed
              16        #   modulo-16
/                       # now, fold over this list from the right:
                 :      #   joining 
                  /     #     the (implicit) first element of the (implicit) left argument
                        #     to the (implicit) right argument

enter image description here

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

J, 31 bytes

(,1}._1{"1(}.,?@#{])^:a:)@i.@16

Try it online!

0 bonus points to whoever can provide the probability distribution of each number becoming the last one standing.

┌──┬──────┐
│0 │1/136 │
├──┼──────┤
│1 │2/136 │
├──┼──────┤
│2 │3/136 │
├──┼──────┤
│3 │4/136 │
├──┼──────┤
│4 │5/136 │
├──┼──────┤
│5 │6/136 │
├──┼──────┤
│6 │7/136 │
├──┼──────┤
│7 │8/136 │
├──┼──────┤
│8 │9/136 │
├──┼──────┤
│9 │10/136│
├──┼──────┤
│10│11/136│
├──┼──────┤
│11│12/136│
├──┼──────┤
│12│13/136│
├──┼──────┤
│13│14/136│
├──┼──────┤
│14│15/136│
├──┼──────┤
│15│16/136│
└──┴──────┘

Proof: For example, the system of equations you'd solve for the n=3 case is:

$$ \begin{align} x_1 &= \frac{x_3}{3} \\ x_2 &= x_1 + \frac{x_3}{3} \\ x_3 &= x_2 + \frac{x_3}{3} \\ x_1 + x_2 + x_3 &= 1 \end{align} $$

where \$x_1\$ is the chance that number in positon 1 wins, etc -- where 1, if it is not picked the first round, vanishes forever.

The first equation represents that 1/3 of the time \$x_1\$ will be picked and move into position 3, and the rest of the time of vanish. Thus its "value" is 1/3 of \$x_3\$'s.

Similarly, \$x_2\$ will always move into slot 1, where it has \$x_1\$ chance of winning, and 1/3 of the time will also move into slot 3, giving it \$x_3\$ chance of winning. And so on...

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Surely (i+1)/136 would be a golfer way to express the probability:) \$\endgroup\$
    – Simd
    Commented Feb 2, 2023 at 7:40
  • 2
    \$\begingroup\$ I can’t pass up a chance to use J’s box drawing… \$\endgroup\$
    – Jonah
    Commented Feb 2, 2023 at 15:12
4
\$\begingroup\$

Excel (ms365), 109 bytes

I do hope that this could get OP's approval. Since volatility would stand in the way of using a list of elements, the only way I could think about a repetitive function that would auto-stop when last 16 elements are exactly the same is to use a custom function made with the name-manager. In this case my function is called 'Z':

=LAMBDA(x,LET(y,RIGHT(x,16),IF(y=REPT(RIGHT(y),16),x,Z(x&MID(y,RANDBETWEEN(1,16),1)))))

enter image description here

Formula in A1:

=Z("ABCDEFGHIJKLMNOP")

This would make for a combined total of 87 + 22 = 109 bytes.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I was really rooting for L. but K pulled through. \$\endgroup\$ Commented Feb 1, 2023 at 20:56
4
\$\begingroup\$

TI-Basic, 54 bytes

For(I,1,16
Disp I
End
cumSum(1 or rand(16
While max(Ans≠max(Ans
augment(ΔList(cumSum(Ans)),{Ans(randInt(1,16
Disp Ans(16
End

max(abs(ΔList(Ans can be used instead of max(Ans≠max(Ans alternatively.

\$\endgroup\$
2
  • \$\begingroup\$ Where does 54 bytes come from? I only calculated 7+2+1+7+6+15+5+1=44 tokens and 7 linebreaks, resulting in 51 bytes. \$\endgroup\$
    – user694733
    Commented Feb 3, 2023 at 13:43
  • \$\begingroup\$ @user694733 ΔList( and cumSum( are worth 2 bytes each. \$\endgroup\$
    – Yousername
    Commented Feb 3, 2023 at 13:49
4
\$\begingroup\$

Pyth, 16 15 bytes

pK<TGWt{=t+KpOK

Try it online!

Thanks @isaacg for -1 byte

Explanation

 K<TG              # K = "abcdefghijklmnop" (all but the last ten elements of the alphabet)
p                  # print(K)
     Wt{           # while deduplicated K has more than one element
            pOK    #   print a random element of K
          +K       #   append this to K
        =t         #   remove the first element of K
\$\endgroup\$
1
  • \$\begingroup\$ Switching from numbers to letters saves 1 byte: Try it online! \$\endgroup\$
    – isaacg
    Commented Feb 2, 2023 at 18:25
3
\$\begingroup\$

Retina, 43 bytes


16*.
Y`.`L
/(.)\1{15}$/^+-16,@v`(.).*
$&$1

Try it online! Uses ABCDEFGHIJKLMNOP. Explanation:


16*.

Insert 16 .s.

Y`.`L

Transliterate them to uppercase letters using a different letter each time.

/(.)\1{15}$/^+

Repeat until the last 16 letters are identical.

-16,@v`

Randomly choose between one of the last 16 overlapping matches.

(.).*

Match any character and the rest of the string.

$&$1

Append the initial character to the match, i.e. append it to the string.

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

Go, 177 bytes

import."math/rand"
func f(){N,M,l:=[]int{},1,16;for i:=1;i<17;i++{N=append(N,i);println(i)}
for M<16{k:=Intn(16)
x:=N[k]
println(x)
N=append(N[1:],x)
if x!=l{l=x;M=1}else{M++}}}

Attempt This Online!

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

Zsh, 73 bytes

set {a..p};<<<${(F)@};while 17=$@[RANDOM%16+1];shift;<<<$16;((${#@:#$1}))

Try it online!

I use single letters instead of up-to-two-digit numbers as the “16 distinct items”, which saves a byte. (It also gives extra flexibility, which I took advantage of in an earlier version of this answer with a more complex termination condition.)

Expanded and commented:

set {a..p}                    # set positional arguments 1=a, 2=b, ...
<<<${(F)@}                    # join arguments with newline, call implicit cat
while
  17=$@[RANDOM%16+1];         # append a random element
  shift;                      # remove the first element
  <<<$16;                     # print the last element
  ((${#@:#$1}))               # termination condition (see below)
                              # no loop body = empty loop body

For those unfamiliar with zsh: the positional arguments can be accessed through $1, $2, … like in other shells, and also through the variable @ which mostly behaves like an array. Zsh array indexes start at 1. RANDOM is a special variable that returns a random number each time it's accessed; fortunately the range 0..32767 is dividible by 16 so all values are equally likely modulo 16.

Now for the termination condition. It's the arithmetic expression ${#@:#$1}: the command is true if the integer expression has a nonzero value. The expression uses several parameter expansion features. From the outside in, first, we have ${#spec} to count the number of elements in the parameter expansion of spec. Inside, we have ${name:#pattern} which, when name is an array, removes the elements that match pattern. The name is @, i.e. the positional parameters. The pattern is $1. Thus we count the number of positional parameters that are not equal to the first one: this is 0 if and only if all the positional parameters are equal.

\$\endgroup\$
2
  • \$\begingroup\$ Nice. So the while condition exits if the anonymous function receives 0 arguments and thus evaluates to "false"? \$\endgroup\$
    – roblogic
    Commented Feb 5, 2023 at 23:11
  • 1
    \$\begingroup\$ @roblogic That's right. But since then I've realized that by using ${name:#pattern} instead of ${name#pattern}, I don't need the empty parameter elimination, and so I don't need an auxiliary function, which saves 3 characters (minus 1 lost for the extra :). \$\endgroup\$ Commented Feb 6, 2023 at 0:05
3
\$\begingroup\$

Julia, 73 70 69 bytes

^,~=last,rand
s=[1:16;]
while s∩s^16!=s^1
push!(s,~s^16)end
show(s)

Attempt This Online!

  • -1 byte thanks to MarcMush: reassign operators on the same line
    • (Otherwise, a space is needed between ^ and =)
  • -2 bytes thanks to MarcMush: replace !allequal(s^16) with s∩s^16!=s^1
    • (!allequal(last(s,16)) with s∩last(s,16)!=last(s,1))
  • -1 byte thanks to MarcMush: remove the newline before end
  • Thanks also to MarcMush for spotting an error or two!
\$\endgroup\$
0
2
\$\begingroup\$

Charcoal, 24 bytes

≔…α¹⁶θθW∧⁻θ⌊θ‽θ«ι≔⁺Φθλιθ

Try it online! Link is to verbose version of code. Uses ABCDEFGHIJKLMNOP. Explanation:

≔…α¹⁶θθ

Get and print the first 16 uppercase letters.

W∧⁻θ⌊θ‽θ«ι

While there is a choice of at least two different letters, pick and output a random letter from those remaining.

≔⁺Φθλιθ

Update the string of available letters.

23 bytes if the last letter does not need to be printed (it will be the same as the preceding 15):

≔…α¹⁶θW⁻θ⌊θ«→Pθ≔⁺Φθλ‽θθ

Try it online! Link is to verbose version of code.

\$\endgroup\$
2
\$\begingroup\$

Pip, 21 bytes

P*Y,16T$=yY SyAE PRCy

Uses 0 to 15. Attempt This Online!

Explanation

P*Y,16T$=yY SyAE PRCy
   ,16                 ; Range(16)
  Y                    ; Yank, storing in y variable
P*                     ; Print each
      T                ; Loop till
       $=y             ; all elements of y are equal:
                  RCy  ;  Choose a random element of y
                 P     ;  Print it
              AE       ;  Append that element to
            Sy         ;  y without its first element
          Y            ;  Yank that list as the new value of y
\$\endgroup\$
2
\$\begingroup\$

Factor, 69 bytes

16 iota [ dup 16 tail* dup all-eq? ] [ random suffix ] until drop ...

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Raku, 56 bytes

|(1..16),{@_.tail(16).pick}...{~@_~~/(\d+)[' '$0]**15$/}

Try it online!

This is a sequence of the form initial-elements, { generator } ... { termination-check }.

  • The initial elements are from the range 1..16, flattened with |.
  • The generator takes the entire sequence generated so far in @_, then randomly picks an element from the last sixteen of them.
  • The termination check stringifies the sequence, then checks that the string satisfies a regex: a space-separate sequence of digits that repeats sixteen times before the end of the string.
\$\endgroup\$
2
\$\begingroup\$

CJam, 24 23 bytes

G,_:p;{_mR_p+(;__|,(}g;

Try it online!

Explanation

G,_:p;                        create and print an array [0-16)
      {             }g        do...
       _mR                      pick a random number from the last 16
          _p+(;                 print, add to the list, and remove the oldest number
               __|,(          ...while the number of unique numbers in the last 16 != 1
                      ;       cleanup

(-1 byte) replacing 1- with (, courtesy of my bestie

\$\endgroup\$
2
\$\begingroup\$

Arturo, 74 70 67 bytes

a:@0..15prints a until[prints->a\0[]=a--a\0][a:@[sample a]++chop a]

Try it

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

Swift 5.6+, 107 bytes

var a=[_](1...16),i=0
a.map{print($0)}
while Set(a).count>1{a[i]=a.randomElement()!
print(a[i])
i=(i+1)%16}

Uses a as a circular buffer, overwriting a different position each run through the loop. For lack of a builtin "all elements are the same" operation, the loop condition converts it to a Set to count the number of unique elements.

SwiftFiddle link

Ungolfed:

var arr = Array(1...16)

for el in arr {
  print(el)
}

var i = 0
while Set(arr).count > 1 {
    let x = arr.randomElement()!
    print(x)
    arr[i] = x
    i = (i + 1) % arr.count
}
\$\endgroup\$
1
\$\begingroup\$

PHP 8, 110 bytes

$o=range(1,16);do$o[]=$o[count($o)-rand(1,16)];while(count(array_unique(array_slice($o,-16)))>1);print_r($o);

I wish PHP's array syntax was a little less verbose...

Works by building up an array by appending a random element from the last 16 elements, then printing it all at once, when the last 16 elements are all the same.

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

Zsh, 101 bytes

seq 16|tee a;set `shuf a`
while shift;16=`shuf -n1 a`;<<<$16;s=(${(n)@});((s[1]<s[16]))&&<<<${(F)@}>a

Try it online!   114 bytes   117b

Writes/reads from file a. Uses the shell $argv array to randomise and pick new values, and a sorted array $s to check equality.

Whoops, the initial version incorrectly ran forever. And then the second version was not uniformly random. Fixed now. Thanks to @Gillies for -13 bytes.

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

Java 8, 135 bytes

()->{int a,m=16,i=0,c=1,t[]=new int[m];for(;c<m;c=a==t[(i+++15)%m]?c+1:1)System.out.println(t[i%m]=a=i<m?i:t[(int)(Math.random()*m)]);}

Try it online!

Even if Java always loses by far, it was still a fun challenge to code!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The best answer in each language wins. As long as there is no shorter answer in Java specifically you are a winner \$\endgroup\$
    – mousetail
    Commented Feb 3, 2023 at 14:12

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.