23
\$\begingroup\$

Given two positive integers a and b, output the frequency distribution of rolling a b-sided die a times and summing the results.

A frequency distribution lists the frequency of each possible sum if each possible sequence of dice rolls occurs once. Thus, the frequencies are integers whose sum equals b**a.

Rules

  • The frequencies must be listed in increasing order of the sum to which the frequency corresponds.
  • Labeling the frequencies with the corresponding sums is allowed, but not required (since the sums can be inferred from the required order).
  • You do not have to handle inputs where the output exceeds the representable range of integers for your language.
  • Leading or trailing zeroes are not permitted. Only positive frequencies should appear in the output.

Test Cases

Format: a b: output

1 6: [1, 1, 1, 1, 1, 1]
2 6: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
3 6: [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
5 2: [1, 5, 10, 10, 5, 1]
6 4: [1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1]
10 10: [1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92368, 167860, 293380, 495220, 810040, 1287484, 1992925, 3010150, 4443725, 6420700, 9091270, 12628000, 17223250, 23084500, 30427375, 39466306, 50402935, 63412580, 78629320, 96130540, 115921972, 137924380, 161963065, 187761310, 214938745, 243015388, 271421810, 299515480, 326602870, 351966340, 374894389, 394713550, 410820025, 422709100, 430000450, 432457640, 430000450, 422709100, 410820025, 394713550, 374894389, 351966340, 326602870, 299515480, 271421810, 243015388, 214938745, 187761310, 161963065, 137924380, 115921972, 96130540, 78629320, 63412580, 50402935, 39466306, 30427375, 23084500, 17223250, 12628000, 9091270, 6420700, 4443725, 3010150, 1992925, 1287484, 810040, 495220, 293380, 167860, 92368, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10, 1]
5 50: [1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316246, 341030, 367215, 394835, 423920, 454496, 486585, 520205, 555370, 592090, 630371, 670215, 711620, 754580, 799085, 845121, 892670, 941710, 992215, 1044155, 1097496, 1152200, 1208225, 1265525, 1324050, 1383746, 1444555, 1506415, 1569260, 1633020, 1697621, 1762985, 1829030, 1895670, 1962815, 2030371, 2098240, 2166320, 2234505, 2302685, 2370746, 2438570, 2506035, 2573015, 2639380, 2704996, 2769725, 2833425, 2895950, 2957150, 3016881, 3075005, 3131390, 3185910, 3238445, 3288881, 3337110, 3383030, 3426545, 3467565, 3506006, 3541790, 3574845, 3605105, 3632510, 3657006, 3678545, 3697085, 3712590, 3725030, 3734381, 3740625, 3743750, 3743750, 3740625, 3734381, 3725030, 3712590, 3697085, 3678545, 3657006, 3632510, 3605105, 3574845, 3541790, 3506006, 3467565, 3426545, 3383030, 3337110, 3288881, 3238445, 3185910, 3131390, 3075005, 3016881, 2957150, 2895950, 2833425, 2769725, 2704996, 2639380, 2573015, 2506035, 2438570, 2370746, 2302685, 2234505, 2166320, 2098240, 2030371, 1962815, 1895670, 1829030, 1762985, 1697621, 1633020, 1569260, 1506415, 1444555, 1383746, 1324050, 1265525, 1208225, 1152200, 1097496, 1044155, 992215, 941710, 892670, 845121, 799085, 754580, 711620, 670215, 630371, 592090, 555370, 520205, 486585, 454496, 423920, 394835, 367215, 341030, 316246, 292825, 270725, 249900, 230300, 211876, 194580, 178365, 163185, 148995, 135751, 123410, 111930, 101270, 91390, 82251, 73815, 66045, 58905, 52360, 46376, 40920, 35960, 31465, 27405, 23751, 20475, 17550, 14950, 12650, 10626, 8855, 7315, 5985, 4845, 3876, 3060, 2380, 1820, 1365, 1001, 715, 495, 330, 210, 126, 70, 35, 15, 5, 1]
\$\endgroup\$
  • \$\begingroup\$ Can we assume that b is at least 2? (Or if not, what should the frequency list for sums of a 1-sided die look like?) \$\endgroup\$ – Misha Lavrov Oct 1 '17 at 3:32
  • \$\begingroup\$ May we have leading or trailing zeroes? \$\endgroup\$ – xnor Oct 1 '17 at 4:56

22 Answers 22

9
\$\begingroup\$

Octave, 38 bytes

@(a,b)round(ifft(fft((a:a*b<a+b)).^a))

Try it online!

Explanation

Adding independent random variables corresponds to convolving their probability mass functions (PMF), or multiplying their characteristic functions (CF). Thus the CF of the sum of a independent, identically distributed variables is given by that of a single variable raised to the power of a.

The CF is essentially the Fourier transform of the PMF, and can thus be computed via a FFT. The PMF of a single b-sided die is uniform on 1, 2, ..., b. However, two modifications are required:

  • 1 is used instead of the actual probability values (1/b). This way the result will be de-normalized and will contain integers as required.
  • Padding with zeros is needed so that the FFT output has the appropriate size (a*b-a+1) and the implicit periodic behaviour assumed by the FFT doesn't affect the results.

Once the characteristic function of the sum has been obtained, an inverse FFT is used to compute the final result, and rounding is applied to correct for floating-point inaccuracies.

Example

Consider inputs a=2, b=6. The code a:a*b<a+b builds a vector with b=6 ones, zero-padded to size a*b-a+1:

[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Then fft(...) gives

[36, -11.8-3.48i, 0.228+0.147i, -0.949-1.09i, 0.147+0.321i, -0.083-0.577i, -0.083+0.577i, 0.147-0.321i, -0.949+1.09i, 0.228-0.147i, -11.8+3.48i]

One can almost recognize the sinc function here (Fourier transform of a rectangular pulse).

(...).^a raises each entry to a and then ifft(...) takes the inverse FFT, which gives

[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Although the results in this case are exactly integers, in general there may be relative errors of the order of 1e-16, which is why round(...) is needed.

\$\endgroup\$
  • 1
    \$\begingroup\$ I really Impressed! \$\endgroup\$ – rahnema1 Oct 2 '17 at 18:08
  • \$\begingroup\$ @rahnema1 Signal processing for the win! \$\endgroup\$ – Luis Mendo Oct 2 '17 at 19:26
8
\$\begingroup\$

Mathematica, 29 bytes

Tally[Tr/@Range@#2~Tuples~#]&

Just generates all possible dice rolls, takes their totals, then counts. Each frequency comes labeled with its value.

Mathematica, 38 bytes

CoefficientList[((x^#2-1)/(x-1))^#,x]&

Expands (1+x+x^2+...+x^(a-1))^b and takes the coefficients of x. Since 1+x+x^2+...+x^(a-1) is the generating function for a single die roll and products correspond to convolutions - adding values of dice - the result gives the frequency distribution.

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

Haskell, 90 79 77 75 bytes

Thanks to Lynn for the Cartesian product trick. -11 bytes thanks to many Haskell tricks from Funky Computer Man, -2 bytes from naming, -2 bytes thanks to Laikoni. Golfing suggestions are welcome! Try it online!

import Data.List
g x=[1..x]
a!b=map length$group$sort$map sum$mapM g$b<$g a

Ungolfed

import Data.List
rangeX x = [1..x]
-- sums of all the rolls of b a-sided dice
diceRolls a b = [sum y | y <- mapM rangeX $ fmap (const b) [1..a]]
-- our dice distribution
distrib a b = [length x | x <- group(sort(diceRolls a b))]
\$\endgroup\$
4
\$\begingroup\$

Pyth - 10 bytes

Just takes all possible dice combinations by taking the cartesian product of [1, b], a times, summing, and getting the length of each sum group.

lM.gksM^SE

Test Suite.

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 8 bytes

LIãO{γ€g

Try it online!

How?

LIãO{γ€g  - Full program.

L         - Range [1 ... input #1]
 I        - Input #2.
  ã       - Cartesian Power.
   O      - Map with sum.
    {     - Sort.
     γ    - Group consecutive equal elements.
      €g  - Get the length of each
\$\endgroup\$
4
\$\begingroup\$

R, 58 bytes

function(a,b)table(rowSums(expand.grid(rep(list(1:b),a))))

Try it online!

\$\endgroup\$
4
\$\begingroup\$

R, 52 bytes

function(a,b)Re(fft(fft(a:(a*b)<a+b)^a,T)/(a*b-a+1))

Try it online!

A port of @Luis Mendo's Octave solution, fft(z, inverse=T) unfortunately returns the unnormalized inverse FFT, so we have to divide by the length, and it returns a complex vector, so we take only the real part.

\$\endgroup\$
  • \$\begingroup\$ well played - payback for yesterday's cmdscale I figure :-) \$\endgroup\$ – flodel Oct 3 '17 at 0:20
  • \$\begingroup\$ @flodel hah! I'm actually going to award you a bounty for that one :) \$\endgroup\$ – Giuseppe Oct 3 '17 at 12:55
  • \$\begingroup\$ You were not joking! So generous of you! I enjoy seeing (and learning from) your answers, I will pay it back quickly! \$\endgroup\$ – flodel Oct 5 '17 at 0:27
3
\$\begingroup\$

SageMath, 40 bytes

lambda a,b:reduce(convolution,[[1]*b]*a)

Try it online

convolution computes the discrete convolution of two lists. reduce does what it says on the tin. [1]*b is a list of b 1s, the frequency distribution of 1db. [[1]*b]*a makes a nested list of a copies of b 1s.


Python 2 + NumPy, 56 bytes

lambda a,b:reduce(numpy.convolve,[[1]*b]*a)
import numpy

Try it online!

I've included this solution with the above one, since they're essentially equivalent. Note that this function returns a NumPy array and not a Python list, so the output looks a bit different if you print it.

numpy.ones((a,b)) is the "correct" way to make an array for use with NumPy, and thus it could be used in place of [[1]*b]*a, but it's unfortunately longer.

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

Jelly, 5 bytes

ṗS€ĠẈ

Try it online!

Note that this takes the arguments in reverse order.

How?

ṗS€ĠL€   - Full program (dyadic) | Example: 6, 2

ṗ        - Cartesian Power (with implicit range) | [[1, 1], [1, 2], ... , [6, 6]]
 S€      - Sum each | [2, 3, 4, ... , 12]
   Ġ     - Group indices by values | [[1], [2, 7], [3, 8, 13], ... , [36]]
    L€   - Length of each group | [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

Alternative solutions:

ṗZSĠL€
ṗZSµLƙ
ṗS€µLƙ
\$\endgroup\$
2
\$\begingroup\$

Python 2, 102 91 bytes

lambda b,a:map(map(sum,product(*[range(a)]*b)).count,range(b*~-a+1))
from itertools import*

Try it online!

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

Haskell, 61 bytes

g x=[1..x]
a#b=[sum[1|m<-mapM g$b<$g a,sum m==n]|n<-[a..a*b]]

Try it online! Use as a#b.

Partly based on Sherlock9's Haskell answer.

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

MATL, 9 bytes

:Z^!Xs8#u

Same approach as Maltysen's Pyth answer.

Inputs are in reverse order. Try it online!

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

Pari/GP, 28 bytes

a->b->Vec(((x^b-1)/(x-1))^a)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ As far as I can tell, this is the shortest solution that definitely doesn't run out of memory on any of the provided test cases. \$\endgroup\$ – Misha Lavrov Oct 1 '17 at 16:09
1
\$\begingroup\$

Perl 5, 53 bytes

$g=join',',1..<>;map$r[eval]++,glob"+{$g}"x<>;say"@r"

Try it online!

Input format:

b
a
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 94 bytes

f=(n,m,a=[1],b=[])=>n?[...Array(m)].map((_,i)=>a.map((e,j)=>b[j+=i]=(b[j]|0)+e))&&f(n-1,m,b):a
<div oninput=o.textContent=f(+n.value,+m.value).join`\n`><input id=n type=number min=0 value=0><input id=m type=number min=1 value=1><pre id=o>1

Limited by 32-bit integer overflow, but floats could be used instead at a cost of 1 byte.

\$\endgroup\$
  • \$\begingroup\$ Umm... this only takes one input \$\endgroup\$ – Herman L Oct 1 '17 at 9:06
  • \$\begingroup\$ @HermanLauenstein Sorry, I somehow completely overlooked that part of the question... will fix shortly. \$\endgroup\$ – Neil Oct 1 '17 at 9:18
1
\$\begingroup\$

J, 25 24 21 20 bytes

3 :'#/.~,+//y$i.{:y'

Try it online!

Initially I incremented the [0..n-1] list to get [1..n] but apparently it’s not necessary.

\$\endgroup\$
  • \$\begingroup\$ Nice answer. Here's a tacit version for same number of bytes: #/.~@,@(+///)@$i.@{:. Seems like there should be a way to shave it down a bit more making the verb dyadic, but I wasn't able to do it. \$\endgroup\$ – Jonah Oct 1 '17 at 16:35
  • \$\begingroup\$ @Jonah you have an extra / in +// \$\endgroup\$ – FrownyFrog Oct 1 '17 at 16:53
  • \$\begingroup\$ Actually, you're right. It just happens to work both ways. I guess that solution saves a byte then :) \$\endgroup\$ – Jonah Oct 1 '17 at 17:14
1
\$\begingroup\$

Javascript (ES6), 89 bytes

b=>g=a=>a?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]

Takes input in currying syntax in reverse order f(b)(a)

f=b=>g=a=>a>0?(l=[..."0".repeat(b-1),...g(a-1)]).map((_,i)=>eval(l.slice(i,i+b).join`+`)):[1]
r=_=>{o.innerText=f(+inb.value)(+ina.value)}
<input id=ina type=number min=0 onchange="r()" value=0>
<input id=inb type=number min=1 onchange="r()" value=1>
<pre id=o></pre>

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

Actually, 13 12 bytes

-1 byte thanks to Mr. Xcoder. Try it online!

R∙♂Σ;╗╔⌠╜c⌡M

Ungolfed

                Implicit input: b, a
R∙              ath Cartesian power of [1..b]
  ♂Σ            Get all the sums of the rolls, call them dice_rolls
    ;╗          Duplicate dice_rolls and save to register 0
      ╔         Push uniquify(dice_rolls)
       ⌠  ⌡M    Map over uniquify(dice_rolls), call the variable i
        ╜         Push dice_rolls from register 0
         c        dice_rolls.count(i)
                Implict return
\$\endgroup\$
  • \$\begingroup\$ You do not need the @, do you? \$\endgroup\$ – Mr. Xcoder Oct 1 '17 at 13:12
  • \$\begingroup\$ As a side note, I found an interesting alternative: R∙♂Σ╗╜╔⌠╜c⌡M \$\endgroup\$ – Mr. Xcoder Oct 1 '17 at 16:54
1
\$\begingroup\$

AWK, 191 bytes

Outputs frequencies as a vertical column.

func p(z){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{t($1,$2)}

Try it online!

Adding 6 more bytes allows for multiple sets of inputs.

func p(z,S){for(m in z)S[z[m]]++
for(i=$1;i<=$1*$2;i++)print S[i]}func t(a,b,z,s){if(a){if(R++)for(n in z)for(i=0;i++<b;)s[n,i]=z[n]+i
else for(i=0;i++<b;)s[i]=i
t(--a,b,s)}else p(z)}{R=0;t($1,$2)}

Try it online!

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

Clojure, 86 bytes

#(sort-by key(frequencies(reduce(fn[r i](for[y(range %2)x r](+ x y 1)))[0](range %))))

An example:

(def f #(...))
(f 5 4)

([5 1] [6 5] [7 15] [8 35] [9 65] [10 101] [11 135] [12 155] [13 155] [14 135] [15 101] [16 65] [17 35] [18 15] [19 5] [20 1])
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 142 bytes

i,j,k;int*f(a,b){int*r=malloc(sizeof(int)*(1+a*~-b));r[0]=1;for(i=1;i<=a;i++)for(j=i*~-b;j>=0;j--)for(k=1;k<b&k<=j;k++)r[j]+=r[j-k];return r;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ sizeof(int)? Really? \$\endgroup\$ – orlp Oct 1 '17 at 20:04
  • \$\begingroup\$ @orlp environment-dependent, you know \$\endgroup\$ – Leaky Nun Oct 1 '17 at 20:11
  • 2
    \$\begingroup\$ It's allowed for a C program to assume a particular architecture. As long as it works on at least one machine. Furthermore, 8 would work on any architecture, overallocating a bit but that's ok. \$\endgroup\$ – orlp Oct 1 '17 at 22:44
  • \$\begingroup\$ r[0]=1;for(i=1;i<=a;i++)for(j=i*~-b; -> for(i=r[0]=1;i<=a;)for(j=i++*~-b; for -2 bytes. \$\endgroup\$ – Kevin Cruijssen Oct 2 '17 at 13:49
0
\$\begingroup\$

Julia, 43 bytes

f(n,d)=reduce(conv,repmat([ones(Int,d)],n))

Try it online!

\$\endgroup\$

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.