Unusual dice
I heard of this problem from Justin James in his TechRepublic post My First IronRuby Application. He tried this fun problem as a toy example to brush up his skills in ruby:
Roll simultaneously a hundred 100sided dice, and add the resulting values. The set of possible outcomes is, of course, Note that there is only one way to obtain the outcome 100—all dice showing a 1. There is also only one way to obtain the outcome 10000—all dice showing 100. For the outcome 101, there are exactly 100 different ways to obtain it: all dice except one show a 1, and one die shows a 2. The followup question is:
Write a (fast) script that computes the different ways in which we can obtain each of the possible outcomes.
The obvious first strategy is to come up with a function of three variables that expresses the number of different ways to obtain the value rolling sided dice. We may rewrite this function iteratively in the following fashion:
with the convention that provided or and of course for
A simple code (in ruby) that takes advantage of this strategy could be written as follows:
#!/usr/bin/ruby idice=ARGV[0].to_i isides=ARGV[1].to_i def vwnd(value,dice,sides) if value &lt; 1 return 0 elsif dice==1 &amp;&amp; value &gt; sides return 0 else collect=0 for step in 1...sides+1 collect=collect+vwnd(valuestep,dice1,sides) end return collect end end for value in idice...idice+(idice*isidesidice)/2+1 stuff = vwnd(value,idice,isides) print value, " and ", idice*isidesvalue+idice, " with ", isides, "sided ", idice, " dice: ", stuff, "\n" end
But this is not the best way to attack this problem: this script chokes even with relative small choices of number of dice and sides per die. A different approach to the functional relationship above offers a better chance. The focus is on the second expression:
The term appears exactly once; the term appears exactly twice; the term appears exactly three times. You start seeing now how this can work in our advantage, right? Let me make it more clear with a small example:
 1 dice with 6 faces each: There are six possible outcomes, and each of them can be obtained in a single way.
 2 dice with 6 faces each: There are eleven possible outcomes, and each of them can be obtained in different ways:
A strategy to obtain this result from the previous is by collecting the previous array of “ways to obtain the outcomes”—in this case, the vector —and creating the following matrix of size from it:
Add all the elements on each column, to obtain the desired result. Do you see now how to iterate this process?
 3 dice with 6 faces each: We start with the previous result—the array —and add the elements of the columns of the matrix of size below:
The result is, in this case,
The method that I propose is then as follows:
To obtain a vector that indicates the possible ways to compute the sums of all outcomes of rolling sided dice by iteration of the above procedure. Start with die, until reaching dice. The initial vector has all ones and length , and each successive th step of this algorithm will provide us with a new vector of length For the last step we have, of course, possible outcomes.
A ruby script that uses this idea could look like this:
#!/usr/bin/ruby dice = ARGV[0].to_i sides= ARGV[1].to_i original_permutation=Array.new(sides) {1} def helper(pattern,target,step,size) if step==1 return target else target+=[0] pattern.each_index{ x target[x+1step+size] += pattern[x] } return helper(pattern,target,step1,size) end end def count_permutations(dice,sides,ary) if dice==1 return ary else return puts count_permutations(dice1,sides,helper(ary,ary,sides,sides)) end end puts count_permutations(dice,sides,original_permutation)
Miscellaneous
Generalizations
It is a great exercise to code this fun script in a language more apt to scientific computing: python, sage, matlab, C/C++, Ocaml, and of course look for tricks to simplify and speed it up. A compiled version of this algorithm should not take much time to obtain the desired result. You can even go a little bit farther and code a new script that will compute the number of different ways to come up with the possible outcomes of rolling sided dice, where the faces of each die belong in a given set The values are allowed to be equal, or nonconsecutive… anything, really.
Helper: more than a mere helper
The small recursive function that computes the key step of the algorithm is also the key to other similar counting problems. I called it helper for lack of a better word, and you can use it to aid you in other related tasks. For instance, to compute all the binomial coefficients for any and you could issue:
first_bc = Array.new(1) {1} def binomial_coeffs(n,ary) if n==0 return ary else return binomial_coeffs(n1,helper(ary,ary,2,2)) end end n=ARGV[0].to_i puts binomial_coeffs(n,first_bc)
Solution to our problem
The script presented above computes the required different ways to come up with the possible outcomes of rolling a hundred 100sided dice… in about a minute! (mileage may vary depending on your computer, of course)
time ./justin 100 100
81900 42634215112710 426342151127100 3943664897925675 33976189889821200 2742363
89824985400 2084196562669889040 14980162794189827475 102217581419177646300 6644
14279224654700950 4126362365711013405900 24551856075980529765105 14029632043417
4455800600 771629762387959506903300
…
102217581419177646300 14980162794189827475 2084196562669889040 2742363898249854
00 33976189889821200 3943664897925675 426342151127100 42634215112710 3911395881
900 325949656825 24370067800 1609344100 91962520 4421275 171700 5050 100 1
real 1m16.462s
user 1m10.895s
sys 0m1.863s

January 27, 2011 at 3:58 pmUnusual dice « Francisco BlancoSilva