31
\$\begingroup\$

Your task is to make a program that takes in an integer n > 1, and outputs the roll of a single n-sided die. However, this dice follows the rules for exploding dice.

When you roll the die, check what value you rolled. If you got the maximum for that kind of die (on a standard d4 that would be 4, or 6 on a d6, etc.), roll again and add the new roll to that total. Each roll continues adding to the total, until you don't roll the max number anymore. That final number is still added though.

Your program should take in a single integer n, and roll the exploding n-sided die. Here's an example distribution to show what it should look like for n=4. Note that you should never output any multiples of n, since they will always explode.

You can assume the stack size for any recursion you do is infinite, and your random function must meet our standards for randomness (built-in random generator or time/date). Your random function should also be as uniform as possible, vs. something like a geometric distribution, since these are dice we're talking about.

\$\endgroup\$
  • 1
    \$\begingroup\$ does the program have to be perfect? Like can its distribution be off by some extremely low amount? \$\endgroup\$ – Maltysen Apr 12 at 14:38
  • \$\begingroup\$ To: Riker; RE: @Maltysen's comment above; or extremely high amount? \$\endgroup\$ – Artemis Fowl Apr 12 at 15:09
  • 2
    \$\begingroup\$ @ArtemisFowl See our standards for randomness. Also, here. \$\endgroup\$ – Rɪᴋᴇʀ Apr 12 at 22:46

50 Answers 50

2
\$\begingroup\$

JavaScript (ES6),  39  30 bytes

Saved 9 bytes thanks to @tsh!

f=n=>Math.random()*n|0||n+f(n)

Try it online! or See the distribution for n=4

\$\endgroup\$
  • 1
    \$\begingroup\$ 30 bytes, f=n=>Math.random()*n|0||n+f(n) \$\endgroup\$ – tsh Apr 15 at 9:18
2
\$\begingroup\$

Excel (pure), 43 bytes

=A1*INT(-LOG(RAND(),A1))-INT(RAND()*(1-A1))

Takes input from A1, outputs in the cell you put this formula.

Explanation

This uses the observation from Robin Ryder's R solution that the requested distribution is the sum of n times a Geom(1-1/n) and an independent Uniform(1..n-1) distribution. The clever bit is that

INT(-LOG(RAND(),A1))

uses a logarithm to scale a Uniform(0,1) distribution exactly to the desired geometric distribution: for instance, with A1=6, the LOG maps the interval (1/6,1) to the interval (-1,0), the interval (1/36,1/6) to the interval (-2, -1), and so on. I also save a +1 on the uniform distribution by scaling a random number "backwards" to (1-A1, 0), then subtracting the floor of this negative number.

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

Haskell, 94 81 78 bytes

import System.Random
f n=do i<-randomRIO(1,n);last$((i+)<$>f n):[return i|i<n]

Try it online!


Original

Quite similar to @dfeuer's, but using do notation.

  • -13 bytes by removing whitespace, thanks to @dfeuer
  • -3 bytes thanks to this
\$\endgroup\$
  • \$\begingroup\$ 81 bytes \$\endgroup\$ – dfeuer Apr 13 at 2:13
  • \$\begingroup\$ Wuups, fixed the typo! And thanks for the suggestion :) \$\endgroup\$ – bugs Apr 13 at 10:16
2
\$\begingroup\$

Octave/MATLAB with Statistics Package/Toolbox, 30 bytes

@(n)geornd(1-1/n)*n+randi(n-1)

Try it online!

How it works

This is an anonymous function which takes n as input and produces a number obtained as follows. The function generates a geometric random variable with parameter 1-1/n (this models the number of rolls that produce n), multiplies by n, and adds a random variable uniformly distributed from 1 to n-1 (this models the last roll).

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

><>, 90 bytes

0&  v
v:::<             <
v/1>{1-:?!v}
>x0^v10~  <
 ^
5=?v>:@}}*{+{2*l
&n;>,*:1%-1+:&+&=?^

Try it online!

The whitespace on the second line is bugging me. I'll work on golfing that out.


><> doesn't have a nice method for producing uniform random integers. This approach generates, for input \$N\$, a random number produced by generating \$N\$ random bits, then taking the resulting binary integer and dividing it by \$2^N\$. This process is repeated until \$N\$ is not generated by this process.

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

Attache, 30 bytes

f:=${If[x=y,f@x+y,y]}#1&Random

Try it online!

Direct implementation of the process.

Alternatives

36 bytes: ${NestWhile[{_+Random[1,x]},x&`|,0]}

37 bytes: ${NestWhile[{_+Random[1,x]},{x|_},0]}

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

Perl 6, 26 bytes

{[+] {^$_ .roll+1}...$_>*}

Try it online!

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

Python 3, 80 bytes

This is pretty much just a tail-call recursive version of @Artemis Fowl's answer, but I liked doing it without unrolling into a while loop.

Uses an accumulator parameter to return the total rolled value once the exploding stops.

from random import*
def r(n,a=0):v=randint(1,n);a+=v;return r(n,a)if v==n else a
\$\endgroup\$
  • \$\begingroup\$ I don’t think python does tail-call optimization, does it? Regardless, good answer anyways! \$\endgroup\$ – JPeroutek Apr 15 at 17:21
  • \$\begingroup\$ Unfortunately not. I've heard that Guido doesn't want python to turn into a functional language 😜 \$\endgroup\$ – Delya Erricson Apr 15 at 17:23
1
\$\begingroup\$

Charcoal, 17 bytes

NθW⁼Lυ№υθ⊞υ⊕‽θIΣυ

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

Nθ

Input n.

W⁼Lυ№υθ

Repeat while the predefined empty list only contains ns (i.e. its length equals its count of ns)...

⊞υ⊕‽θ

... push a random integer from 1 to n to the list.

IΣυ

Print the total.

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

C# (Visual C# Interactive Compiler), 60 bytes

int f(int n,int k=1)=>(k=new Random().Next(n)+1)<n?k:k+f(n);

Saved 4 bytes thanks to @ExpiredData!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 60 bytes \$\endgroup\$ – Expired Data Apr 12 at 19:48
  • \$\begingroup\$ @ExpiredData Using new Random() gives it the same seed if you call it again, which doesn't make it truly random \$\endgroup\$ – Embodiment of Ignorance Apr 12 at 20:11
  • \$\begingroup\$ Nah it's a new seed, run my tio a few times. But even if it was same seed random() isn't true random anyway it's a prng.... \$\endgroup\$ – Expired Data Apr 12 at 20:40
  • \$\begingroup\$ I've noticed when running on TIO, you either get values less than n or way, way, higher. I think creating a new Random in a tight loop causes the same seed to be used? In any case, this might save a byte? int f(int n,int k=1)=>(k+=new Random().Next(n))<n?k:k+f(n); \$\endgroup\$ – dana Apr 13 at 5:38
  • 1
    \$\begingroup\$ This is longer, but seems to give better results? var r=new Random();int k;int f(int n)=>(k=r.Next(n)+1)<n?k:k+f(n); \$\endgroup\$ – dana Apr 13 at 5:42
1
\$\begingroup\$

Perl 6, 25 bytes

{sum {.rand+|0+1}...$_>*}

Try it online!

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

SmileBASIC 3, 49 bytes

Function D N OUT R implements exploding dice rolls recursively.

DEF D N OUT R
R=RND(N)+1IF R==N THEN R=R+D(N)
END

Ungolfed

DEF D N OUT R  'N is sides and R is output param (shorter than using RETURN in this case)
 R=RND(N)+1  'random number in [1, N]
 IF R==N THEN R=R+D(N)  'if roll is same as N then roll again and add
END

Note that in SmileBASIC, functions can have multiple return values. If a function has one return value then fun in OUT var and var = fun(in) are exactly the same, which is why we can define the function in OUT form and also call it in an expression in the function body itself. If I had defined the function as DEF D(N) I would have to explicitly state RETURN R in the function body; mixing both syntaxes saved me bytes.

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

F#, 83 bytes

let r=System.Random()
let e d=
 let mutable t=0
 while t%d=0 do t<-t+r.Next(d)+1
 t

Try it online! The first argument in the TIO program is the number of sides on the die, the second is the amount of tests to make. The output is printed to the console and shows each total and the number of times it has been rolled.

The random number generator r is initialised outside of the function. Initialising it within the function, combined with calling this function many times in succession, will cause it to return the same random numbers over and over again (try it for yourself!)

For the life of me I could not figure out how to write this without using mutable, especially since the last roll must be counted (Seq.takeWhile would not include the terminating element). I thought about using Seq.mapFold but it seems like it evaluates the input sequence first, which was a no-go for me.

\$\endgroup\$
  • \$\begingroup\$ You're implementing so many extra things. They don't appear to be in the code you're counting, though, so...okay. \$\endgroup\$ – Stackstuck Apr 17 at 8:18
  • \$\begingroup\$ What do you mean by extra things? \$\endgroup\$ – Ciaran_McCarthy Apr 17 at 20:04
  • \$\begingroup\$ "shows ...the number of times it has been rolled", not a requirement. \$\endgroup\$ – Stackstuck Apr 17 at 21:14
  • \$\begingroup\$ ..You need to roll one exploding die. Not 10,000. I'm not sure this is valid...? \$\endgroup\$ – Stackstuck Apr 17 at 21:22
  • \$\begingroup\$ The submission does only roll one die. The TIO program demonstrates the function being run 10000 times to show that its results are distributed similar to the example distribution. It's common to have a TIO to show the function being used and that its output is valid. And that is not included in the byte count. \$\endgroup\$ – Ciaran_McCarthy Apr 18 at 21:34
1
\$\begingroup\$

C (gcc), 36 32 bytes

-4 bytes thanks to Ben Voigt

f(n,x){x=rand()%n;x=x?x:n+f(n);}

Try it online!

Here a Test with 100k d4

\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't srand(time(0)) be included in the byte count? AFAIK rand() will always return the same value if it was never seeded \$\endgroup\$ – Tau Apr 12 at 16:42
  • 1
    \$\begingroup\$ I'm not entirely sure, but I remember the meta consensus being that using an unseed PRNG is acceptable @Tau \$\endgroup\$ – Conor O'Brien Apr 12 at 16:50
  • 1
    \$\begingroup\$ This is not even close to being C code. Your recursive call has the wrong number of parameters, and you are missing a return. \$\endgroup\$ – Ben Voigt Apr 13 at 18:46
  • 1
    \$\begingroup\$ Even on gcc it returns 0 all the time (if compiled with -O3) or total garbage (if compiled with -O1). If you have optimization-unstable code that depends on particular compile settings, that should be mentioned. \$\endgroup\$ – Ben Voigt Apr 15 at 14:32
  • 1
    \$\begingroup\$ @BenVoigt unless mentioned in the post, it is assumed compilers use default options. The default for gcc is -O0, which works perfectly fine for this code. The purpose of codegolfing is to write code in as few bytes as possible, not write functional, production-ready code. If it works, it works. \$\endgroup\$ – Skidsdev Apr 15 at 14:55
1
\$\begingroup\$

Ruby, 28 bytes

f=->n{(a=rand n)>0?a:n+f[n]}

Try it online!

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

Java (JDK), 61 bytes

int f(int n){int r=1;r+=Math.random()*n;return r<n?r:r+f(n);}

Try it online!

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

Funky, 38 bytes

f=n=>ifn==x=math.random(n)f(n)+x elsex

Try it online!

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

C# (.NET Core), 155 153 145 144 bytes

using C=System.Console;class A{static void Main(){int i=int.Parse(C.ReadLine()),j=0;while((j+=new System.Random().Next(i)+1)%i<1){}C.Write(j);}}

Try it online!

This code instantiates a new RNG every time, but that uses time as a seed anyway so it should still satisfy randomness requirements.

I wonder if console input is cheaper in the long run.

\$\endgroup\$
  • \$\begingroup\$ Saved 2 bytes by using [0,i)+1 rather than [1,i+1) \$\endgroup\$ – Stackstuck Apr 17 at 19:35
  • \$\begingroup\$ Saved 8 bytes by forgoing principles about RNG and just making a new one in the loop. \$\endgroup\$ – Stackstuck Apr 17 at 21:19
  • \$\begingroup\$ Saved one byte w/ <1 instead of ==0 \$\endgroup\$ – Stackstuck Apr 20 at 7:35
1
\$\begingroup\$

Clojure, 63 bytes

#(loop[n 0](let[r(+ n(rand-int %)1)](if(<(- r n)%)r(recur r))))

A naive solution to the problem.

Expanded:

(defn exploding-die [sides]
  (loop [total 0]
    (let [new-total (+ total (rand-int sides) 1)]
      (if (< (- new-total total) sides) new-total
        (recur new-total)))))
\$\endgroup\$
1
\$\begingroup\$

VTL-2, 54 53 51 bytes

1 A=?
2 C=C+B
3 B='/A*0+%+1
4 #=B=A*2
5 ?=C+B

Line 1 takes input into variable A, this will be our die's sidedness. Line 2 does what it appears to, though it's important to note that in VTL-2, referencing a variable that hasn't been initialized assumes 0, so for the first pass, this is C=0+0. Line 3 divides a random number by our dice sides (' is the system variable for a random number) and then turns this into a roll - % is the remainder of the last division operation; add 1 and put this in B. Line 4 is a little cryptic: B=A is evaluated first. It evaluates to 1 if the two are equal (if our die roll is the same as its number of sides), otherwise it evaluates to 0. This result is multiplied by two (*2), and then the final value here is handed to #=, which is equivalent to a GOTO. If this is given a zero, it ignores it; otherwise we GOTO 2, adding the roll to the total and rolling again. Line 6 prints the total of C+B.

Had an epiphany right after posting this, and golfed off one byte. I was doing 3 B='/A and 4 B=%+1 because % is a system variable with the remainder of the last division operation; you need to do a division operation to get that value. But it occurred to me that I could do the division and then multiply that by zero since I don't need it. But since I've done it, the remainder is now in % and so I can add that to the zero I just made, and add 1 to get the die roll. This is long, but still shorter than two lines - line numbers always take two bytes in VTL-2, plus a space to separate the line number, plus a CR.

Second edit, did my math wildly wrong on byte count both times. Eesh. Third, golfed off two leftover parens.

\$\endgroup\$
  • \$\begingroup\$ Is this the language from the Altair systems? Google seems to imply so. But this is really cool! \$\endgroup\$ – Rɪᴋᴇʀ May 4 at 20:55
  • \$\begingroup\$ @Rɪᴋᴇʀ Yup! Stumbled across it recently while looking for some totally unrelated 680 info. I'm running the interpreter in an 8800 emulator. It's a very interesting language, a lot of fun design decisions were made to fit it in ~1KB (VTL-1 was closer to ~700B!). \$\endgroup\$ – brhfl May 4 at 21:29
  • 1
    \$\begingroup\$ Huh, that's pretty cool. I'm glad you decided to answer my challenge in that language, of all things. \$\endgroup\$ – Rɪᴋᴇʀ May 4 at 23:38

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.