Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
More efficiently calculate the value of a game that involves rerolling dice; see http://math.stackexchange.com/questions/1118263.
import java.math.BigInteger;
import java.util.Arrays;
public class Question1118263 {
final static int [] values = {1,2,3,4,5,6};
final static int nsides = values.length;
final static int ndice = 20;
static Rational [] v = new Rational [ndice];
static int n;
public static void main (String [] args) {
Arrays.fill (v,Rational.ZERO);
Rational p = Rational.ONE;
for (n = 1;n < ndice;n++) {
p = p.divide (BigInteger.valueOf (nsides));
recurse (0,n,new int [nsides]);
v [n] = v [n].multiply (p);
System.out.println (n + " : " + v [n].subtract (v [n - 1]));
}
}
static void recurse (int depth,int left,int [] counts) {
if (depth == nsides - 1) {
counts [depth] = left;
int sum = 0;
for (int i = 0;i < counts.length;i++)
sum += counts [i] * values [i];
int [] dice = new int [n];
for (int i = 0,k = 0;i < counts.length;i++)
for (int j = 0;j < counts [i];j++)
dice [k++] = values [i];
Rational max = Rational.ZERO;
for (int reroll = 0;reroll < n;reroll++) {
Rational newValue = v [reroll].add (sum);
if (newValue.compareTo (max) > 0)
max = newValue;
sum -= dice [reroll];
}
BigInteger multinomial = BigInteger.ONE;
int upper = n;
for (int i = 0;i < counts.length;i++) {
multinomial = multinomial.multiply (binomial (upper,counts [i]));
upper -= counts [i];
}
v [n] = v [n].add (max.multiply (multinomial));
}
else
for (counts [depth] = 0;counts [depth] <= left;counts [depth]++)
recurse (depth + 1,left - counts [depth],counts);
}
static BigInteger [] [] binomials = new BigInteger [20] [20];
static BigInteger binomial (int n,int k) {
if (k > n)
return BigInteger.ZERO;
if (binomials [n] [k] == null) {
binomials [n] [k] = BigInteger.ONE;
for (int i = 0;i < k;i++)
binomials [n] [k] = binomials [n] [k].multiply (BigInteger.valueOf (n - i)).divide (BigInteger.valueOf (i + 1));
}
return binomials [n] [k];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment