Twoim zadaniem jest stworzenie programu, który przyjmuje liczbę całkowitą n > 1i generuje rzut jednostronnej nkostki. Te kości są jednak zgodne z zasadami eksplozji kości .

Kiedy rzucasz kością, sprawdź, jaką wartość rzuciłeś. Jeśli uzyskasz maksimum dla tego rodzaju kości (na standardowym k4, czyli 4 lub 6 na k6 itd.), Rzuć ponownie i dodaj nowy rzut do tej sumy. Każdy rzut kontynuuje dodawanie do sumy, dopóki nie rzucisz już maksymalnej liczby. Ten ostatni numer jest jednak dodawany.

Twój program powinien przyjąć jedną liczbę całkowitą ni rzucić nkością eksplodującą . Oto przykładowa dystrybucja pokazująca, jak powinna wyglądać n=4. Pamiętaj, że nigdy nie powinieneś generować żadnych wielokrotnościn , ponieważ zawsze będą wybuchać.

Możesz założyć, że rozmiar stosu dla każdej rekurencji, którą wykonujesz, jest nieskończony, a twoja funkcja losowa musi spełniać nasze standardy losowości (wbudowany generator losowy lub czas / data ). Twoja losowa funkcja powinna być również możliwie jak najbardziej jednolita, w przeciwieństwie do rozkładu geometrycznego, ponieważ mówimy o kościach.

Kod maszynowy x86 (dla Intel Ivy Bridge i nowszych), 17 bajtów

31 C9 0F C7 F0 31 D2 F7 F6 42 01 D1 39 F2 74 F2 C3

Powyższe bajty kodu definiują funkcję symulującą eksplodującą matrycę. Wymaga pojedynczego wejścia, przekazanego wESI rejestru, wskazującego maksymalną liczbę kości. Zwraca pojedynczą wartość wECX rejestrze, która jest wynikiem rzutów.

Wewnętrznie używaRDRAND instrukcji aby wygenerować liczbę losową. Używa to generatora liczb losowych (RNG) wbudowanego w sprzęt procesorów Intel Ivy Bridge i późniejszych (niektóre procesory AMD również obsługują tę instrukcję).

Logika funkcji jest poza tym dość prosta. Wygenerowana liczba losowa jest skalowana, aby mieściła się w pożądanym zakresie przy użyciu standardowej techniki ((rand % dieSize) + 1 ), a następnie jest sprawdzana, czy powinna spowodować wybuch. Ostateczny wynik jest przechowywany w rejestrze akumulatorów.

Oto wersja z adnotacjami pokazująca mnemoniki języka asemblera:

           unsigned int RollExplodingDie(unsigned int dieSize)
31 C9        xor     ecx, ecx    ; zero-out ECX, which accumulates the final result
           Roll:
0F C7 F0     rdrand  eax         ; generate a random number in EAX
31 D2        xor     edx, edx    ; zero-out EDX (in preparation for unsigned division)
F7 F6        div     esi         ; divide EDX:EAX by ESI (the die size)
                                 ;   EAX receives the quotient; EDX receives the remainder
42           inc     edx         ; increment the remainder
01 D1        add     ecx, edx    ; add this roll result to the accumulator
39 F2        cmp     edx, esi    ; see if this roll result should cause an explosion
74 F2        jz      Roll        ; if so, re-roll; otherwise, fall through
C3           ret                 ; return, with result in ECX register

Trochę oszukuję . Wszystkie standardowe konwencje wywoływania x86 zwracają wynik funkcji do EAXrejestru. Ale w prawdziwym kodzie maszynowym nie ma konwencji wywoływania. Możesz użyć dowolnych rejestrów dla wejścia / wyjścia. Wykorzystanie ECXrejestru wyjściowego pozwoliło mi zaoszczędzić 1 bajt. Jeśli chcesz użyć EAX, wstaw 1-bajtową XCHG eax, ecxinstrukcję bezpośrednio przed retinstrukcją. Ten swapy Wartości EAXi ECXrejestry, skutecznie kopiuje wynik od ECXdo EAX, a koszu ECXze starej wartości EAX.

Wypróbuj online!

Oto równoważna funkcja transkrybowana w C, przy użyciu funkcji __builtin_ia32_rdrand32_stepwewnętrznej obsługiwanej przez GCC, Clang i ICC do wygenerowaniaRDRAND instrukcji:

#include <immintrin.h>

unsigned int RollExplodingDie(unsigned int dieSize)
{
    unsigned int result = 0;
Roll:
    unsigned int roll;
    __builtin_ia32_rdrand32_step(&roll);
    roll    = ((roll % dieSize) + 1);
    result += roll;
    if (roll == dieSize)   goto Roll;
    return result;
}

Co ciekawe, GCC z -Osflagą przekształca to w prawie dokładnie ten sam kod maszynowy . EDIZamiast tego pobiera dane wejściowe ESI, co jest całkowicie arbitralne i nie zmienia nic istotnego w kodzie. Musi zwrócić wynik EAX, jak wspomniałem wcześniej, i korzysta z bardziej wydajnej (ale większej) MOVinstrukcji, aby to zrobić bezpośrednio przed RET. W przeciwnym razie same zady. Zawsze jest zabawnie, gdy proces jest w pełni odwracalny: napisz kod w asemblerze, transkrybuj go do C, uruchom go za pomocą kompilatora C i odzyskaj oryginalny zestaw!

Python 2 , 66 64 61 bajtów

-3 bajty dzięki xnor

f=lambda n,c=0:c%n or c+f(n,randint(1,n))
from random import*

Wypróbuj online!

Poprzedni zwój jest przechowywany w c , co pozwala nam na dostęp do niej wiele razy bez konieczności przechowywania jej w zmiennej, czego nie można zrobić w lambda Pythona. Przy każdej rekursji sprawdzamy, czy rzuciliśmy eksplodującymi kośćmi.

c jest inicjowany na zero, więc c%n jest tam falsey. W następnych iteracjach będzie to falsey tylko wtedy, gdy rzuci się eksplodującymi kostkami.

Python 2 , 55 bajtów

f=lambda n:randint(1,n)%n or n+f(n)
from random import*

Wypróbuj online!

Moja druga odpowiedź wydaje się być nieco przerobiona, ponieważ wydaje się, że to również działa ... i tak zostawię.

R , 39 bajtów

n=scan();n*rgeom(1,1-1/n)+sample(n-1,1)

Wypróbuj online!

Objaśnienie: to rozwiązanie pozwala uniknąć pętli rekurencyjnych / while, bezpośrednio obliczając rozkład liczby wybuchów, które wystąpią. Niech $n$ będzie liczbą stron na kości. Jeśli uznajesz sukces za rzut $n$ a porażkę za rzut cokolwiek innego, masz prawdopodobieństwo $\frac1n$ sukcesu. Całkowita liczba wybuchów to liczba sukcesów przed pierwszą awarią. Odpowiada to$\mathrm{Geometric}\left(1-\frac{1}{n}\right)$dystrybucja (patrzstrona wikipedia, która określa sukces i porażkę na odwrót). Każda eksplozja prowadzido sumy$n$. Końcowe rolki następuje$\mathrm{Uniform}(1,2,\ldots,n-1)$rozdzielczy, który dodać do całości.

Perl 6 , 26 bajtów

{sum {roll 1..$_:}...*-$_}

Wypróbuj online!

Wyjaśnienie

{                        } # Anonymous block
                  ...      # Sequence constructor
     {roll 1..$_:}         #   Next elem is random int between 1 and n
                           #   (Called as 0-ary function with the original
                           #   $_ for the 1st elem, then as 1-ary function
                           #   with $_ set to the previous elem which
                           #   equals n.)
                     *-$_  #   Until elem not equal to n (non-zero difference)
 sum                       # Sum all elements

J , 16 11 bajtów

(+$:)^:=1+?

Wypróbuj online!

Wyjaśnienie

TL; DR 1+? wykonuje rzut matrycą, (+$:)^:=powtarza tylko wtedy, gdy równa się wejściowi.

Funkcja to ciąg 4 czasowników:

             ┌─ + 
         ┌───┴─ $:
  ┌─ ^: ─┴─ =     
  │               
──┤      ┌─ 1     
  └──────┼─ +     
         └─ ?     

Pociąg ma miejsce, gdy 2 lub więcej czasowników jest połączonych. Tutaj odpowiedź ma postać f g h j:

(+$:)^:=  1  +  ?
    f     g  h  j

Tak zwany „4-pociąg” jest analizowany jako hak i widelec:

f g h j   ⇔   f (g h j)

Zatem odpowiedź jest równoważna z:

(+$:)^:= (1 + ?)

Haki: (f g) xix (f g) y

Monadyczny (jeden argument) hak dwóch czasowników, biorąc pod uwagę argument x, obowiązuje następująca równoważność:

(f g) x   ⇔   x f (g x)

Na przykład (* -) 5ocenia do 5 * (- 5), który ocenia _25.

Oznacza to, że nasz 4-pociągowy hak fi (g h j)jest równoważny z:

(f (g h j)) x   ⇔   x f ((g h j) x)

Ale co ftu robi? (+$:)^:=jest koniunkcją dwóch czasowników używających koniunkcji Mocy^: : innym hookiem ( (+$:)) i czasownikiem ( =). Zauważ tutaj, że fjest drastyczny - ma dwa argumenty ( xi (g h j) x). Musimy więc sprawdzić, jak się ^:zachowuje. Koniunkcja potęgi f^:oprzyjmuje czasownik fi czasownik lub rzeczownik o(rzeczownik jest tylko fragmentem danych) i stosuje f oczasy. Na przykład weź o = 3. Obowiązują następujące równoważności:

(f^:3) x     ⇔   f (f (f x))
x (f^:3) y   ⇔   x f (x f (x f y))

Jeśli ojest czasownikiem, koniunkcja potęgi po prostu oceni oargumenty i użyje wyniku rzeczownika jako liczby powtórzeń.

Dla naszego czasownika ojest =to czasownik równości. Ocenia się 0dla różnych argumentów i 1dla równych argumentów. Powtarzamy hak (+$:)raz dla równych argumentów, a nie dla różnych. Dla ułatwienia notacji wyjaśnienia, pozwól y ⇔ ((g h j) x). Pamiętaj, że nasz początkowy hak jest równoważny z tym:

x   (+$:)^:=   ((g h j) x)
x   (+$:)^:=   y

Po rozwinięciu koniunkcji staje się to:

x ((+$:)^:(x = y)) y

Jeśli xi ysą takie same, staje się to:

x (+$:)^:1 y   ⇔   x (+$:) y

W przeciwnym razie staje się to:

x (+$:)^:0 y   ⇔   y

Teraz widzieliśmy monadyczne widelce. Tutaj mamy dyadyczny widelec:

x (f g) y   ⇔   x f (g y)

Tak więc, kiedy xi ysą takie same, otrzymujemy:

x (+$:) y   ⇔   x + ($: y)

Co to jest $:? Odnosi się do całego czasownika i pozwala na rekursję. Oznacza to, że kiedy xi y are the same, we apply the verb toyand add x` do tego.

Widły: (g h j) x

Co robi wewnętrzny widelec? To był ynasz ostatni przykład. W przypadku monadycznego rozwidlenia trzech czasowników, z podaniem argumentu x, obowiązuje następująca równoważność:

(g h j) x   ⇔   (g x) h (j x)

W następnym przykładzie załóżmy, że mamy czasowniki o nazwach SUMi DIVIDE, i LENGTHktóre, jak przypuszczasz, mogą mieć. Jeśli połączymy trójkę w rozwidlenie, otrzymamy:

(SUM DIVIDE LENGTH) x   ⇔   (SUM x) DIVIDE (LENGTH x)

Ten widelec ocenia się na średnią x(zakładając, że xjest to lista liczb). W J napisalibyśmy to jako przykład jako+/ % # .

Ostatnia rzecz dotycząca widelców. Gdy skrajnie lewy „ząb” (w naszym symbolicznym przypadku powyżej,g ) jest rzeczownikiem, jest traktowany jako stała funkcja zwracająca tę wartość.

Po tym wszystkim możemy teraz zrozumieć powyższy widelec:

(1 + ?) x   ⇔   (1 x) + (? x)
            ⇔   1 + (? x)

?$[0,x)$$[1, x]$.

Kładąc wszystko razem

Biorąc pod uwagę wszystkie te rzeczy, nasz czasownik jest równoważny z:

((+$:)^:=1+?) x   ⇔   ((+$:)^:= 1 + ?) x
                  ⇔   ((+$:)^:= (1 + ?)) x
                  ⇔   x ((+$:)^:=) (1 + ?) x
                  ⇔   x ((+$:)^:=) (1 + (? x))
                  ⇔   x (+$:)^:(x = (1 + (? x))
(let y = 1 + (? x))
if x = y          ⇒   x + $: y
otherwise         ⇒   y

To wyraża pożądaną funkcjonalność.

Galaretka , 7 bajtów

X+ß}¥=¡

Wypróbuj online!

Wykorzystuje rekurencję. Ponownie uruchamia program ( ß) i dodaje ( +), jeśli ( ¡) liczba losowa ( X) jest równa ( =) wejściu programu. }sprawia, że ßakt na wejściu programu i ¥kombajnów+ß} się w jedno łącze ¡do konsumpcji.

Tutaj rozkład 1000 wyników dla n = 6, które zebrałem za pomocą tego programu. Drukowane za pomocą python / matplotlib.

Oto 5000 punktów danych od n = 3 na wykresie semiloga, który pokazuje (w przybliżeniu?) Rozkład wykładniczy.

Pyth - 12 11 bajtów

Korzysta z funkcji podczas. Wydaje mi się, że powinna istnieć mądrzejsza odpowiedź, która po prostu symuluje dystrybucję.

-.W!%HQ+hOQ

-         (Q)         Subtract Q. This is because we start Z at Q to save a char
 .W                   While, functionally
  !                   Logical not. In this case, it checks for 0
   %HQ                Current val mod input
  +     (Z)           Add to current val
   h                  Plus 1
    OQ                Random val in [0, input)

Wypróbuj online .

Python 3 , 80 bajtów

import random as r,math
lambda n:int(-math.log(r.random(),n))*n+r.randint(1,n-1)

Wypróbuj online!

05AB1E , 10 bajtów

[ILΩDIÊ#}O

Wypróbuj online lub sprawdź listy .

10 bajtów alternatywnych:

[LΩDˆÊ#}¯O

Wypróbuj online lub sprawdź listy .

Although I like the top one more because it got the 'word' DIÊ in it, which suits the challenge.

Explanation:

[         # Start an infinite loop:
 IL       #  Create a list in the range [1, input]
   Ω      #  Pop and push a random value from this list
    D     #  Duplicate it
     IÊ   #  If it's NOT equal to the input:
       #  #   Stop the infinite loop
}O        # After the loop: sum all values on the stack
          # (which is output implicitly as result)

[         # Start an infinite loop
 L        #  Create a list in the range [1, (implicit) input]
  Ω       #  Pop and push a random value from this list
   Dˆ     #  Add a copy to the global_array
     Ê    #  If it's NOT equal to the (implicit) input:
      #   #   Stop the infinite loop
}¯        # After the loop: push the global_array
  O       # Pop and push its sum
          # (which is output implicitly as result)  

Wolfram Language (Mathematica), 50 bytes

R@#//.x_/;x~Mod~#==0:>x+R@#&
R=RandomChoice@*Range

Try it online!

R, 47 42 bytes

function(n){while(!F%%n)F=F+sample(n,1)
F}

Try it online!

Credit to ArBo's approach.

Still a byte longer than Robin Ryder's, go upvote his!

Ruby, 35 bytes

->n,s=0{s+=x=1+rand(n);x<n||redo;s}

Try it online!

APL (Dyalog Unicode), 15 14 bytes

{×r←?⍵:r⋄⍵+∇⍵}

Try it online!

Haskell, 77 76 bytes

import System.Random
f x=randomRIO(1,x)>>=(x!)
x!y|y<x=pure y|0<1=(y+)<$>f x

Try it online!

Thanks to killmous for one byte.

If <|> were in the prelude, we could do better with MonadComprehensions:

Haskell, non-competing, 66 bytes

import System.Random
f x=do y<-randomRIO(1,x);[y|y<x]<|>(y+)<$>f x

Try it online!

Python 2, 53 bytes

f=lambda n:random()*n//1or n+f(n)
from random import*

Try it online!

Uses the or short-circuiting idea from ArBo's answer. The expression random()*n//1 generates a number from 0 to n-1, with 0 taking the place of a roll of n. The or takes the that number, except if it's zero (Falsey) it continues on to n+f(n).

Japt, 13 bytes

ö)g@¶°X?X+ß:X

Try it

Port of Arnauld's answer. Figured out how to make a recursive call ;)

Transpiled JS:

// U: Implicit input
// ö: generate a random number [0,U)
(U.ö())
  // g: run the result through a function
  .g(function(X, Y, Z) {
    // increment the result and compare to input
    return U === (++X)
      // if they are the same, roll again and add to current roll
      ? (X + rp())
      // if they are different, use current roll
      : X
   })

Japt, 12 bytes

It may be shorter than dana's solution, but it's a hell of a lot uglier. I'm only posting it 'cause it seems like forever since we had a Japt solution that started with an empty line.

ö
>°V©VªV+ß

Try it

PowerShell, 49 bytes

for($a=$l="$args";$a-eq$l){$o+=$l=1..$a|Random}$o

Try it online!

Iterative method. Sets the input $args to $a and the $last roll (done so we enter the loop at least once). Then, so long as the last roll is -equal to the input, we keep rolling. Inside the loop we accumulate into $o the last roll, which is updated by creating a range from 1 to input $a and picking a Random element thereof. (Honestly, I'm a little surprised that $o+=$l= works.) Once we're out of the loop, we leave $o on the pipeline and output is implicit.

Forth (gforth), 72 bytes

include random.fs
: f >r 0 begin i random 1+ >r i + r> i < until rdrop ;

Try it online!

Code Explanation

include random.fs      \ include library file for random
: f                    \ start a new word definition
  >r                   \ stick the input on the return stack (for easy access)
  0                    \ add a counter to hold the sum
  begin                \ start an indefinite loop
    i random 1+        \ generate a random number from 1 to n
    >r i + r>          \ add the result to the counter, use the return stack to save a few bytes
    i <                \ check if result was less than n
  until                \ end the loop if it was, otherwise go back to begin
  rdrop                \ remove n from the return stack
;                      \ end the word definition

Batch, 70 bytes

@set t=0
:g
@set/at+=d=%random%%%%1+1
@if %d%==%1 goto g
@echo %t%

Takes input n as a command-line parameter %1. d is the current roll, t the cumulative total. Simply keeps rolling until d is not equal to n.

Jelly, 9 bytes

x⁹X€Ä%ƇµḢ

Try it online!

A monadic link that takes n as its argument and returns a number generated by an exploding n-sided die. This generates 256 numbers from 1 to n and returns the first cumulative sum that is not a multiple of n. In theory this could return 256n, but even for a 2-sided die this would happen only one every $2^{256}$ times.

An alternative that doesn’t have this limitation is:

Jelly, 10 bytes

X³X¤+¥³ḍ¥¿

Try it online!

Note both TIO links generate 400 numbers to show the distribution.

Python 3, 81 72 bytes

from random import*
def f(x,a=0):
 while a%x<1:a+=randint(1,x)
 return a

Try it online!

-9 bytes thanks to ArBo

Explanation

import random             #load the random module              
def explodeDice(num):     #main function
    ans = 0                     #set answer to 0
    while a % num != 0:         #while a isn't a multiple of the input
        ans += random.randint(1, num) #add the next dice roll to answer
    return ans                  #return the answer

TI-BASIC, 28 23 bytes

-5 bytes thanks to this meta post!

Ans→N:0:Repeat fPart(Ans/N:Ans+randInt(1,N:End:Ans

Input is in Ans.
Output is in Ans and is implicitly printed.

Examples:

4
              4
prgmCDGF11
              5
6
              6
prgmCDGF11
              3

Explanation:

Ans→N:0:Repeat fPart(Ans/N:Ans+randInt(1,N:End:Ans   ;full logic

Ans→N                                                ;store the input in "N"
      0                                              ;leave 0 in "Ans"
        Repeat fPart(Ans/N                 End       ;loop until the sum
                                                     ; is not a multiple of
                                                     ; the input
                               randInt(1,N           ;generate a random
                                                     ; integer in [1,N]
                           Ans+                      ;then add it to "Ans"
                                               Ans   ;leave the sum in "Ans"
                                                     ;implicitly print "Ans"

Notes:

• TI-BASIC is a tokenized language. Character count does not equal byte count.

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.

PowerShell, 43 bytes (Iterative method)

param($n)do{$x+=1..$n|random}until($x%$n)$x

Try it online!

PowerShell, 48 bytes (recursive method)

filter f{if($_-eq($x=1..$_|random)){$x+=$_|f}$x}

Try it online!

Jelly, 7 bytes

X=п⁸S_

A monadic Link accepting an integer, n, which yields an integer.

Try it online! Or see the counts of $10^5$ runs

How?

X=п⁸S_ - Link: integer, n
  п    - Collect up while...
 =  ⁸   - ...condition: equal to chain's left argument, n
X       - ...next value: random number in [1..n]
     S  - sum
      _ - subtract n (since the collection starts with [n])

SmileBASIC, 41 bytes

INPUT N@L
S=S+RND(N)+1ON S MOD N GOTO@L?S

After reading:

Note that you should never output any multiples of n, since they will always explode.

I realized that rather than checking if a dice roll was n, you can just repeat while the sum is a multiple of n.

AnyDice, 36 bytes

Almost a built-in in the language:

function:f I:n{result: [explode dI]}

For this to be correct I have to abuse the infinite recursion depth assumption. AnyDice limits the recursion depth with a global property maximum function depth. the explode builtin however uses it's own; explode depth - which defaults to 2.

set "explode depth" to 99

Would add another 25 bytes; and would not really match the requirements since it's theoretically possible for a dice to explode more than 99 times.

The output of the function is a die, ie. an AnyDice built-in type that is a paring of results and probabilities for the result.

CJam, 19 bytes

qi{__mr)_T+:T;=}g;T

Explanation:

T is pre-set to 0

qi{__mr)_T+:T;=}g;T - whole code
qi                  - read input as integer (n) | Stack: n
  {            }    - block
   __               - Duplicate twice | Stack: n n n
     mr)            - Choose a random number from 1 to n (r). Since 'mr' picks a
                      number from 0 to n-1, the number has to be incremented with ')' 
                      Stack: n n r
        _           - Duplicate |  Stack: n n r r
         T          - push T | Stack: n n r r T
          +         - add the random number to T (t) | Stack: n n r t
           :T;      - pop the value and store in T | Stack: n n r
              =     - are the top two stack values the same (c) | Stack: n c
               }
                g   - do while loop that pops the condition from the stack after each
                      iteration | Stack: n
                 ;  - pop the top stack element and discard | Stack: T
                  T - push T | Stack: T
                    - implicit output

Or in pseudocode:

input n
var sum = 0
do {
    var random_number = pick random number from 1 to n
    sum = sum + random_number
} while (random_number == n)
output n

As a flowchart:

Try it online!

Excel VBA, 46 bytes

Thanks to @TaylorScott

Do:v=-Int(-[A1]*Rnd):t=t+v:Loop While[A1]=v:?t

Executed in the command window.

As a user-defined function.

Excel VBA, 108 67 bytes

Function z(i)
Do
v=Int((i*Rnd)+1)
z=z+v
Loop While v=i
End Function