[Chicago] Throw those dice!!!!

Tue Aug 4 07:30:01 CEST 2015

Sorry I misread the problem. This was only for a 2 dice or a coin. Ignore me.

On Aug 4, 2015, at 12:23 AM, DiPierro, Massimo <MDiPierro at cs.depaul.edu> wrote:

> If you need a specific row of the triangle this is as fast as it gets:
> 
> def pascal_row(n,k):
>    a = b = 1
>    for i in range(k,n): a=a*i
>    for i in range(1,n-k): b=b*i
>    return a/b
> 
> 
> def print_triangle(n_max=10):
>    for n in range(1,n_max+1):
>        for k in range(0,n+1):
>            print pascal_row(n,k),
>        print
> 
> print_triangle()
> 
> On Aug 3, 2015, at 10:11 PM, Ken Schutte <kenschutte at gmail.com<mailto:kenschutte at gmail.com>> wrote:
> 
> Note that you can solve this iteratively - which I think is easier and is much more efficient (at least in the cases where you want to compute the full distribution of possible sums):
> 
> I tried it here, https://gist.github.com/kts/65d71c761baa9714151c
> 
> I haven't fully tested it, but try running "$ time python multcoeff.py 6 1000 > out". which takes ~2.5sec on my little chromebook. It outputs the counts for all possible values, in this case they correspond to sums 1000, 1001, ..., 5999, 6000.
> 
> The binomial coefficients can be computed in Pascal's triangle by simply sweeping across and adding two numbers from the row above. Here, it is similar, but you just have to add 6 numbers from the row above for each value.
> 
> I think this is a nice example of "dynamic programming" - where an optimal solution depends upon a lot of highly overlapping sub-problems.  For example - how many ways can 100 dice add up to the value of 307? That is complicated, BUT if you know the distribution for 99 dice, it is trivial - you only have to know the counts for values 301,302,...,306 because those are the only sums of 99 dice that influence the question at hand.  And that's what this code does (and how one computes values in Pascal's triangle).
> 
> A side note for anyone familiar with convolution - each level in computing such a triangle is really a convolution with all ones - for example K=6 sided die is a convolution with [1,1,1,1,1,1].  Which makes you wonder if you can use fast (FFT, N log N) convolutions for such a problem - I would guess no in this case.
> 
> Ken
> 
> 
> On Mon, Aug 3, 2015 at 2:00 PM, Adam Forsyth <adam at adamforsyth.net<mailto:adam at adamforsyth.net>> wrote:
> The bug has been spotted and fixed (off-list reply)! I updated the gist<https://gist.github.com/agfor/8c59d6a6e9a643223f2d>. (range(m) replaced with range(max(m, k)).) The fixed algorithm is still fast enough to handle 1000 dice in about six minutes on my laptop.
> 
> Adam
> 
> On Sun, Aug 2, 2015 at 10:37 PM, Adam Forsyth <adam at adamforsyth.net<mailto:adam at adamforsyth.net>> wrote:
> Douglas,
> 
> Using your algorithm -- generating all possible rolls -- but a different implementation, the best I was able to do was calculate the frequencies for 11 dice in a couple of minutes. So there is no way the naive algorithm can handle large numbers of dice. If you're looking to speed yours up, I suggest you work on writing your own version of the built-in itertools.product, as this is at least the second problem you've posted to the list where that would have come in handy.
> 
> Using a different algorithm, I was able to calculate the frequencies for 1000+ dice in just a few seconds (though there is a bug in my code causing the answers to be wrong for more than ~20 dice). Calculating the frequencies is the same as calculating the coefficients for the expansion of the polynomial:
> 
> (x**6 + x ** 5 + .... x ** 2 + x + 1) ** n
> 
> where n is the number of dice. While this is complicated, doing it for two sided dice is simple -- you're using the binomial theorem<https://en.wikipedia.org/wiki/Binomial_theorem>, and the coefficients<https://en.wikipedia.org/wiki/Binomial_coefficient> for a given n are the nth row of Pascal's Triangle<https://en.wikipedia.org/wiki/Pascal%27s_triangle>. I found a paper<http://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?article=2852&context=thesesdissertations> that gives the formula we need to do this for n-sided dice instead of two-sided dice -- property 6 given in section 2.1.2.
> 
> I've put my work in a gist<https://gist.github.com/agfor/8c59d6a6e9a643223f2d>. I'll buy lunch for anyone who can correct the mistake in my code.
> 
> Adam
> 
> 
> 
> On Sun, Aug 2, 2015 at 8:16 PM, Joshua Herman <zitterbewegung at gmail.com<mailto:zitterbewegung at gmail.com>> wrote:
> Dear Lewitt,
> What is the expected value of two die rolls? Also, given N dice rolls could I create a compression algorithm for those dice rolls?
> Sincerely,
> Joshua Herman
> 
> On Sun, Aug 2, 2015 at 8:04 PM Lewit, Douglas <d-lewit at neiu.edu<mailto:d-lewit at neiu.edu>> wrote:
> Hey guys,
> 
> I will admit that I'm rather proud of this little Python program that I wrote, but for values larger than 6 either the program crashes because of a stack overflow or the program becomes really painfully SLOW!
> 
> Let me explain what this program does.  Let's say that you roll two dice.  What are all the possible sums.  If both dice land with the one-side face up, that's a sum of 2.  If both dice land with the six-side face up, that is 6 + 6, which gives you a sum of 12.  Then you have all the sums in between.  Any student of statistics will tell you that these sums are NOT all equally probable or equally likely.  For example, in the case of two dice, the most probable sum is 7 because there are several ways to get that sum.  First die = 3, second die = 4, {3, 4} or {4, 3} or {5, 2} or {2, 5} or {1, 6} or {6, 1} or ..... get the idea?
> 
> But why limit ourselves to just two dice?  What about three dice?  Or four dice?  Or five dice?  Or six dice?  Or any number of dice that we choose to throw?
> 
> My approach works pretty well for any number of dice from 1 to 6.  Beyond 6 however, that's when I run into some real problems.
> 
> Is there an "easy" way to fix this?  Probably not, but I thought I would check with people who are more experienced in Python than I am.
> 
> I appreciate the feedback, but may not be able to reply until next weekend.  I'm VERY busy this week!  But still I appreciate any constructive feedback that you can provide.
> 
> Many thanks,
> 
> Douglas Lewit
> 
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
> 
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
> 
> 
> 
> 
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
> 
> 
> _______________________________________________
> Chicago mailing list
> Chicago at python.org<mailto:Chicago at python.org>
> https://mail.python.org/mailman/listinfo/chicago
> 
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago