Frequency Distribution of Mixed Dice Rolls

Question

^{A follow-up to this challenge}

Given a set of mixed dice, output the frequency distribution of rolling all of them and summing the rolled numbers on each die.

For example, consider 1d12 + 1d8 (rolling 1 12-sided die and 1 8-sided die). The maximum and minimum rolls are 20 and 2, respectively, which is similar to rolling 2d10 (2 10-sided dice). However, 1d12 + 1d8 results in a flatter distribution than 2d10: [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1] versus [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1].

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.
• You may take the input in any reasonable format (list of dice ([6, 8, 8]), list of dice pairs ([[1, 6], [2, 8]]), etc.).
• The frequencies must be normalized so that the GCD of the frequencies is 1 (e.g. [1, 2, 3, 2, 1] instead of [2, 4, 6, 4, 2]).
• All dice will have at least one face (so a d1 is the minimum).
• This is code-golf, so the shortest code (in bytes) wins. Standard loopholes are forbidden, as per usual.

Test Cases

These test cases are given as input: output, where the input is given as a list of pairs [a, b] representing a b-sided dice (so [3, 8] refers to 3d8, and [[1, 12], [1, 8]] refers to 1d12 + 1d8).

[[2, 10]]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[[1, 1], [1, 9]]: [1, 1, 1, 1, 1, 1, 1, 1, 1]
[[1, 12], [1, 8]]: [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1]
[[2, 4], [3, 6]]: [1, 5, 15, 35, 68, 116, 177, 245, 311, 363, 392, 392, 363, 311, 245, 177, 116, 68, 35, 15, 5, 1]
[[1, 3], [2, 13]]: [1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 37, 36, 33, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3, 1]
[[1, 4], [2, 8], [2, 20]]: [1, 5, 15, 35, 69, 121, 195, 295, 423, 579, 761, 965, 1187, 1423, 1669, 1921, 2176, 2432, 2688, 2944, 3198, 3446, 3682, 3898, 4086, 4238, 4346, 4402, 4402, 4346, 4238, 4086, 3898, 3682, 3446, 3198, 2944, 2688, 2432, 2176, 1921, 1669, 1423, 1187, 965, 761, 579, 423, 295, 195, 121, 69, 35, 15, 5, 1]
[[1, 10], [1, 12], [1, 20], [1, 50]]: [1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 285, 360, 444, 536, 635, 740, 850, 964, 1081, 1200, 1319, 1436, 1550, 1660, 1765, 1864, 1956, 2040, 2115, 2180, 2235, 2280, 2316, 2344, 2365, 2380, 2390, 2396, 2399, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2400, 2399, 2396, 2390, 2380, 2365, 2344, 2316, 2280, 2235, 2180, 2115, 2040, 1956, 1864, 1765, 1660, 1550, 1436, 1319, 1200, 1081, 964, 850, 740, 635, 536, 444, 360, 285, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]

Answer 1

Jelly,  14  7 bytes

-3 bytes thanks to Mr. Xcoder (use of an implicit range to avoid leading R; replacement of reduce by the dyadic Cartesian product and flatten, p/F€, with the Cartesian product built-in for that very purpose, Œp.)

ŒpS€ĠL€

A monadic link taking a list of dice faces and returning the normalised distribution of the increasing sums.

Try it online!

How?

Goes through the list of dice "sizes" (implicitly) makes them into their list of faces, then gets the Cartesian product of those lists (all possible rolls of the set of dice), then sums up those rolls, gets the groups of equal indices (by ascending value) and takes the length of each group.

ŒpS€ĠL€ - Link: list of numbers, dice  e.g. [2,5,1,2]
Œp      - Cartisian product (implicit range-ification -> [[1,2],[1,2,3,4,5],[1],[1,2]])
        -                   -> [[1,1,1,1],[1,1,1,2],[1,2,1,1],[1,2,1,2],[1,3,1,1],[1,3,1,2],[1,4,1,1],[1,4,1,2],[1,5,1,1],[1,5,1,2],[2,1,1,1],[2,1,1,2],[2,2,1,1],[2,2,1,2],[2,3,1,1],[2,3,1,2],[2,4,1,1],[2,4,1,2],[2,5,1,1],[2,5,1,2]]
  S€    - sum €ach          -> [4,5,5,6,6,7,7,8,8,9,5,6,6,7,7,8,8,9,9,10]
    Ġ   - group indices     -> [[1],[2,3,11],[4,5,12,13],[6,7,14,15],[8,9,16,17],[10,18,19],[20]]
     L€ - length of €ach    -> [1,3,4,4,4,3,1]

Note: there is only ever one way to roll the minimum (by rolling a one on each and every dice) and we are not double-counting any rolls, so there is no need to perform a GCD normalisation.

Answer 2

Haskell, 54 bytes

1%r=r
n%r=zipWith(+)(r++[0,0..])$0:(n-1)%r
foldr(%)[1]

Try it online!

---

Haskell, 63 bytes

f l=[sum[1|t<-mapM(\x->[1..x])l,sum t==k]|k<-[length l..sum l]]

Try it online!

---

Haskell, 68 bytes

k%(h:t)=sum$map(%t)[k-h..k-1]
k%_=0^k^2
f l=map(%l)[length l..sum l]

Try it online!

Answer 3

MATL, 8 bytes

1i"@:gY+

The input is an array of (possibly repeated) die sizes.

Try it online! Or verify all test cases.

Explanation

1      % Push 1
i      % Input: numeric array
"      % For each k in that array
  @    %   Push k
  :    %   Range: gives [1 2 ... k]
  g    %   Convert to logical: gives [1 1 ... 1]
  Y+   %   Convolution, with full size
       % End (implicit). Display (implicit)

Answer 4

Husk, 7 bytes

mLkΣΠmḣ

Input is a list of dice. Try it online!

Explanation

mLkΣΠmḣ  Implicit input, say x=[3,3,6].
     mḣ  Map range: [[1,2,3],[1,2,3],[1,2,3,4,5,6]]
    Π    Cartesian product: [[1,1,1],[1,1,2],..,[3,3,6]]
  kΣ     Classify by sum: [[[1,1,1]],[[1,1,2],[1,2,1],[2,1,1]],..,[[3,3,6]]]
mL       Map length: [1,3,6,8,9,9,8,6,3,1]

Answer 5

Octave, 88 69 58 56 bytes

As mentioned in the Haskell answer, this uses the fact that the distribution of e.g. a 3-sided and a 5-sided dice is the discrete convolution of the two vectors [1,1,1] and [1,1,1,1,1]. Thanks @LuisMendo for -11 bytes worth of clever golfing!

function y=f(c);y=1:c;if d=c(2:end);y=conv(~~y,f(d));end

Try it online!

This submission is using an recursive approach. But if you would use a loop it would be slightly longer:

function y=f(c);y=1;for k=cellfun(@(x)ones(1,x),c,'Un',0);y=conv(y,k{1});end

Answer 6

Wolfram Language (Mathematica), 26 bytes

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

Try it online!

A modification of my answer to the previous challenge. This just generates all possible outcomes, adds them up, and tallies the results.

For fun, we could write it as Tally@*Total@*Thread@*Tuples@*Range, but that's longer.

Wolfram Language (Mathematica), 41 bytes

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

Try it online!

This is the convolution-based approach (here, we take convolutions via the product of generating functions - 1+x+x^2+...+x^(N-1) is the generating function for rolling a dN - and then take the list of coefficients). I include it because the first solution isn't practical for large inputs.

Answer 7

Mathematica, 44 bytes

Outputs the frequencies labeled with the corresponding sums

Tally@*Fold[Join@@Table[#+i,{i,#2}]&]@*Range

Try it online!

-5 bytes from Martin Ender

thanks to Misha Lavrov for letting me know that "labeled" is valid

Answer 8

Pyth, 12 bytes

lM.gs.nk*FSM

Try it here!

How?

lM.gs.nk*FSM  ~ Full program.

          SM  ~ Map with inclusive unary integer range [1, N].
        *F    ~ Fold (Reduce by) Cartesian product.
  .g          ~ Group by function result.
    s.n       ~ The sum of the list when flattened.
lM            ~ Length of each group.

Answer 9

Jelly, 14 bytes

R+Ѐ/FċЀSR$ḟ0

Try it online!

Input is a list of die values. I could golf this down by stealing ĠL€ from the other Jelly answer but then I could also golf down the first half and end up with the same thing so I'll just leave it how it is

Answer 10

Haskell, 80 78 64 bytes

This solution ended up being almost the same as the one of @Sherlock9 in the previous challenge with the maybe more natural approach. @xnor has an even shorter Haskell solution!

import Data.List
g x=[1..x]
map length.group.sort.map sum.mapM g

Explanation:

                              mapM g -- all possible outcomes
                      map sum        -- the sums of all possible outcomes
map length.group.sort                -- count the frequency of each sum

Try it online!

Previous solution:

This is using the @AndersKaseorg discrete convolution function. The observation here is that the distribution of e.g. a 3-sided and a 5-sided dice is the discrete convolution of the two vectors [1,1,1] and [1,1,1,1,1].

foldl1(#).map(`take`l)
(a:b)#c=zipWith(+)(0:b#c)$map(a*)c++[]#b
_#c=0<$c
l=1:l

Try it online!

Answer 11

Python 2, 120 119 bytes

lambda v:[reduce(lambda a,c:sum([[b+y for b in a]for y in range(c)],[]),v,[0]).count(d)for d in range(sum(v)-len(v)+1)]

Try it online!

Thks for Mego/Jonathon Allan for 1 byte.

Answer 12

05AB1E, 11 bytes

€L.«âOO{γ€g

Try it online!

How it works

€L.«âOO{γ€g - Full program.

€L          - For each N in the list, get [1 .. N].
  .«        - Fold a dyadic function between each element in a list from right to left.
    â       - And choose cartesian product as that function.
     O      - Flatten each.
      O     - Sum each.
       {γ   - Sort, and group into runs of equal adjacent values.
         €g - Get the lengths of each.

Saved 1 byte thanks to Emigna!

Answer 13

R, 51 bytes

function(D){for(x in D)F=outer(F,1:x,"+")
table(F)}

Try it online!

Takes a list of dice and returns a named vector of frequencies; the names (values of the dice sums) are printed above the frequencies.

R, 59 bytes

function(D)table(Reduce(function(x,y)outer(x,1:y,"+"),D,0))

Try it online!

A Reduce approach rather than the iterative one above.

R, 62 bytes

function(D)Re(convolve(!!1:D,"if"(sum(x<-D[-1]),f(x),1),,"o"))

Try it online!

A convolution approach. It will give a few warnings that it's only using the first element of D for the expression 1:D but it doesn't affect the output. If we didn't have to take the Real part of the solution, it'd be 58 bytes.

Answer 14

APL (Dyalog Classic), 12 10 bytes

-2 thanks to @Adám

⊢∘≢⌸+/↑,⍳⎕

Try it online!

the input ⎕ is a list of N dice

⍳⍵ is an N-dimensional array of nested vectors - all possible die throws

+/↑, flattens the arrays and sums the throws

⊢∘≢⌸ counts how many of each unique sum, listed in order of their first appearance, which fortunately coincides with their increasing order

Answer 15

Ruby, 72 bytes

->d{r=[0]*d.sum
[0].product(*d.map{|e|[*1..e]}){|e|r[e.sum-1]+=1}
r-[0]}

Try it online!

Takes a list of dice as input. No doubt it can be golfed down, but not too bad.

Answer 16

Pari/GP, 35 bytes

v->Vec(prod(i=1,#v,1/(1-x)%x^v[i]))

Try it online!

Answer 17

Clean, 154 142 136 107 100 85+13=98 bytes

Input is a list of dice.

\l#t=foldr(\a-> \b=[x+y\\x<-[1..a],y<-b])[0]l
=[length[v\\v<-t|u==v]\\u<-removeDup t]

Answer is in the form of a lambda.

+13 bytes from import StdEnv, which imports the module needed for this to work.

Try it online!

Answer 18

JavaScript (ES6), 83 bytes

f=(n,...a)=>n?f(...a).map((e,i)=>[...Array(n)].map(_=>r[i]=~~r[i++]+e),r=[])&&r:[1]
g=s=>o.textContent=f(...(s.match(/\d+/g)||[]).map(n=>+n)).join`, `

<input oninput=g(this.value)><p id=o>1

Takes input of each die as a separate parameter.

Answer 19

JavaScript (ES6), 76 74 bytes

Takes input as a list of dice.

a=>(g=k=>a.map(d=>(s+=n%d|0,n/=d),s=0,n=k)|n?x:g(k+1,x[s]=-~x[s]))(0,x=[])

Test cases

Processing the last two test cases would require to enable TCO or increase the default stack size limit of the JS engine.

let f =

a=>(g=k=>a.map(d=>(s+=n%d|0,n/=d),s=0,n=k)|n?x:g(k+1,x[s]=-~x[s]))(0,x=[])

console.log(f([10,10]).join(', '))
console.log(f([1,9]).join(', '))
console.log(f([12,8]).join(', '))
console.log(f([4,4,6,6,6]).join(', '))
console.log(f([3,13,13]).join(', '))

Formatted and commented

NB: This is a commented version of my initial submission which was using reduce(). It's 2 bytes longer but easier to read.

a =>                    // given the list of dice a
  (g = k =>             // g = recursive function taking k = counter
    a.reduce((k, d) =>  //   for each die d in a:
      (                 //     k % d represents the current face of d
        s += k % d,     //     we add it to the total s
        k / d | 0       //     and we update k to pick the face of the next die
      ),                //     initialization:
      k,                //     start with the current value of k
      s = 0             //     total = 0
    ) ?                 //   reduce() returns 1 as soon as k = product of all dice
      x                 //     in which case we're done: stop recursion and return x
    :                   //   else:
      g(                //     do a recursive call to g() with:
        k + 1,          //       k incremented
        x[s] = -~x[s]   //       x[s] incremented
      )                 //     end of recursive call
  )(0, x = [])          // initial call to g() with k = 0 and x = empty array

Answer 20

Clojure, 96 bytes

#(sort-by key(frequencies(reduce(fn[R D](for[d(range D)r R](+ r d 1)))[0](mapcat repeat % %2))))

First input is a list of number of dice, and the second input is a list of number of sides on each dice.

Answer 21

Perl 5, 94 bytes

map$k{$_}++,map eval,glob join'+',map'{'.(join',',1..$_).'}',<>;say$k{$_}for sort{$a-$b}keys%k

Try it online!

Input format is a list of dice separated by newlines. Thus, 1d10+2d8 would input as:

10
8
8

Answer 22

SageMath, 46 bytes

lambda*a:reduce(convolution,[x*[1]for x in a])

Try it online

This is an adaptation of my solution to the other challenge. It takes in any number of dice as parameters (e.g. f(4,4,6,6,6) for 2d4+3d6), and returns a list.

---

Python 2 + NumPy, 62 bytes

lambda*a:reduce(numpy.convolve,[x*[1]for x in a])
import numpy

Try it online!

As before, 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(x) is the "correct" way to make an array for use with NumPy, and thus it could be used in place of [x*[1]], but it's unfortunately much longer.